Hash functions

A Python list finds an item by its position. Often you want to find it by a name instead: the price of a ticket from its code, or the count of a word. A hash table does this in O(1) time on average. Python’s dict and set are hash tables.

What a hash table does

A hash table stores keys, and usually a value with each key. It answers three questions quickly: add this key, find this key, remove this key.

Inside, it is an array of m places called buckets, numbered 0 to m − 1. The key idea is to work out, from the key alone, which bucket the key belongs in. Then a find does not search the whole table. It goes straight to one bucket.

fares = {}                 # an empty dict: a hash table
fares['NDLS'] = 450        # add a key with a value
fares['NDLS']              # 450: find it by its key
'BCT' in fares             # False
del fares['NDLS']          # remove it

A hash function

A hash function turns a key into a whole number, called its hash. The table then takes the remainder after dividing by m, written hash % m. The remainder is always between 0 and m − 1, so it is a bucket number.

The figure hashes four short words into 7 buckets. ord(ch) gives the code number of a letter: ord('a') is 97. Step through both versions and compare where the words land:

def bucket(word, m):
    total = 0
    for ch in word:
        total = total * 31 + ord(ch)
    return total % m

When two keys land in the same bucket, it is called a collision. With more keys than buckets, collisions cannot be avoided, so every hash table needs a plan for them. Lessons 2 and 3 show the two usual plans.

What makes a hash function good

A good hash function has three properties:

• It is fixed. The same key always gives the same number, while it is in the table.
• It is fast. Hashing a key of length L should take O(L) time, one pass over the key.
• It spreads keys evenly. Keys that look alike, such as cat and act, or 100 and 101, should land in buckets that look unrelated.

Adding the letter codes fails the third test: it ignores the order of the letters. Multiplying the total by a number like 31 before adding each letter fixes this. The first letter ends up multiplied by 31 many times, the last letter once, so moving a letter changes the result. Java hashes its strings in exactly this way. The method has a name: a polynomial hash, because the result is c₀·31^L−1 + c₁·31^L−2 + … + c_L−1. Here c₀ is the first letter’s code, and 31^L−1 means L − 1 copies of 31 multiplied together (and 31⁰ is 1).

The choice of m matters too. If m is 10, then k % 10 keeps only the last digit of k. Keys like 10, 20, 30 would all collide. A prime m, or a hash that mixes all the digits first, avoids this.

hash() in Python

Python has a built-in hash(x). A dict calls it on every key. Some things to know:

hash(42)          # 42: a small whole number is its own hash
hash(-1)          # -2: a quirk; inside CPython, -1 means "error"
hash(1.0)         # 1: equal numbers have equal hashes, so
{1: 'a'}[1.0]     # 'a': 1 and 1.0 are the same key
hash((2, 3))      # works: a tuple of hashable items is hashable
hash([2, 3])      # TypeError: unhashable type: 'list'

A list can change after you add it to a table. Its hash would then change too, and the table would look in the wrong bucket. So Python refuses to hash lists, dicts and sets. Their fixed versions, tuple and frozenset, are hashable. Things that can be hashed are called hashable.

Your own classes follow one rule:

By default, an object is equal only to itself, and its hash comes from its identity. If you define __eq__ to compare by value, Python sets __hash__ to None, so the objects become unhashable. That stops you from breaking the rule by accident. To make them hashable again, define __hash__ from the same fields that __eq__ compares:

class Station:
    def __init__(self, code, name):
        self.code, self.name = code, name
    def __eq__(self, other):
        return isinstance(other, Station) and self.code == other.code
    def __hash__(self):
        return hash(self.code)      # the same field __eq__ uses