algorithm - 请解释这段用于计算字符串哈希码的代码

Question

我看了一本算法书，上面说给定字符串的key是这样计算的

 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，我们使用的是简单的赋值。

如果您确实编写了代码并看到了错误的值，请检查您是否使用了“+=”而不是“=”。