字符串的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];
}

我有什么明显的遗漏吗？请帮我看看。

- sanbhat

---

你使用的Java版本是什么？我看到了一个稍微不同的实现（虽然仍然不符合文档）。 - Turing85

@Turing85 提到了 Java 8。 - Thiyagu

@Turing85，确切地说是1.8.0_131。 - sanbhat

Answer 1

这个实现是正确的，但要注意可能会发生整数溢出（在这里没问题，不会造成任何影响）。它使用 霍纳算法 进行多项式求值。

以下是在示例字符串 "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是字符串s中i的索引。每次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的因子。

- rgettman

---

请参阅强度降低。此外，这个答案则相反。List.hashCode已经被规定为乘法循环，我将其转换为指数和的总和以使其可并行化。 - Holger

Answer 2

通过一些示例最容易看到发生了什么。让我们取一个长度为n的字符串s，并采用上述所有符号。我们将逐个分析循环迭代。我们将称呼h_old为当前迭代开始时h的值，并称呼h_new为当前迭代结束时h的值。很容易看出，第i次迭代的h_new将是第i + 1次迭代的h_old。

╔═════╦════════════════════════════╦═════════════════════════════════════════════════╗
║ It. ║ h_old                      ║ h_new                                           ║
╠═════╬════════════════════════════╬═════════════════════════════════════════════════╣
║ 1   ║ 0                          ║ 31*h_old + s[0] =                               ║
║     ║                            ║          s[0]                                   ║
║     ║                            ║                                                 ║
║ 2   ║ s[0]                       ║ 31*h_old + s[1] =                               ║
║     ║                            ║ 31      *s[0] +          s[1]                   ║
║     ║                            ║                                                 ║
║ 3   ║ 31  *s[0] +    s[1]        ║ 31^2    *s[0] + 31      *s[1] +    s[2]         ║
║     ║                            ║                                                 ║
║ 4   ║ 31^2*s[0] + 31*s[1] + s[2] ║ 31^3    *s[0] + 31^2    *s[1] + 31*s[2] + s[3]  ║
║ :   ║ :                          ║ :                                               ║
║ n   ║ ...                        ║ 31^(n-1)*s[0] + 31^(n-2)*s[1] + ... + 31^0*s[n] ║
╚═════╩════════════════════════════╩═════════════════════════════════════════════════╝

（使用Senseful生成的表格）

通过循环和常数乘以31（利用乘法的分配律），可以创建31的幂次。 正如我们在表格的最后一行中所看到的，这正是文档所说的。

- Turing85