Collision Resolution Strategies
Hashmaps & Hash Tables · Data & Hashing track
7 min read
In this module
When Keys Collide
Collisions are inevitable. With more possible keys than buckets, the pigeonhole principle guarantees that some keys end up sharing a bucket. You can't dodge them. The interesting question is how you handle them gracefully once they show up.
Two major families do this work: separate chaining and open addressing.
Separate Chaining
Each bucket holds a linked list (or another small collection) of every entry that hashes to that index. Collision? Append the new entry to the list and move on.
Bucket array with chaining:[0]: ("cat", 1) -> null[1]: ("bird", 3) -> null[2]: ("dog", 2) -> ("fish", 4) -> null[3]: null[4]: null[5]: null[6]: null[7]: nullInsertion: hash to the bucket, walk the chain to check the key isn't already there (if it is, overwrite its value), then add the new entry. That walk makes insertion cost the same as a lookup, O(1 + chain length). Only a table that allows duplicate keys gets a true O(1) append.
Lookup: hash to the bucket, then walk the chain comparing keys until something matches. Cost is O(1 + chain length) — fine if chains stay short.
Deletion: find the entry inside the chain and unlink it.
Separate chaining parks a linked list at each bucket. Lookup stays O(1) while chains are short (low load factor), and slumps to O(n) if every entry piles up in one chain. Java's HashMap uses chaining and swaps a chain for a red-black tree once it reaches eight entries, but only when the table already has at least 64 buckets. Smaller tables just resize instead.
Open Addressing
Open addressing keeps everything in the bucket array itself. No chains, no external lists. When a slot is taken, the algorithm probes other buckets in a deterministic order until it lands on an empty one.
Linear Probing
The simplest probing strategy: if bucket i is occupied, try i+1, then i+2, and so on (wrapping around to the beginning).
Insert ("fish", 4): hash("fish") % 8 = 2, but bucket 2 is taken Try bucket 3: empty! Store ("fish", 4) at bucket 3.
Bucket array:[0]: ("cat", 1)[1]: ("bird", 3)[2]: ("dog", 2)[3]: ("fish", 4) <-- found an empty slot[4]: empty[5]: empty[6]: empty[7]: emptyLookup with linear probing: hash to a bucket, compare keys. No match? Try the next bucket, then the next. Stop when you find the key or hit an empty bucket (which tells you the key was never inserted).
The clustering problem: linear probing makes entries clump together into long runs. Once buckets 2, 3, 4, 5 are all taken, any fresh key hashing to any of those four has to walk the whole cluster before settling. Clusters then snowball, and performance with them.
You can grow a cluster by hand below. This table uses the sum-of-characters hash from the last lesson, so cat, act and tac all hash to 0, and bird and cow both hash to 1. Insert those five keys in that order and read the "probed" line after each one: cow has to step over three occupied slots before it settles in bucket 4. Then switch the strategy to quadratic probing and watch the same keys spread out.
Hash Table Explorer
Quadratic Probing
Rather than i+1, i+2, i+3..., probe at i+1, i+4, i+9... — successive squares. Probes spread out across the table, and clusters lose their grip.
Collision at bucket i: Try i + 1^2 = i + 1 Try i + 2^2 = i + 4 Try i + 3^2 = i + 9 ...Double Hashing
A second hash function decides the step size. Each key now walks its own bespoke probe sequence, which all but kills clustering.
step = hash2(key)Collision at bucket i: Try i + step Try i + 2*step Try i + 3*step ...Chaining vs. Open Addressing
| Aspect | Separate Chaining | Open Addressing |
|---|---|---|
| Memory | Extra pointers for chains | All data in one array |
| Cache performance | Poor (linked list traversal) | Good (data is contiguous) |
| Load factor limit | Can exceed 1.0 | Must stay below 1.0 |
| Deletion | Simple (remove from chain) | Complex (need tombstones) |
| Clustering | No clustering | Clustering risk |
Most modern high-performance tables land on open addressing (Google's SwissTable, Rust's hashbrown) because contiguous memory wins on real CPUs. They don't probe one slot at a time, though: they check a group of 16 slots at once with SIMD and jump between groups with a quadratic stride. The other trick is to resize aggressively so the load factor stays low.
The Deletion Problem in Open Addressing
Deletion is the awkward bit. You can't just blank the slot, because doing so would sever the probe chain for any later entry that was inserted past this position during a collision.
The fix is tombstones. A deleted slot is marked "deleted" instead of "empty". Probes treat tombstones as occupied and keep walking; insertions are happy to overwrite them. Pile up enough tombstones and probes slow down, which is exactly why periodic rehashing sweeps them out of the table.
What Happens When Everything Goes Wrong
In the absolute worst case, every key hashes to the same bucket. Chaining gives you one linked list of n elements, so lookup is O(n). Open addressing has every lookup probing through the whole table, also O(n). The hash function alone separates an O(1) data structure from an O(n) one — pick badly and the structure collapses.
Attackers know this. If they control the keys flowing into a server's hash table (HTTP query parameters are a classic vector), they can hand-pick inputs that all collide and grind every lookup down to O(n). The trade name is a hash-flooding denial-of-service attack. The defence is a randomised, keyed hash like SipHash, where the attacker can't reverse-engineer which inputs will collide.
The program below fills a 1,024-slot table to three load factors and counts how many slots a successful lookup touches on average, for both strategies. Predict how linear probing copes at 0.9 before you run it, then look at the last line, where every key was chosen to land in the same bucket.
Chaining barely notices the load factor, while linear probing climbs steeply as clusters merge. The flooding run is the same disaster for both: about n/2 comparisons per lookup, because every key shares one bucket.