时间戳

首页 > 解决方案 > 不同的地图具有相同的哈希码

java - 不同的地图具有相同的哈希码

问题描述

我有两个不同 Map的 s，但它们具有相同的哈希码值：

    Map<String,Boolean> map1=new HashMap<>();
    map1.put("a", false);
    map1.put("b", true);
    map1.put("c", true);
    map1.put("d", true);
    map1.put("e", true);
    map1.put("f", false);
    map1.put("g", true);
    map1.put("k", false);
    Map<String,Boolean> map2=new HashMap<>();
    map2.put("a", false);
    map2.put("b", false);
    map2.put("c", false);
    map2.put("d", false);
    map2.put("e", true);
    map2.put("f", true);
    map2.put("g", false);
    map2.put("k", true);

    System.out.println(map1.hashCode()); //9595
    System.out.println(map2.hashCode()); //9595 --> should be different as the values are different!

该hashcode 函数的行为对我来说非常好：如果地图发生变化，那么哈希码当然应该改变。如果映射中的值相同，则哈希码应该相同。然而，标准哈希显然会导致相似对象的冲突。如何计算这两张地图的哈希值？

我尝试使用 HashCodeBuilderorg.apache.commons 

System.out.println(new HashCodeBuilder(17, 31)
        .append(map1.values())
        .toHashCode());

System.out.println(new HashCodeBuilder(17, 31)
        .append(map2.values())
        .toHashCode());

System.out.println(new HashCodeBuilder(17, 31)
        .append(map4.values())  //identical values as map2
        .toHashCode());

它为 map1、map2 和 map4（具有相同的值 als map2）返回不同的哈希值。但是，具有相同值的映射的哈希值应该相同......

标签： javahashhashmaphashcode

解决方案

哈希码函数的行为对我来说非常好：如果地图发生变化，那么哈希码当然应该改变。

强调应该改变，而不是必须改变。对此的唯一要求hashCode是，如果值相等，则散列必须相等。如果值不同，它没有给出关于应该发生什么的任何要求。它建议散列应该不同，但这只是一个建议，在实践中存在许多hashCode不能遵循该建议的情况。

你的方法有缺陷。您不能对不同值的散列做出任何假设，尤其是不要假设它们不同。

如果您有散列冲突，例如在基于散列的集合中，您必须使用equals第二步来检查它实际上是相同的元素还是只是两个不同元素的冲突。

从以下文档：Object#hashCode

不要求如果两个对象根据方法不相等equals(java.lang.Object)，则对两个对象中的每一个调用该hashCode方法必须产生不同的整数结果。但是，程序员应该意识到，为不相等的对象生成不同的整数结果可能会提高哈希表的性能。

这当然是有技术原因的。散列是关于用相当小的东西来表示可能非常大的东西。

在这种特殊情况下，Object用单个int. 只有2^32不同的整数值，但有无数种不同的Map设置。因此，不可能为int它们中的每一个设置不同的哈希值。

有关此主题的更多信息，请参阅 Wikipedia#Hash function。

推荐阅读