如何减少HashMap<String、Integer>类数据结构的内存使用量

Question

在开始解释我的问题之前，我应该提到，我并不是在寻找一种增加Java堆内存的方法。我应该严格地保存这些物品。

我正致力于在哈希表中存储大量DNA序列及其计数(Integer) (5-10 GB)。DNA序列(长度32或更短)由'A‘、'C’、'G‘、'T’和'N‘(未定义的)字符组成。我们知道，在内存中存储大量对象时，与C和C++等低级语言相比，Java的空间效率很低。因此，如果我将这个序列存储为string (对于长度为30的序列，它拥有大约100 MB的内存)，我就会看到错误。

我试图用'A'=00，'C'=01，'G'=10，'T'=11来表示核酸，而忽略'N‘(因为它破坏了作为第5酸的炭到2位的转换)。然后，将这些2位酸串联到字节数组中.它带来了一些改进，但不幸的是，在几个小时后，我又看到了错误。我需要一个方便的解决方案，或者至少需要一个解决办法来处理这个错误。提前谢谢你。

Answer 1

由于非常复杂，也许这是一个奇怪的想法，需要做大量的工作，但这就是我要尝试的：

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

• 对于这样大的集合大小，默认的HashMap实现可能不是最优的。
• 你需要存储其他东西而不是字符串

地图实现

我建议为Map<String, Long>接口编写一个高度定制的散列图实现。在内部，您不必存储字符串。不幸的是，5^32 > 2^64，所以没有办法将整个字符串打包成一个长的，那么，让我们坚持两个长键。当为映射实现提供字符串键(使用位移位等)时，可以动态地使字符串到/回long2转换相当有效。

至于包装这些值，以下是一些注意事项：

对于一个键值对，标准的hashmap将需要一个N个对桶的多头数组，其中N是当前的容量，当从哈希键中找到桶时，它将需要一个键值对的链接列表，以解析产生相同哈希代码的键。对于您的具体情况，您可以尝试以下列方式优化它：

• 使用大小为long[]的3N，其中N是在连续数组中存储键和值的能力。
• 在这个数组中，在locations 3 * (hashcode % N)和3 * (hashcode % N) + 1中存储键的long2表示，与此桶匹配的第一个键或唯一一个(插入时为零，否则为零)的long2表示，在3 * (hashcode % N) + 2位置存储相应的计数。
• 对于不同的键导致相同的哈希代码从而产生相同的桶的所有情况，您可以将数据存储在一个标准的HashMap<Long2KeyWrapper, Long>中。这样做的目的是保持上面提到的数组的容量(并相应地调整大小)足够大，以便到目前为止在该连续数组中拥有数据的最大部分，而不是在回退散列映射中。这将大大减少hashmap的存储开销。
• 不要在N=2N迭代中扩大容量，做较小的增长步骤，例如10-20%。这将花费填充映射的性能，但将使您的内存占用保持在控制范围内。

钥匙

考虑到不等式，5^32 > 2^64，你用比特编码5个字母的想法似乎是我现在能想到的最好的方法。使用3位和相应的long2。

Answer 2

我建议您查看Trove4j收集器API；它提供了包含原语的集合，与它们的装箱包装类相比，这些原语使用的内存更少。

具体来说，您应该查看他们的TObjectIntHashMap。

另外，在JDK 9发布之前，我不建议将任何东西存储为String或char，因为String的支持char数组是UTF-16编码的，每个char使用两个byte。JDK 9默认为UTF-8，其中只使用一个byte。

Answer 3

如果您使用的数据大小为~10‘t，或者至少是内存中的表示大小为~10’t的数据，那么您可能需要考虑如何将当前不需要的数据写入磁盘，并将数据集的各个部分加载到内存中来处理它们。

几年前，当我进行蒙特卡罗模拟研究时，我遇到了这个问题，所以我写了一个Java数据结构来解决这个问题。您可以在这里克隆/分叉源代码：github.com/tylerparsons/surfdep

库支持MySQL和SQLite作为底层数据库。如果两者都没有，我建议使用SQLite，因为设置起来要快得多。

完全免责声明:这不是最有效的实现，但如果让它运行几个小时，它将处理非常大的数据集。我在我的Windows笔记本电脑上成功地测试了多达10亿元素的矩阵。