47.05.01 · theoretical-cs / randomized-algorithms

Universal Hashing, Perfect Hashing, and the FKS Construction

shipped3 tiersLean: none

Anchor (Master): CLRS 2022 Introduction to Algorithms 4e (MIT Press) §11.3-11.5; Fredman, Komlos & Szemeredi 1984 (FKS construction with $O (1)$ worst-case lookup); Dietzfelbinger et al. 1994 (dynamic perfect hashing)

Intuition Beginner

A hash table maps keys to array positions using a hash function. A good hash function spreads keys evenly so that few keys land in the same slot (a collision). A bad hash function concentrates keys, causing many collisions and slow lookups.

The problem is: how do you guarantee a good hash function? If an adversary knows your hash function, they can choose keys that all collide. Universal hashing solves this by choosing the hash function at random from a carefully designed family. No matter what keys the adversary picks, a randomly chosen function from a universal family has low collision probability.

Think of it like seating guests at a dinner party. If you always seat people by last name, a family reunion would cluster everyone at one table. But if you assign seats by a random formula (say, "birthday mod number of tables"), then no group can guarantee they all sit together. Universal hashing is that random formula, with a mathematical guarantee that collisions are rare.

Perfect hashing goes further: for a fixed, known set of keys, it constructs a hash table with zero collisions and constant-time lookup. The FKS construction (named after Fredman, Komlos, and Szemeredi) achieves this in $O (n)$ space for $n$ keys.

Visual Beginner

Universal hashing: choosing a random function from a family:

Hash family H = {h_1, h_2, h_3, ...}
Keys: {Alice, Bob, Carol, Dave}

         h_1    h_2    h_3    h_4
Alice:    0      2      0      1
Bob:      1      0      2      3
Carol:    0      2      1      1      ← h_1: Alice & Carol collide
Dave:     2      1      0      0      ← h_3: Carol & Dave don't

Pick $h$ at random from $H$ . For any two distinct keys, the probability that they collide is at most $1/ m$ where $m$ is the table size.

Property	Universal hash	Fixed hash
Collision probability	$\leq 1/ m$ for any pair	Depends on input
Adversary resistance	No input causes many collisions	Adversary can force collisions
Choice	Random from family	Deterministic
Expected chain length	$\leq n / m$ (load factor)	Unbounded in worst case

Worked example Beginner

A universal hash family for keys that are integers in ${0, 1, \dots, p - 1}$ (where $p$ is a prime larger than any key) and a hash table of size $m$ :

h_{a, b} (x) = ((a x + b) mod p) mod m

where $a \in {1, 2, \dots, p - 1}$ and $b \in {0, 1, \dots, p - 1}$ are chosen uniformly at random.

Let $p = 17$ and $m = 6$ . Pick $a = 3, b = 7$ . Compute $h_{3, 7} (5) = ((3 \cdot 5 + 7) mod 17) mod 6 = 22 mod 17 mod 6 = 5 mod 6 = 5$ . Compute $h_{3, 7} (11) = ((3 \cdot 11 + 7) mod 17) mod 6 = 40 mod 17 mod 6 = 6 mod 6 = 0$ . No collision.

Pick different parameters: $a = 5, b = 2$ . $h_{5, 2} (5) = ((27) mod 17) mod 6 = 10 mod 6 = 4$ . $h_{5, 2} (11) = ((57) mod 17) mod 6 = 6 mod 6 = 0$ . Still no collision.

The collision probability for any pair of distinct keys is at most $1/ m = 1/6$ , regardless of which keys are chosen.

Check your understanding Beginner

Formal definition Intermediate+

Definition (universal hash family). Let $U$ be a universe of keys and $m$ a positive integer. A family $H$ of hash functions from $U$ to ${0, 1, \dots, m - 1}$ is universal if for every pair of distinct keys $x, y \in U$ with $x \neq = y$ :

\frac{∣ { h \in H : h ( x ) = h ( y )} ∣}{∣ H ∣} \leq \frac{1}{m} .

Equivalently, if $h$ is chosen uniformly at random from $H$ :

h \in H Pr [h (x) = h (y)] \leq \frac{1}{m} .

The family is strongly universal (or pairwise independent) if for all $x \neq = y$ and all $i, j \in {0, \dots, m - 1}$ :

h \in H Pr [h (x) = i \land h (y) = j] = \frac{1}{m ^{2}} .

Definition ( $k$ -universal). A family $H$ is $k$ -universal if for any $k$ distinct keys $x_{1}, \dots, x_{k}$ and any values $v_{1}, \dots, v_{k}$ :

h \in H Pr [h (x_{1}) = v_{1} \land \dots \land h (x_{k}) = v_{k}] = \frac{1}{m ^{k}} .

Theorem (collision bound for universal hashing). If $h$ is chosen from a universal family $H$ and $n$ keys are stored in a table of size $m$ , then for any key $x$ , the expected number of other keys colliding with $x$ is at most $n / m$ (the load factor $α$ ).

Proof. Let $S$ be the set of $n$ stored keys. For a query key $x \in / S$ , the number of collisions is $\sum_{y \in S} 1 [h (x) = h (y)]$ . By linearity of expectation: $E [collisions] = \sum_{y \in S} Pr [h (x) = h (y)] \leq n \cdot (1/ m) = n / m$ . $□$

Counterexamples to common slips

"Universal hashing prevents all collisions." No. It bounds the expected number of collisions; individual pairs can still collide. Perfect hashing (FKS) is needed for zero collisions.
"A universal hash family must be large." The family $h_{a, b} (x) = ((a x + b) mod p) mod m$ has only $p (p - 1)$ functions, which is polynomial in the key range. Universality does not require an exponentially large family.
"Strongly universal implies universal." It does: strong universality gives $Pr [h (x) = h (y)] = \sum_{i} Pr [h (x) = i \land h (y) = i] = m \cdot (1/ m^{2}) = 1/ m$ , which satisfies the universal bound with equality.

Key theorem with proof Intermediate+

Theorem (FKS construction). Given a static set $S$ of $n$ keys, the FKS scheme constructs a hash table using $O (n)$ space with $O (1)$ worst-case lookup time. The construction succeeds with high probability.

Proof. Top level: choose a universal hash function $h$ mapping keys to $m = n$ slots. Let $n_{i}$ be the number of keys landing in slot $i$ . By universality, $E [n_{i}] = 1$ for each $i$ (if the load is balanced). The total space for second-level tables is $\sum_{i} n_{i}^{2}$ . By linearity of expectation:

E [i \sum n_{i}^{2}] = E [i \sum n_{i}] + 2 E [i \sum (2 n _{i})] = n + 2 \cdot (total collisions) .

The total collisions are $\sum_{x \neq = y \in S} Pr [h (x) = h (y)] \leq (2 n) / m = n (n - 1) / (2 n) < n /2$ . So $E [\sum n_{i}^{2}] < n + n = 2 n = O (n)$ .

By Markov's inequality, $Pr [\sum n_{i}^{2} > 4 n] < 1/2$ . So a random $h$ gives total second-level space at most $4 n$ with probability at least $1/2$ . Repeat until this holds.

Second level: for each slot $i$ with $n_{i}$ keys, choose a universal hash function $h_{i}$ mapping to $m_{i} = n_{i}^{2}$ slots. By the birthday paradox, the collision probability for any pair is $\leq 1/ n_{i}^{2}$ , so the expected number of collisions is $(2 n _{i}) / n_{i}^{2} < 1/2$ . Markov gives: $Pr [any collision] < 1/2$ . Repeat until collision-free.

Lookup: compute $j = h (x)$ , then $h_{j} (x)$ . Two hash computations, $O (1)$ . $□$

Bridge. Universal hashing is the foundational reason hash tables achieve $O (1)$ expected performance without assumptions about the input distribution: random choice from a structured family ensures that no adversary can force pathological behaviour. This builds toward the randomised algorithms of 47.05.02 where randomisation provides similar adversarial robustness for sorting and searching, and it appears again in 47.05.03 where Miller-Rabin primality testing uses random witnesses with the same collision-probability argument. The central insight is that the pairwise independence property of universal hash families gives strong concentration bounds on the number of collisions, and putting these together with the two-level FKS construction yields $O (1)$ worst-case lookups in $O (n)$ space — the static equivalent of an ideal hash table.

Exercises Intermediate+

Exercise 8 (hard, short answer).

A $k$ -universal hash family generalises universality from pairs to $k$ -tuples. Show that a 2-universal family is also universal, but a universal family need not be 2-universal.

Answer

2-universal implies universal: for $x \neq = y$ and any $i$ , $Pr [h (x) = i \land h (y) = i] = 1/ m^{2}$ . Summing over $i$ : $Pr [h (x) = h (y)] = m \cdot (1/ m^{2}) = 1/ m$ . So the collision probability is exactly $1/ m \leq 1/ m$ . Universal does not imply 2-universal: the family $h_{a, b} (x) = ((a x + b) mod p) mod m$ is universal but not necessarily 2-universal. A universal family only constrains pairwise collisions, not the joint distribution of $h (x)$ and $h (y)$ . For example, the family of all constant functions (every $h$ maps all keys to the same slot) has $Pr [h (x) = h (y)] = 1 \leq 1/ m$ only when $m = 1$ , but for $m > 1$ it is not universal. A more careful example: take $H = {h_{0}, h_{1}}$ where $h_{0}$ maps all even keys to 0 and all odd to 1, and $h_{1}$ maps all keys to 0. Then $Pr [h (x) = h (y)] = 1/2$ for $m = 2$ , satisfying universality, but $Pr [h (0) = 0 \land h (1) = 0] = 1/2 \neq = 1/4 = 1/ m^{2}$ , violating 2-universality.

Lean formalization Intermediate+

Mathlib has basic hash table infrastructure but no universal hash family definition, no collision probability bounds, and no FKS construction. The formal definition of universality as $Pr [h (x) = h (y)] \leq 1/ m$ and the construction of concrete universal families (the $h_{a, b}$ family over prime fields) are absent. A Codex.Algorithms.Hashing module defining universal hash families with collision probability proofs and the FKS space bound would be the foundational target; this unit ships without it.

Advanced results Master

Theorem 1 (cuckoo hashing). For dynamic sets, cuckoo hashing (Pagh and Rodler, 2004) achieves $O (1)$ worst-case lookup using two hash functions $h_{1}, h_{2}$ and two tables. Each key $x$ is stored in either table 1 at position $h_{1} (x)$ or table 2 at position $h_{2} (x)$ . Lookup checks both locations. Insertion may require relocating existing keys, and fails (requiring rehash) if a cycle forms. For load factor $α < 1/2$ , the expected insertion time is $O (1)$ and the failure probability is exponentially small.

Theorem 2 (power of two choices). If each key is hashed to $d \geq 2$ random locations and placed in the least loaded, the maximum load drops from $Θ (lo g n / lo g lo g n)$ (for $d = 1$ ) to $Θ (lo g lo g n)$ ^{[CLRS §11.3]}. This "power of two choices" phenomenon has far-reaching consequences in load balancing and parallel computing.

Theorem 3 (dynamic perfect hashing). Dietzfelbinger et al. (1994) extended FKS to dynamic sets, supporting insertions and deletions while maintaining $O (1)$ worst-case lookup and $O (n)$ space. The amortized insertion and deletion cost is $O (1)$ with high probability. The key idea is to rebuild the second-level tables incrementally when a slot grows beyond its allocated size.

Synthesis. Universal hashing is the foundational reason hash tables achieve robust $O (1)$ expected performance: the pairwise independence property bounds collision probability regardless of the input distribution, and the FKS construction extends this to $O (1)$ worst-case performance for static sets. The central insight is that random choice from a structured algebraic family (linear functions over finite fields) gives the same probabilistic guarantees as a truly random function, and putting these together with the two-level construction of FKS yields a data structure whose space and time are simultaneously optimal. This builds toward the randomised algorithms of 47.05.02 where random choices from structured families provide adversarial robustness in sorting and searching, and appears again in 47.03.01 where the BPP class captures the same principle at the complexity-theoretic level: random choices from polynomial-size families suffice for efficient computation.

Full proof set Master

Proposition 1 (collision bound). If $h$ is chosen from a universal family mapping to ${0, \dots, m - 1}$ and $n$ keys are stored, then for any key $x$ , the expected number of collisions with $x$ is at most $n / m$ .

Proof. $E [\sum_{y \in S, y \neq = x} 1 [h (x) = h (y)]] = \sum_{y \neq = x} Pr [h (x) = h (y)] \leq (n - 1) / m \leq n / m$ . $□$

Proposition 2 (FKS space bound). In the FKS construction with top-level table size $m = n$ , the expected total second-level space is at most $2 n$ .

Proof. $E [\sum_{i} n_{i}^{2}] = E [\sum_{i} n_{i} + 2 (2 n _{i})] = n + 2 \sum_{x \neq = y} Pr [h (x) = h (y)] \leq n + 2 (2 n) / m \leq n + n = 2 n$ . $□$

Proposition 3 (second-level success probability). For a slot with $n_{i}$ keys and second-level table size $m_{i} = n_{i}^{2}$ , a randomly chosen universal hash function is collision-free with probability at least $1/2$ .

Proof. The expected number of collisions is $(2 n _{i}) / n_{i}^{2} = n_{i} (n_{i} - 1) / (2 n_{i}^{2}) < 1/2$ . By Markov's inequality, $Pr [at least 1 collision] < 1/2$ , so $Pr [collision-free] \geq 1/2$ . $□$

Connections Master

37.01.01 — Probability spaces and expectation provide the mathematical foundation for bounding collision probabilities; linearity of expectation is the main tool.
46.01.02 — Mutual information and entropy quantify the randomness in hash function output; the entropy of the hash function choice determines the collision probability.
47.05.02 — Randomised quicksort and treaps use random choices from structured families for adversarial robustness, paralleling universal hashing.
47.03.01 — BPP captures the complexity-theoretic version of the same principle: random choice from polynomial-size families enables efficient computation with bounded error.

Historical & philosophical context Master

Universal hashing was introduced by Larry Carter and Mark Wegman in their 1979 paper "Universal Classes of Hash Functions" ^{[CLRS §11.3]}. Their key insight was that a randomly chosen hash function from a carefully designed algebraic family provides the same probabilistic guarantees as a truly random function, while being efficiently computable. The $h_{a, b} (x) = ((a x + b) mod p) mod m$ construction is their most famous example.

The FKS construction was introduced by Michael Fredman, Janos Komlos, and Endre Szemeredi in 1984, proving that static hash tables can achieve $O (1)$ worst-case lookup in $O (n)$ space — resolving a question that had been open since the invention of hash tables. The result was surprising because it showed that perfect hashing does not require quadratic space.

Cuckoo hashing was introduced by Rasmus Pagh and Flemming Rodler in 2004, extending the FKS ideas to dynamic sets with $O (1)$ worst-case lookups. The name comes from the cuckoo bird's habit of pushing eggs out of other birds' nests, mirroring the algorithm's eviction strategy.

Bibliography Master

@book{clrs2022,
  author    = {Cormen, T. H. and Leiserson, C. E. and Rivest, R. L. and Stein, C.},
  title     = {Introduction to Algorithms},
  edition   = {4th},
  publisher = {MIT Press},
  year      = {2022},
}
@article{carter1979universal,
  author  = {Carter, J. Lawrence and Wegman, Mark N.},
  title   = {Universal Classes of Hash Functions},
  journal = {Journal of Computer and System Sciences},
  volume  = {18},
  number  = {2},
  pages   = {143--154},
  year    = {1979},
}
@article{fredman1984storing,
  author  = {Fredman, Michael L. and Koml{\'o}s, J{\'a}nos and Szemer{\'e}di, Endre},
  title   = {Storing a Sparse Table with $O(1)$ Worst Case Access Time},
  journal = {Journal of the ACM},
  volume  = {31},
  number  = {3},
  pages   = {538--544},
  year    = {1984},
}
@article{pagh2004cuckoo,
  author  = {Pagh, Rasmus and Rodler, Flemming Friche},
  title   = {Cuckoo Hashing},
  journal = {Journal of Algorithms},
  volume  = {51},
  number  = {2},
  pages   = {122--144},
  year    = {2004},
}

Prerequisites

37.01.01
46.01.02

Tier anchors

beginner: CLRS 2022 Introduction to Algorithms 4e (MIT Press) §11.3-11.4 (hash functions that spread keys evenly, avoiding worst-case collisions by random choice)
intermediate: CLRS 2022 Introduction to Algorithms 4e (MIT Press) §11.3-11.5 (universal hash families, collision probability bounds, perfect hashing via the FKS construction)
master: CLRS 2022 Introduction to Algorithms 4e (MIT Press) §11.3-11.5; Fredman, Komlos & Szemeredi 1984 (FKS construction with $O (1)$ worst-case lookup); Dietzfelbinger et al. 1994 (dynamic perfect hashing)

References

Cormen, T. H., Leiserson, C. E., Rivest, R. L. & Stein, C. — Introduction to Algorithms (4th ed.) · MIT Press (2022). Section 11.3 defines a universal hash family $H$ as a collection of hash functions $h : U \to {0, 1, \dots, m - 1}$ such that for any two distinct keys $x \neq = y$ in the universe $U$ : $∣ {h \in H : h (x) = h (y)} ∣ \leq ∣ H ∣/ m$ ; equivalently $Pr_{h \in H} [h (x) = h (y)] \leq 1/ m$ . Theorem 11.2 proves that for a universal hash family and $n$ keys in a table of size $m$ , the expected number of collisions for any key is at most $n / m$ (the load factor). Section 11.5 presents the FKS construction: choose a top-level universal hash function $h$ with $m = n^{2}$ slots; by the Markov bound, $Pr [more than n collisions in any slot] < 1/2$ , so a random $h$ gives at most $n$ collisions per slot with constant probability; then within each slot of size $n_{i}$ , use a second-level perfect hash table of size $n_{i}^{2}$ , chosen randomly until collision-free. Total space: $O (n)$ , worst-case lookup: $O (1)$ .
Fredman, M. L., Komlos, J. & Szemeredi, E. — Storing a Sparse Table with O(1) Worst Case Access Time · Journal of the ACM 31(3) (1984) 538-544. The original FKS paper proves that a static set of $n$ keys can be stored in $O (n)$ space with $O (1)$ worst-case lookup time, using a two-level hashing scheme where the top level hashes into $O (n)$ bins and each bin uses a quadratic-space collision-free hash table. The construction succeeds with high probability and can be derandomised.

Estimated time

beginner: 15m
intermediate: 40m
master: 75m