Skip to interview prep
Apexed

304. Compare linear probing, quadratic probing and double hashing in open addressing. How does the load factor affect them?

MediumSymbol tables & hashing

Technical
Show model answer

Open addressing stores entries directly in the array and, on a collision, probes a sequence of other slots. Linear probing tries h, h + 1, h + 2, …; it is very cache friendly but suffers primary clustering, where long runs of occupied slots grow and slow everyone down. Quadratic probing tries h + 1², h + 2², …, avoiding primary clustering but still causing secondary clustering (keys with the same home slot follow the same path); with a prime table size it is guaranteed to find a free slot only when the table is at most half full.

Double hashing uses a second hash for the step size, h₁(k) + i·h₂(k), so different keys follow different sequences; the step must be nonzero and coprime with the table size. For an unsuccessful search, expected probes are about 1/(1 − α) for well-distributed probing and about ½(1 + 1/(1 − α)²) for linear probing, so performance collapses as α nears 1. Keep α around 0.5–0.7 and resize early. Deletion needs tombstones (or backward-shift deletion for linear probing) so later searches do not stop too soon.

Compare linear probing, quadratic probing and double hashing in open addressing. How does the load factor affect them — Data structures & algorithms interview q