Java 包含不同但相似字符串的对象的 hashcode() 冲突

Question

在验证程序的输出数据时，我确定了两个不同对象的哈希码相同的情况。为了获得这些代码，我使用了以下函数：

int getHash( long lID, String sCI, String sCO, double dSR, double dGR, String sSearchDate ) {

    int result = 17;
    result = 31 * result + (int) (lID ^ (lID >>> 32));
    long temp;
    temp = Double.doubleToLongBits(dGR);
    result = 31 * result + (int) (temp ^ (temp >>> 32));
    temp = Double.doubleToLongBits(dSR);
    result = 31 * result + (int) (temp ^ (temp >>> 32));
    result = 31 * result + (sCI != null ? sCI.hashCode() : 0);
    result = 31 * result + (sCO != null ? sCO.hashCode() : 0);
    result = 31 * result + (sSearchDate != null ? sSearchDate.hashCode() : 0);

    return result;
}

这是两个示例案例：

getHash( 50122,"03/25/2015","03/26/2015",4.0,8.0,"03/24/15 06:01" )
getHash( 51114,"03/24/2015","03/25/2015",4.0,8.0,"03/24/15 06:01" )

我想，这个问题出现了，因为我的数据中存在三个非常相似的字符串，并且字符串 A 到 B 和 B 到 C 之间的哈希码差异大小相同，导致返回相同哈希码。

IntelliJ 提议的 hashcode() 实现使用 31 作为对最终哈希码有贡献的每个变量的乘数。我想知道为什么不为每个变量使用不同的值（比如 33、37、41（我在其他处理哈希码的帖子中提到过））？就我而言，这将导致我的两个对象之间存在差异。

但我想知道这是否会导致其他情况出现问题？

对此有什么想法或提示吗？非常感谢！

Answer 1

hashCode() 合约允许不同的对象拥有相同的哈希码。来自 documentation:

It is not required that if two objects are unequal according to the equals(java.lang.Object) method, then calling the hashCode method on each of the two objects must produce distinct integer results. However, the programmer should be aware that producing distinct integer results for unequal objects may improve the performance of hash tables.

但是，由于您有一堆哈希参数，您可以考虑使用 Objects.hash() 而不是自己实现：

@Override
int getHash(long lID, String sCI, String sCO, double dSR, double dGR, String sSearchDate) {
    return Objects.hash(lID, sCI, sCO, dSR, dGR, sSearchDate);
}

例如：

Objects.hash(50122, "03/25/2015", "03/26/2015", 4.0, 8.0, "03/24/15 06:01")
Objects.hash(51114, "03/24/2015", "03/25/2015", 4.0, 8.0, "03/24/15 06:01")

结果：

-733895022
-394580334

Answer 2

您显示的代码可能会添加零，例如

result = 31 * result + (sCI != null ? sCI.hashCode() : 0);

添加一些零时，这可能会退化为

的乘法

31 * 31 * 31 ...

这会破坏唯一性。

然而，hashCode 方法并非旨在 return 唯一值。它应该简单地提供值的均匀分布并且应该易于计算（或像 String class 那样缓存 hashCode）。

从更理论的角度来看，hashCode 从一个大的集合 A 映射到一个较小的集合 B。因此，冲突（A 中的不同元素映射到 B 中的相同值）是不可避免的。你可以选择一个比 A 大的集合 B，但这会违反 hashCode 的目的：性能优化。真的，你可以用链表和一些额外的逻辑来实现任何你用 hashCode 实现的东西。

选择质数是因为它们会导致更好的分布。例如，如果使用 none 素数 4*3 = 12 = 2*6 会产生相同的 hashCode。有时会选择 31，因为它是梅森素数 2^n-1，据说在处理器上性能更好（我不确定）。

由于未指定 hashCode 方法，因此 return 明确标识元素的非唯一 hashCode 完全没问题。假设哈希码的唯一性是一个错误。

然而，HashMap 可以描述为一组桶，每个桶包含一个元素链表。桶由 hashCode 索引。因此，提供相同的 hashCodes 会导致更少的桶和更长的列表。在最极端的情况下（return将任意常量作为 hashCode）映射退化为链表。

在哈希数据结构中搜索对象时，hashCode用于获取桶索引。对于此存储桶中的每个对象，都会调用 equals 方法 -> 长列表意味着大量的 equals 调用。

结论：假设hashCode方法使用正确，不会导致程序出错。但是，这可能会导致严重的性能损失。

Answer 3

Ash 其他答案解释得很好，允许 hashCode 到 return 不同对象的相同值。这不是加密哈希值，因此很容易找到 hashCode 冲突的示例。

但是，我指出了您代码中的一个问题：如果您自己制作了 hashCode 方法，那么您肯定应该使用更好的哈希算法。看看 MurmurHash：http://en.wikipedia.org/wiki/MurmurHash. You want to use the 32-bit version. There are also Java implementations.

是的，哈希冲突会导致性能问题。因此，使用好的哈希算法很重要。此外，为了安全起见，MurmurHash 允许使用种子值来使哈希冲突拒绝服务攻击变得更加困难。您应该生成在程序开始时随机使用的种子值。您实施的 hashCode 方法容易受到这些哈希冲突 DoS 攻击。

Java 包含不同但相似字符串的对象的 hashcode() 冲突

Java hashcode() collision for objects containing different but similar Strings

java

string

collision

hashcode