请解释此代码以计算字符串的哈希码

Question

我读了一本算法书,其中说明给定字符串的键计算如下

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

使用int算术,其中s [i]是字符串的第i个字符,n是字符串的长度,^表示取幂.(空字符串的哈希值为零.)

或在代码中:

 int h = 0;
 for (int i = 0; i < n; i++) {
   h = 31*h + s.charAt(i);
 }

我的问题是,似乎代码实现并不等同于上面所述的计算方法.例如,给定字符串"ha"(分别为ascii代码104和97)

s [0]*31 ^(2-1)+ s [1]*31 ^ 0 = 104*31 + 97

从代码执行开始,结果是104 + 31*104 + 97

绝对两者不相等,那么如何解释呢？

参考链接:http://www.informatics.sussex.ac.uk/courses/dats/notes/html/node114.html

Answer 1

我认为你误读了代码.

在第一次迭代之后,h是104.

所以第二次迭代说:

h = 31 * 104 + 97;

......这正是你所期待的.

看起来你误读了这一行:

h = 31 * h + s.charAt(i);

如下:

h += 31 * h + s.charAt(i);

在给出的代码中,我们没有添加新值h,我们使用简单的赋值.

如果您实际编写了代码并看到了错误的值,请检查您是否有"+ ="而不是"=".