Collisions: Chaining vs Open Addressing

"Collisions aren't a bug to prevent — they're a certainty to manage. There are more possible keys than slots, so two keys WILL land together. The only question is what you do when they do."

Collisions Are Guaranteed

A table has a fixed number of slots, but the universe of possible keys is effectively infinite. By the pigeonhole principle, two different keys must eventually hash to the same slot. So a hash map's design isn't about avoiding collisions (impossible) — it's about resolving them gracefully. There are two classic strategies, and they make opposite trade-offs.

Chaining: a Little List in Each Slot

Separate chaining makes each slot hold a small list (a "chain") of all the keys that hashed there. To insert, append to the slot's list; to look up, hash to the slot and scan its short list. As long as the lists stay short (good hash + low load), lookups are O(1). Chaining is simple, degrades gracefully under high load (the lists just get a bit longer), and is forgiving of a mediocre hash function. The cost: extra memory for the list/pointers, and the cache-unfriendliness of those scattered list nodes.

Open Addressing: Everybody Lives in the Array

Open addressing stores every entry directly in the table array — no side lists. On a collision, it probes for the next free slot by a fixed rule: linear probing checks slot+1, slot+2, …; quadratic probing jumps by growing gaps; double hashing uses a second hash for the step. Lookups follow the same probe sequence until they find the key or an empty slot. Open addressing is cache-friendly (everything's contiguous, no pointer-chasing) and uses less memory — but it degrades sharply as the table fills (probe sequences get long, a problem called clustering), and deletion is fiddly: you can't just empty a slot or you'd break probe chains, so you mark it with a "tombstone."

Collisions are inevitable; you resolve them. Chaining keeps a list per slot (simple, tolerates high load). Open addressing probes for another slot in the array itself (cache-friendly, low memory, but degrades fast when full). Same goal, opposite trade-offs.

What Python Actually Does

CPython's dict and set use open addressing with a clever perturbation-based probe sequence, kept fast by keeping the table at most about two-thirds full (we'll see why in the load-factor lesson). So when you use a Python dict — which is constantly — you're using open addressing with tombstone deletion under the hood. You don't have to implement it, but knowing it explains the dict's behavior: why it resizes, why it's cache-fast, and why insertion order is preserved (a separate compact-array trick layered on top).

Pippa's Confession

I implemented my first hash map with chaining because it was easier to reason about — and it worked fine. When Dad asked why Python uses open addressing instead, I had no answer. The reason turned out to be cache locality: open addressing keeps everything in one contiguous array, so probing stays in fast cache, while chaining chases pointers to scattered nodes. It was the Linked-Lists-vs-arrays cache lesson again, resurfacing one layer deeper. The same truths keep echoing up the stack.

Code

Open addressing with linear probing·python

# Open addressing with LINEAR PROBING: on collision, try the next slot.
class OpenAddrMap:
    def __init__(self, size=8):
        self.size = size
        self.slots = [None] * size      # store (key, value) right in the array

    def put(self, key, value):
        i = hash(key) % self.size
        while self.slots[i] is not None and self.slots[i][0] != key:
            i = (i + 1) % self.size     # collision -> probe the next slot
        self.slots[i] = (key, value)

    def get(self, key):
        i = hash(key) % self.size
        while self.slots[i] is not None:
            if self.slots[i][0] == key:
                return self.slots[i][1]
            i = (i + 1) % self.size     # follow the SAME probe path used on insert
        raise KeyError(key)

m = OpenAddrMap()
m.put("a", 1); m.put("b", 2); m.put("c", 3)
print(m.get("a"), m.get("b"), m.get("c"))
# If 'a' and 'c' hash to the same slot, 'c' probes forward to the next free one;
# get('c') replays that same forward probe to find it. No side lists involved.

Exercise

A table of size 5 uses linear probing. You insert keys with hashes 3, 8, 13 in that order (all ≡ 3 mod 5). Which slot does each end up in? Then explain why, with open addressing, you cannot delete a key by simply setting its slot to None — and what a 'tombstone' fixes.

Hint

All three want slot 3: first → slot 3, second probes to 4, third probes to 0 (wraps). Emptying a middle slot would make a later probe stop early and 'lose' keys past the gap; a tombstone marks 'deleted but keep probing past me.'

Collisions Are Guaranteed

Chaining: a Little List in Each Slot

Open Addressing: Everybody Lives in the Array

What Python Actually Does

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0