Hash Collision Resolution: Chaining vs Open Addressing

A hash collision happens when two different keys hash to the same slot in a hash table. Since a hash function maps a potentially unlimited key space onto a fixed number of slots, collisions aren’t a bug or an edge case — they’re mathematically guaranteed to happen eventually, and every hash table implementation needs an explicit strategy for handling them. The two dominant strategies, chaining and open addressing, make different tradeoffs between memory layout, worst-case behavior, and implementation complexity.

Separate chaining

Chaining resolves collisions by turning each slot into a small collection — typically a linked list, sometimes a small tree for high-collision buckets — that holds every key-value pair whose hash landed in that slot.

slot 0: []
slot 1: [("alice", 30)] -> [("frank", 22)]
slot 2: []
slot 3: [("bob", 45)]

To look up a key, you hash it to find the slot, then walk that slot’s chain comparing keys until you find a match. Insertion is a hash plus a prepend to the chain; deletion is a hash plus a chain traversal and unlink.

Advantages: simple to implement correctly, degrades gracefully — performance decays smoothly as load factor increases past 1.0 rather than failing outright, and deletion is straightforward since removing an entry from a chain doesn’t disturb any other entry’s position.

Drawbacks: each entry carries pointer overhead for the chain links, and chains scattered across memory mean lookups can involve cache-unfriendly pointer chasing rather than sequential access — a real cost given how much CPU cache behavior dominates real-world performance at this scale.

Open addressing

Open addressing keeps everything in a single flat array — no chains, no extra pointers. When a collision occurs, the algorithm probes for the next available slot according to a defined sequence, and both insertion and lookup follow that same probe sequence.

• Linear probing — check the next slot, then the next, wrapping around at the end of the array. Simple and cache-friendly (sequential memory access), but prone to clustering: once a run of occupied slots forms, it tends to grow, since any new collision within its range extends it further.
• Quadratic probing — check slots at increasing quadratic offsets (+1, +4, +9, …) instead of strictly sequential ones, which spreads out clusters better than linear probing at some cost to cache locality.
• Double hashing — use a second hash function to determine the probe step size itself, so different keys that collide at the same initial slot follow different probe sequences entirely, largely eliminating clustering.

Advantages: no pointer overhead, and the flat array layout is far more cache-friendly, which often makes open addressing faster in practice than chaining at moderate load factors despite the two having similar theoretical average-case complexity.

Drawbacks: deletion is genuinely awkward — you can’t just clear a slot, because that would break the probe sequence for any later key that collided into a slot past it and is relying on it being occupied to know to keep probing. The standard fix is a special “deleted” tombstone marker rather than a true empty slot, which keeps probe sequences intact but means tombstones accumulate and degrade performance until the table is rebuilt. Open addressing also degrades sharply, not gracefully, as load factor approaches 1.0 — probe sequences get long fast, which is why open-addressing tables typically resize at a lower load factor threshold (often 0.7) than chaining tables.

Side-by-side

	Chaining	Open addressing
Memory layout	Array of lists/trees	Single flat array
Memory overhead	Pointer per entry	None (beyond the array itself)
Cache behavior	Poor (pointer chasing)	Good (sequential/local probing)
Deletion	Straightforward	Requires tombstones
Degradation past load factor 1.0	Graceful	Not possible — must resize before then
Typical resize threshold	~0.75–1.0	~0.5–0.7

Why this matters even though it’s usually hidden from you

Almost nobody implements their own hash table for production use — you reach for the standard library’s map or dictionary type. But the strategy underneath affects real, observable behavior: Python’s dict and Java’s HashMap use variants of chaining (Java’s buckets even upgrade to trees under heavy collision, bounding worst-case lookup), while many high-performance hash table implementations, including several used inside language runtimes for smaller or performance-critical maps, use open addressing specifically for its cache-friendliness. If you’ve ever seen advice to reserve capacity upfront for a large map you’re about to fill, that’s a direct consequence of this — avoiding resize-triggered rehashing matters more, and costs more, under one strategy than the other.

The same underlying idea — spreading data deterministically across a fixed space while handling overlap — shows up again, differently shaped, in consistent hashing, which solves the analogous problem of minimizing redistribution when the number of buckets (servers, not slots) changes, and in Bloom filters, which trade exactness for space by allowing false-positive collisions on purpose.

The takeaway

Chaining resolves hash collisions by letting each slot hold multiple entries in a list; open addressing resolves them by probing for another slot in the same flat array. Chaining is simpler, deletes cleanly, and degrades gracefully — open addressing is more memory- and cache-efficient but needs tombstones for deletion and a lower resize threshold to avoid probe sequences blowing up. Neither is universally better; the choice is a real engineering tradeoff between memory overhead, cache locality, and deletion complexity, which is why different language runtimes and libraries land on different answers.