Collision Handling in Hash Tables

AQA 4.2.9 — Collision handling

Retrieval: the previous lesson's own coding challenge showed data silently lost — "bee" overwrote "dog" because both hashed to the same bucket. This lesson fixes that properly.

Key vocabulary

• Collision — when two different keys hash to the same bucket index.
• Separate chaining — a collision-handling strategy where each bucket holds a list of items rather than a single item; a collision simply appends to that list.
• Load factor — the ratio of items stored to the number of buckets available (n / size).

Understand — collisions are inevitable, not a design flaw

A hash function maps a potentially unlimited number of possible keys onto a fixed number of buckets. Once the number of distinct keys stored exceeds the number of buckets, at least two keys must share a bucket eventually — this is the same reasoning as the pigeonhole principle (more pigeons than holes means some hole gets more than one). In practice, collisions happen far sooner than that, purely from how the hash function happens to distribute real keys. A hash table implementation that doesn't plan for collisions isn't handling an edge case — it's ignoring a certainty.

See it — separate chaining

class HashTable:
    def __init__(self, size):
        self.size = size
        self.buckets = [[] for _ in range(size)]   # each bucket is now a list

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

    def put(self, key, value):
        index = self._hash(key)
        for i, (k, v) in enumerate(self.buckets[index]):
            if k == key:
                self.buckets[index][i] = (key, value)   # update existing key
                return
        self.buckets[index].append((key, value))          # new key: append

    def get(self, key):
        index = self._hash(key)
        for k, v in self.buckets[index]:
            if k == key:
                return v
        return None

Trace it — cat, dog, bee, then get("bee")

put("cat", 5): index 4, buckets[4] is empty, so buckets[4] becomes [("cat", 5)]. put("dog", 3): index 6, buckets[6] is empty, so buckets[6] becomes [("dog", 3)]. put("bee", 9): index 6 again — but this time, instead of overwriting, the loop scans buckets[6] for a matching key, finds none, and appends: buckets[6] becomes [("dog", 3), ("bee", 9)]. Now get("bee"): index 6, scans the chain — skips ("dog", 3) (key doesn't match), finds ("bee", 9), returns 9. Both keys survive the collision.

Understand — the alternative: open addressing

Linear probing is a different strategy: keep one item per bucket, but if the computed bucket is already occupied, check the next bucket instead (wrapping around if necessary), continuing until an empty slot is found. Chaining is generally simpler to implement and copes more gracefully with a high load factor; probing avoids the extra list overhead per bucket but degrades badly as the table fills up, since a long run of occupied buckets forces an increasingly long search even for keys that never collided directly.

Debug it — diagnose, explain, fix, test, justify (missing/incorrect collision handling)

class HashTable:
    def __init__(self, size):
        self.size = size
        self.buckets = [[] for _ in range(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)]

ht = HashTable(7)
ht.put("dog", 3)
ht.put("bee", 9)
print(ht.buckets[6])

This prints [('bee', 9)] — "dog"'s data is still lost, even though the buckets are now lists.

1. Diagnose: is self.buckets[index] = [(key, value)] genuinely adding to the existing chain, or replacing it entirely?
2. Explain: does simply making each bucket a list automatically give you chaining behaviour?
3. Fix: correct put so it appends to the existing chain instead of replacing it.
4. Test: confirm buckets[6] now contains both ("dog", 3) and ("bee", 9) after both insertions.
5. Justify: explain why changing the bucket type to a list isn't, by itself, enough to fix the collision problem.

(Assigning a brand-new single-item list to buckets[index] discards whatever list was already there - it's still an overwrite, just of a list instead of a tuple. The fix is self.buckets[index].append((key, value)). Using a list as the bucket type is necessary for chaining but not sufficient on its own - the insertion logic itself must be written to genuinely append to the existing list, not replace it.)

Analyse — performance with chaining, and load factor

Average-case lookup stays close to O(1) as long as the load factor (n / size) stays low and the hash function distributes keys reasonably evenly, keeping each chain short. Worst case is O(n) if every key collided into a single bucket (a poor hash function, or a determined adversary), degrading that one chain into a plain list requiring a full linear scan. This is precisely why real hash table implementations — including Python's own dict — automatically resize (rehash everything into a larger table) once the load factor crosses a threshold, keeping average performance close to O(1) even as more items are added.

Compare, select, justify

A cybersecurity system needs to store and check thousands of banned IP addresses, expecting extremely fast lookups even as the list grows over time. Would a hash table or a BST be more appropriate? Justify your answer, referring to both structures' typical-case performance.

(A hash table. Average O(1) lookup beats a BST's average O(log n) for a use case where raw lookup speed matters most and the data never needs to be retrieved in sorted order or by range. A BST would only be preferable here if the system also needed banned IPs in sorted order or needed to find IPs within a range - capabilities a hash table cannot provide at all.)

Common mistake

Assuming that once a bucket becomes a list (chaining), performance no longer depends on how full the table is. As the Analyse section shows, a high load factor still degrades performance towards O(n) per chain, regardless of the collision strategy used.

Why this matters for the NEA

Many NEA projects need fast lookup by a unique key — a student ID, a product code. Recognising that Python's own dict is already a professionally-implemented hash table with proper collision handling means an NEA project rarely needs to hand-build one — but understanding why dict lookups are fast, and when a hash table genuinely is or isn't the right structure, is exactly the design justification AQA's marking criteria reward.

Check your understanding

Two students design hash tables of size 10. Student A's hash function is hash(key) = 7 for every key. Student B's hash function is hash(key) = ord(key[0]) % 10. (a) Identify which student's hash table will suffer the most collisions, and explain why. (b) Suggest one genuine improvement to Student B's hash function. (4 marks)

((a) Student A - their function ignores the key entirely and always returns the same fixed value, so EVERY key collides into bucket 7, making the table effectively one long chain (the worst possible case). Student B's function at least varies by the key's first character, spreading keys across multiple buckets, though still crudely. (b) Use more of the key's content in the calculation - for example summing ord() across every character, as used throughout this lesson - rather than just the first character, spreading keys more evenly.)

Challenge

Extend the HashTable class with a method remove(key) that correctly removes a key from its chain without disturbing any other keys sharing the same bucket.

Looking ahead: the final lesson of this sequence brings graphs, trees, BSTs and hash tables together — comparing them directly and practising selecting the right one for an unfamiliar scenario.