作者:摄影爱好者Summer_100 | 来源:互联网 | 2022-12-18 16:05
下面是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
*
* s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
*
* using {@code int} arithmetic, where {@code s[i]} is the
* ith 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
文档说,你可以看到,这hashCode()
是使用下面的公式计算的
s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
而实际的实施是不同的
for (int i = 0; i
我错过了任何明显的事情吗?请帮我.
1> rgettman..:
实现是正确的,但需要注意整数溢出可能发生(这里没问题,它不会对任何东西造成伤害).它使用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
在添加下一个字符的值之前乘以另一个因子.
2> Turing85..:
最简单的看一些例子会发生什么.让我们采用一串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
(利用的的分布性倍增的).正如您在表格的最后一行中所看到的,这正是文档所说的.