Universal hashing — probabilistic guarantee: Worked examples

Parent: Universal hashing — probabilistic guarantee

This page is a drill through every case universal hashing can throw at you. We do not introduce new theory — we exercise the theory of the parent note until no scenario surprises you. If a symbol here is not obvious, it was built in the parent; we re-anchor the important ones as we go.

Before anything, let us re-fix the two objects we compute with, in plain words:

The scenario matrix

Think of every problem as landing in exactly one cell. Here is the full grid we must cover.

Cell	Case class	What is special about it	Hit by
A	Normal load, $x$ not yet inserted	use $α = n / m$	Ex 1, Ex 3(cont.)
B	Normal load, $x$ already inserted	use $1 + (n - 1) / m$	Ex 2
C	Degenerate: empty table ( $n = 0$ )	limiting value $α = 0$	Ex 3
D	Degenerate: single key ( $n = 1$ ) & tiny table ( $m = 1$ )	boundary of the formula	Ex 3
E	Overloaded: $n ≫ m$ (rehash trigger)	$α > 1$ , cost still $O (1 + α)$	Ex 4
F	Compute $h_{a, b}$ — generic key	the two-mod pipeline	Ex 5
G	Compute $h_{a, b}$ — edge keys: $k = 0$ , $k = p$ , and $b = 0$	zero / wraparound inputs	Ex 5
H	Collision probability when $m ∣ p$ (exactly universal)	bound is exactly $1/ m$	Ex 6
I	Collision probability when $m ∤ p$ (almost universal)	bound is $1/ m + 1/ p$	Ex 6
J	Real-world word problem	choosing $m$ for a target cost	Ex 7
K	Exam twist: adversary + "why can't he win?"	conceptual, no arithmetic	Ex 8

Read the table top-to-bottom once. Every row below is a worked example that nails that cell.

Group 1 — Expected chain length (cells A–E)

The engine for all of these is one line from the parent, re-stated (recall $X$ from the definition above):

Figure — Universal hashing — probabilistic guarantee

The picture above shows the straight line $cost = 1 + α$ . Every example in this group is just one point on that line — look at where each lands.

Worked example Example 1 — Cell A (normal,

$x$ not inserted) Table $m = 100$ , already holding $n = 50$ keys. A brand-new key $x$ arrives. Expected keys already sitting in $x$ 's slot?

Forecast: guess before reading — is it above or below 1?

$x$ is not yet in the table, so we do not subtract a self-term. Why this step? The $(n - 1) / m$ formula subtracts $x$ 's comparison-with-itself, but that only makes sense when $x$ is already one of the $n$ stored keys. Here $x$ is a fresh arrival — it will become key number $n + 1$ once inserted — so all $n$ existing keys are genuine potential colliders and we use $n / m$ .
$E [X] \leq \frac{n}{m} = \frac{50}{100} = 0.5$ . Why? Direct load factor.
Search cost $= 1 + 0.5 = 1.5$ . Why? Add the mandatory look at the slot itself.

Verify: $α = 0.5 < 1$ , so cost $< 2$ — well under $O (n) = 50$ . Units: comparisons, dimensionless count. ✓

Worked example Example 3 — Cells C & D (degenerate: empty table; single key,

$m = 1$ ) Two sub-cases. (C) Empty table, $n = 0$ , insert first key $x$ . (D) One key already in, $n = 1$ , and a degenerate one-slot table $m = 1$ .

Forecast: In case D, everything hashes to slot 0. What can the average even be?

Case C:

$E [X] \leq \frac{n}{m} = \frac{0}{m} = 0$ . Why this step? No other keys exist to collide.
Cost $= 1 + 0 = 1$ . Why? You look at exactly one empty slot.

Case D ( $n = 1, m = 1$ ), searching the stored key $x$ :

Other colliders $\leq \frac{n - 1}{m} = \frac{0}{1} = 0$ . Why? There is no other key — $n - 1 = 0$ .
Cost $= 1 + 0 = 1$ . Why? The single slot holds only $x$ .

Continuation — this next part is a Cell A scenario (query with a new, not-yet-inserted key on a one-slot table). Insert a second key $y$ into that $m = 1$ table, then search for $y$ ; at query time $n = 1$ key is present and $y$ is the fresh arrival, so Cell A's $n / m$ applies: 3. $E [X] \leq \frac{n}{m} = \frac{1}{1} = 1$ . Why? Cell A formula with $n = 1, m = 1$ : the one existing key is guaranteed to share the only slot — probability 1, and $Pr \leq 1/ m = 1/1 = 1$ is (trivially) satisfied. 4. Cost $= 1 + E [X] = 1 + 1 = 2$ . Why? Keeping the pattern honest: you look at the single slot ( $+ 1$ ) and then scan the one stranger guaranteed to be there ( $+ 1$ ).

Verify: The bound $1/ m = 1$ with $m = 1$ says "collision certain", which matches reality — a one-slot table always collides, and the cost $2$ is exactly "look at slot, then walk past the one other key". The formula degrades gracefully across cells C, D, and A alike, never breaking. ✓

Group 2 — Computing $h_{a, b}$ (cells F–G)

Worked example Example 5 — Cells F & G (generic key + zero/wraparound edges)

Fix $p = 17$ , $m = 6$ , $a = 3$ , $b = 4$ .

Forecast: Which of these will land in slot 0?

(F) Generic $k = 10$ :

$ak + b = 3 \cdot 10 + 4 = 34$ . Why? Apply the affine map $ak + b$ .
$34 mod 17 = 0$ . Why? Inner mod $p$ : $34 = 2 \cdot 17 + 0$ .
$0 mod 6 = 0$ . Why? Squeeze into $[0, 6)$ . → $h (10) = 0$ .

(G1) Zero key $k = 0$ :

$a \cdot 0 + b = 0 + 4 = 4$ . Why? With $k = 0$ the key vanishes; only $b$ survives — this is exactly why $b$ exists (an offset so $k = 0$ isn't special).
$4 mod 17 = 4$ ; $4 mod 6 = 4$ . → $h (0) = 4$ .

(G2) Wraparound key $k = 17 = p$ (a key equal to the modulus):

$3 \cdot 17 + 4 = 55$ . Why? Same map; keys may exceed $p$ in edge tests.
$55 mod 17$ : $55 = 3 \cdot 17 + 4$ , so $= 4$ . Why? $k \equiv 0 (mod p)$ , so it behaves like $k = 0$ .
$4 mod 6 = 4$ . → $h (17) = 4$ . Note $h (17) = h (0)$ — a genuine collision, which is allowed; universality only bounds its probability.

(G3) Zero offset $b = 0$ , key $k = 10$ :

$3 \cdot 10 + 0 = 30$ ; $30 mod 17 = 13$ ; $13 mod 6 = 1$ . → $h (10) = 1$ when $b = 0$ .

Verify: All outputs lie in ${0, \dots, 5}$ ✓. And $h (0) = h (17) = 4$ because $0 \equiv 17 (mod 17)$ — consistent with the bijection being mod $p$ , so keys differing by a multiple of $p$ tie. ✓

Group 3 — Collision probability, both regimes (cells H–I)

This is the sharpest distinction on the page: exactly universal vs almost universal.

The figure below draws exactly this evenness argument. Each bar is a table slot; its height is how many of the $p$ residues ${0, \dots, p - 1}$ land in that slot after the outer $mod m$ . Read the left panel ( $m ∣ p$ ): all bars are the same height, so the buckets are perfectly balanced and the collision bound tightens to a clean $1/ m$ (green). Read the right panel ( $m ∤ p$ ): the bars are uneven — some reach $⌈ p / m ⌉$ , one is shorter — and that lopsidedness (orange) is precisely the gap that forces the extra $+ 1/ p$ . Look at how the tallest orange bar is one unit above the shortest: that single-unit imbalance is the " $1/ p$ ".

Worked example Example 6 — Cells H & I (both regimes side by side)

(H) $m ∣ p$ : choose $p = 5$ , $m = 5$ (a prime $p$ with $m ∣ p$ , indeed $m = p$ ).

$⌈ p / m ⌉ = ⌈ 5/5 ⌉ = 1$ . Why? Each slot gets exactly one residue.
Bound $= \frac{1 - 1}{p - 1} = \frac{0}{4} = 0 \leq \frac{1}{m} = \frac{1}{5}$ . Why? With $m = p$ the outer mod is a no-op bijection, so distinct residues never re-collide — collision prob from the outer mod is 0. Clean and exact. ✓ (Here $p$ is prime, as required, and $m ∣ p$ — both conditions hold together.)

(I) $m ∤ p$ : the parent's case $p = 17$ , $m = 6$ . $6 ∤ 17$ .

$⌈ 17/6 ⌉ = 3$ . Why? Residues ${0..16}$ split into slots of sizes $3, 3, 3, 3, 3, 2$ — uneven.
Tight bound $= \frac{3 - 1}{17 - 1} = \frac{2}{16} = 0.125 \leq \frac{1}{6} \approx 0.1667$ . Why? This is the tight per-pair bound; it is even below $1/ m$ .
Almost-universal quote $= \frac{1}{m} + \frac{1}{p} = \frac{1}{6} + \frac{1}{17} \approx 0.2255$ . Why? This is the commonly cited loose ceiling — a safe over-estimate. Note the tight $0.125$ sits comfortably under it.

Verify: For $p = 17, m = 6$ , brute-force over all valid $(a, b)$ (that's $16 \times 17 = 272$ functions) the empirical collision fraction for a fixed pair must sit $\leq \frac{2}{16} = 0.125$ (the tight bound), hence also $\leq 1/ m + 1/ p \approx 0.2255$ . The VERIFY block runs this exhaustively. ✓

Group 4 — Word problem & exam twist (cells J–K)

Worked example Example 7 — Cell J (real-world: sizing a table)

A web service caches $n = 1, 000, 000$ session tokens. Product wants average lookup $\leq 1.25$ comparisons. What load factor $α$ , and hence table size $m$ , achieves this with universal hashing?

Forecast: Bigger or smaller than a million slots?

Cost model: $1 + α \leq 1.25$ . Why this step? Expected search cost is $1 + α$ ; set it to the target.
Solve: $α \leq 0.25$ . Why? Subtract the mandatory $1$ .
$α = n / m \leq 0.25 \Rightarrow m \geq \frac{n}{0.25} = 4 n = 4, 000, 000$ . Why? Invert the load-factor definition.
Choose any convenient $m \geq 4, 000, 000$ (e.g. a power of two for cheap masking, or just $4, 000, 000$ ). Why? Universality only requires the prime $p$ (bigger than every key) to be prime; the table size $m$ need not be prime. Do not confuse the two moduli — $p$ is the universality engine, $m$ is just the range. See Modular arithmetic and primes.

Verify: With $m = 4, 000, 000$ , $α = 1 0^{6} /4 \cdot 1 0^{6} = 0.25$ , cost $= 1.25$ ✓ — exactly the target. Memory cost: 4× the entries, a standard space-time trade. ✓

Worked example Example 8 — Cell K (exam twist: why the adversary loses)

Statement: An adversary sees your source code, including the family $H_{p, m}$ and the values $p, m$ . He hands you keys before you run. Can he force $O (n)$ behaviour? Explain — no arithmetic.

Forecast: Does knowing the family help him?

He knows $H$ but not the specific $(a, b)$ you will roll at runtime. Why this step? The randomness lives in the choice of function, not the family (parent's core point). See Adversarial inputs and randomized algorithms.
For any fixed pair $x, y$ he submits, $Pr_{(a, b)} [h (x) = h (y)] \leq 1/ m + 1/ p$ . Why? This holds for every pair simultaneously — he cannot pick a pair that beats the bound, because all pairs obey it.
By Linearity of expectation over his $n$ keys, expected chain on any key is $\leq 1 + α$ regardless of which keys he chose. Why? Linearity needs no independence and no niceness of data.
Conclusion: he cannot force worst-case, because to do so he'd need to know $(a, b)$ , which is drawn after he commits his keys. Checkmate.

Verify: No number to plug — the check is logical: the bound quantifies over all key pairs, so an adversary's freedom in choosing keys is already covered. This is the whole reason universal hashing exists. ✓

Recall Self-test across the matrix

Cell A vs B — which uses $n / m$ ? ::: A (x not inserted) uses $n / m$ ; B (x already inserted) uses $(n - 1) / m$ . In Cell D ( $m = 1$ ), what is the collision probability bound, and does it break the theory? ::: $1/ m = 1$ — collision is certain, and this is correct: a one-slot table always collides. The formula degrades gracefully, never breaking. Cell E: does $α > 1$ break universality? ::: No; $Pr \leq 1/ m$ is untouched. Only the constant $1 + α$ grows; rehash to fix. Cell H vs I: when is the bound exactly $1/ m$ ? ::: Only when $m ∣ p$ ; otherwise carry $+ 1/ p$ (bound $1/ m + 1/ p$ ). Cell J: must the table size $m$ be prime? ::: No — only $p$ must be prime; $m$ can be any size (e.g. a power of two). Cell K: why can't the adversary win? ::: He commits keys before the random $(a, b)$ is chosen, and the bound holds for every pair.

Connections

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