java - 什么是非常大的 HashMap 的有效替代方案？

Question

我正在尝试使用“中间相遇”攻击来破解对称加密。为此，我需要存储 2**32 个整数对。我正在存储从 4 字节密文到 4 字节 key 的映射。

起初我尝试使用数组，但后来我意识到在 java 中不能有这么大的数组(最大大小受 Integer.MAX_VALUE 限制)。

现在我正在使用 HashMap，但是当映射变大时，即使使用 -Xmx8192M 将最大内存增加到 8GB，这也会变得太慢。

什么是超大 HashMap 的有效替代方案？

这是我目前用来填充 HashMap 的代码:

HashMap<Integer, Integer> map = new HashMap<>(Integer.MAX_VALUE);
// Loop until integer overflow
for (int k = 1; k != 0; k++)
    map.put(encrypt_left(c, k), k);

我还没有看到这段代码完成，即使让它运行了几个小时。进度记录显示前 2**24 个值是在 22 秒内创建的，但随后性能迅速下降。

Answer 1

I'm storing the mapping from a 4-byte cyphertext to a 4-byte key.

方便地，4 个字节是一个int。如您所见，数组大小受 Integer.MAX_VALUE 限制。这表明您可以使用数组——但有一个小问题。整数是有符号的，但数组只允许值 >=0。

因此您创建了两个数组:一个用于正密文，一个用于负密文。然后您只需确保为 JVM 提供了足够的堆。

那是多少堆？

4 个字节 * Integer.MAX_VALUE * 2 个数组
= 17179869176 字节
= ~16.0 GB。