What is the best hash function for Rabin-Karp algorithm?

user_1126268 0
Viewed 8299

I'm looking for an efficient hash function for Rabin-Karp algorithm. Here is my actual code (C programming language).

static bool f2(char const *const s1, size_t const n1, 
               char const *const s2, size_t const n2)
{
    uintmax_t hsub = hash(s2, n2);
    uintmax_t hs   = hash(s1, n1);
    size_t   nmax = n2 - n1;

    for (size_t i = 0; i < nmax; ++i) {
        if (hs == hsub) {
            if (strncmp(&s1[i], s2, i + n2 - 1) == 0)
                return true;
        }
        hs = hash(&s1[i + 1], i + n2);
    }
    return false;
}

I considered some Rabin-Karp C implementations, but there are differences between all the codes. So my question is: what are the characteristics that a Rabin-Karp hash function should have?

rabin-karp pseudocode c algorithm c++
4 Answers

what are the characteristics that a Rabin-Karp hash function should have?

Rabin-Karp needs a rolling hash. The easiest rolling hash is a moving sum. Adler-32 and Buzhash are pretty simple too and perform better than a moving sum.

Any of these rolling hash techniques should work for Rabin-Karp:

  • Moving sum
    • remove the oldest byte with subtraction
    • add a new byte with addition
  • Polynomial rolling hash
    • remove the oldest byte with subtraction
    • add a new byte with multiplication and addition
  • Rabin fingerprint
    • a polynomial rolling hash whose polynomial is irreducible over GF(2)
  • Tabulation hashing
    • remove the oldest byte with a table lookup and an xor
    • add a new byte with a table lookup and an xor
  • Cyclic polynomial, aka Buzhash
    • tabulation hashing based on circular shifts
  • Adler-32 checksum
    • not a rolling checksum by default but easily adjusted to "roll"
    • remove the oldest byte with two subtractions
    • add a new byte with two additions
user_1744630

For the problem with the small alphabets, such as nucleic acid sequence searching (e.g. alphabet = {A, T, C, G, U}), nt-Hash may be a good hash function. It uses the binary operation, which is faster, and rolling hash update, and it also gives uniform distributed hash values.

user_111801980
user_54122490
Related