32

我一直在研究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 开始？
任何保证这将使哈希码不太可能相互冲突？

4

1 回答 1

7

是的，哈希码冲突的概率非常低，例如在字符串的情况下，它取决于字符串值。如果我们没有使用 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;
}
于 2013-03-20T08:31:59.257 回答