Hash Collisions Explained: When a Hash Table Degrades to O(n)

"Hash map lookup is O(1)" is the first thing everyone learns about hash tables and the first thing an interviewer will push on. It is true on average, under assumptions about the hash function and the load factor. Break either assumption and every lookup becomes a walk through a list. Knowing when that happens is the difference between using a hash map and understanding one.

The problem it solves

A hash table maps a key to a bucket with hash(key) % buckets. Different keys can land in the same bucket: that is a collision, and it is not an error. With more possible keys than buckets, collisions are guaranteed, so every hash table has a strategy for them:

• Separate chaining: each bucket holds a small list of entries. A lookup jumps to the bucket, then compares keys along its chain.
• Open addressing: all entries live in one array. A collision probes other slots in a fixed sequence until it finds the key or an empty slot. CPython's dict works this way.

Either way, the cost of a lookup is one hash plus the number of keys compared in that bucket or probe sequence. The table is fast exactly as long as that number stays small.

The intuition

Two things keep chains short.

A hash that spreads keys evenly. If keys land in buckets roughly at random, the expected chain length is the load factor, entries / buckets. Tables resize, typically doubling, when the load factor passes a threshold such as 0.75, so the average stays bounded by a constant. That constant is where O(1) comes from.

Keys that never change. An entry is filed under the bucket its hash pointed to when it was inserted. If the key later changes and hashes differently, lookups go to a different bucket and never find it, while the entry still sits in the table. That is why hashable types are the immutable ones: strings, numbers, tuples of hashables. A list can change after insertion, so Python refuses to hash it.

When the first condition fails, nothing crashes; the table silently slows down. A hash that looks at only part of the key, such as its length or first letter, sends similar keys to the same bucket, and resizing does not help, because keys with the same hash value share a bucket at every table size. With n keys in one bucket, a lookup compares up to n keys: O(n). It can also be forced: if an attacker can predict the hash, they can send many keys that collide, a denial-of-service technique called hash flooding. Python randomises string hashing per process, controlled by PYTHONHASHSEED, largely as a defence against it.

Watch it run

The animation uses the lesson's crowding hash, len(key) % n, over six bins. It is cheap to compute, and every name here is three letters long. ana, bob, cal and dee each go to bucket 3, like everyone before them; five bins stay empty while one grows a chain. Then comes the lookup for dee: bucket 3 is one jump, but then the chain has to be walked, and ana, bob and cal are each not it. It is found after 4 key comparisons, and the table has quietly degraded into a list scan. Swap in a hash that actually reads the key and the four names spread across four bins; only the function changed. Now dee is one probe. O(1) was never a promise, it is an average that a crowding hash destroys. The last frame adds the other rule: a key must keep hashing to the same bin for life, which is why a list cannot be a key and a tuple can.

The code

A chained table with a pluggable hash, resizing at a 0.75 load factor and counting key comparisons. Both hashes are deterministic, so the output does not depend on the hash seed. A thousand six-character names go in, then each is looked up:

class ChainedTable:
    """Separate chaining with a pluggable hash; counts key comparisons."""
    def __init__(self, hash_fn, buckets=8):
        self.hash_fn = hash_fn
        self.buckets = [[] for _ in range(buckets)]
        self.size = 0
        self.comparisons = 0

    def _chain(self, key):
        return self.buckets[self.hash_fn(key) % len(self.buckets)]

    def put(self, key, value):
        chain = self._chain(key)
        for pair in chain:
            self.comparisons += 1
            if pair[0] == key:
                pair[1] = value
                return
        chain.append([key, value])
        self.size += 1
        if self.size > 0.75 * len(self.buckets):   # keep the load factor bounded
            self._resize(2 * len(self.buckets))

    def get(self, key):
        for k, v in self._chain(key):
            self.comparisons += 1
            if k == key:
                return v
        raise KeyError(key)

    def _resize(self, n):
        old = [pair for chain in self.buckets for pair in chain]
        self.buckets = [[] for _ in range(n)]
        for k, v in old:
            self._chain(k).append([k, v])

def by_length(key):
    return len(key)                               # the lesson's crowding hash

def fnv1a(key):
    h = 2166136261                                # reads every byte of the key
    for byte in key.encode():
        h = ((h ^ byte) * 16777619) % 2**32
    return h

names = ["%s%03d" % (p, i) for p in ("ana", "bob", "cal", "dee") for i in range(250)]
for fn in (by_length, fnv1a):
    t = ChainedTable(fn)
    for n in names:
        t.put(n, True)
    t.comparisons = 0
    for n in names:
        t.get(n)
    longest = max(len(c) for c in t.buckets)
    print(fn.__name__, len(t.buckets), longest, round(t.comparisons / len(names), 1))
# by_length 2048 1000 500.5
# fnv1a 2048 4 1.2

Both tables grew to 2,048 buckets, and resizing did nothing for the crowding hash: one chain of 1,000 entries and an average of 500.5 comparisons per lookup, against 1.2 for a hash that reads every byte. The mutable-key failure needs no bad hash at all, only a key that changes after insertion:

class Seat:
    def __init__(self, row, col):
        self.row, self.col = row, col
    def __eq__(self, other):
        return (self.row, self.col) == (other.row, other.col)
    def __hash__(self):
        return hash((self.row, self.col))         # hash depends on mutable fields

s = Seat(3, 7)
booked = {s: "ana"}
s.row = 4                                         # mutated while inside the dict
print(s in booked, Seat(3, 7) in booked, len(booked))   # False False 1

The entry is still in the dictionary, and neither the mutated object nor a fresh Seat(3, 7) can reach it. Checked on 300 seeded random workloads of inserts, overwrites and lookups, with both hashes and starting sizes as small as one bucket, against Python's dict as the reference:

import random

random.seed(27)
ok = True
for _ in range(300):
    fn = random.choice([by_length, fnv1a])
    t, ref = ChainedTable(fn, buckets=random.choice([1, 2, 8])), {}
    for _ in range(random.randint(0, 200)):
        key = "".join(random.choice("abc") for _ in range(random.randint(0, 5)))
        if random.random() < 0.6:
            value = random.randint(0, 9)
            t.put(key, value)
            ref[key] = value
        else:
            try:
                got = t.get(key)
            except KeyError:
                got = "missing"
            ok &= got == ref.get(key, "missing")
    ok &= t.size == len(ref) == sum(len(c) for c in t.buckets)
print(ok)                                         # True

The crowding hash is slow, not wrong, which is why it goes unnoticed.

The complexity

• Average lookup, insert, delete: O(1) with a well-spread hash and a bounded load factor. The Big-O cheat sheet lists it as O(1) average and O(n) worst for this reason.
• Worst case: O(n) when all keys share one bucket or probe sequence.
• Resize: O(n) for the rehash, amortised to O(1) per insert because the size doubles.
• Space: O(n) entries plus the empty slots that keep the load factor down.

Where it goes wrong

• Hashing only part of the key. Length, first letter or a timestamp rounded to the day all crowd real data.
• Mutable keys. Use tuples or frozen dataclasses; never hash fields that can change.
• Defining __eq__ without a matching __hash__. Equal objects must hash equally, or lookups miss.
• Quoting O(1) as a guarantee. Say "expected O(1)"; mention the worst case and hash flooding.

When it shows up in interviews

As follow-ups to any problem solved with a hash map, such as two sum or group anagrams: what is the worst case, how are collisions handled, why must the key be immutable. Design questions ask for chaining versus open addressing, or when a balanced tree map is preferable. The basics are in how hash tables work.

How to say it in an interview

"A hash table is O(1) on average, not in the worst case. Collisions are normal and are handled by chaining or by probing; the cost of a lookup is the number of keys compared in that bucket. A good hash spreads keys evenly and the table resizes to keep the load factor bounded, so the expected chain length is constant. A hash that crowds keys, or an attacker who forces collisions, makes lookups O(n). And keys have to be immutable, because an entry is filed under its hash at insertion time; if the key changes, lookups go to the wrong bucket."