Universal hashing — probabilistic guarantee: Visual walkthrough

We start with zero notation. We will earn each piece.

Step 1 — The table is a row of buckets

Figure — Universal hashing — probabilistic guarantee

Look at the figure. Three keys ( $x$ , $y_{1}$ , $y_{2}$ ) each get an arrow into a box. Two of them landed in the same box — that shared box is a collision. Collisions are the enemy: a box with several keys forces us to walk down a little list (a chain) to find ours.

Small $X$ means fast lookup. So the whole page is: find the typical size of $X$ .

Step 2 — Randomness lives in $h$ , not in the keys

The fix, drawn below: we roll dice to choose $h$ from a whole bag of hash functions (a family $H$ ), and we roll after the bully has committed to the keys — and secretly.

This is why we can beat any input: the bully cannot aim at randomness he has not seen. See Adversarial inputs and randomized algorithms.

Step 3 — The universal promise, as a coin-flip per pair

Definition Where the tiny wrinkle comes from — meet the prime

$p$ To build an actual universal bag, the standard recipe (parent note) first stretches every key through a large prime number $p$ — a whole number, bigger than any key, divisible only by $1$ and itself (see Modular arithmetic and primes). The rule is $h (k) = ((ak + b) mod p) mod m$ : first fold the key down into the range $0.. p - 1$ using $p$ , then squeeze into our $m$ boxes.

$p$ ::: the big prime "workbench" the recipe computes on — a fixed, publicly known number, not the number of boxes.
The final $mod m$ ::: the last squeeze into the $m$ real boxes.

WHY $\leq$ and not $=$ ? Those $p$ intermediate values get chopped into $m$ boxes. Unless $m$ divides $p$ evenly ( $m ∣ p$ ), some boxes catch one more value than others, so collisions can be a hair above $1/ m$ . The honest bound is $\leq \frac{1}{m} + \frac{1}{p}$ ; since $p$ is astronomically large, the extra $\frac{1}{p}$ is invisible. On this page we simply use the clean bound $\leq \frac{1}{m}$ .

Step 4 — Turn "count" into 0/1 switches

The figure shows a row of light bulbs, one per key. Lit bulbs (value $1$ ) are the collisions; counting lit bulbs = the value of $X$ . Nothing clever yet — we just renamed the count. The payoff comes next.

Step 5 — Each switch's average is its collision probability

Step 6 — Add the averages (linearity of expectation)

Step 7 — Name the load, read off $O (1)$

Combine with Step 6:

$avg others in x ’s box E [X] \leq \frac{n - 1}{m} < \frac{n}{m} = α \Rightarrow walk the chain expected search = 1 + E [X] = O (1 + α)$

The $+ 1$ is $x$ itself (we always touch our own box). See Load factor and rehashing.

Step 8 — The degenerate cases (never leave the reader stranded)

Worked example All the edge cases, one by one

$n = 0$ or $n = 1$ ::: no other keys, so $\sum_{y \neq = x}$ is an empty sum $= 0$ . $E [X] = 0$ , cost $= 1$ . The formula $\frac{n - 1}{m}$ gives $\leq 0$ — consistent (an "at most" of $0$ ).
$x$ already inserted ::: then $x$ is one of the $n$ keys, so only $n - 1$ others can collide — exactly the $\frac{n - 1}{m}$ we derived.
$x$ not yet inserted ::: all $n$ stored keys are "others", so use $\frac{n}{m} = α$ . (One larger, negligible difference.)
$α ≫ 1$ (overloaded table) ::: the bound still holds — cost is $O (1 + α)$ , which is now large. Universal hashing does not magically fix an under-sized table; it fixes the adversary, not the load. Cure the load by rehashing into a bigger $m$ .
$m ∤ p$ (boxes don't split the prime evenly) ::: boxes slightly uneven; bound loosens to $\frac{1}{m} + \frac{1}{p}$ per pair (Step 3's prime $p$ ). Since $p$ is enormous, $\frac{1}{p}$ is invisible. Guarantee survives.

The one-picture summary

One flow, left to right: random $h$ → per-pair collision $\leq \frac{1}{m}$ → switch $X_{x y}$ with average $\leq \frac{1}{m}$ → add $n - 1$ of them via linearity → $E [X] \leq \frac{n - 1}{m}$ → cost $O (1 + α)$ .

Recall Feynman: the whole walk in plain words

We have a wall of numbered boxes and we want to drop our key into one and later find it fast. Trouble: a bully picks keys on purpose to jam one box. Our escape is to roll dice and pick our sorting-rule from a bag — and we roll secretly, so the bully can't aim. The bag is "fair" (universal) if any two keys the bully names only crash into the same box about one time in $m$ . Now, to count how many keys crash into our box, we put a light bulb on every other key: lit if it crashes into us, dark otherwise. The number of lit bulbs is our slowdown. The average brightness of one bulb is just its crash chance, $\leq \frac{1}{m}$ . And here's the magic: the average of the whole wall of bulbs is just the sum of each bulb's average — this is true even though all the bulbs are wired to the same dice. Add up $n - 1$ bulbs at $\frac{1}{m}$ each and you get at most $\frac{n - 1}{m}$ . Keep the wall about as wide as the pile of keys and that number is a constant — so every lookup is fast, no matter what the bully does.

Connections

Universal hashing — probabilistic guarantee (parent)
Linearity of expectation
Modular arithmetic and primes
Adversarial inputs and randomized algorithms
Hashing — chaining vs open addressing
Load factor and rehashing
Perfect hashing (FKS) — uses universal hashing as a building block

Visual walkthrough — Universal hashing — probabilistic guarantee