The previous lesson ended with a collision — two keys mapped to the same slot. One slot, two values. Something has to give.

Here is the uncomfortable truth about hash functions: they compress a vast key space into a tiny index space. Suppose your table has 8 slots. Any key whose value is a multiple of 8 — 0, 8, 16, 24 — maps to slot 0. Keys 5, 13, 21, 29 all map to slot 5. The pigeonhole principle guarantees collisions as soon as you insert more keys than you have slots, but in practice, collisions happen much sooner. Even with a perfectly random hash function and a table of 365 slots, you have a 50% chance of a collision after just 23 insertions (the birthday paradox). With real hash functions and real data, collisions are not edge cases — they are inevitable.

What if the slot could hold more than one value? Insert these keys and find out what happens when two keys want the same slot.

Think of each slot as a hook on a wall. When one hook is full, you hang a chain from it — one coat per link. Looking for your coat means walking the chain, link by link.

The idea is simple: instead of each slot holding one value, let each slot hold a list. When two keys hash to the same slot, both go into that slot's list — its chain. Insertion appends to the chain head in O(1). The cost moves to lookup: scanning the chain to find your key.

Notice where the pile-up landed. Keys 5, 13, and 21 all satisfy key % 8 = 5, so they stack into the same slot regardless of insertion order. The distribution is not random — it is the hash function projected onto the data.

As long as chains stay short, every operation stays close to O(1). If one chain grows to length k, searching it costs O(k) — a linear scan through that single chain. In the pathological case, every key hashes to the same slot, the single chain has length n, and lookup degrades to O(n). A good hash function makes that vanishingly unlikely, but the possibility is what drives the next question: how does searching a chain actually feel?

Inserting was easy — values stacked up in their slots. Finding one again is the part that costs.

The search algorithm has two steps. First, compute slot = key % tableSize to jump directly to a chain. That step is O(1) regardless of table size. Second, walk through that chain comparing each entry to the target. There is no skipping ahead — chains are linked lists, so the scan is sequential.

Predict the cost of each search before watching the scan.

The pattern that just played out is the trade-off of chaining: insertion is always O(1) (just append to the head), but search cost varies from O(1) to O(n) depending on chain length. In the best case, every key lands in its own slot and every search checks exactly one entry. In the worst case, every key hashes to the same slot, the table degenerates into a single linked list, and every search walks all n entries.

This worst case is not purely theoretical. An attacker who knows your hash function can craft inputs that all collide, turning your O(1) hash map into an O(n) linked list. This is the basis of hash-flooding denial-of-service attacks, and the reason why languages like Python randomize their hash seeds on startup.

Chaining works but requires extra memory for linked lists. Every chain node is a separate heap allocation — a pointer to a struct that holds the key, the value, and another pointer to the next node. On modern CPUs, those pointer hops are expensive. Each dereference can trigger a cache miss, sending the processor to main memory (a 100x slowdown compared to an L1 cache hit). What if you could avoid pointers entirely and store everything in the table itself?

That is the idea behind open addressing. When a slot is full, you do not create a list — you look at the next slot in the array. The simplest variant is linear probing: check slot hash(key), then hash(key)+1, then hash(key)+2, and so on, wrapping around to slot 0 when you pass the end. Because the entries live in a contiguous array, the CPU prefetcher can load upcoming slots into cache before you even ask for them. For tables that fit in cache, this makes open addressing significantly faster than chaining in practice — despite having the same O(1) amortized complexity.

Insert these keys. Watch what happens as more slots fill up.

But linear probing has a subtle and devastating failure mode: primary clustering. Once a run of consecutive occupied slots forms, it acts like a gravitational well. Any new key that hashes to ANY slot within the cluster — or to the slot immediately after it — must probe all the way to the cluster's end before finding an empty slot, and then it extends the cluster by one. The growth is superlinear: a cluster of length k captures new keys at a rate proportional to k, so clusters grow faster the larger they get. Two nearby clusters will eventually merge into one massive cluster, amplifying the problem further.

Imagine slots 4, 5, 6, and 7 are all occupied. That is a cluster of length 4. Any new key that hashes to slot 4, 5, 6, OR 7 must probe all the way to slot 0 — that is 4 extra comparisons per insertion. But it is worse than that: even a key that hashes to slot 3 is unaffected, but one that hashes to slot 4 eats 4 probes, slot 5 eats 3, slot 6 eats 2, slot 7 eats 1. On average, any key in that range costs 2.5 extra probes. The cluster does not just slow down keys that directly collide — it taxes every key in its gravitational radius.

Compare that to chaining: in a chaining table, a long chain at slot 5 has zero effect on lookups at slot 4 or slot 6. Each chain is independent. Open addressing trades that independence for cache locality — and the price is clustering.

You have seen chains grow and probes cluster. Both degrade as the table fills. How full is too full — and what do you do when the answer is “too full”?

There is one number that predicts every hash-table cost: the load factor, α = n / tableSize. Insert keys into the table below and watch what α does to the search cost. When the curve starts to bite, a way out will appear.

That single O(n) resize is what makes the amortized O(1) story honest. Each doubling absorbs the cost of all the inserts that paid for it — the same argument that makes dynamic arrays O(1) per append. Real implementations pick their threshold by feel: Python's dict resizes around α = 2/3 (≈ 0.67), Java's HashMap at α = 0.75.

Chaining and open addressing both pay this amortized O(1), but the trade-offs matter in practice. Chaining is simpler to implement: chains grow naturally, deletions just unlink a node, and the load factor can safely exceed 1.0 (chains of length 2 or 3 are fine). Java's HashMap uses chaining for exactly these reasons — and since Java 8 it even converts long chains to balanced trees when they exceed 8 entries, capping each slot at O(log n).

Open addressing stores everything in the table array itself. No pointer chasing, no heap allocation per entry — just contiguous memory the CPU prefetcher loves. Python's dict uses open addressing with a custom perturbation probe; Rust's HashMap uses Robin Hood hashing with linear probing. The trade-off is that deletions require tombstone markers (you cannot just empty a slot, because it would break probe chains), and the load factor must stay well below 1.0 to avoid runaway clustering.

The choice depends on the workload: if your keys are small and lookups dominate, open addressing wins on cache performance. If you need frequent deletions or your load factor is unpredictable, chaining is more forgiving.