perfect hashing
Universal hashing keeps collisions rare on average, but rare is not zero — sometimes you want a static set of keys (say a fixed dictionary of words) stored so that every single lookup is guaranteed to take exactly one probe, with no collisions at all. Perfect hashing achieves this for a known, fixed set: a hash function tailored so that no two of those keys ever land in the same slot.
Precisely: given a fixed set S of n keys, a perfect hash function maps the keys of S into a table with no collisions, so lookups are true worst-case O(1). The famous FKS construction (Fredman, Komlos, Szemeredi) builds it in two levels using universal hashing. The top level hashes the n keys into n buckets with a universal function; some buckets get several keys. For each bucket holding b keys, build a small second-level table of size b^2 and pick (by trying a few random universal functions) one that hashes those b keys with zero collisions — possible because, with a table of size b^2, a random universal function is collision-free with probability at least one-half, so a couple of tries succeed. The clever counting fact is that, although each second table is quadratic in its bucket size, the expected total of all the b^2 values is only O(n), so the whole structure uses linear space.
Perfect hashing matters when you have a fixed key set and need both guaranteed constant-time lookups and linear space — compilers' keyword tables, read-only dictionaries, routers. It shows how to spend randomness once, during construction, to buy a deterministic worst-case guarantee at query time (a kind of Las Vegas build feeding a deterministic lookup). The honest caveat: classic perfect hashing assumes the key set is static; inserting new keys can force a costly rebuild. Dynamic variants (cuckoo hashing, dynamic perfect hashing) restore updates at the price of more machinery and amortized or expected bounds.
Storing 4 fixed keys: the top hash sends two keys to bucket 0 and one each to buckets 1 and 3. Bucket 0's two keys get a size-4 (= 2^2) second table with a universal function chosen so they do not collide; the empty/singleton buckets need almost nothing. Total space stays O(n), every lookup is exactly two probes.
Two levels of universal hashing give guaranteed O(1) lookups in O(n) space for a fixed key set.
Perfect hashing gives a worst-case O(1) lookup, but only for a static set; the randomness lives in building the function, and adding keys later may require rebuilding. The space stays linear because the sum of squared bucket sizes is O(n) in expectation, not despite being quadratic per bucket.