为什么以下三个字符串的哈希码是相同的？

Question

在阅读了JDK的源代码之后,我仍然对这些字符串"AaAa", "AaBB" and "BBBB"具有相同的哈希码感到惊讶 .

JDK的来源如下,

int h = hash;
if (h == 0 && value.length > 0) {
    char val[] = value;

    for (int i = 0; i < value.length; i++) {
        h = 31 * h + val[i];
    }
    hash = h;
}
return h;

任何人都可以澄清一下吗？

Answer 1

因为这是为如何计算哈希码的计算方法String:

String对象的哈希码计算为

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

所以:

• 用于AaAa:65*31^3 + 97*31^2 + 65*31 + 97 = 2031744
• 用于AaBB:65*31^3 + 97*31^2 + 66*31 + 66 = 2031744
• 用于BBBB:66*31^3 + 66*31^2 + 66*31 + 66 = 2031744

Answer 2

因为概率.

有大约40亿个可能的哈希码(Integer.MIN_VALUE -> Integer.MAX_VALUE)和基本上无限可能的字符串.必然会发生碰撞.实际上,生日问题告诉我们,任意碰撞的可能性很高,只需要约77,000个字符串 - 如果散列函数具有极高的熵,那就不会这样.

也许您正在考虑加密哈希函数,其中

对消息进行小的更改应该如此广泛地更改哈希值,以使新哈希值看起来与旧哈希值不相关

在这种情况下,Object.hashCode不是为加密目的而设计的.

另请参阅Java的hashCode()安全性如何？