10

著名的 JDK 文档说：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;

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

4

5 回答 5

25

展开循环。然后你得到：

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

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

于 2009-05-04T22:26:17.557 回答
13

我不确定您是否错过了该文档中“^ 表示求幂”（不是 xor）的位置。

每次通过循环，hash 的前一个值再次乘以 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 的每个值代入以下语句，将它们组合成一个语句：

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

并转换为指数（不再是真正的 Java）：

hash = 31^3 * value[0] + 31^2 * value[1] + 31^1 * value[2] + value[3];
于 2009-05-04T22:45:36.560 回答
10

归纳证明：

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)

我想我有它，并要求提供证明。

于 2009-05-04T22:31:50.477 回答
9

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

散列0 = 0 + s 0 = s 0
散列1 = 31(散列0 ) + s 1 = 31(s 0 ) + s 1
散列2 = 31(散列1 ) + s 2 = 31(31(s 0 ) + s 1 ) + s 2 = 31 2 (s 0 ) + 31(s 1 ) + s 2
...
于 2009-05-04T22:31:46.577 回答
0

从所有字符中算出字符串的哈希码难道一点用都没有吗？想象一下将完整路径放入 HashSet 的文件名或类名。或者使用字符串文档的 HashSets 而不是 Lists 的人，因为“ HashSet 总是胜过 Lists ”。

我会做类似的事情：

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

最后，哈希码只不过是一个提示。

于 2013-07-21T14:54:15.487 回答