Java中String的hashCode()方法背后的原理是什么？

Question

Java中String的hashCode()方法背后的原理是什么？

37

我一直在研究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？
有保证这样做可以使哈希码更不可能发生冲突吗？

- HarryLv

2

请查看此答案：https://dev59.com/oHVD5IYBdhLWcg3wBm1g - NilsH

3

这个是https://dev59.com/gnVC5IYBdhLWcg3wbQfA#299748。 - Serkan Arıkuşu

数字31被选为哈希表中的素数，以避免碰撞。 - hatranpro

与主题无关，但是为什么Oracle使用这种代码“int h = hash”？？为什么不直接在hash上执行操作？？我在Oracle代码中看到了这一点！！！我不理解这个...“char val [] = value”更让我困惑！！！ - marcolopes

1

@marcolopes 如果对hash直接进行操作，那么它就不是线程安全的，因为一个线程可能在另一个线程仍在计算哈希值时尝试读取hash。在这种情况下，hash != 0，所以hashCode会返回中间值，这是不正确的。如果你只在最后一次使用正确的值修改hash（就像Oracle的实现一样），那么hash的值始终是0或者正确的哈希值（因为访问int是原子操作）。 - undefined

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Shreyos Adikari · Accepted Answer

是的，哈希码碰撞的概率非常低，例如在字符串的情况下它取决于字符串的值。如果我们没有使用new操作符创建任何字符串，那么如果新字符串具有与已经存在的相同的值，则不会创建一个新的字符串对象，它会引用堆中旧值，在这种情况下hashCode的值将会与预期相同。

hashCode的一般合约是：

在Java应用程序的执行过程中，每当它被多次调用相同的对象时，hashCode方法必须始终返回相同的整数，前提是在对象上使用的任何信息未被修改。这个整数不需要在应用程序的一个执行和另一个执行之间保持一致。

从Java 1.2开始，java.lang.String类使用整个文本的乘积和算法实现它的hashCode()。例如，给定java.lang.String类的实例s，将定义一个哈希码h(s)

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

使用Java 32位整数相加对术语进行求和，在这里，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;
}