5. The Power of Two Choices

A second, unrelated way to exploit having two hash functions — the last hashing topic of the course (43:34, 44:13).

Baseline: hashing with chaining / balls into bins

Hash table of m cells, each cell a pointer to a doubly linked list of the items hashing there (44:37).
Query time = length of that list (46:53).
With m = n and a perfectly random h, this is n balls into n bins; the heaviest bin holds Θ(log n / log log n) balls — better than log n, but not much better (45:14, 46:26).
With a merely 2-wise independent h, expected query time is O(1), and w.h.p. the worst case is at most log n / log log n (46:53, 47:10).
Goal: keep the constant expectation and get a much better worst case (47:10).

Pick two random hash functions g and h.
Insert x: place it in the least loaded of A[g(x)] and A[h(x)].
Query x: search both locations (48:45).
In balls-and-bins terms: sample two bins per ball, drop it into the smaller (48:45).

W.h.p. the heaviest bin has ln ln n / ln 2 + Θ(1) items (49:39).
The distribution is tightly concentrated: that value ± a constant (50:23).
This is an exponential improvement — roughly log n down to log log n — from a trivially simple change (50:23).

Natural extension: hash to d locations, insert into the least loaded; query cost rises by a factor of d in expectation (50:52).
Result: ln ln n / ln d (51:17).
The jump is all in the first extra choice: 1 → 2 goes log → log log; 2 → d only changes the base of the log, i.e. a constant factor (51:17, 51:57).

Stated without proof (52:19, 52:40):

Split the bins into d groups of n/d bins each.
Probe one random location per group (not d free random locations) (53:25).
Insert into the least loaded, breaking ties by taking the leftmost bin — counter-intuitively not a random tie-break (53:25, 54:12).

Heaviest load becomes ln ln n / d, with the exact constant proved (54:44).
Interpretation: the effective log base goes from d to e^d — an exponential gain over plain power-of-d, purely from the group structure plus the deterministic tie-break (54:44, 55:10).

Scheme	Max load w.h.p.
1 choice (plain chaining)	`Θ(log n / log log n)` (`46:26`)
2 choices	`ln ln n / ln 2 + Θ(1)` (`49:39`)
`d` choices	`ln ln n / ln d` (`51:17`)
Vöcking (`d` groups, leftmost tie-break)	`ln ln n / d` (`54:44`)