HashMap 获取的大小不正确。

Question

我正在尝试从一个HashSet中将一些密钥导出为byte[]，并使用HashMap存储数据对。然而，我遇到了一个问题，就是HashSet的大小比HashMap的大小要大，原因不明。我想知道是什么原因导致了这种情况，因为HashMap在foreach循环中，迭代从0到HashSet的大小，即2^20。因此，我也期望HashMap的大小也是2^20。

所以，我要在HashMap中存储两个字节数组。我目前正在处理2DES的meet-in-the-middle攻击。我的加密已经正确实现。此外，我的DES密钥生成器也已经正确实现，所以我能够生成2^20个密钥（只有20位是有效的）。然而，当我尝试将密钥放入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 映射大小：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?
    }

}

- user8231110

---

你可能在键上发生了冲突。你可以通过检查put方法的返回值来检查它。如果没有发生冲突，它将返回null。 - ByeBye

(encrypt(key, plainText) this will probably produce duplicates. You can check it by adding if(putReturn != null) sysout(putReturn) - ByeBye

我尝试使用if (intermediateCipher.get(key)！= null) {System.out.println（“ NULL”）;}，但它从未打印“ NULL”。 - user8231110

你必须检查 intermediateCipher.put((encrypt(key, plainText)).toString(), key); 的返回值。 - ByeBye

他正在使用 byte[] 作为密钥……因此会出现重复。 - Stephen C

Answer 1

如此处所示，哈希碰撞的概率为：

对于给定k个输入的大小为n的集合，平均碰撞次数为：

对于n等于2^32和k等于2^20的情况，平均碰撞次数为

(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);
}

---

- flakes

---

非常有趣，但我该如何避免碰撞？ - user8231110

即使哈希冲突，HashSet和HashMap仍使用equals来检查冲突（因此首先是hashCode桶，然后是具有equals检查的列表）。在我的答案中，我提供了解决问题的完整解决方案。 - ByeBye

@user8231110，我加入了一种简单的方法来获取所需的大小！ - flakes

非常有趣，但我该如何避免碰撞呢？你不能。你不需要这样做。你要检测到碰撞...并生成另一个密钥来替换它。@flakes-碰撞在possibleKeySet中！ - Stephen C

@user8231110，那很接近了，但还不够。我假设generateDesKey()每次调用都会产生一个不同的值。如果你调用两次，你将得到两个不同的密钥。看一下我的答案的最后一部分。 - flakes

Answer 2

如果您的Set和HashMap大小不同，可能会发生键冲突。看起来您的函数encrypt(key, plainText)返回了重复项。

尝试使用：

for (byte[] key : possibleKeySet) {
    Object oldValue = intermediateCipher.put((encrypt(key, plainText)).toString(), key);
    if(oldValue != null) {
        System.out.println("Duplicated!");
    }
}

它可能会产生一些错误。

还要注意，即使在Java中将两个数组存储在Set中，只有当它们是同一个对象时，generateDesKey()也可以产生相同的值。

你可以做什么？创建一个自定义对象：

class ByteArray {

    private byte[] key;

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

    byte[] getKey() {
        return key;
    }

    public boolean equals(Object obj) {
        //implement your equals logic using array members equality
    }

    public int hashCode() {
        //implement your hashCode logic using array members equality
    }

}

- ByeBye

---

你可以使用一个新的自定义对象，将你的数组存储为一个字段，然后重写hashCode和equals方法来检查数组内部的内容。 - ByeBye

我认为这些症状意味着你的 generateDesKey 也在生成非唯一的密钥。 - Stephen C

为了生成一个密钥，我正在使用SecureRandom()函数。 - user8231110

现在你有什么问题吗？我提供了一个解决方案，并回答了为什么你的 Set 大小与 HashSet 大小不同。如果你有另一个问题——比如帮助创建更好的函数示例，那就应该是一个新的独立的问题。 - ByeBye

我曾试图实现相等和哈希码，但我不确定如何实现哈希码。我已经尝试过了，希望你能帮助我。 - user8231110

Answer 3

该集合的实现方式要求其中每个项目都必须是唯一的 - 不允许重复。这意味着，当您将两个相等的对象放入集合中时，结果集合中只会有一个。

可能您的generateDesKey()方法对于所有2^20个值都返回了非唯一值，在结果集合中，项目计数少于2^20

基本上，您可以在将值复制到HashMap之前检查possibleKeySet的大小，例如：

System.out.println(possibleKeySet.size());

或者仅通过使用调试器

- m.antkowicz

---

我已经完成了这个任务，大小为1048576（2^20）。 - user8231110

其实并不奇怪。Bytearrays（以及数组）不能用作HashSet或HashMap中的键，这是由于equals的语义所决定的。请参考ByeBye的回答。 - Stephen C

但是他正在使用一个字符串作为键。 - Bab