在Java语言中，字符串的hashCode()方法背后是什么？

Question

我一直在研究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操作符创建任何字符串，那么如果新字符串具有与已经存在的值相同的值，则不会创建新的字符串对象，它引用堆中的旧值，在这种情况下，只有hashCode的值与预期的值相同。

hashCode的总合同是：

在Java应用程序执行期间，只要在同一对象上多次调用hashCode方法，它就必须一致地返回相同的整数，前提是该对象的equals比较中使用的信息没有被修改。从应用程序的一次执行到同一应用程序的另一次执行，该整数不必保持一致。

从Java1.2开始，java.lang.String类在字符串的整个文本上使用乘积和算法实现其hashCode()。例如，给定java.lang.String类的实例s，将具有由

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

其中，使用Java32位整数加法对项求和，si表示字符串的第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;
}