skip to content

How do quadratic probing and double hashing differ, and what must the second hash satisfy?

level: middleimportance: nice to knowfreq 33%

answer

  1. Both aim at the runs linear probing builds
  2. One sequence depends only on the home slot
  3. The other derives a per-key step size
  4. Ask what a zero step size would do
  5. Step d visits m divided by gcd(d, m) slots

basics

~20 s

Quadratic probing offsets the home slot by a square-growing amount, so same-home-slot keys still share one probe path: secondary clustering. Double hashing uses a per-key stride from a second hash, which must be nonzero and co-prime with the table size.

solid answer

~50 s

Both break up the solid runs that linear probing builds, but differently. **Quadratic probing** probes `home + i^2` modulo the table size, so the walk jumps in widening steps and no long contiguous run forms. Its weakness is **secondary clustering**: the sequence depends only on the home slot, so two keys landing there follow the identical path forever. It also fails to visit every slot — on a prime-sized table an insert is only guaranteed to succeed below 0.5 load. **Double hashing** probes `home + i * stride`, the stride coming from a second, independent hash of the key, so same-home-slot keys diverge at once. The stride must never be zero, which would re-probe the home slot forever, and must be co-prime with the table size, or the walk cycles through a fraction of the slots and misses free ones.

code

pseudocode · 11 lines
pseudocode
// probe number i = 0, 1, 2, ... until a free slot is found
// quadratic probing (m prime):
idx = (h1(key) + i*i) mod m
// double hashing:
idx = (h1(key) + i * h2(key)) mod m
// for two keys with h1(k1) == h1(k2):
//   quadratic -> identical sequences forever (secondary clustering)
//   double    -> sequences diverge at i == 1 unless h2 also collides
// required of the stride:
//   h2(key) != 0            (else every probe revisits the home slot)
//   gcd(h2(key), m) == 1    (else the walk covers only m/gcd slots)

go deeper

for a junior

Recall that there is more than one rule for choosing the next slot after a collision, and that the rule must be identical on insert and on lookup for entries to be findable.

for a middle

Explain both sequences and their weak spots: a square-growing offset depends only on the home slot and may not reach every slot, while a per-key stride must be nonzero and co-prime with the table size.

for a senior

Justify a pick for a real workload — fill ceiling, key structure, cost of a second hash, loss of contiguous access — instead of reciting that one scheme is better than another.

for a principal

Frame it as choosing where to spend: an extra hash per probe and scattered memory access buys resilience against structured keys, and that bargain is only worth making where key distribution is genuinely out of your control.

### Probe sequences as a design knob Open addressing needs a rule that maps `(key, probe number)` to a slot. Linear probing uses the simplest rule, `home + i`, and pays with primary clustering — long contiguous runs that swallow keys from many home slots. The two standard alternatives change the shape of the walk to break those runs up. ### Quadratic probing The probe sequence is `(home + i^2) mod m` for `i = 0, 1, 2, ...` (a common variant uses `(home + (i*i + i)/2) mod m`). The first few probes are close together, then the steps widen quickly. Because successive probes are not adjacent, keys do not build one solid block, and the primary-clustering feedback loop is broken. Two caveats matter in an interview: **Secondary clustering.** The sequence is a function of the home slot alone. Every key that hashes to slot 41 walks 41, 42, 45, 50, 57, ... in exactly that order. So keys that truly collide still queue behind one another for their entire lifetime. The effect is much milder than primary clustering — it affects only genuine same-home-slot collisions, not the unrelated neighbours that linear probing entangles — but it is real, and naming it is the thing interviewers listen for. **Incomplete coverage.** `i^2 mod m` does not enumerate all `m` residues. The classic guarantee: with `m` prime, the sequence visits at least `ceil(m/2)` distinct slots, so an insert is guaranteed to find a free slot as long as the load factor stays below 0.5. Above that, an insert can fail even though free slots exist. (The triangular-offset variant with a power-of-two table size does visit every slot, which is why that pairing is popular.) So quadratic probing constrains table size and fill level together. ### Double hashing The probe sequence is `(h1(key) + i * h2(key)) mod m` — a per-key stride. Now the home slot and the walk are decided by two independent quantities. Two keys with the same home slot almost certainly get different strides and separate after the very first probe, which removes secondary clustering too. Statistically, double hashing comes closest to the idealized "uniform hashing" model in which each key's probe sequence is a random permutation of the slots — the model whose expected unsuccessful-search cost is about `1/(1-alpha)`. The price is a set of hard requirements on `h2`: - **`h2(key)` must never be 0.** A zero stride makes every probe land on the home slot again; the insert loop never advances and either spins or fails on a full-looking table. Implementations force this, typically by producing a value in `1..m-1` or by setting the lowest bit. - **`h2(key)` must be co-prime with `m`.** Stepping by `d` modulo `m` visits `m / gcd(d, m)` distinct slots. If `gcd(d, m) = 4`, the walk cycles through a quarter of the table and can report "full" while three quarters of the slots are free. Two standard ways to guarantee co-primality: make `m` prime and keep `0 < h2 < m`, or make `m` a power of two and force `h2` odd. - **`h2` should be independent of `h1`.** If the second hash is a simple transform of the first, keys colliding in `h1` collide in `h2` too and secondary clustering returns. - Each probe costs a second hash evaluation (or one extra derived value cached at insert time), and the walk jumps across memory instead of stepping through it — the cache-locality advantage of linear probing is gone. ### Choosing between them Picture a game server's connection table keyed by session identifiers, sized once at startup and held at moderate load. Quadratic probing is attractive there: no second hash to compute, no co-primality bookkeeping, decent spread — provided the fill level stays under the coverage guarantee and the table size is chosen to match the variant. Double hashing is the choice when the fill level must be allowed to run higher, or when session identifiers have structure that makes same-home-slot collisions common, because per-key strides make colliding keys diverge instead of trailing each other. The honest summary: **linear probing** has the best locality and the worst clustering; **quadratic probing** removes primary clustering for free but keeps secondary clustering and constrains size and fill; **double hashing** removes both kinds of clustering and pays with an extra hash and scattered memory access. All three are O(1) expected and O(n) worst case — the differences live entirely in the constants and in how fast those constants deteriorate as the table fills.

  • Why is a prime table size such a common recommendation for these schemes?
    Primality makes co-primality nearly free: if the table size is prime, any stride in the range 1 to m-1 is automatically co-prime with it, so a double-hashing walk always reaches every slot. It also underpins the classic quadratic-probing guarantee that at least half the slots are visited. A power-of-two size can work too, but then the stride must be forced odd.
  • Is secondary clustering actually a problem worth solving?
    Usually much less than primary clustering. Secondary clustering only entangles keys that genuinely share a home slot, and with a well-mixing hash those are rare. Primary clustering entangles unrelated keys through shared runs, which is why it compounds. Reach for per-key strides when collisions are common by construction — structured or adversarial keys — not as a reflex.
  • What goes wrong if the second hash can return zero?
    Every probe computes home + i*0, which is the home slot again, so the walk never advances. An insert loops until its probe counter hits the table size and then reports the table full, and a lookup inspects one slot and concludes the key is absent even when it sits three slots away. Implementations therefore constrain the stride into a nonzero range.

saying these in an interview costs you the question

  • Says quadratic probing eliminates all clustering
  • Allows a second-hash stride of zero
  • Assumes any probe sequence visits every slot
  • Derives the second hash from the first one
  • Ignores that double hashing gives up cache locality

context

resolving links…