Geek asks and answers

Explain this code to calculate the hash of the string

I read the book of algorithms, which indicates that the key of this line 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 that the implementation of the code is not equivalent to the calculation method mentioned 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 execution of the code, the result is 104 + 31 * 104 + 97

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

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

+3
2

, .

h 104.

, :

h = 31 * 104 + 97;

... , .

, :

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

:

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

h, .

, , "+ =" "=".

+6

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

, .

Horner, .

+4

More articles:


All Articles