Hash Tables and Hashing

AQA 4.2.9 — Hash tables and hashing

Retrieval: the previous lesson's BST search achieves O(log n) average performance by comparing the target against nodes to eliminate half the possibilities each time. A hash table aims for O(1) average performance using a completely different strategy — computing directly where a key belongs, with no comparisons at all. This also genuinely retrieves something you've used since Year 12 without seeing how it works: every time you've used a Python dict, you've been using a hash table underneath — this lesson opens it up.

Key vocabulary

• Key — the value used to look an item up (e.g. a name, an ID).
• Hash function — a function that deterministically converts a key into a number (its hash value).
• Bucket / index — the specific slot within the table where a key's data is actually stored, found by reducing the hash value into a valid range (typically via modulo).
• Table size — the fixed number of buckets available.

Understand — the hashing mechanism, precisely

A hash function takes a key of any type or size and produces a number. That number, on its own, could be far larger than the table — so it's reduced using % table_size into a genuinely valid bucket index. Crucially, the same key must always produce the same index (determinism), which is what lets a hash table jump directly to a key's data rather than searching for it.

See it — a simple hash function, worked

def simple_hash(key, table_size):
    total = sum(ord(char) for char in key)
    return total % table_size

print(simple_hash("cat", 7))

Working it through: ord('c') = 99, ord('a') = 97, ord('t') = 116; total = 312; 312 % 7 = 4. So "cat" hashes to index 4 in a table of size 7.

Repeating this for a few more keys in the same size-7 table: "dog" → total 314 → index 6. "ant" → total 323 → index 1. "bee" → total 300 → index 6 — the same index as "dog".

See it — Python's own dict is a hash table

This is precisely why a Python dictionary's lookups average O(1) regardless of how many items it holds, and precisely why dictionary keys must be hashable (immutable) — a mutable key could change after being hashed and stored, leaving it in the wrong bucket forever, silently breaking every future lookup for it.

See it — a basic hash table implementation

class HashTable:
    def __init__(self, size):
        self.size = size
        self.buckets = [None] * size

    def _hash(self, key):
        return sum(ord(char) for char in key) % self.size

    def put(self, key, value):
        index = self._hash(key)
        self.buckets[index] = (key, value)

    def get(self, key):
        index = self._hash(key)
        if self.buckets[index] is not None and self.buckets[index][0] == key:
            return self.buckets[index][1]
        return None

Trace it — put, then put again

put("cat", 5) computes index 4, stores ("cat", 5) at buckets[4]. put("dog", 3) computes index 6, stores ("dog", 3) at buckets[6]. Now put("bee", 9) also computes index 6 (from "See it" above) — and simply overwrites buckets[6] with ("bee", 9). Calling get("dog") afterwards computes index 6 again, finds ("bee", 9) there instead, sees the stored key doesn't match "dog", and returns None — "dog"'s data has been silently lost.

Debug it — diagnose, explain, fix, test, justify (indexing error)

class HashTable:
    def __init__(self, size):
        self.size = size
        self.buckets = [None] * size

    def _hash(self, key):
        return sum(ord(char) for char in key)

    def put(self, key, value):
        index = self._hash(key)
        self.buckets[index] = (key, value)

ht = HashTable(7)
ht.put("hello", 1)

This crashes with IndexError: list assignment index out of range.

1. Diagnose: what is the actual range of values sum(ord(char) for char in key) can produce, compared to the table's real size?
2. Explain: without the modulo step, is the "index" ever guaranteed to be a valid position in a 7-slot list?
3. Fix: correct _hash so it always returns a value within the table's bounds.
4. Test: confirm put("hello", 1) now succeeds without error.
5. Justify: explain why the modulo operation isn't just a formatting detail — what does it actually convert the raw hash value into?

(Without % self.size, the raw sum of character codes can be any size at all, far exceeding a 7-slot list's valid indices (0-6). The fix restores % self.size. Modulo is what converts an unbounded hash value into a genuinely valid bucket index - it's the entire mechanism that makes a fixed-size table work for keys of any length.)

Common mistake

Assuming a hash table stores or iterates keys in any human-meaningful order. The bucket index is essentially arbitrary from a human perspective, determined purely by the hash function — unlike a BST's in-order traversal, walking a hash table's buckets in index order does not give you keys in alphabetical, numerical, or insertion order.

Analyse — why lookup averages O(1)

Computing a hash and jumping directly to that bucket takes constant time, regardless of how many items the table holds — a fundamentally different guarantee from a BST or sorted array, both of which must perform some number of comparisons that grows with the amount of data stored.

Check your understanding

A programmer uses the hash function hash(key) = len(key) % 5 for a table of size 5. Explain why this is a poor choice of hash function, giving a specific example of two different keys that would cause a problem. (3 marks)

(This hash function depends only on the LENGTH of the key, so any two keys of the same length - for example "cat" and "dog", both length 3 - always hash to exactly the same index, causing far more collisions than necessary. A good hash function should use more of the key's actual content (such as every character's code, as used in this lesson), not a single coarse property like length alone.)

Challenge

Using simple_hash above and a table of size 5, compute the bucket index for the keys "red", "green" and "blue". State which (if any) collide.

Looking ahead: this lesson's own worked example showed "bee" silently overwriting "dog"'s data. The next lesson fixes that properly — handling collisions instead of ignoring them.