Collision Resolution: Separate Chaining

Blueprint: the hanging hook

Remember the mailroom clerk from the last lesson, and remember that double-bookings are guaranteed — sooner or later two packages get called out to the same slot. Watch it happen: a package labeled "dog" comes in and the clerk's trick sends it to Slot 2. Later, a package labeled "god" — same three letters, different order — comes in, and by pure chance the trick sends it to Slot 2 as well. Here's the clerk's first fix: they don't panic and don't turn either package away. They install a small metal hook inside Slot 2. "Dog" goes on the hook first. "God" arrives next for the same slot, so the clerk simply hangs it right behind "dog" — a growing chain of packages, all sharing one slot, one hook. Meanwhile "cat" and "emu," which landed in their own slots with no company, just sit there each on their own single-package hook.

In the language of hash tables: each bucket holds a list of the entries that hashed there. Insert appends to the bucket's list (after checking for the key); lookup scans only that one list — the clerk doesn't check every hook in the cabinet, just the one hook the trick pointed them to.

The cost of any operation is the length of one hook's chain. So the whole performance question becomes: how many packages, on average, end up sharing a hook?

Why "O(1) on average" is an honest claim, not a slogan

Here's the intuition first: if you have 10 slots and 10 packages spread out reasonably evenly, the average hook only has about 1 package hanging on it. The clerk almost never has to flip through more than one or two items to find what they're looking for. That ratio — packages per slot — is the whole story.

Formally, define the load factor α = n / m (entries per bucket). Under uniform hashing, each of the n keys lands in a given bucket with probability 1/m, so the expected chain length is exactly α. Keep α bounded by a constant (say ≤ 1) — keep the mailroom from getting too crowded — and the expected work per operation is O(1 + α) = O(1). Two premises make this true, and you now know both:

1. uniformity — the hash spreads keys evenly (last lesson's job);
2. bounded load factor — the table resizes before α grows (this lesson's job).

But imagine a prankster who brings in 100 packages, every single one addressed with a name that the clerk's trick maps to Slot 4. The instant lookup collapses — the clerk has to flip through all 100 packages on that one hook, one at a time, exactly like the lost-and-found closet from the first lesson. An adversary (or a genuinely bad hash function) can always force this: put all n keys in one chain → O(n) per operation. When you quote "hash lookup is O(1)," you are quoting the average case under the two premises above, not a guarantee that survives a hostile or unlucky set of keys — the Big O module's case-discipline, applied.

Moving day: the dynamic array trick, again

To keep the mailroom from turning back into a giant unsorted pile, the clerk has a standing rule: the moment the cabinet gets too crowded (α crosses a threshold, commonly 0.75–1), shut down for the day, wheel in a brand-new cabinet with twice as many slots, and re-run the word-trick on every single package to re-file it into the roomier cabinet. Because the number of slots changed, a package's slot is hash mod m, and m just changed — so almost every package moves to a new hook (a full O(n) rehash).

Sound familiar? It's the dynamic array's growth policy with a rename, and the same amortized argument applies verbatim: doubling means the rare "moving day" costs 1 + 2 + 4 + ⋯ + n/2 < n total spread across n regular deliveries, so insert stays O(1) amortized on top of O(1) average.

One practical corollary: if you walk down the cabinet's slots after a moving day, you'll see packages in a completely different order than before — iteration order can change after any insert that triggers a rehash. That's one reason you never rely on bucket order. (Python dicts and JS Maps do guarantee insertion order — a deliberate extra mechanism layered on top, not a property of hashing.)

Watch a chain form, the load factor cross 0.75, and every surviving key get re-filed under the doubled modulus — including one that collides again at the new size, because doubling reduces collisions statistically, not individually:

Chaining is one way to survive a double-booking — never turn a package away, just grow the hook. The next lesson builds the clerk's system in code; the one after that covers a completely different way to handle a collision, one that never uses a hook at all.