java - String hashCode() 文档与实现

Question

下面是Java 8(准确地说是1.8.0_131)的String.hashCode()方法的源代码片段

/**
 * Returns a hash code for this string. The hash code for a
 * {@code String} object is computed as
 * <blockquote><pre>
 * s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
 * </pre></blockquote>
 * using {@code int} arithmetic, where {@code s[i]} is the
 * <i>i</i>th character of the string, {@code n} is the length of
 * the string, and {@code ^} indicates exponentiation.
 * (The hash value of the empty string is zero.)
 *
 * @return  a hash code value for this object.
 */
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;
}

您可以看到，文档说，hashCode() 是使用以下公式计算的

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

虽然实际实现不同

for (int i = 0; i < value.length; i++) {
    h = 31 * h + val[i];
}

我是否漏掉了任何明显的东西？请帮助我。

Answer 1

实现是正确的，需要注意的是可能会发生整数溢出(在这里没关系，它不会造成任何伤害)。它正在使用 Horner's method用于多项式评估。

下面是示例字符串“CAT”的步骤。

h = 0

第一个循环:

i = 0
h = 31 * 0 + 'C' (67) = 67

第二个循环:

i = 1
h = 31 * 67 + 'A' (65) = 2142

第三个循环:

i = 2
h = 31 * 2142 + 'T' (84) = 66486

让我们从代码中推导出公式。这里，n 是 i 在字符串 s 中的索引。 for 循环的每次迭代都执行此公式。

h_n = 31h_n-1 + s_n

h0 /* after loop i = 0 */ = s[0]
h1 /* after loop i = 1 */ = 31*h0 + s[1] = 31*s[0] + s[1]
h2 /* after loop i = 2 */ = 31*h1 + s[2] = 31*(31*s[0] + s[1]) + s[2]
h = 31*31*s[0] + 31*s[1] + s[2]

您看到的 31 次方的指数是因为每个循环在添加下一个字符的值之前乘以 31 的另一个因子。