Hash Tables

Finding without searching

To answer x in items for a list, Python compares x with each item in turn until it finds it or runs out: O(n) ¹. That’s fine for ten items and slow for ten million. A hash table avoids the search: it computes where an item belongs from the item itself, and looks only there. Python’s dict and set are hash tables ².

This program asks the same question of a list and of a set holding the same million numbers, choosing the last number, the worst case for a scan. Save it as lookup.py:

# lookup.py: is a number in the collection? A list scans; a set hashes.
import time

N = 1_000_000
as_list = list(range(N))
as_set = set(as_list)

for name, coll in [("list", as_list), ("set", as_set)]:
    start = time.perf_counter()
    for _ in range(100):
        found = (N - 1) in coll         # the last number: worst case for a scan
    each = (time.perf_counter() - start) / 100
    print(f"{name:<5} {each * 1e6:10.2f} microseconds per lookup")

On a desktop PC:

me@linuxbox:~$ python3 lookup.py
list     3043.62 microseconds per lookup
set         0.06 microseconds per lookup

About fifty thousand times faster, and the gap grows with the data: a list twice as long takes twice as long to scan, while the set’s lookup stays about the same.

How a hash table works

A hash table with chaining is an array of buckets, each a short list ³. To store a key:

1. A hash function turns the key into an integer, its hash.
2. The remainder after dividing the hash by the number of buckets picks a bucket.
3. The key and its value go into that bucket’s list.

To look a key up, do steps 1 and 2 again and search only that bucket. Two keys that land in the same bucket are a collision; with chaining they simply share the bucket’s list ³.

What keeps lookups fast is keeping buckets short. The table keeps the number of items no more than the number of buckets, so buckets average one item or fewer; when it gets fuller than that, it doubles the number of buckets and places every item again ³, the same doubling trick the array used. A hash function must give equal keys equal hashes, or a lookup would search the wrong bucket, and should give different keys different hashes as often as possible, so collisions stay rare ³.

Building one

This hash table uses a simple hash function for strings: start at 0, and for each character multiply the total by 31 and add the character’s code, keeping the result to 32 bits. Hashes built from a polynomial like this are a standard way to hash strings ³. Save it as hashtable.py:

# hashtable.py: a small hash table with chaining, built on a Python list of lists.

def string_hash(s):
    """Turn a string into a big number: each character shifts the total and adds its code."""
    h = 0
    for ch in s:
        h = (h * 31 + ord(ch)) % 2**32
    return h

class HashTable:
    def __init__(self, size=8):
        self.buckets = [[] for _ in range(size)]
        self.count = 0

    def _bucket(self, key):
        return self.buckets[string_hash(key) % len(self.buckets)]

    def put(self, key, value):
        bucket = self._bucket(key)
        for pair in bucket:
            if pair[0] == key:          # key already there: replace its value
                pair[1] = value
                return
        bucket.append([key, value])
        self.count += 1
        if self.count > len(self.buckets):
            self._grow()                # keep buckets short: about one item each

    def get(self, key):
        for k, v in self._bucket(key):  # only one short bucket is searched
            if k == key:
                return v
        raise KeyError(key)

    def _grow(self):
        pairs = [pair for bucket in self.buckets for pair in bucket]
        self.buckets = [[] for _ in range(2 * len(self.buckets))]
        self.count = 0
        for k, v in pairs:
            self.put(k, v)

stock = HashTable()
for wood, boards in [("oak", 12), ("ash", 7), ("pine", 30), ("birch", 4), ("maple", 9), ("elm", 2)]:
    stock.put(wood, boards)
for k in ["oak", "ash", "pine"]:
    print(f"{k!r:8} hashes to {string_hash(k):>8}, bucket {string_hash(k) % 8}")
for i, bucket in enumerate(stock.buckets):
    print(i, bucket)
print("pine:", stock.get("pine"))

me@linuxbox:~$ python3 hashtable.py
'oak'    hashes to   109785, bucket 1
'ash'    hashes to    96886, bucket 6
'pine'   hashes to  3441008, bucket 0
0 [['pine', 30], ['birch', 4]]
1 [['oak', 12]]
2 []
3 []
4 []
5 [['maple', 9]]
6 [['ash', 7], ['elm', 2]]
7 []
pine: 30

Six woods in eight buckets: four landed alone, and two pairs collided and share a bucket. get("pine") hashed "pine" to bucket 0 and compared at most two keys. With a million items in a million or so buckets, it would still compare about one or two.

Python’s dict and set

CPython’s dictionaries are resizable hash tables, and sets work the same way ^{2 1}. On average, key in d, d[key], d[key] = value, and del d[key] are all O(1). The catch is “on average”: if every key hashed to the same value, they’d all share one bucket and each operation would become O(n) ¹.

That worst case could be forced on purpose: someone who knew the hash function could feed a program thousands of keys that all collide, making a dictionary of them take O(n²) time to build. So Python salts the hashes of strings with a random value chosen when each Python process starts ⁴. Within one run a string’s hash never changes; between runs it does:

me@linuxbox:~$ python3 -c 'print(hash("oak"), {"oak", "ash", "pine", "elm"})'
-5631937654534608314 {'oak', 'pine', 'ash', 'elm'}
me@linuxbox:~$ python3 -c 'print(hash("oak"), {"oak", "ash", "pine", "elm"})'
7551618212067019069 {'elm', 'pine', 'ash', 'oak'}
me@linuxbox:~$ python3 -c 'print(hash(42), hash(7))'
42 7

The set’s order changed too: a set is listed in the order of its internal table, so different hashes mean a different order ⁴. Never rely on the order of a set. A dict, by contrast, always keeps its keys in the order they were added ⁵. Small integers just hash to themselves.

Keys can’t change

A key’s hash decides its bucket when it’s stored. If the key could change afterward, its hash would change, and a lookup would search a different bucket and never find it. So dictionary keys must be immutable: strings, numbers, and tuples, but not lists ².

me@linuxbox:~$ python3 -c 'd = {}; d[[1, 2]] = "x"'
Traceback (most recent call last):
  File "<string>", line 1, in <module>
TypeError: unhashable type: 'list'

To key a dictionary by a sequence, convert it to a tuple: d[(1, 2)] = "x" works ².

Hash tables everywhere

Bash keeps a hash table of the commands you’ve run, mapping each name to its full path, so it doesn’t search every directory in PATH each time ⁶. The hash command shows it, with how often each was used:

me@linuxbox:~$ hash
hits    command
   3    /usr/bin/ls
   1    /usr/bin/date
   1    /usr/bin/sort

If you install a program somewhere earlier in PATH and bash keeps running the old one, hash -r makes it forget ⁶.

Counting is a dictionary job: counts[word] = counts.get(word, 0) + 1 for each word in a file tallies a whole book in one pass.

Git names every object by a SHA-1 hash of its contents (Git course). That’s a different, much longer kind of hash, used as a fingerprint to check the data’s integrity ⁷, but the idea is the same: a fixed-size number computed from the data.

Your turn

So

A hash table computes where each key belongs: a hash function turns the key into a number, and the remainder picks a bucket, so a lookup searches one short bucket instead of everything. Collisions share a bucket; doubling the table as it fills keeps buckets short and operations O(1) on average. Python’s dict and set are hash tables, fifty thousand times faster than a list for membership among a million items. String hashes are salted per run, so set order changes; keys must be immutable; and the same idea runs bash’s command lookup.