Java中String的hashCode（）方法背后的内容是什么？ [英] What's behind the hashCode() method for String in Java?

问题描述

我一直在调查java中的 hashCode（）方法，并发现String类奇怪的方法。源代码如下：

I've been investigating the hashCode() methods in java and found the one for String class strange. The source code is as follows:

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？
任何保证这会使哈希码不太可能与之冲突彼此？

The code itself is quite straight forward. But I wonder what's the reason for calculating hash code this way?
Why choose 31?
Why start from 0 instead of value.length - 1?
Any guarantee that this would make hashcodes less possible to collide with each other?

推荐答案

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

Yes the probability of hashcode collision is very low as for example in case of String it depends upon the string value. If we are not creating any String with new operator then if the a new String has the same value that already present , then new String object is not created, it refers to the old value from heap and in this case only the value of hashCode will be same as expected.

hashCode的一般合约是：

The general contract of hashCode is:

每当在同一个对象上调用它时在执行Java应用程序期间，不止一次，hashCode方法必须始终返回相同的整数，前提是不修改对象的equals比较中使用的信息。从应用程序的一次执行到同一应用程序的另一次执行，这个整数不需要保持一致。

Whenever it is invoked on the same object more than once during an execution of a Java application, the hashCode method must consistently return the same integer, provided no information used in equals comparisons on the object is modified. This integer need not remain consistent from one execution of an application to another execution of the same application.

从Java 1.2开始，java.lang.String类实现了它的hashCode（）在字符串的整个文本中使用乘积和算法。[2]例如，给定java.lang.String类的实例s将具有由

From Java 1.2, java.lang.String class implements its hashCode() using a product sum algorithm over the entire text of the string.[2] Given an instance s of the java.lang.String class, for example, would have a hash code h(s) defined by

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

其中术语使用Java 32位int加法求和，s [i]表示字符串的第i个字符，n是长度s。

where terms are summed using Java 32-bit int addition, s[i] denotes the ith character of the string, and n is the length of s.

您在Apache Harmony中的参考方法hashCode是：

For your reference in Apache Harmony the method hashCode is:

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

这篇关于Java中String的hashCode（）方法背后的内容是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！