Lecture 8: Randomization: Universal & Perfect Hashing

What this lecture covers

This lecture answers a question left open by the introductory treatment of hash tables: how do you get constant-time dictionary operations without assuming the input keys are random? It follows the randomized-algorithms unit on skip lists, and moves from a predecessor/successor structure to the dictionary problem, where you can only ask whether an exact key is present. The lecture builds up hashing with chaining from an analysis you may already know, then replaces its unrealistic assumption (simple uniform hashing) with a randomized guarantee that holds for any input.

After watching, you should be able to explain why choosing a random hash function, rather than assuming random keys, removes the need for average-case analysis, prove that a universal hash family gives constant expected-time operations, construct a concrete universal hash family using modular dot products, and describe how perfect hashing achieves zero collisions and constant worst-case search time for static key sets.

Key ideas

• Dictionary problem: maintain a set of items by key, supporting insert, delete and exact search (no neighbor information), unlike the predecessor/successor search solved by AVL trees or skip lists.
• Simple uniform hashing: the textbook assumption that any two distinct keys collide with probability 1/m; it is an assumption about the keys being random, which the lecture treats as cheating because real inputs can be adversarial.
• Universal hash family: a set of hash functions H such that for any two distinct keys, the probability a randomly chosen h from H sends them to the same slot is at most 1/m; randomness comes from the choice of function, not the keys.
• Expected chain length theorem: if h is drawn uniformly from a universal family, the expected number of keys sharing a slot with any given key is at most 1 + alpha, where alpha = n/m is the load factor.
• Indicator random variables and linearity of expectation: the proof technique used throughout, writing a count (like collisions) as a sum of 0/1 variables so expectations can be summed term by term.
• Dot-product hash family: viewing a key in base m as a vector of digits and computing h_a(k) = (a . k) mod m for a random vector a, using a prime table size so digits have modular inverses; this family is provably universal.
• Perfect (FKS) hashing: a two-level scheme for static key sets (Fredman, Komlos and Szemeredi, 1984) that gets zero collisions and constant worst-case search time, using linear space, by hashing each first-level slot's colliding keys into a second-level table of size proportional to the square of how many keys land there.
• Birthday paradox / union bound: sizing a secondary table at l_j^2 makes the probability of any collision among its keys at most one half, so retrying a failed hash choice converges in an expected constant (and with high probability logarithmic) number of tries.

Walkthrough

Reviewing the dictionary problem and hashing with chaining (0:00)

The lecture opens by distinguishing the dictionary abstract data type (insert, delete, exact search) from hash tables, the data structure that implements it. It recaps hashing with chaining: a table of m slots, each a linked list, with a hash function mapping the universe of keys into slots. Under simple uniform hashing, this gives expected 1 + alpha time per operation, where alpha = n/m. The lecture flags that this assumption is really about the keys being random, contrasted with the earlier quicksort analysis, where randomizing the pivot choice avoided any assumption about the input at all. The goal for today is the same move for hashing: keep the analysis worst-case over keys, and push all the randomness into the algorithm.

Universal hashing and its guarantee (15:12)

The lecture introduces universal hash families: a set H of hash functions from which one is drawn uniformly at random, with the property that any two distinct keys collide with probability at most 1/m, no matter what the keys are. It then proves the main theorem: with h drawn from a universal family, the expected chain length for any key is at most 1 + alpha. The proof defines indicator variables for pairwise collisions, applies linearity of expectation, bounds each term by 1/m using universality, and adds back the key colliding with itself to recover the 1 + alpha bound.

Building a universal hash family (27:29)

After noting that "all functions from the universe to slots" is universal but useless (too much time and space to store), the lecture constructs an efficient family. With a prime table size m and universe size a power of m, a key is viewed as a vector of base-m digits. The hash function h_a(k) is the dot product of k with a random vector a, taken modulo m; the family is all such functions over choices of a. Choosing a hash function means choosing one random key-sized vector, which is constant time and space in the word-RAM model. A simpler-to-compute alternative family, h_{a,b}(k) = ((a*k + b) mod p) mod m, is mentioned but left to the textbook.

Proving the dot-product family is universal (42:06)

For two distinct keys, their base-m digit vectors must differ in some digit d. The lecture rewrites the collision probability as a condition on a linear combination of the a_i, isolates the a_d term, and uses the fact that m is prime (so multiplicative inverses exist) to solve for the exact value a_d would need to take for a collision. Since a_d is chosen independently and uniformly at random from m values, the probability of hitting that one value is exactly 1/m, which proves universality.

Perfect hashing: the two-level idea (55:16)

For the static dictionary problem (keys fixed in advance, only search needed), the lecture presents FKS perfect hashing: constant worst-case search time and linear worst-case space. The idea uses two levels of hashing. A first-level universal hash function h1 maps n keys into m = theta(n) slots. Instead of chaining colliding keys in a linked list, each slot j gets its own second-level hash table sized at l_j^2, where l_j is the number of keys landing in that slot. Sizing quadratically invokes the birthday paradox: with l_j items hashed into l_j^2 slots, the chance of zero collisions is at least one half.

Making it work: retries and space control (1:04:34)

The full construction has four steps: build the first-level table, then check that the total space (sum of l_j^2) is linear (retry step one if not), build each second-level table, then check each for zero collisions (retry that table's hash function if not). The lecture proves via a union bound that each second-level retry succeeds with probability at least one half, giving an expected constant number of trials, and that with high probability all l_j are O(log n), keeping each retry cheap. For the space check, it computes that the expected sum of l_j^2 is linear using indicator variables and linearity of expectation, then applies Markov's inequality to show the probability of exceeding a constant multiple of n is at most one half, again giving expected constant retries. The total build time works out to roughly n log^2 n.

Before you watch

• Know hashing with chaining and the load-factor bound from an introductory algorithms course (referred to here as "6.006").
• Be comfortable with indicator random variables and linearity of expectation, and with union bound and Markov's inequality.
• Recall the randomized quicksort analysis from the previous lecture, since it motivates avoiding average-case assumptions here.
• Basic modular arithmetic (multiplicative inverses modulo a prime) is used directly in the universality proof.

Check your understanding

1. Why does assuming a random hash function (universal hashing) avoid the need to assume the input keys are random?
2. Walk through how indicator random variables and linearity of expectation are used to prove the 1 + alpha chain-length bound.
3. Why must the table size m be prime for the dot-product hash family's universality proof to go through?
4. Why does sizing each second-level table at l_j^2 rather than theta(l_j) make sense, given the birthday paradox?
5. What guarantees that the perfect hashing construction terminates quickly, both for the first-level space bound and the second-level collision-free property?