如何减少HashMap <String,Integer>的内存使用情况,如数据结构

Question

在开始解释我的问题之前,我应该提一下,我不是在寻找增加Java堆内存的方法.我应该严格存储这些对象.

我正在努力将大量(5-10 GB)的DNA序列及其计数(整数)存储在哈希表中.DNA序列(长度为32或更短)由'A','C','G','T'和'N'(未定义)字符组成.众所周知,当在内存中存储大量对象时,与C和C++等低级语言相比,Java的空间效率较差.因此,如果我将此序列存储为字符串(它为长度为~30的序列保存大约100 MB内存),我会看到错误.

我试图将核酸表示为'A'= 00,'C'= 01,'G'= 10,'T'= 11并忽略'N'(因为它将char烧成2位变换为5-酸).然后,将这些2位酸连接成字节数组.它带来了一些改进但不幸的是我再次看到错误几个小时后.我需要一个方便的解决方案或至少一种解决方法来处理此错误.先感谢您.

Answer 1

由于相当复杂，也许这是一个奇怪的想法，并且需要大量的工作，但这就是我会尝试的：

您已经指出了整个任务的两个单独的子问题：

• 对于如此大的集合大小，默认HashMap实现可能不是最佳的
• 你需要存储字符串以外的东西

地图实施

我建议为该Map<String, Long>接口编写一个高度定制的哈希映射实现。在内部您不必存储字符串。不幸的是 5^32 > 2^64，所以没有办法将整个字符串打包成一个长字符串，好吧，让我们坚持使用两个长字符串作为键。当为映射实现提供字符串键时（使用位移位等），您可以相当有效地进行字符串到/返回 long[2] 的转换。

至于打包值，有一些注意事项：

对于键值对，标准哈希映射需要有一个由 N 个 long 组成的存储桶数组，其中 N 是当前容量，当从哈希键中找到存储桶时，它将需要有一个键值对的链表解析产生相同哈希码的密钥。针对您的具体情况，您可以尝试通过以下方式进行优化：

• 使用 long[] 大小3N，其中N是在连续数组中存储键和值的容量
• 在此数组中的位置，3 * (hashcode % N)您3 * (hashcode % N) + 1存储键的 long[2] 表示形式、与此存储桶匹配的第一个键或唯一一个键的表示形式（插入时，否则为零），在3 * (hashcode % N) + 2存储相应计数的位置
• 对于所有不同的键导致相同的哈希码并因此导致相同的存储桶的情况，您将数据存储在标准的HashMap<Long2KeyWrapper, Long>. 这个想法是保持上面提到的数组的容量（并相应地调整大小）足够大，以使迄今为止最大的数据部分位于该连续数组中，而不是在后备哈希图中。这将大大减少哈希图的存储开销
• 不要在 N=2N 次迭代中扩大容量，采用较小的增长步长，例如 10-20%。这会降低填充地图的性能，但会控制内存占用

按键

考虑到不平等，5^32 > 2^64你使用位来编码 5 个字母的想法似乎是我现在能想到的最好的。使用 3 位和相应的 long[2]。