Hash Table Collision Resolution
Concept
A hash table maps keys to array slots via a hash function, giving average O(1) insert/lookup/delete — but any hash function mapping an unbounded key space onto a bounded array of slots will eventually produce two different keys landing on the same slot (a collision), which is guaranteed by the pigeonhole principle once the table holds more entries than it has extremely sparse hashing, and is common in practice well before that. What separates a correct hash table implementation from a broken one is entirely in how it handles that collision — the hash function only gets you to "probably empty," never "guaranteed empty."
There are two families of solution:
- Separate chaining — each array slot holds a small independent structure (traditionally a linked list, though modern implementations often switch to a balanced tree or small array once a bucket gets large) of every key that hashed to it. A collision just means appending to that slot's list; lookup means hashing to the slot, then scanning its list.
- Open addressing — every key lives directly in the array itself, no auxiliary structure. On collision, a probe sequence deterministically computes the next candidate slot to try (linear probing: check the next slot; quadratic probing: check slots at increasing quadratic offsets; double hashing: use a second hash function to compute the step size), continuing until an empty slot is found.
Both approaches degrade as the load factor (entries ÷ number of slots) rises, but differently. Chaining degrades gracefully — buckets just get longer, and lookup cost grows roughly linearly with load factor past 1.0, but the table stays correct even at a load factor of 2 or 3 (just slower). Open addressing degrades sharply and stops working at all past load factor 1.0 — there is no room left, full stop — and in practice needs to trigger a resize well before that (typically around 0.5–0.75) because probe sequences get dramatically longer as slots fill up (a phenomenon called primary clustering for linear probing specifically, where long runs of occupied slots snowball into even longer ones).
Tradeoffs
| Aspect | Separate chaining | Open addressing |
|---|---|---|
| Practical max load factor | Works (slower) even past 1.0 | Must resize well before 1.0, typically ~0.5–0.75 |
| Cache locality | Poor — each bucket is a separate heap allocation, pointer-chasing on lookup | Good — all data lives in one contiguous array, better cache-line utilization |
| Memory overhead | Extra pointer/node overhead per entry | No auxiliary structure, more compact (until table is oversized for the load factor) |
| Deletion | Simple — remove from the bucket's list | Needs care — removing a slot outright breaks later probe sequences that skipped over it; typically requires a tombstone marker, which itself needs periodic cleanup |
| Behavior with large/variable-size values | Handles naturally — bucket just holds a reference | Awkward if values are large or variable-sized, since the array must hold full entries inline |
Neither dominates unconditionally: chaining is the safer default when load factor is unpredictable, keys/values are large or variable-sized, or worst-case correctness under adversarial input matters more than raw throughput. Open addressing wins in read-heavy, cache-sensitive workloads where the table size can be kept well ahead of the load factor and deletions are rare or absent.
When to use / when not to
- Default to the language's built-in hash map/set for almost all application code — Python's
dict/set, Go'smap, Java'sHashMap— and only think about the underlying collision strategy when implementing a hash table from scratch (systems/infra code, or an interview question that specifically asks for it). - Reach for chaining-style implementations when entries vary wildly in size, deletions are frequent, or the load factor can't be tightly bounded in advance.
- Reach for open addressing (or verify that the stdlib you're using already does — CPython's
dictand Go'smapboth use open-addressing-family designs internally) when lookups dominate, entries are small and roughly uniform in size, and the table's growth can be resized proactively. - Don't hand-roll a custom hash function or collision strategy for application-level code where a mature stdlib implementation already exists and is well-tested against adversarial inputs (hash-flooding attacks are a real concern the standard library has already hardened against).
Common pitfall
Not resizing (rehashing into a larger table) proactively enough under open addressing. Because open addressing has no fallback structure to absorb overflow the way chaining does, a table that's allowed to approach load factor 1.0 doesn't just get slower — probe sequences start approaching O(n) per operation, and near-full tables can pathologically fail to terminate probing at all if the resize threshold logic has an off-by-one bug. The fix is always the same: pick a load-factor threshold (commonly 0.7) well below 1.0, and resize (typically doubling capacity and rehashing every existing entry) the moment insertion would cross it — never react to slowness after the fact.
Engineering Lens
The chaining-vs-open-addressing decision is a concrete instance of a pattern that recurs across systems design generally: trade a pointer-chasing, flexible structure for a compact, cache-friendly, but more rigid one. The same tradeoff shows up in database page layouts (row-store vs. columnar), in-memory caches, and even network protocol buffer design. Knowing why CPython's dict implementation moved from a simple open-addressing scheme to one with better collision behavior under adversarial keys (and why Python randomizes string hashing by default specifically to defeat hash-flooding denial-of-service attacks) is a good concrete example of collision handling being a real production security and performance concern, not just an academic exercise.