Hash collisions

A hash function’s job usually gets summarised as “spread keys out and avoid collisions,” which makes a collision sound like something a well-chosen function should mostly prevent. It cannot. Once there are more possible keys than slots — and there almost always are — two keys sharing a slot is not a design failure; it is the pigeonhole principle stating a fact. The question worth asking instead is what a hash table does the moment that happens, because two different answers to it produce two structures with two different shapes of failure.

Collisions are the normal case#

A hash function maps an effectively unlimited space of possible keys onto a small, fixed space of slots. With more keys than slots, some pair of keys must land on the same one — that is the pigeonhole principle, not a property of any particular hash function, and no amount of tuning removes it. What a hash function controls is how evenly the collisions that must happen get spread across the table; it cannot get their count to zero once the table holds fewer slots than the keys being pushed through it.

The part that catches people out is when the first collision shows up — and it is not an event reserved for a table that is nearly full. This is the birthday-bound effect: the odds of at least one pair already sharing a slot become better than even once a little past the square root of the slot count worth of keys are in the table, which by any everyday reading is still mostly empty. The birthday problem itself is usually told with people and calendar days rather than keys and slots, but the shape of the result carries over: the number of pairs being compared grows much faster than the number of items being compared, so a match becomes likely long before any individual slot looks crowded.

Two recoveries, two failure curves#

Chaining keeps every recovery local to the one slot that collided. Each slot holds a small list rather than a single entry; when a new key hashes to a slot that is already occupied, it simply gets appended to that slot’s list. A lookup goes straight to the right slot by its hash, then walks that slot’s list comparing keys until it finds a match or runs out of list. As the table fills, an average slot’s list gets a little longer, and lookups drift for the same reason a queue does: the more that lands in one place, the more each arrival at that place has to check.

Open addressing keeps every entry inside the slot array itself, with no separate list. When a key’s home slot is taken, it steps to another slot by some fixed rule — a probe sequence — and keeps stepping until it finds one that is empty. A lookup follows that same sequence, starting at the home slot and stepping onward until the key turns up or an empty slot ends the search. That last detail is what makes open addressing degrade more sharply than chaining as the table fills: an empty slot is the only signal that tells a lookup to give up, so once the table is mostly full, empty slots get rare, and a lookup for almost any key — not only the ones that actually collided — ends up stepping past a long run of occupied slots before it finds its key or finally reaches the empty one that says to stop.

def chained_lookup(buckets, key):
    for k, v in buckets[hash(key) % len(buckets)]:
        if k == key:
            return v
    raise KeyError(key)

def probed_lookup(slots, key):
    i = hash(key) % len(slots)
    step = 1
    while slots[i] is not None:
        if slots[i][0] == key:
            return slots[i][1]
        i = (i + step) % len(slots)
        step += 1
    raise KeyError(key)

Same shape, opposite direction: chained_lookup only ever walks the one list its key hashed to, however long that list has grown. probed_lookup walks the slot array itself, and near a full table, most of the slots it passes on the way there are occupied by other keys entirely.

Where a concrete number belongs is the point at which an implementation decides “full enough” and grows the table — a design choice each implementation documents for itself, not a property of hashing in general. Java’s HashMap, which resolves collisions by chaining, documents a default load factor of 0.75 in its own reference documentation, reasoning that this offers a good trade-off between memory wasted and how long chains are allowed to get before a resize pays for shorter ones again. That figure is Java’s own choice for its own implementation, not a threshold for chaining as such — a table with different costs for a resize versus a long chain can reasonably choose a different point to grow at.

The two strategies also part ways on deletion. Removing a key under chaining is ordinary: find it in its slot’s list and unlink it, and every other key’s lookup is unaffected, because each slot’s list is independent of the rest. Open addressing is not that simple, because a probe sequence uses an empty slot as its stopping signal. Clearing a slot outright can leave an empty slot in the middle of another key’s probe path — a key pushed further along by an earlier collision — so a later lookup for that key would stop early at the newly emptied slot and report it missing, even though it still sits a few slots further on. The fix is a marker distinct from both occupied and truly empty, usually called a tombstone. CPython’s own dict shows exactly this: its source comments describe a deleted slot as one that cannot be made empty again, “else the probe sequence in case of collision would have no way to know they were once active.”

Both recoveries answer the same underlying question — where does this key actually live once its first-choice slot is taken — and other structures answer a related version of it without hashing at all. The site’s own B-tree split visualiser shows what a B-tree does when a page, its equivalent of a full slot, has no room for a new key: the full node splits in two rather than searching elsewhere, and the visualiser’s own stats track how often that happens as keys go in. The binary search tree visualiser answers a different question — not where a key hashes to, but where comparison places it — by stepping left or right at every node until the key, or the empty spot where it belongs, turns up: the ordering a hash table skips by computing an address instead.

One slot holding half the table#

The failure has one recognisable shape: a table that is supposed to give near-constant-time lookups instead behaves like the flat list it was built to avoid. Under chaining, this happens when a hash function maps an unusually large share of the real keys in use to the same few slots — keys with structure the hash does not spread out, or a set chosen specifically to land together — so one slot’s list grows to hold a large fraction of the table while the rest sit close to empty. Every lookup hashing into that one slot now walks a list close to the size of the table itself, and the structure’s advertised near-constant cost quietly becomes linear for the keys unlucky, or unlucky on purpose, enough to land there.

This kind of degradation does not need an accident to happen. Web application frameworks were shown to be exposed to exactly this: an attacker who can predict or reverse a hash function can construct a batch of keys — form field names, in the disclosed cases — that all collide, submit them in a single request, and turn a hash table’s near-constant insert cost into something close to linear per key for that whole batch. The class of attack was formally disclosed as oCERT-2011-003 and led several languages to randomise their hash function’s seed per process, specifically so an attacker outside the process could no longer predict which keys would collide.

One symptom pins it down: performance falls off with a particular shape of input, not with its size, so a load test built from random keys never reproduces it — random keys spread out roughly the way the hash function assumes, and the pathological case only appears once someone hands the table keys chosen, or shaped, to defeat that assumption. This is not a flaw in chaining, or in hashing generally — it is a property of a specific hash function meeting a specific set of keys, and the fix is a better-distributed hash or a randomised seed, not abandoning the strategy itself. Open addressing is not immune either: a probe sequence that clusters colliding keys onto neighbouring slots turns the same shape of input into the same shape of failure, by a different mechanism.