Hash collisions: chaining and linear probing on the same keys

You insert key 1, then key 6. Both choose slot 1 in the example below, but both values must remain retrievable. A table needs a collision rule that tells it where to put the second entry and how to find it later.

Two keys choose one slot#

This simplified hash uses key mod 5, the remainder after division by five. Keys 1, 6 and 11 all have remainder 1. Predict their locations after three insertions, then switch the collision strategy. You can compare the same keys without resetting them.

With chaining, bucket 1 holds the sequence 1 → 6 → 11. With linear probing, key 1 occupies slot 1, key 6 moves to slot 2, and key 11 passes both occupied slots to reach slot 3. Linear probing is one form of open addressing, where entries stay in the table’s slot array. Other probe rules visit slots in a different order.

More possible keys than buckets means some keys must share a bucket, even with a well-designed hash. This is the pigeonhole principle. It does not mean every small input already contains a collision. A useful hash spreads the keys actually used across the buckets; it cannot assign a unique bucket to every possible key.

A collision can appear long before the table fills. If distinct keys choose slots independently and uniformly, the chance of at least one collision is about one half after roughly 1.18 times the square root of the slot count, for a large table. With m slots and k keys, the chance of no collision is 1 × (1 − 1/m) × … × (1 − (k − 1)/m): each new key must avoid the slots already chosen. The 1.18 figure approximates where that product reaches one half; it is not an exact integer cutoff or a guarantee about a particular hash or input set.

Follow the same path during lookup#

To find 11 with chaining, choose bucket 1 and compare its entries: 1, then 6, then 11. An absent key with the same bucket number requires checking the whole chain. The simple model uses a list; Java HashMap can also use trees in large collision bins, so its behaviour is not fully described by a linked-chain worst case.

With linear probing, lookup checks slots 1, 2 and 3 to find 11. It follows the same path as insertion and wraps around after the last slot. A never-used slot ends an unsuccessful search. In a full table, no such slot exists: the lookup below stops after checking every slot once. A key still at its original slot can remain a one-probe hit even when the table is busy.

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

def probed_lookup(slots, key):
    if not slots:
        raise KeyError(key)
    i = hash(key) % len(slots)
    for _ in range(len(slots)):
        if slots[i] is None:
            break
        if slots[i][0] == key:
            return slots[i][1]
        i = (i + 1) % len(slots)
    raise KeyError(key)

These lookup-only examples assume matching insertion rules, stable hashes and equality, and no deleted-slot markers. Linear probing visits at most the slot count, so even an absent key in a full table terminates. A production table also needs insertion, resizing and a deletion policy.

The entry count divided by the bucket count is the load factor. Chaining can exceed one because a bucket can hold several entries. Open addressing needs one free slot per new entry. Java HashMap documents a default growth threshold of 0.75; that is its time/space choice, not a general failure boundary. See lookup, capacity and resize costs to distinguish occupancy from the growth policy.

Now change the example: delete key 6 from slot 2. If that slot becomes an ordinary empty stopping point, a search for 11 ends there and wrongly reports it missing. A tombstone records that an entry was deleted while telling lookup to continue. The CPython 3.14 dict source distinguishes unused slots from deleted dummy slots for this reason. CPython has its own probe sequence and storage layout; it is not this five-slot simulator.

Deletion under simple chaining removes a node from its bucket’s list. It does not create a stopping point in another key’s probe path. The linked-list insertion and traversal example explains why locating a node and changing its links are separate costs. The published lookup functions above deliberately omit deletion markers; do not add deletion without updating their lookup rule.

Hashing is not the only way to locate a key. In the binary search tree visualiser, comparisons choose left or right at each node. In the B-tree split visualiser, a full node splits to preserve an ordered search structure. These tools teach different placement rules; a B-tree node is not a hash slot.

When collisions become expensive#

The preset keys deliberately collide. If n entries all share a linked bucket, looking for the last one requires n comparisons. That is O(n) work even if most other buckets are empty. In linear probing, nearby collisions create occupied runs that later lookups must cross. Resize policies and better key distribution can reduce pressure; tree bins and other probe strategies change the details.

Deliberately chosen keys can turn this into a security problem. The historical oCERT-2011-003 advisory describes denial of service from predictable hash collisions, particularly where web applications accepted many attacker-controlled request parameters. It is evidence for that attack mechanism and the versions named in the advisory, not a claim that current versions retain those vulnerabilities.

Compare equal-sized inputs with different key shapes: a random-key test can miss the deliberately colliding case. Defences depend on the implementation. Python randomises string and byte hashes, unless randomisation is disabled; it does not cover every numeric or custom hash. Request-size limits also bound attacker-controlled work. Randomisation alone is no universal denial-of-service guarantee.