304. Compare linear probing, quadratic probing and double hashing in open addressing. How does the load factor affect them?
MediumSymbol tables & hashing
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.