How does a hash table handle collisions?
Updated Feb 20, 2026
Short answer
A collision occurs when two distinct keys hash to the same bucket, which is unavoidable because the key space exceeds the number of buckets. The two main resolution strategies are separate chaining, where each bucket holds a secondary structure such as a linked list, and open addressing, where a colliding entry is placed in a different bucket found by probing. Both keep the average lookup at O(1) while the load factor stays low.
Deep explanation
Collisions are guaranteed by the pigeonhole principle — infinitely many possible keys map into a finite array. The design question is not how to avoid them but how to resolve them cheaply.
Separate chaining. Each bucket points at a container of entries that hashed there.
buckets[3] -> ("cat", 1) -> ("act", 7) -> nullLookup hashes to the bucket, then scans the chain comparing full keys. Simple, degrades gracefully past a load factor of 1, and deletion is trivial. The costs are a pointer per entry and poor cache locality — chain nodes are scattered across memory. Java's HashMap converts a chain to a balanced tree once it exceeds eight entries, bounding worst-case lookup at O(log n) instead of O(n).
Open addressing. All entries live in the array itself; a collision triggers a probe sequence for the next free slot.
- Linear probing — try
h+1, h+2, …. Excellent cache behaviour, but suffers primary clustering: occupied runs coalesce and grow, and probe lengths rise sharply. - Quadratic probing — try
h+1², h+2², …. Breaks up primary clustering at the cost of worse locality. - Double hashing — step by a second hash of the key, largely eliminating clustering.
Open addressing must stay well below full; performance collapses as the load factor approaches 1, and most implementations resize at around 0.7. Deletion is also awkward: simply emptying a slot severs a probe chain and makes later entries unreachable, so deleted slots are marked with a tombstone that probes traverse but insertions may reuse.
Load factor and resizing. Both strategies rely on n/m staying bounded. When it crosses the threshold, the table allocates a larger array — usually double — and rehashes every entry, since bucket indices depend on the array size. That single insertion is O(n), but amortised across all insertions it is O(1).
Hash quality underpins everything. A poor hash concentrates keys into few buckets and degrades every operation to O(n). This is exploitable: hash-flooding attacks craft colliding keys to make a server's dictionary quadratic, which is why runtimes such as Python and Rust randomise their hash seed per process.
Real-world example
Inserting "cat" and "act" into an 8-bucket table where both hash to index 3.
Separate chaining [0] [1] [2] [3]-> ("cat",1) -> ("act",7) [4] [5] [6] [7] lookup("act"): hash -> 3, walk chain, compare keys, found.
Linear probing [0] [1] [2] [3]=("cat",1) [4]=("act",7) [5] [6] [7] lookup("act"): hash -> 3, key mismatch, probe 4, match.Now delete "cat" under linear probing. Clearing slot 3 outright means a later lookup("act") hashes to 3, finds it empty, and concludes the key is absent — even though it sits at slot 4. Hence the tombstone:
[3]=<deleted> [4]=("act",7) lookup("act"): slot 3 is a tombstone -> keep probing -> slot 4 -> found.Common mistakes
- - Claiming hash tables are O(1) without qualification
- that is the average case, and the worst case is O(n) with a degenerate hash.
- - Deleting from an open-addressed table by clearing the slot instead of writing a tombstone, silently orphaning entries further along the probe chain.
- - Overriding equality without overriding the hash function (or vice versa), so equal objects land in different buckets and lookups fail.
- - Using a mutable object as a key and then mutating it — its hash changes, and the entry becomes unreachable in its original bucket.
- - Letting the load factor approach 1 with open addressing, where probe sequences grow catastrophically long.
- - Assuming a good hash distributes any input well
- adversarial input can force collisions deliberately unless the seed is randomised.
Follow-up questions
- What is the load factor and why does it drive resizing?
- Why do tombstones exist and what do they cost?
- What is primary clustering?
- How does a hash-flooding attack work?