以下是Java 8中String.hashCode()
方法的源代码片段(准确地说是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];
}
我错过了任何明显的事情吗?请帮我。
实现是正确的,但需要注意整数溢出可能发生(这里没问题,它不会对任何东西造成伤害)。它使用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
循环的每次迭代都执行此公式。
它们是= 31 + -1年
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
的另一个因子中相乘。
最简单的看一些例子会发生什么。让我们采用长度为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
的恒定乘法(利用乘法的distributivity)创建的。正如您在表格的最后一行中所看到的,这正是文档所说的。