Hashing

hash function
page 264, clrs
h.k/ D bm.kA mod 1/c

Division Method:
h(k) = k mod m
where m is ideally prime

Multiplication Method:
h(k) = [(a k) mod 2w] (w >> r)
where a is a random odd integer between 2^(w-1) and 2^w, k is given by w bits, and m = table
size = 2r.

universal hashing

----------------------------------
Karp Rabin_wiki, Rolling Hash_wiki

However, there are two problems with this. First, because there are so many different strings, to keep the hash values small we have to assign some strings the same number. This means that if the hash values match, the strings might not match; we have to verify that they do, which can take a long time for long substrings. Luckily, a good hash function promises us that on most reasonable inputs, this won't happen too often, which keeps the average search time within an acceptable range.

hash functions used for karp rabin, go to wiki hash function
The key to the Rabin–Karp algorithm's performance is the efficient computation of hash values of the successive substrings of the text. One popular and effective rolling hash function treats every substring as a number in some base, the base being usually a large prime. For example, if the substring is "hi" and the base is 101, the hash value would be 104 × 101¹ + 105 × 101⁰ = 10609 (ASCII of 'h' is 104 and of 'i' is 105)

multiple pattern search
The Rabin–Karp algorithm is inferior for single pattern searching to Knuth–Morris–Pratt algorithm, Boyer–Moore string search algorithm and other faster single pattern string searching algorithms because of its slow worst case behavior. However, it is an algorithm of choice for multiple pattern search.

------------------------------------------
Probing 
Liner probing
quadratic probing 
Double hashing
h(k, i) = (h1(k) + i * h2(k) mod m