java - Java 中 String 的 hashCode() 方法背后是什么？

Question

这个问题已经有答案了:

Why does Java's hashCode() in String use 31 as a multiplier? (13 个回答)

已关闭 10 年前。

我一直在调查 hashCode() java 中的方法，发现 String 类的方法很奇怪。源码如下:

public int hashCode() {
    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;
}

代码本身非常简单。但我想知道这样计算哈希码的原因是什么？
为什么选择31？
为什么从0开始而不是value.length - 1？
任何保证这都会使哈希码不太可能互相碰撞？

Answer 1

是的，哈希码冲突的概率非常低，例如在字符串的情况下，它取决于字符串值。如果我们不使用 new 运算符创建任何 String，那么如果新 String 具有与已存在的值相同的值，则不会创建新 String 对象，它引用堆中的旧值，在这种情况下，只有 hashCode 的值会被创建。与预期相同。

hashCode的通用约定是:

每当在 Java 应用程序执行期间对同一对象多次调用 hashCode 方法时，如果对象的 equals 比较中使用的信息没有被修改，则 hashCode 方法必须始终返回相同的整数。从一个应用程序的一次执行到同一应用程序的另一次执行，该整数不需要保持一致。

从 Java 1.2 开始，java.lang.String 类在字符串的整个文本上使用乘积和算法来实现其 hashCode()。[2]例如，给定 java.lang.String 类的实例 s，其哈希码 h(s) 定义为

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

其中各项使用 Java 32 位 int 加法求和，s[i] 表示字符串的第 i 个字符，n 是 s 的长度。

供您在 Apache Harmony 中引用，方法 hashCode 为:

public int hashCode() {
    if (hashCode == 0) {
        int hash = 0, multiplier = 1;
        for (int i = offset + count - 1; i >= offset; i--) {
            hash += value[i] * multiplier;
            int shifted = multiplier << 5;
            multiplier = shifted - multiplier;
        }
        hashCode = hash;
    }
    return hashCode;
}