please explain this code for calculating hash code of a string

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开发者_C百科 explain this?

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

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 "=".

You can do

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

for the code to be clear and as efficient as yours.

Your code uses Horner's scheme and is correct, you should be able to understand it from the above wikipedia page.