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

Question

这个问题在这里已经有了答案:

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

关闭 9年前。

我一直在研究 java 中的 hashCode() 方法，发现 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 对象，它引用堆中的旧值，在这种情况下，只有 hashCode 的值会和预期的一样。

hashCode的一般合约是:

只要在 Java 应用程序的执行过程中对同一个对象多次调用，hashCode 方法必须始终返回相同的整数，前提是没有修改对象上的 equals 比较中使用的信息。该整数不需要在应用程序的一次执行与同一应用程序的另一次执行之间保持一致。

从 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;
}