Hash Functions

A hash function turns any key (a string, a tuple, a number) into an integer of fixed size. A hash table uses it to pick a slot in an array: index = h(key) % m, where m is the array size. The better the hash function, the more evenly the keys spread out and the closer lookup gets to O(1).

Properties of a good hash function

• Deterministic: the same key always gives the same hash (within one process).
• Consistent: if a == b then hash(a) == hash(b) (the converse is false: hashes may coincide).
• Uniform: values should fall into 0..m-1 with equal density.
• Fast: linear time in the size of the key.
• Avalanche effect: changing one character of the key should change the hash a lot.

String hash: summing is bad, polynomial is good

If you just add the character codes (sum_hash), anagrams get the same hash. A polynomial hash takes the position into account: h = s[0]*p^(n-1) + ... + s[n-1] (mod m). With Horner's scheme it is computed in O(n): h = h * p + ord(ch).

def sum_hash(s):
    return sum(ord(ch) for ch in s)

def poly_hash(s, p=31, m=2**32):
    h = 0
    for ch in s:
        h = (h * p + ord(ch)) % m
    return h

for w in ["listen", "silent", "enlist", "banana"]:
    print(w, sum_hash(w), poly_hash(w))

listen 655 3192458695
silent 655 3392640085
enlist 655 2996453575
banana 609 2898612069