Universal Hashing

The Problem with Fixed Hash Functions

Any fixed hash function $h$ can be adversarially exploited. If an attacker knows (or reverse-engineers) the hash function, they can craft a set of keys that all map to the same slot:

$h(k_1) = h(k_2) = \cdots = h(k_n) = s$

The result: chaining degrades to a linked list of length $n$, or open addressing probes through all slots. All operations become $\Theta(n)$. This is not just a theoretical concern: it has been used in denial-of-service attacks against web frameworks and network infrastructure.

Randomising the input data or picking a random pivot (as in quicksort) reduces the probability of hitting the worst case, but for hash tables a stronger guarantee exists.

Universal Families of Hash Functions

Universal hashing: the hash function is chosen randomly at runtime from a family $\mathcal{H}$ of hash functions. The family is designed so that, regardless of which keys the adversary provides, the probability of collision between any two distinct keys is bounded.

Definition: A family $\mathcal{H}$ of functions mapping $U$ to $\{0, 1, \ldots, m-1\}$ is universal if, for any distinct $k_1, k_2 \in U$:

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

The probability is taken over the random choice of $h$ from $\mathcal{H}$, not over the choice of keys. The keys can be chosen adversarially after $\mathcal{H}$ is known; the guarantee still holds.

A Concrete Universal Family

Choose a prime $p > |U|$ (larger than any possible key value). Define:

$h_{a,b}(k) = ((ak + b) \bmod p) \bmod m$

where $a \in \{1, 2, \ldots, p-1\}$ and $b \in \{0, 1, \ldots, p-1\}$ are chosen uniformly at random. The family $\mathcal{H}_{p,m} = \{h_{a,b}\}$ is universal.

Proof sketch: For any $k_1 \neq k_2$, the values $(ak_1 + b) \bmod p$ and $(ak_2 + b) \bmod p$ are uniformly distributed and pairwise independent over $\{0, \ldots, p-1\}$. The probability they collide modulo $m$ is at most $1/m$.

Why Universal Hashing Works

With a universal family and chaining, the expected search time is $O(1 + \alpha)$ even against an adversary. The adversary can choose keys knowing the family $\mathcal{H}$ but not which $h \in \mathcal{H}$ will be chosen at runtime.

The proof: for any search key $k$, the expected number of other keys in the same chain is:

$\mathbb{E}[\text{collisions}] = \sum_{k' \neq k} \Pr[h(k) = h(k')] \le (n-1) \cdot \frac{1}{m} < \alpha$

Thus the expected chain length is $< 1 + \alpha$, giving $O(1)$ expected search when $\alpha = O(1)$.

Static Dictionaries and Perfect Hashing

For a static dictionary (keys known in advance, no insert/delete after construction), universal hashing can achieve $O(1)$ worst-case search time with no collisions, using a two-level scheme:

1. Hash $n$ keys into $n$ primary slots using a universal function.
2. For each slot with $n_i$ keys, build a secondary hash table of size $n_i^2$ using another universal function.

The expected total space is $O(n)$, and with high probability (by choosing random hash functions repeatedly until no collisions occur), all secondary tables are collision-free. This is called perfect hashing.

Practical Considerations

Many production hash table implementations (Python’s dict, Rust’s HashMap) use a fixed high-quality hash function with per-process randomisation (a random seed). This approximates universal hashing: the seed is chosen at startup, making it difficult for an attacker to predict slot assignments.

The Cambridge course treats universal hashing as the theoretical foundation: a fixed function cannot beat an adversary, but a randomly chosen function from a universal family can.

Summary

Concept	Definition
Fixed hash function	Vulnerable to adversarial input
Universal family $\mathcal{H}$	$\Pr[h(k_1)=h(k_2)] \le 1/m$ for any $k_1 \neq k_2$
Example family	$h_{a,b}(k) = ((ak+b) \bmod p) \bmod m$
Expected search time	$O(1 + \alpha)$ even against adversary
Perfect hashing	Zero collisions, $O(1)$ worst-case search, $O(n)$ expected space
Per-process randomisation	Practical approximation of universal hashing