java - HashMap 获取错误的大小

Question

我正在尝试将一些键作为 byte[] 从 HashSet 导出到 HashMap 并使用 HashMap 存储数据对。但是，我遇到了一个问题，由于某种原因，集合的大小大于 HashMap 的大小。我想知道是什么原因导致的，因为 HashMap 在 foreach 中，它从 0 迭代到 HashSet 的大小，即 2^20。因此，我还希望 HashMap 的大小也为 2^20。

因此，我试图在 HashMap 中存储的是两个字节数组。我目前正在研究 2DES 的中间相遇攻击。我的加密已正确实现。此外，我的 DES key 生成器也已正确实现，因此我能够生成 2^20 个 key (只有 20 位 key 有效)。但是，当我尝试将键放入 HashMap 时，大小与 HashSet 不同，这没有任何意义。

for (int i = 0; i < Math.pow(2, 20); i++) {
    possibleKeySet.add(generateDesKey());
}

for (byte[] key : possibleKeySet) {
    intermediateCipher.put((encrypt(key, plainText)).toString(), key);
}

输出:设置大小:1048576 map 大小:1048295

PS:intermediateCipher 是我的 HashMap。

更新:我尝试过实现 hashcode 和 equals，但我不确定如何实现 hashcode。

class ByteArray {

    private byte[] key;

    ByteArray(byte[] key) {
        this.key = key;
    }

    byte[] getKey() {
        return key;
    }

    public boolean equals(Object obj) {
      ByteArrayOutputStream bos = new ByteArrayOutputStream();
      ObjectOutputStream oos = new ObjectOutputStream(obj);
      oos.writeObject(obj);
      oos.flush();
      byte [] data = bos.toByteArray();
      return key.equals(data);
}

    public int hashCode() {
        // what should I write here?
    }

}

Answer 1

哈希冲突的概率是(可以是 seen here ):

给定 k 输入的一组大小 n 的平均碰撞次数是:

给定 2^32 的 n 和 2^20 的 k，平均碰撞为

(2^20) * (2^20 - 1) / (2 * 2^32)
~= 2^40/2^33
~= 2^7
~= 128

您看到的碰撞次数是 1048576 - 1048295 = 281。鉴于此信息，我假设 encrypt(key, plainText) 返回值的实际熵大约为 ~31 位(而不是 32 位)。

---

要获得所需数量的键，您可能只想继续生成值，直到达到所需的大小。这可能会使该方法需要很长时间才能完成:

while (intermediateCipher.size() < Math.pow(2,20)) {
    byte[] key = generateDesKey();
    intermediateCipher.put((encrypt(key, plainText)).toString(), key);
}

---