Java中String的hashCode()方法背后的内容是什么？

Question

我一直在调查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

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