证明：为什么java.lang.String.hashCode（）的实现与其文档相匹配？

StackOverflow https://stackoverflow.com/questions/822363

  •  03-07-2019
  •  | 
  •  

题

<的JDK文档code> java.lang.String.hashCode（） 着名的说：

  

String对象的哈希码计算为

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

使用 int 算术，其中 s [i] 是字符串的* i *字符， n 是字符串的长度， ^ 表示取幂。

此表达式的标准实现是：

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

看着这个让我觉得我正在通过算法课程沉睡。这个数学表达式如何转化为上面的代码？

有帮助吗？

解决方案

我不确定你是否错过了它所说的“^表示取幂” （不是xor）在该文件中。

每次循环时，先前的哈希值再次乘以31 ，然后再添加到 value 的下一个元素。

有人可以通过归纳证明这些事情是平等的，但我认为一个例子可能更多 明确：

假设我们正在处理一个4字符串。让我们展开循环：

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

现在通过将每个哈希值替换为以下语句将它们组合成一个语句：

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

31 * 0为0，因此简化：

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

现在将两个内部术语乘以第二个31：

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

现在将三个内部术语乘以前一个31：

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

并转换为exponents（不再是Java）：

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

其他提示

展开循环。然后你得到：

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]...

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

归纳证明：

T1(s) = 0 if |s| == 0, else s[|s|-1] + 31*T(s[0..|s|-1])
T2(s) = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
P(n) = for all strings s s.t. |s| = n, T1(s) = T2(s)

Let s be an arbitrary string, and n=|s|
Base case: n = 0
    0 (additive identity, T2(s)) = 0 (T1(s))
    P(0)
Suppose n > 0
    T1(s) = s[n-1] + 31*T1(s[0:n-1])
    T2(s) = s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] = s[n-1] + 31*(s[0]*31^(n-2) + s[1]*31^(n-3) + ... + s[n-2]) = s[n-1] + 31*T2(s[0:n-1])
    By the induction hypothesis, (P(n-1)), T1(s[0:n-1]) = T2(s[0:n-1]) so
        s[n-1] + 31*T1(s[0..n-1]) = s[n-1] + T2(s[0:n-1])
    P(n)

我想我拥有它，并且要求提供证据。

看看前几次迭代，你会看到模式开始出现：

hash0 = 0 + s0 = s0
hash1 = 31(hash0) + s1 = 31(s0) + s1
hash2 = 31(hash1) + s2 = 31(31(s0) + s1) + s2 = 312(s0) + 31(s1) + s2
...

将String的哈希码计算为的所有字符根本没用吗？想象一下文件名或类名，并将其完整路径放入HashSet中。或者使用HashSets of String文档而不是列表的人，因为“ HashSet始终击败列表”

我会做类似的事情：

int off = offset;
char val[] = value;
int len = count;

int step = len <= 10 ? 1 : len / 10;

for (int i = 0; i < len; i+=step) {
   h = 31*h + val[off+i];
}
hash = h

最后，hashcode只不过是一个提示。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top