I'm reading the source code of JPlag and came across their rabin-karp algorithm implemented found here.

Here's the gist of it:

// modulo = 63

            for (i=0; i<loops; i++) {
                hash -= factor * (s.tokens[i].type & modulo);
                hash = (2*hash) + (s.tokens[i+hashLength].type & modulo);

What makes this a "good" hash function (or is it a terrible one)?

Couple of things I don't understand:

  1. there isn't a modulus applied to the hash at each iteration of the loop unlike the traditional rabin karp algorithm, so is there a "table size" this adheres to, and why?

  2. (2*hash) - what is the significance of choosing 2 as the base? In the regular rabin-karp, the base is recommended to be larger than the character set size. 2 certainly isn't.

  3. (s.tokens[i+hashLength].type & modulo) - What is the bitwise AND doing here?

  • $\begingroup$ 63 in binary is just 8 set bits in the LSBs and unset bits elsewhere. $x \land m = x \mod (m - 1)$ when $modulo$ is a power of 2. $\endgroup$ – Throckmorton Apr 25 at 17:40

Your Answer

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

Browse other questions tagged or ask your own question.