Hash Tables

Data Structures in Practice

Chapter 9 · Hash Tables Built by Hand

You have used dict and set in every chapter of this course, and relied on one promise: looking up a key takes roughly the same time however many keys there are (Data Structures in Practice 1 and 3). This chapter builds that machinery yourself, so the promise stops being magic. A hash table is a list of slots plus a hash function that turns a key into a number; the number, reduced to the table's size, says which slot to look in.

What was run, and what was not

Every snippet below was run and the output shown is what it printed. No timings are quoted, because they differ between machines. Slot numbers, counts and chain lengths are exact, because they depend only on the data and on the hash function written here (Python's own string hashes are deliberately randomised between runs, so this chapter uses its own).

The Hash Function

A good hash function is deterministic (the same key always gives the same number), fast, and spreads keys out, so that different keys rarely land in the same slot. The usual recipe for text multiplies a running total by a small prime before adding each character, so that the position of each letter matters. The final number is reduced with % (modulo) to a slot index.

def simple_hash(text):
    h = 0
    for ch in text:
        h = (h * 31 + ord(ch)) % 1_000_003
    return h

for w in ["cat", "act", "tac", "apple"]:
    print(w, simple_hash(w), simple_hash(w) % 8)

def bad_hash(text):
    return sum(ord(c) for c in text)       # order of letters is ignored
print(bad_hash("cat"), bad_hash("act"), bad_hash("tac"))
    

cat 98262 6
act 96402 2
tac 114582 6
apple 28931 3
312 312 312
    

cat and tac both land in slot 6 even though they are different words. The poor function that merely adds up letter codes cannot tell the three anagrams apart at all: they all hash to 312. Which slot a key gets does not matter; what matters is that the keys use all the slots evenly.

Collisions and Chaining

Two different keys with the same slot is a collision. It is unavoidable: there are far more possible keys than slots, so a table must have a plan for it. The first plan is separate chaining: each slot (called a bucket) holds a small list of the (key, value) pairs that landed there. To look up a key, hash it, go to its bucket, and compare keys one by one along that short list.

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

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

    def put(self, key, value):
        bucket = self._bucket(key)
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)     # replace an existing key
                return
        bucket.append((key, value))
        self.count += 1
        if self.count / len(self.buckets) > 0.75:
            self._grow()

    def get(self, key, default=None):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default

    def delete(self, key):
        bucket = self._bucket(key)
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.count -= 1
                return True
        return False

    def _grow(self):
        old = self.buckets
        self.buckets = [[] for _ in range(len(old) * 2)]
        self.count = 0
        for bucket in old:
            for k, v in bucket:
                self.put(k, v)               # every key is re-hashed

    def __len__(self):
        return self.count

    def load_factor(self):
        return self.count / len(self.buckets)

    def longest_chain(self):
        return max(len(b) for b in self.buckets)
    

t = ChainedTable()
for i, w in enumerate(["cat", "act", "tac", "apple", "pear", "plum", "fig", "kiwi"]):
    t.put(w, i)
    print(w, len(t), len(t.buckets), round(t.load_factor(), 2))
print(t.get("fig"), t.get("nope"), t.get("nope", -1))
t.put("fig", 99)
print(t.get("fig"), len(t))
print(t.delete("fig"), t.delete("fig"), len(t))
print(t.longest_chain())
    

cat 1 8 0.12
act 2 8 0.25
tac 3 8 0.38
apple 4 8 0.5
pear 5 8 0.62
plum 6 8 0.75
fig 7 16 0.44
kiwi 8 16 0.5
6 None -1
99 8
True False 7
2
    

Read the output as a story. The table starts with 8 buckets. Adding the seventh key pushed the load factor (keys divided by buckets) to 7/8 = 0.88, past the 0.75 limit, so the table doubled to 16 buckets and re-hashed every key, which is why the load fell back to 0.44. That re-hash is needed because the slot is hash % size: when the size changes, nearly every key belongs somewhere new. It is the same trade as the list from Data Structures in Practice 2: an occasional expensive step buys a cheap average one, which is why adding keys is amortised constant time.

Why the load factor matters

A bucket's average chain length is exactly the load factor. Keep the load factor below a fixed limit and chains stay short on average, so lookups cost a constant amount of work. Let it grow without bound and a lookup slides toward scanning a list, which is the linear cost you started the course trying to avoid.

A Bad Hash Function Ruins Everything

The table is only as good as its spreading. The next snippet hashes 2,000 distinct random six-letter words into 256 buckets with each function, and reports how many buckets were used and the longest chain. (It needs simple_hash and bad_hash from the first snippet.)

import random
random.seed(1)
words = ["".join(random.choice("abcdefghij") for _ in range(6)) for _ in range(2000)]
words = list(dict.fromkeys(words))               # drop repeats, keep order
print(len(words))

for name, fn in [("good", simple_hash), ("bad", bad_hash)]:
    counts = {}
    for w in words:
        b = fn(w) % 256                          # 256 buckets
        counts[b] = counts.get(b, 0) + 1
    print(name, len(counts), max(counts.values()))
    

2000
good 256 17
bad 44 119
    

The multiplying function used every one of the 256 buckets and its fullest bucket held 17 words, against an average of about 8. The letter-sum function used only 44 buckets and piled 119 words into one. Sums of six small letter codes all fall in a narrow band, so most buckets can never be chosen. With chains that long, a lookup is back to scanning a list: the table has the right shape but none of the speed.

Open Addressing

The second plan stores everything in the one flat list, with no inner lists. If a key's slot is taken, step to the next slot (linear probing), wrapping round at the end, until a free one is found. A lookup follows the same steps and stops at the first never-used slot, because the key cannot be any further along. This layout is friendly to memory caches and is the idea behind Python's own dict, though CPython uses a more elaborate probe order.

Deleting is the tricky part. If you simply emptied a slot, a lookup for a key that had been pushed past it would stop at the new hole and wrongly conclude the key is absent. The fix is a tombstone: mark the slot "deleted", so searches walk through it, while inserts may reuse it. Tombstones count towards how full the table is, so the code below tracks used (live plus tombstones) as well as count (live only).

EMPTY = object()                         # never used
DELETED = object()                       # used once, then removed (a tombstone)

class ProbeTable:
    def __init__(self, size=8):
        self.keys = [EMPTY] * size
        self.vals = [None] * size
        self.used = 0                    # live slots plus tombstones
        self.count = 0                   # live slots only

    def _find(self, key):
        n = len(self.keys)
        i = simple_hash(key) % n
        first_deleted = None
        for _ in range(n):
            k = self.keys[i]
            if k is EMPTY:               # the search ends at a never-used slot
                return (first_deleted if first_deleted is not None else i), False
            if k is DELETED:
                if first_deleted is None:
                    first_deleted = i    # a slot we may reuse for an insert
            elif k == key:
                return i, True
            i = (i + 1) % n              # linear probing: try the next slot
        return first_deleted, False

    def put(self, key, value):
        if (self.used + 1) / len(self.keys) > 0.6:
            self._grow()
        i, found = self._find(key)
        if not found:
            if self.keys[i] is EMPTY:
                self.used += 1
            self.count += 1
        self.keys[i] = key
        self.vals[i] = value

    def get(self, key, default=None):
        i, found = self._find(key)
        return self.vals[i] if found else default

    def delete(self, key):
        i, found = self._find(key)
        if not found:
            return False
        self.keys[i] = DELETED
        self.vals[i] = None
        self.count -= 1
        return True

    def _grow(self):
        old = list(zip(self.keys, self.vals))
        n = len(self.keys) * 2
        self.keys = [EMPTY] * n
        self.vals = [None] * n
        self.used = self.count = 0
        for k, v in old:
            if k is not EMPTY and k is not DELETED:
                self.put(k, v)
    

p = ProbeTable()
for w in ["cat", "act", "tac", "apple"]:
    i, _ = p._find(w)
    print(w, simple_hash(w) % 8, "stored at", i)
    p.put(w, 1)
print(p.delete("act"), p.get("tac"), p.get("act"), p.count, p.used)
p.put("act", 5)
print(p.get("act"), p.count, p.used)
    

cat 6 stored at 6
act 2 stored at 2
tac 6 stored at 7
apple 3 stored at 3
True 1 None 3 4
5 4 4
    

cat and tac both want slot 6; tac was pushed on to slot 7. After act was deleted, tac was still found and the live count dropped from 4 to 3, while used stayed at 4 because of the tombstone. Putting act back reused that slot, so nothing grew. Open addressing needs a lower load limit than chaining (0.6 here), because probe sequences lengthen sharply as the table fills. Exercise 3 measures that.

	Separate chaining	Open addressing
Where collided keys go	Into a list inside the bucket	The next free slot in the same flat list
Load factor	Can exceed 1; chains just lengthen	Must stay below 1; keep it well under
Deleting	Remove from the bucket's list	Needs a tombstone
Memory	Extra list object per bucket	One flat array
Weak spot	Pointer-heavy; many small lists	Clustering as the table fills

What Makes a Key Safe to Use

The whole scheme relies on a contract, the one behind the hashing rules in Data Structures in Practice 3: keys that are equal must have equal hashes, and a key's hash must never change while it is in the table. If a key could change, it would sit in a bucket its new hash no longer points to, and could never be found again. This is why lists and dicts are not allowed as keys, while numbers, strings and tuples of them are.

print(hash(5), hash(5.0), hash((1, 2)) == hash((1, 2)))

class K:
    def __init__(self, v): self.v = v
    def __eq__(self, other): return self.v == other.v
    def __hash__(self): return hash(self.v)

d = {K(1): "a"}
print(d[K(1)])                 # a different object, but equal and same hash

class Bad:
    def __eq__(self, other): return True    # defines == but no __hash__

try:
    hash(Bad())
except TypeError as e:
    print(e)
    

5 5 True
a
unhashable type: 'Bad'
    

Note that 5 and 5.0 hash alike, because they are equal and so must find the same entry. A class that defines __eq__ without __hash__ is made unhashable by Python for exactly this reason: equality was changed, so the old hash could no longer be trusted. When you define both, base the hash on exactly the fields that __eq__ compares.

Constant time is an average, not a guarantee

If many keys share a hash, every operation degrades to scanning a chain or probe run. Real tables defend against this with well-mixed hashes (and Python randomises string hashes per run so outsiders cannot craft colliding keys on purpose). The practical lesson is the one the bad hash showed: the speed of a dict comes from spreading, not from the word "hash".

What You Have Rebuilt

Idea	In your hand-built table	In real Python
Key to slot	`simple_hash(key) % size`	`hash(key)` reduced to the table size
Collisions	Chains, or probing to the next slot	Probing (a more elaborate sequence)
Growth	Double and re-hash at a set load factor	Resizes automatically as it fills
Deletion	Remove from a chain, or a tombstone	A similar dummy-marker idea
Key rules	Equal keys, equal hashes; no mutation	Exactly the same, enforced by `__hash__`

You would never use a hand-built table in production Python: the built-in is written in C and heavily tuned. The value is understanding what it costs and why, which tells you when a dict is the right tool, why a list of keys is not, and what to look at when a lookup is unexpectedly slow.

Challenges

Exercise 1

Build a HashSet class using separate chaining and the chapter's simple_hash. Give it add (returning True if the item was new, False if already present), in support, remove (raising KeyError if absent), len and iteration. Start with 4 buckets and double whenever the item count exceeds twice the bucket count. Test duplicates, growth past the limit, removal, and removing a missing item.

📄 View solution

Exercise 2

Make a chained table behave like a real dict by writing a MyDict class with d[key] = value, d[key] (raising KeyError when missing), del d[key], in, len, get, items and iteration over keys. Then use it to count the words in a sentence, and confirm your counts equal those from a real dict doing the same job.

📄 View solution

Exercise 3

Write a small open-addressing set of keys with linear probing in a fixed 16-slot table, with a switch that chooses between tombstones and simply emptying a slot on removal. First add several keys that share a starting slot, remove the first, and show that the naive version loses a key that is still present while the tombstone version does not. Then, in a 32-slot table, add 8, 16, 24 and 28 keys and print the load factor, the longest probe run and the average probe count to find each key, to see how probing cost grows as the table fills.

📄 View solution

Quick Reference

Hash table: a list of slots plus a hash function; slot = hash(key) % size
Good hash: deterministic, fast, and spreads keys evenly over all slots
Collision: two keys, one slot; unavoidable, so every table needs a plan
Chaining: each bucket holds a short list of pairs
Open addressing: one flat list; on a collision probe the next slot; delete with tombstones
Load factor: keys divided by slots; keep it under a limit by doubling and re-hashing
Amortised: an occasional full re-hash is repaid by many cheap inserts
Key contract: equal keys have equal hashes, and a key's hash never changes inside a table
Weakness: a poor hash turns lookups back into list scans

Coming next

Data Structures in Practice 10 is the capstone: a decision guide for choosing a structure, and three worked case studies that use what the whole course has built.