Handling Hash Collisions

A hash table maps keys to array slots using a hash function, but no hash function is perfect: sooner or later two different keys will land on the same slot. This is a collision, and how a hash table handles it determines whether lookups stay fast or silently degrade to a linear scan. This lesson covers the two major collision-resolution families — separate chaining and open addressing — how to implement each from scratch, their complexity tradeoffs, and the mistakes that trip people up when building or reasoning about hash tables.

Overview: Why Collisions Are Inevitable

A hash table stores n keys in an underlying array of m slots (often called buckets). The hash function converts a key into an index in the range [0, m - 1]. By the pigeonhole principle, if n > m a collision is guaranteed — but collisions actually show up far earlier than that. This is the same math behind the "birthday paradox": with just 23 people in a room there’s better than even odds two share a birthday, out of 365 possible days. A hash table behaves the same way — even with relatively few keys compared to the number of slots, collisions are common, not rare.

Imagine a tiny hash table with 5 buckets storing animal names. If both "cat" and "bird" happen to hash to bucket 2, the table needs a strategy to store both without simply overwriting one. There are two main families of strategies:

Separate Chaining

Each bucket holds a small collection (usually a list, sometimes a linked list or balanced tree) of every key that hashes to it. A collision just means appending to that bucket’s list. Lookup hashes the key to find the right bucket, then scans that bucket’s (hopefully short) list for a match.

Open Addressing

There is no per-bucket collection — every key lives directly in the underlying array, one key per slot. When the target slot is already occupied, the algorithm probes for another slot using a deterministic sequence: linear probing (try the next slot, then the next, wrapping around), quadratic probing (try slots at increasing squared offsets to reduce clustering), or double hashing (use a second hash function to compute the step size, which spreads collisions out much more evenly).

A critical number here is the load factor, α = n / m — how full the table is. Separate chaining degrades gracefully even when α > 1 (buckets just get longer lists). Open addressing has no such luxury: once every slot is full, there is nowhere left to probe, so implementations must keep α below a threshold (commonly 0.7) and resize and rehash into a bigger array before that point.

Why Python’s hash() is randomized for strings

If you tried these examples using Python’s built-in hash() on strings, you’d get different, non-deterministic output on every run. That’s intentional: CPython randomizes the string hash seed per process (PYTHONHASHSEED) specifically to prevent "hash-flooding" denial-of-service attacks, where an attacker crafts many keys that all collide on purpose to force a hash table into worst-case O(n) behavior. Because deterministic, reproducible output matters for learning, every example below uses a small custom hash function instead of the built-in hash(). In real production code, you’d simply use Python’s dict or set, which already implement open addressing with this randomization built in.

Time and Space Complexity

Strategy Average Insert / Search / Delete Worst Case Extra Space
Separate Chaining O(1) O(n) (all keys hash to one bucket) O(n + m)
Linear Probing O(1) O(n) O(m)
Quadratic Probing O(1) O(n) O(m)
Double Hashing O(1) O(n) O(m)

Here n is the number of stored keys and m is the number of buckets/slots. The average case is O(1) because a good hash function distributes keys roughly evenly, so each bucket holds only a small constant number of entries (chaining) or a probe sequence only needs a few steps before finding an open slot (open addressing). The worst case is O(n) because a poor hash function (or an adversarial one) can send every key to the same bucket or the same starting probe index, degenerating the whole table into a single linked list or a single long probe chain that must be scanned linearly. Space is O(n + m) for chaining because you need the array of buckets plus storage for every key across all the lists; open addressing needs only O(m) because keys live directly inside the fixed-size array with no auxiliary list nodes.

Examples

Example 1: Separate Chaining From Scratch

This builds a 5-bucket table and deliberately picks words whose custom hash values collide, so you can see chaining resolve it.

class HashTableChaining:
    def __init__(self, size: int = 5) -> None:
        self.size = size
        self.buckets: list[list[tuple[str, int]]] = [[] for _ in range(size)]

    def _hash(self, key: str) -> int:
        total = sum(ord(ch) for ch in key)
        return total % self.size

    def put(self, key: str, value: int) -> None:
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (existing_key, _) in enumerate(bucket):
            if existing_key == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key: str) -> int | None:
        index = self._hash(key)
        bucket = self.buckets[index]
        for existing_key, existing_value in bucket:
            if existing_key == key:
                return existing_value
        return None


table = HashTableChaining(size=5)
animals = [('cat', 1), ('dog', 2), ('bird', 3), ('ant', 4), ('bat', 5)]
for name, count in animals:
    table.put(name, count)

for index, bucket in enumerate(table.buckets):
    print(f'Bucket {index}: {bucket}')

print(table.get('bird'))
print(table.get('fox'))

Output:

Bucket 0: []
Bucket 1: [('bat', 5)]
Bucket 2: [('cat', 1), ('bird', 3)]
Bucket 3: [('ant', 4)]
Bucket 4: [('dog', 2)]
3
None

Summing character codes, 'cat' hashes to bucket 2 and 'bird' also hashes to bucket 2 — a real collision. Because the table uses chaining, both simply live together as a list [('cat', 1), ('bird', 3)] in bucket 2 instead of one overwriting the other. get('bird') hashes to bucket 2, then scans that short list until it finds the matching key and returns 3. get('fox') hashes to bucket 3 (where 'ant' lives), scans it, finds no match, and returns None.

Example 2: Open Addressing With Linear Probing

This example uses integer keys that are deliberately chosen to all hash to the same starting bucket, to make the probing (and the resulting clustering) obvious.

class HashTableLinearProbing:
    def __init__(self, size: int = 7) -> None:
        self.size = size
        self.keys: list[int | None] = [None] * size
        self.slots: list[int | None] = [None] * size

    def _hash(self, key: int) -> int:
        return key % self.size

    def put(self, key: int, value: int) -> None:
        index = self._hash(key)
        for step in range(self.size):
            probe_index = (index + step) % self.size
            if self.keys[probe_index] is None or self.keys[probe_index] == key:
                self.keys[probe_index] = key
                self.slots[probe_index] = value
                return
        raise RuntimeError('Hash table is full')

    def get(self, key: int) -> int | None:
        index = self._hash(key)
        for step in range(self.size):
            probe_index = (index + step) % self.size
            if self.keys[probe_index] == key:
                return self.slots[probe_index]
            if self.keys[probe_index] is None:
                return None
        return None


table = HashTableLinearProbing(size=7)
for number in [10, 3, 17, 24, 31]:
    table.put(number, number * 100)

for index in range(table.size):
    print(f'Slot {index}: key={table.keys[index]}, value={table.slots[index]}')

print(table.get(17))
print(table.get(99))

Output:

Slot 0: key=31, value=3100
Slot 1: key=None, value=None
Slot 2: key=None, value=None
Slot 3: key=10, value=1000
Slot 4: key=3, value=300
Slot 5: key=17, value=1700
Slot 6: key=24, value=2400
1700
None

With size=7, every one of 10, 3, 17, 24, 31 satisfies key % 7 == 3 — they all collide on the very first probe. Linear probing resolves each collision by walking forward one slot at a time: 10 claims slot 3, 3 gets bumped to slot 4, 17 to slot 5, 24 to slot 6, and 31 wraps around the array end to slot 0. This back-to-back pileup is called primary clustering — a well-known weakness of linear probing, since once a run of occupied slots forms, any new key hashing anywhere into that run makes the run even longer.

Example 3: Measuring How Table Size Affects Collisions

A more realistic question: how much does bucket count actually matter? This counts collisions for the same 8 words at two different table sizes.

def simple_hash(key: str, size: int) -> int:
    return sum(ord(ch) for ch in key) % size


def count_collisions(keys: list[str], size: int) -> int:
    buckets: list[list[str]] = [[] for _ in range(size)]
    collisions = 0
    for key in keys:
        index = simple_hash(key, size)
        if buckets[index]:
            collisions += 1
        buckets[index].append(key)
    return collisions


words = ['cat', 'dog', 'bird', 'ant', 'bat', 'fox', 'owl', 'cow']
small_table_collisions = count_collisions(words, size=5)
large_table_collisions = count_collisions(words, size=101)

print(f'Collisions with 5 buckets: {small_table_collisions}')
print(f'Collisions with 101 buckets: {large_table_collisions}')

Output:

Collisions with 5 buckets: 4
Collisions with 101 buckets: 0

With only 5 buckets, 4 of the 8 words collide with something already in their bucket. Spreading the same 8 words across 101 buckets (a size deliberately chosen as prime, which tends to distribute sums-of-character-codes more evenly) produces zero collisions. This is exactly why real hash table implementations grow (resize) as they fill up — more buckets relative to the number of keys means a lower load factor and fewer collisions.

How It Works Step by Step

Trace the linear-probing insert of 17 from Example 2, assuming 10 and 3 were already inserted (occupying slots 3 and 4):

  1. index = 17 % 7 = 3 — the search always starts at the home slot.
  2. step = 0: probe_index = (3 + 0) % 7 = 3. keys[3] is 10, which is occupied and not equal to 17, so keep probing.
  3. step = 1: probe_index = (3 + 1) % 7 = 4. keys[4] is 3, occupied and not a match, keep probing.
  4. step = 2: probe_index = (3 + 2) % 7 = 5. keys[5] is None — an empty slot. Insert 17 here and stop.

Deletion in open addressing needs the same care in reverse. If you delete 10 from slot 3 by simply setting it back to None, a later get(17) would stop at slot 3 (now empty) and incorrectly report 17 as missing, even though it’s sitting in slot 5. The standard fix is a tombstone: mark the deleted slot with a special "deleted" sentinel (distinct from an original, never-used empty slot) so get keeps probing past it, while put is still allowed to reuse it for a new key.

Common Mistakes

Mistake 1: An Unbounded Probe Loop

It’s tempting to write the probing loop as a plain while loop that stops when it finds an empty slot:

def put(self, key, value):
    index = self._hash(key)
    while self.keys[index] is not None and self.keys[index] != key:
        index = (index + 1) % self.size
    self.keys[index] = key
    self.slots[index] = value

This works fine right up until the table is full. If every slot is occupied by a different key, the loop condition never becomes false — it just keeps wrapping around the array forever, hanging the program. The fix is to bound the number of probe attempts to self.size (one full pass over the array), and treat exhausting that many attempts as "the table is full" rather than looping indefinitely:

def put(self, key, value):
    index = self._hash(key)
    for step in range(self.size):
        probe_index = (index + step) % self.size
        if self.keys[probe_index] is None or self.keys[probe_index] == key:
            self.keys[probe_index] = key
            self.slots[probe_index] = value
            return
    raise RuntimeError('Hash table is full')

Mistake 2: A Mutable Default Argument for the Table

A subtler bug shows up when a helper function that builds a table tries to give itself a "default" empty dictionary:

def build_table_from_pairs(pairs, table={}):
    for key, value in pairs:
        table[key] = value
    return table


first = build_table_from_pairs([('a', 1)])
second = build_table_from_pairs([('b', 2)])
print(second)

Output:

{'a': 1, 'b': 2}

The default value table={} is created exactly once, when the function is defined — not once per call. Every call that doesn’t pass its own table argument shares and mutates that same dictionary, so the second call unexpectedly inherits 'a' from the first. The fix is the standard Python idiom: default to None and create a fresh dictionary inside the function body.

def build_table_from_pairs(
    pairs: list[tuple[str, int]],
    table: dict[str, int] | None = None,
) -> dict[str, int]:
    if table is None:
        table = {}
    for key, value in pairs:
        table[key] = value
    return table


first = build_table_from_pairs([('a', 1)])
second = build_table_from_pairs([('b', 2)])
print(second)

Output:

{'b': 2}

Best Practices

  • In real Python code, use the built-in dict or set — they implement a highly tuned open-addressing scheme (with randomized string hashing and automatic resizing) that will outperform anything you hand-roll. Build your own table only to learn the internals.
  • Pick a table size that is a prime number where practical; it tends to spread out sums or multiples in a hash function more evenly and reduces patterns of clustering.
  • Track the load factor (n / m) and resize (typically doubling the array and rehashing every existing key into it) before it crosses a threshold like 0.7 for open addressing.
  • Prefer separate chaining when the number of keys is unpredictable or could exceed the table size, since it degrades gracefully instead of running out of room.
  • Prefer open addressing when memory locality matters and you can bound the load factor, since keys live in one contiguous array with no extra list-node overhead.
  • Always use a tombstone marker for deletions in open addressing — never reset a deleted slot to a plain empty value, or you’ll break the probe chain for keys that were pushed past it.
  • Never build an unbounded probing while loop; always cap probe attempts at the table size so a full table raises an error instead of hanging.
  • Avoid mutable default arguments (like table={}) on any function that builds or accumulates into a hash table — default to None and initialize inside the function.

Practice Exercises

  • Extend HashTableLinearProbing from Example 2 with a delete(key) method that uses a tombstone sentinel (distinct from None) instead of resetting the slot to None, so that get() still finds later-inserted keys that collided past the deleted one. Verify by deleting 10 and then confirming get(17) still returns 1700.
  • Using separate chaining with 7 buckets and hash(key) = key % 7, insert 14, 21, 5, 28, 12 in that order and predict the contents of every bucket by hand before running code to check yourself. (Hint: more than one key ends up sharing a bucket.)
  • Write a function load_factor(n: int, m: int) -> float that returns n / m, then write a second function that prints a warning if the load factor of a table you’re building exceeds 0.7. In a sentence or two, explain why this threshold matters for open addressing but is far less urgent for chaining.

Summary

  • Collisions are unavoidable: with m buckets and n keys, collisions become likely well before n reaches m, by the same math as the birthday paradox.
  • Separate chaining stores colliding keys together in a list per bucket; it tolerates a load factor above 1 and degrades gracefully.
  • Open addressing (linear probing, quadratic probing, double hashing) stores every key directly in the array and probes for the next open slot on a collision; it requires the load factor to stay below 1 and needs periodic resizing.
  • Average-case time for insert/search/delete is O(1) for both families given a good hash function; worst case is O(n) when a poor hash function funnels many keys into one bucket or one probe run.
  • Space is O(n + m) for chaining versus O(m) for open addressing.
  • Deletion in open addressing needs a tombstone marker, not a plain empty slot, or later lookups can incorrectly report a still-present key as missing.
  • Python’s dict/set already solve all of this internally (with randomized hashing to resist collision-flooding attacks) — reach for them in real code, and build your own table only to understand what’s happening underneath.