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

Question

我正在尝试使用 'meet-in-the-middle' 攻击来破解对称加密。为此，我需要存储 2**32 个整数对。我正在存储从 4 字节密文到 4 字节密钥的映射。

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

现在我正在使用 HashMap，但是当映射变大时，即使使用 -Xmx8192M.

将最大内存增加到 8GB，它也会变得太慢

什么是一个非常大的 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。

Answer 2

构建彩虹时table，请考虑您将要生成的数据的大小。还要考虑一个事实，这个问题可以在没有大量 RAM 的情况下解决。这是通过使用文件而不是将所有内容放入内存来完成的。通常，您构建的文件大小适合您的文件缓冲区。例如 4096 字节或 8192 字节。如果你得到一个密钥，你只需将它除以文件缓冲区的大小，加载文件并查看 mod x 位置。棘手的部分是您需要布置加密数据，而不是密钥。所以你从虚拟文件开始，在加密数据的位置写入密钥数据。

这么说吧，你的密钥是1026，加密后的数据是126。写入1026的flke是0.rbt因为126*4 byte / 4096 = 0。位置是126*4 byte。当然，你需要 nio 类。

Answer 3

这是大数据问题，在这种情况下更像是一个大内存问题。为了性能，计算应该在内存中完成。使用 Hazelcast 分布式 HashMap。它非常易于使用且非常高效。您可以使用 2 台或更多机器来解决您的问题。

示例用法：

HazelcastInstance hzInstance = Hazelcast.newHazelcastInstance();
Map<Integer, Integer> map = hzInstance.getMap("map1");
map.put(x,y);
..

Answer 4

按照@MattBall 的建议，我实现了自己的 BigArray，它由 4 个单独的数组组成一个 32 位长度的数组。

运行如果没有建议的 JVM 参数，这将导致 OutOfMemoryError。将其与建议的 JVM 参数一起使用但内存太少可能会导致您的机器崩溃。

/**
 * Array that holds 2**32 integers, Implemented as four 30-bit arrays.
 * <p>
 * Requires 16 GB RAM solely for the array allocation. 
 * <p>
 * Example JVM Arguments: <code>-Xmx22000M -Xms17000M</code>
 * <p>
 * This sets the max memory to 22,000 MB and the initial memory to 17,000 MB
 * <p>
 * WARNING: don't use these settings if your machine does not have this much RAM.
 * 
 * @author popovitsj
 */
public class BigArray
{

    private int[] a_00= new int[1 << 30];
    private int[] a_01 = new int[1 << 30];
    private int[] a_10 = new int[1 << 30];
    private int[] a_11 = new int[1 << 30];

    private static final int A_00 = 0;
    private static final int A_01 = 1 << 30;
    private static final int A_10 = 1 << 31;
    private static final int A_11 = 3 << 30;
    private static final int A_30 = A_01 - 1;

    public void set(int index, int value)
    {
        getArray(index)[index & A_30] = value;
    }

    public int get(int index)
    {
        return getArray(index)[index & A_30];
    }

    private int[] getArray(int index)
    {
        switch (index & A_11)
        {
        case (A_00):
            return a_00;
        case (A_01):
            return a_01;
        case (A_10):
            return a_10;
        default:
            return a_11;
        }
    }
}

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

What is an efficient alternative for an extremely large HashMap?

java

hashmap