Symptom

Your service went down under a hash collision attack.

Somebody noticed your web framework put POST parameters into a hash table, found thousands of distinct keys colliding under its hash function, and posted a form with 20,000 of them. Every insert walked a chain. Quadratic behaviour, one CPU pinned per request, service dead. This actually happened, across PHP, Python, Ruby, Java and .NET in 2011, and again against Rust’s default HashMap before it switched to SipHash.

Your hash function was fine. It distributed real-world keys beautifully. That was never the property you needed.

What does a hash function actually guarantee? “Looks random” is not a guarantee, because an adversary — or an unlucky workload — gets to pick the keys after seeing your function. The fix is not a better function. It is a different kind of promise.

Statement

A family $\mathcal{H}$ of functions from universe $U$ to ${0,\dots,m-1}$ is universal if for every pair of distinct keys $x \ne y$,

$$\Pr_{h \in \mathcal{H}}[h(x) = h(y)] \le \frac{1}{m}$$

where the probability is over the random choice of $h$ from the family, not over the keys. That inversion is the entire idea.

$\mathcal{H}$ is pairwise independent (or strongly universal) if for distinct $x, y$ and any values $a, b$,

$$\Pr_{h}[h(x) = a \wedge h(y) = b] = \frac{1}{m^2}$$

which is stronger: not only are collisions rare, any two keys land independently.

Carter–Wegman construction. Pick a prime $p > |U|$ and choose $a \in {1,\dots,p-1}$, $b \in {0,\dots,p-1}$ uniformly:

$$h_{a,b}(x) = ((ax + b) \bmod p) \bmod m$$

This family is universal, and pairwise independent when $m = p$.

Consequence. With $n$ keys in $m$ buckets, the expected chain length for any key is at most $1 + n/m$. For every input, including adversarial ones, because the randomness is yours and the adversary cannot see your choice of $h$.

Argument

Why the guarantee has to be over $h$. Fix any single hash function $h: U \to [m]$. Since $|U| \gg m$, some bucket receives at least $|U|/m$ keys by pigeonhole. An adversary enumerates them and sends those. No fixed function escapes; the only defence is that the adversary does not know which function you picked.

Universality of $h_{a,b}$. Work in $\mathbb{Z}_p$, a field since $p$ is prime. Fix $x \ne y$ and let

$$r = (ax + b) \bmod p, \qquad s = (ay + b) \bmod p$$

First, $r \ne s$: their difference is $a(x-y) \bmod p$, and in a field a product of nonzero elements is nonzero, since $a \ne 0$ and $x \ne y$. So there are no collisions before the final mod $m$.

Second, the map $(a,b) \mapsto (r,s)$ is a bijection from the $p(p-1)$ valid pairs onto the $p(p-1)$ pairs with $r \ne s$. Given any such $(r,s)$, solve: $a = (r-s)(x-y)^{-1}$ and $b = r - ax$, both uniquely determined in the field. So $(r,s)$ is uniform over distinct pairs.

Now collisions can only come from the final $\bmod, m$. Given $r$, how many $s \ne r$ have $s \equiv r \pmod m$? At most $\lceil p/m \rceil - 1 \le (p-1)/m$. Dividing by the $p-1$ available values of $s$:

$$\Pr[h(x) = h(y)] \le \frac{(p-1)/m}{p-1} = \frac{1}{m}$$

Universal. Two facts did the work: a field has no zero divisors, and an affine map with nonzero slope is a bijection.

From the pair bound to chain length. This is where linearity of expectation (T007) makes the analysis trivial. Fix a key $x$ and a set $S$ of $n$ keys. Let $C_y = 1$ if $y \ne x$ collides with $x$. Then

$$\mathbb{E}[\text{chain length at } x] = 1 + \sum_{y \in S, y \ne x} \Pr[h(y) = h(x)] \le 1 + \frac{n}{m}$$

No independence between different $C_y$ is needed, because expectation is linear regardless. Universality alone, a statement about pairs, gives the bound you actually want, a statement about a whole table. With $m \ge n$ the expected chain is under 2 and hash table operations are $O(1)$ expected — for every input.

Randomize the algorithm, not the assumption. The classical analysis assumes keys are random. Carter and Wegman assume nothing about keys and make the algorithm random. This is the same move as randomized quicksort: it converts “fast on typical inputs” into “fast on every input, with high probability over my own coins,” which is a guarantee an adversary cannot attack.

What stronger independence buys. Pairwise independence is what Chebyshev-based variance arguments need, so 2-universal families are exactly right for sketching. Count-Min needs pairwise; higher moment estimators need 4-wise. The hierarchy is not academic: each level costs more and unlocks a specific concentration inequality, and picking the level is a real design decision in T105’s sketches.

A worked collision count. Take $p = 2{,}147{,}483{,}647$ (a Mersenne prime, $2^{31}-1$, which makes the modulus cheap) and $m = 2^{20}$ buckets holding a million keys. Universality says any specific pair collides with probability at most $2^{-20}$. The expected number of colliding pairs among $n = 10^6$ keys is at most $\binom{10^6}{2} \cdot 2^{-20} \approx 4.77 \times 10^{5}$, so about half a million colliding pairs — which sounds alarming until you notice it is spread over a million buckets, giving the expected chain length just under 2 that the theorem promised. The pair count is large and the per-key cost is constant, and confusing those two quantities is how people talk themselves out of a correct data structure.

Forbids

Any fixed hash function with worst-case guarantees. By pigeonhole. If your function is public and deterministic, adversarial inputs exist and can be found.

Assuming your keys are random. They are usernames, URLs, sequential IDs and attacker-chosen strings. The uniformity assumption is not a technicality that usually holds; it is false in production.

Ignoring the seed. A universal family used with a constant seed is a fixed function, and provides nothing. Seeding per process from a real source is the whole mechanism.

Believing collisions can be eliminated. With $|U| > m$ they are forced. The guarantee is on their rate, not their existence.

Does not forbid

It does not mean non-universal hashing is wrong in practice. MurmurHash3, xxHash and FNV are not universal families and are used everywhere, correctly, because they are far faster and most workloads are not adversarial. Google’s Abseil and Rust’s hashbrown use fast non-cryptographic hashes with randomized seeds — the seed is doing the security work, and the hash is doing the speed work. That split is the actual engineering answer.

It does not require cryptographic strength. SipHash-1-3, the default in Rust and Python since 3.4, is a keyed PRF rather than a Carter–Wegman family, and it is chosen because it resists key recovery at a few cycles per byte. Universality gives collision-probability bounds; a keyed PRF gives a stronger practical property at comparable cost. Both solve the 2011 attack; neither is the unique answer.

It does not make expected-case bounds worst-case. The $1 + n/m$ chain is an expectation. Some chains will be longer — the maximum is $\Theta(\log n / \log\log n)$ under full randomness (T009). Cuckoo hashing and perfect hashing exist precisely because expectation is sometimes not enough.

It does not mean you need pairwise independence for hash tables. Plain universality suffices for chaining, and linear probing needs 5-independence for its classical bound, though tabulation hashing gets there cheaply. Reaching for the strongest family available is a common and costly mistake.

It does not stop hash flooding on its own if the seed leaks. Timing side-channels can reveal seeds. This is why Python randomizes per process and why long-lived servers with observable timing still need rate limiting. The theorem protects against key-guessing, not against key-learning.

Boundary

  • Perfect hashing (FKS). For a static key set, two levels of universal hashing give worst-case $O(1)$ lookup in $O(n)$ space, with the second-level table for a bucket of size $b$ sized $b^2$ so it is collision-free with probability at least 1/2. Static sets escape the expectation entirely.
  • Cuckoo hashing. Two functions, two candidate slots, worst-case $O(1)$ lookup with amortized expected $O(1)$ insert. The trade is rehashing on failure, which universality bounds.
  • Tabulation hashing. XOR precomputed random tables indexed by each byte. Only 3-independent, yet it behaves like full randomness for linear probing, min-wise hashing and Chernoff-type bounds, and it is faster than multiply-shift. The best speed-to-guarantee ratio available.
  • Multiply-shift. $h(x) = (ax \bmod 2^{w}) \gg (w - \ell)$ with odd $a$ is 2-universal up to a factor of 2 and needs one multiply and one shift, no division and no prime. This is what production code should use when it wants a provable family.
  • The seed has to come from somewhere. A universal family is only as good as the randomness selecting from it. Python seeds from os.urandom at interpreter start, Rust’s RandomState draws from the OS per HashMap instance, and a hardcoded seed in a config file silently reverts you to a fixed function with none of the guarantees. This is the commonest way the protection is lost in practice, and it is invisible in testing.
  • Where this feeds forward. Bloom filters (T073), Count-Min and HyperLogLog (T105) all assume a hash family with a stated independence level. Their error bounds are theorems about that assumption, so knowing which level you have is the difference between a proved bound and a hope.