0
$\begingroup$

I am reading Algorithms 4th edition by Robert Sedgewick and am stumped at a particular problem. On page 460 of the book the author is describing a technique to hash strings and use prime numbers for modular hashing. Starting from the fourth line:

 If R is greater than any character value, this computation would
 be equivalent to treating the String as an N-digit base-R integer, 
 computing the remainder that results when dividing that number by M.

Where the algorithm being used to hash a N-character long String is:

int hash = 0;
for (int i = 0; i < s.length(); i++)
   hash = (R * hash + s.charAt(i)) % M;

How does the above algorithm result in a base-R integer?

Here M and R are integers (random) and s is the string of length N.

I am assuming that by the 'above computation' the author means the computation within the parentheses => R*hash + s.charAt(i)

$\endgroup$
0
$\begingroup$

The iteration results in :

(R^2*C + R^1*B + R^0*A + some constant)mod(M) for the string ABC, the value inside the brackets is a base 16 representation of CBA plus some constant value.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.