字符串hashCode()文档与实现

Question

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

/**
 * 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的方法进行多项式评估.

以下是示例字符串"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在添加下一个字符的值之前乘以另一个因子.

Answer 2

最简单的看一些例子会发生什么.让我们采用一串s长度n和所有符号,如上所述.我们将分析迭代的循环迭代.我们将在当前迭代开始时调用h_old值h,并且h_new值h在当前迭代结束时调用.很容易看出h_new迭代i将是h_old迭代的i + 1.

??????????????????????????????????????????????????????????????????????????????????????
? 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是通过循环和不断繁殖创造h与31(利用的的分布性倍增的).正如您在表格的最后一行中所看到的,这正是文档所说的.