A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Universal hashing and perfect hashing provide rigorous, provable guarantees for hash-based data structures. A universal hash family is a collection of hash functions where the probability of any two distinct keys colliding is at most 1/m (for m buckets) when the function is chosen randomly from the family — eliminating adversarial worst cases without knowing the input distribution. Perfect hashing goes further: given a static set of n keys, it constructs a hash function with zero collisions, achieving O(1) worst-case lookup in O(n) space. The FKS (Fredman-Komlós-Szemerédi) scheme achieves this by using two levels of universal hashing, with the second level sized quadratically to guarantee no collisions at each bucket.
You already know that hash tables achieve O(1) average-case operations under the assumption that the hash function distributes keys uniformly. But this assumption is fragile: for any fixed hash function, an adversary can choose keys that all collide, degrading to O(n) per operation. Universal hashing eliminates this vulnerability by randomizing the choice of hash function. A universal hash family guarantees that for any pair of distinct keys, the collision probability is at most 1/m — the same guarantee a truly random function would provide, but using only O(1) parameters to specify the function.
The classic construction is the Carter-Wegman family: h(x) = ((ax + b) mod p) mod m, where p is a prime larger than the universe, and a, b are chosen randomly. For any two distinct keys x and y, the values (ax + b) mod p and (ay + b) mod p are uniformly distributed and independent, so the collision probability after the final mod m is at most 1/m. This elegant construction shows that pairwise independence suffices for the universal hashing guarantee. Stronger notions — k-wise independence, almost-universality — provide tighter concentration bounds at the cost of more complex hash functions.
Perfect hashing, achieved by the FKS scheme, goes beyond probabilistic guarantees to deterministic O(1) worst-case lookup. The construction uses two levels. The first level hashes n keys into n buckets using a universal hash function. The second level resolves collisions: for each bucket containing n_i keys, it constructs a second-level hash table of size O(n_i2) with a universal hash function chosen to have zero collisions. Quadratic space at each bucket guarantees collision freedom (the birthday paradox in reverse: with n_i keys and n_i2 slots, a random function has no collisions with constant probability). The total space remains O(n) because the universal first-level hash ensures the sum of n_i2 is O(n) in expectation.
The theoretical significance extends beyond hash tables. Universal hashing is a foundational derandomization concept: it shows that limited randomness (pairwise independence, specified by O(log n) random bits) suffices for many applications that seem to require full randomness. This principle recurs throughout algorithm design — in streaming algorithms, sketching, and load balancing — wherever probabilistic guarantees with small random seed size are needed.