Collision Resolution: Open Addressing

Blueprint: the spilling row

Two lessons ago you watched the clerk survive a double-booking by installing a hook and letting packages queue up — chaining. There's a second way the clerk could have handled that first collision, one that never uses a hook at all. In this blueprint, the clerk refuses to let two packages share a slot, period — every slot holds exactly one package. When Bob's package is called to Slot 4 but Alice is already sitting there, the clerk doesn't hang it behind hers. Instead they say: "walk down the row and take the very next empty slot you find." Bob's package spills into Slot 5.

In hash-table terms: entries are stored directly in the bucket array, and on collision you probe for the next free slot by a fixed rule (linear probing: try i+1, i+2, …). This is denser and more cache-friendly than chaining — no per-entry list nodes scattered across memory, so it leans on the Arrays module's locality argument. You already built the chaining version; this is the alternative design, not a replacement for it — Python's dict and most modern language runtimes actually use open addressing, while textbook implementations often chain because the code is simpler.

The cost of density: clustering

Density is the whole appeal of open addressing, and it's also where the cost hides. As the row fills up, you get long, uninterrupted blocks of occupied slots. A new package that lands in the middle of one of these blocks has to walk all the way to the far end before it finds space — and every insert into an occupied run extends that run by one, so future collisions landing anywhere inside it have to probe past the whole thing. Runs snowball, and performance degrades sharply as α → 1.

This is exactly why open-addressed tables resize earlier than chained ones — commonly α ≈ 0.5–0.7, versus chaining's 0.75–1. A chained table can tolerate a fuller cabinet because a longer hook is still just a longer hook; an open-addressed table's cost curve steepens far more sharply because a longer run blocks every probe that has to cross it, not just the packages hanging on it.

Deletion gets subtle: tombstones

Say Alice leaves Slot 4 empty again. Now picture the clerk searching for Bob, who's sitting in Slot 5 because Slot 4 was taken when he arrived. The clerk checks Slot 4 first, finds it empty, and — reasonably — assumes nobody ever passed through here, so Bob must not exist. The search stops early, and Bob becomes unfindable even though his package is sitting right there in Slot 5. Emptying a slot can break the probe path that runs through it.

The fix is a tombstone: instead of leaving Slot 4 looking brand new, the clerk leaves a marker — an orange traffic cone — that says "nothing here right now, but keep probing, someone used to park here." A lookup treats a tombstone as "keep going"; an insert treats it as "free to reuse." Reachability survives the deletion because every slot along the original probe path still looks like it was once occupied.