java - 证明 : why does java. lang.String.hashCode() 的实现与其文档相匹配？

Question

java.lang.String.hashCode() 的 JDK 文档famously说:

The hash code for a String object is computed as

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

using int arithmetic, where s[i] is the *i*th character of the string, n is the length of the string, and ^ indicates exponentiation.

这个表达式的标准实现是:

int hash = 0;
for (int i = 0; i < length; i++)
{
    hash = 31*hash + value[i];
}
return hash;

看着这个让我觉得我正在通过我的算法类(class) sleep 。该数学表达式如何转化为上面的代码？

Answer 1

展开循环。然后你得到:

int hash = 0;

hash = 31*hash + value[0];
hash = 31*hash + value[1];
hash = 31*hash + value[2];
hash = 31*hash + value[3];
...
return hash;

现在您可以进行一些数学运算，为初始哈希值插入 0:

hash = 31*(31*(31*(31*0 + value[0]) + value[1]) + value[2]) + value[3])...

再简化一下:

hash = 31^3*value[0] + 31^2*value[1] + 31^1*value[2] + 31^0*value[3]...

这基本上就是给定的原始算法。