Why does primary clustering make linear probing degrade faster than the raw collision count suggests?
answer
- Occupied slots form runs, not isolated cells
- What does a run capture?
- The longer the run, the wider its target
- Growth feeds on itself; runs also merge
- Squared term in the linear-probing probe estimate
basics
~20 sRuns of occupied slots absorb keys from many different home slots, and each absorbed key extends the run, widening the target that catches the next one. Runs merge and grow superlinearly, so probe lengths climb far faster than true collisions do.
solid answer
~50 sA collision in linear probing does not cost one extra step — it costs the length of whatever run of occupied slots the key lands in, because the key must walk to the end of that run. Any key whose home slot falls *anywhere inside* a run of length `L` extends the run to `L+1`, so the run's capture width grows with the run. Two runs separated by a single free slot merge the moment that slot is taken. This positive feedback is **primary clustering**: keys that never collided in the hash sense still pile onto each other's probe sequences. Sequentially assigned identifiers under a weak hash — say device ids 1000, 1001, 1002 with a hash that preserves adjacency — produce one enormous run, and lookups degrade toward a linear scan even though the hash function itself is spreading keys out.
go deeper
Know that colliding keys settle next to each other and that these occupied stretches make later searches walk further; being able to draw a growing run on a small table is enough here.
Explain the feedback loop precisely: a run captures any key hashing into it, each capture lengthens it, and neighbouring runs merge when the gap between them is claimed.
Diagnose it in the field — recognize sequential or structured keys plus weak mixing as the usual cause, and be able to argue why a table at moderate load can still show long probe walks.
Own the tradeoff explicitly: linear probing buys the best constant per probe and pays with the worst growth in probe count, so it is a defensible choice only alongside strong key mixing and a firmly enforced fill ceiling.
### What clustering means In a linear-probing table, occupied slots do not sit in isolation — they form **runs**: maximal stretches of consecutive occupied slots bounded by free slots. Primary clustering is the tendency of these runs to grow and merge into a few long ones rather than staying short and evenly scattered. The mechanism is a feedback loop. Consider a run of `L` consecutive occupied slots. A newly inserted key joins this run if its home slot is *any* of those `L` slots — it walks forward to the run's end and settles in the free slot just beyond, making the run `L+1` long. So the run's probability of capturing the next key is proportional to its current length, and each capture makes it longer. Long runs get longer faster: growth compounds. Worse, runs merge. If two runs are separated by exactly one free slot and a key claims that slot, the two runs become one run of combined length plus one. A single insert can therefore double the effective cost for keys hashing anywhere into either former run. ### Why the collision count under-reports the damage Candidates often reason: "a good hash function spreads keys, so collisions are rare, so probing is rare." That reasoning counts only **hash collisions** — two keys with the same home slot. Primary clustering is driven by something else: keys with *different* home slots that happen to fall inside the same run. Those keys never collided in the hash sense at all, yet they queue behind each other. The arithmetic makes it concrete. Under an idealized probe sequence that hops randomly, the expected number of slot inspections for an unsuccessful search is roughly `1/(1-alpha)`, where `alpha = n/m` is the load factor. For *linear* probing the classic estimate is about `(1 + 1/(1-alpha)^2)/2` — the squared term is exactly the price of clustering. At `alpha = 0.5` the two are close (about 2 vs 2.5). At `alpha = 0.9` the idealized figure is 10 while linear probing is around 50. The gap between them *is* primary clustering. ### The scenario that makes it visible Take a fixed-size registry keyed by sequentially assigned device identifiers: 1000, 1001, 1002, and so on. If the hash function is weak in the specific sense that it preserves adjacency — the low bits pass through, or the hash is close to the identity modulo the table size — then consecutive ids get consecutive home slots. Now every insert lands directly against the previous one. Instead of scattering, the registry builds one solid block. The table is only half full, the hash function produced almost no true collisions, and yet a lookup for a recently added id walks hundreds of slots. This is the failure mode to describe out loud; it is far more common in practice than a pathological, everything-to-one-slot hash, because sequential keys are everywhere. ### The tempting wrong answer "Linear probing is fine because the array is cache-friendly." The cache argument is real: a probe walk touches consecutive addresses, and stepping through five adjacent slots may cost a single cache line, whereas five pointer hops into scattered memory cost five misses. That is precisely why linear probing survives in high-performance designs. But locality attacks the *constant factor*, and clustering attacks the *number of steps* — and the number of steps grows quadratically in `1/(1-alpha)`. Locality cannot rescue a walk of two hundred slots. The honest answer holds both: linear probing has the best constant per probe and the worst growth in probe count, so it wins at moderate load and loses badly at high load. ### What actually fixes it Three levers, in rough order of leverage: 1. **A hash that destroys adjacency.** Mixing the key's bits so that ids differing by one land in unrelated slots removes the sequential-key pathology outright. This is the cheapest and biggest win. 2. **Keeping the load factor well away from 1**, so free slots stay common and runs stay short. 3. **Changing the probe sequence** so that colliding keys diverge instead of queueing — the reason quadratic probing and per-key strides exist. ### The framing that lands Say it as one sentence: in linear probing, cost is not driven by how many keys share your home slot, it is driven by how long the run of occupied slots your home slot happens to sit in has grown — and runs grow by feeding on themselves.
- Sequential identifiers make this worse. What is the cheapest fix?Improve the mixing in the hash so adjacent identifiers do not produce adjacent home slots. If the hash effectively passes the low bits through, consecutive ids build one solid run by construction. Avalanche-style bit mixing before the modulo scatters them, which removes the pathology without touching the probe strategy or the table size.
- Does primary clustering hurt unsuccessful lookups more than successful ones?Yes. A successful lookup stops as soon as it meets its key, which on average is partway into the run. An unsuccessful lookup must traverse the entire run to reach the free slot that proves absence. That is why the classic estimate for unsuccessful search grows with the square of 1/(1-alpha) while successful search grows more gently.
- If linear probing has this flaw, why do high-performance tables still use it?Because its constant factor is unbeatable: probes touch consecutive memory, so a short walk is often one cache line and no pointer chasing. Designs that use it pair it with strong bit-mixing and a firmly bounded load factor, so runs stay short and the excellent constant dominates the poor growth curve.
One slow customer at a single checkout is a small delay; but the longer the queue gets, the more arriving shoppers join it rather than an empty lane, and two queues that touch become one long one.
saying these in an interview costs you the question
- Assumes only keys sharing a home slot slow each other down
- Says a good hash function eliminates clustering entirely
- Claims cache locality cancels the growth in probe count
- Thinks run growth is linear rather than self-reinforcing
- Ignores that adjacent runs merge when the gap is filled