please explain this code for calculating hash code of a string

Question

I read an algorithm book which stated that the key of a given string is calculated as follows

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

using int arithmetic, where s[i] is the ith character of the string, n is the length of the string, and ^ indicates exponentiation. (The hash value of the empty string is zero.)

or in code:

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

My question is that it seems the code implementation is not equivalent to the calculation method stated above.For example,given the string "ha" (ascii code 104 and 97 respectively)

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

from the code execution,the result is 104+31*104+97

absolutely the two are not equal,so how to explain this?

Reference Link: http://www.informatics.sussex.ac.uk/courses/dats/notes/html/node114.html

Answer 1

I think you're misreading the code.

After the first iteration, h is 104.

So the second iteration says:

h = 31 * 104 + 97;

... which is exactly what you were expecting.

It looks like you misread this line:

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

as this:

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

In the code that's given, we're not adding a new value to h, we're using simple assignment.

If you're actually written the code and seen the wrong value, check whether or not you've got "+=" instead of "=".