0

我有一个类的哈希码实现，哈希码实现与 eclipse 生成的内容一致，也是此处讨论的最普遍接受的做法

这是我的哈希码实现（此方法中使用的所有 Id 构成对象的键）：

public int hashCode() {
    final int prime = 31;
    int hashCode = 1;
    if(uId != null){
        hashCode = prime * hashCode + uId.hashCode();
    }
    if(rId != null){
        hashCode = prime * hashCode + rId.hashCode();
    }
    if(bId != null){
        hashCode = prime * hashCode + bId.hashCode();
    }
    if(reId != null){
        hashCode = prime * hashCode + reId.hashCode();
    }
    if(cId != null){
        hashCode = prime * hashCode + cId.hashCode();
    }
    return hashCode;
}

我遇到了一个场景，我正在使用一个非常大的数据集进行测试，而我的集合没有这个类的预期数量的对象。仔细观察，下面的两个数据集产生了相同的哈希码：50268236873，因此一条记录被添加到集合中的最后一条替换，因为它们的哈希码相同。

  Existing record :
  Record@2c0781cd[uId=54046,rId=10967,bId=177,reId=1728,cId=50194] 

  Record being inserted into the collection :
  Record@20dad050[uId=53806,rId=18389,bId=177,reId=19026,cId=50194]

Both of these had the hashCode value = 50268236873

所以，问题：

1]这是两个不同对象的哈希码具有相同值的明显情况。那么如何确保任何数据集都不会发生这种情况呢？质数应该更大吗？

2] 如果我们仔细观察，实现中的 hashCode 变量是 int 数据类型，其最大值为 2^31 - 1 = 2147483647，大于为上述数据集计算的 hashcode = 50268236873，因此存在溢出. 使用 long 作为 hashCode 值的类型有什么后果吗？

感谢
Nohsib

编辑 ：

我正在使用 HashSet 并在阅读完发布的答案后，我查看了 equals 实现，如下所示，我认为因为在 equals 中我检查两个对象的 hashCodes 是否相同并使用它来确定它们是否是相同的对象导致了这个问题。

你们中的任何人都可以证实这一点吗？

@Override
    public boolean equals(Object paramObject) {
        boolean equals = false;
        if (paramObject != null) {
            ACRecord other = (ACRecord) paramObject;
            if ((this.hashCode() == other.hashCode()) // I think this is where I am going wrong
                    || (this.uId.equals(other.getUId())
                            && this.rId.equals(other.getRId())
                            && this.reId.equals(other.getReId())
                            && this.bId.equals(other.getBId()) 
                            && this.cId.equals(other.getCId))) {
                equals = true;
            }
        }
        return equals;
    }

解决方案：我的 equals 方法实现是错误的，因为我使用 hashCode 来确定两个对象是否相等。纠正 equals 方法实现解决了我的问题是 hashset 正在替换现有记录。

4

5 回答 5

9

通常，哈希码不保证唯一性。HashMap 实现通常通过在后台存储一个列表来处理冲突，但它们包含一个检查，以确保您不会将列表中的所有内容都作为匹配项，而只是真正匹配的那些。

换句话说，如果您执行 map.get("foo") 并且存在冲突，则哈希映射将检查每个结果（未哈希）以查看它是否真的与“foo”匹配。然后它只返回完全匹配。

另请注意，虽然哈希码合约规定任何两个对 equals() 响应为 true 的对象都应具有相同的哈希码，但相反的不一定是正确的。

于 2015-03-20T00:24:59.213 回答
3

这是Java 8 文档中的 hashCode 合同（摘要）：

  1. 在同一个对象上调用该方法两次必须产生相同的值（每个 JVM 实例）。

  2. 如果两个对象a和b根据 相等a.equals(b)，则 hashCodes 必须相同。

这是满足上述条件的最小定义：

public int hashCode() {
  return 0;
}

所有java.util.*Collections 都喜欢HashTable并HashMap遵守此合同，并且永远不会因为重复的 hashCodes 而丢弃项目，即使像上面的示例中那样过度重复也是如此。它会很慢，但它会是正确的。

相反，在基于散列的集合中添加或检索时出现意外结果的典型原因包括：

  • 重用/修改对象，使其哈希码在运行时更改（违反#1）
  • 不覆盖.equals(Object)
  • 使用一个错误的集合（在 之外java.*），它假设的内容hashCode比合同规定的要多。
于 2015-03-20T00:50:51.233 回答
0

hashCode 不要求是唯一的，只要两个对象相等，它们的哈希值也必须相等。

哈希冲突是意料之中的，也是不可避免的原因，因为您注意到只能有 2*maxint 可能的值，因此如果可能的对象空间超过此数字，则必须发生冲突。

您不能将 hashCode 更改为 long，因为它已经定义为 int 并且将被使用。

hashMap 或 HashSet 之类的集合知道可能的冲突，并且不受它们的影响。您的自定义代码也必须是防碰撞的。

于 2015-03-20T00:40:36.323 回答
0

哈希码通常将较大范围的值映射到较小范围的值。这意味着即使是最完美的数据散列算法也会在达到可能的散列值数量的值时产生冲突（n + 1使用int 作为散列码时）n2^32

您的实现需要通过对对象的所有成员进行完整检查以验证它们实际上是否相等来处理此类冲突。

散列通常通过减少验证结果所需的检查数量来大大减少完整检查，因为您只需要检查具有相同散列码的值，直到找到与您的数据完全匹配的值，或者如果没有一个与您的数据匹配不存在于地图中。

有关哈希映射实现的简要说明，请参见此答案。

于 2015-03-20T00:50:00.740 回答
0

哈希绝不意味着是完全唯一的。但是，有一些散列算法更擅长避免冲突。正如您在代码中已有的那样，通常最好使用质数来帮助解决冲突。

于 2015-03-20T00:51:25.283 回答