java - 如何减少 HashMap 类数据结构的内存使用

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 实现

我建议为 Map<String, Long> 编写一个高度定制的 HashMap 实现。界面。在内部你不必存储字符串。不幸的是 5^32 > 2^64，所以无法将整个字符串打包成一个长字符串，好吧，让我们坚持使用两个长字符串作为一个键。当为您的 map 实现提供字符串键(使用位移位等)时，您可以相当高效地即时进行字符串到/返回 long[2] 的转换。

至于打包值，这里有一些注意事项:

对于一个键值对，一个标准的hashmap需要一个包含N个longs的桶数组，其中N是当前容量，当从哈希键中找到桶时，它需要一个键的链表-value 对来解析产生相同哈希码的键。对于您的具体情况，您可以尝试通过以下方式对其进行优化:

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

key

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