Perfect Hashing

• State what "perfect hashing" means precisely: zero collisions, worst-case O(1) lookup, for a fixed, known set of keys.
• Explain why perfect hashing is only possible for a static set of keys known in advance, not for a table that accepts arbitrary future insertions.
• Describe the two-level (FKS) construction: a universal first-level hash into n buckets, followed by a second-level universal hash sized quadratically to its bucket, guaranteeing no collisions within each bucket.
• Compute the expected total space used by the second-level tables, and explain why it is O(n) despite each bucket's table being quadratic in its own size.
• Identify realistic use cases for perfect hashing: compiler keyword lookup, read-only configuration tables, and similar fixed dictionaries.

Universal hashing, the previous concept, made a specific promise: expected O(1) performance, even against an adversary, by bounding the expected number of collisions per key. It did not promise zero collisions, only a bounded expected number of them, and for a genuinely dynamic hash table (keys inserted and removed unpredictably over the table's lifetime) that is the best one can generally do. But a great many real dictionaries are not dynamic in that sense: the set of keywords in a programming language's compiler (if, while, class, and so on) is fixed the moment the language's grammar is finalized; a routing table built once from a static configuration file, or an in-memory index built once over a fixed dataset, never receives an insertion after it is constructed. For exactly this situation, a stronger guarantee than "expected O(1)" is achievable: perfect hashing, in which every lookup is O(1) in the worst case, with zero collisions, guaranteed, not merely likely.

Why perfection requires a static key set

The reason perfect hashing cannot apply to a fully dynamic table is structural, not a limitation of cleverness: any hash function that guarantees zero collisions for one specific set of n keys is, by construction, tailored to that set. Insert one additional key not in the original set, and there is no guarantee whatsoever that the same function keeps mapping everything to distinct slots; the new key might land exactly on top of an existing one. Building a hash function with zero collisions for a known set is a search problem (find a function, from some family, under which this particular set happens not to collide), and that search is only well posed if the set is fixed while the search is being performed. This is why perfect hashing is specifically a technique for static dictionaries: a set of keys known completely before the table is built, with no future insertions expected.

The two-level construction (Fredman, Komlós, and Szemerédi, 1984)

The FKS construction builds a perfect hash table for a static set of n keys in two levels, each one a universal hash table from the previous concept, used in a specific, clever way:

Level one. Choose a universal hash function h (from the multiply-mod-prime family, for instance) mapping the n keys into n buckets. As the birthday paradox concept already established, this level alone will typically have collisions, some buckets will receive more than one key. The insight is not to avoid these collisions, but to isolate them: each bucket's colliding keys become their own small, separate sub-problem.

Level two. For each bucket i that received n_i keys (n_i can be 0, 1, or more), build a second, independent universal hash table sized m_i = n_i² slots (quadratic in the bucket's own key count, not in n), and search among random choices of that bucket's hash function until finding one under which all n_i keys land in distinct slots. This search is guaranteed to terminate quickly: because the sub-table has n_i² slots, the birthday-paradox-style collision probability for n_i keys landing in n_i² slots is at most 1/2 for a randomly drawn universal hash function (a direct consequence of the universal property applied at this specific, quadratic size), so on average it takes only about two random tries to find a collision-free function for that bucket, and testing "does this specific choice actually give zero collisions" is a cheap, one-time check done during table construction.

Looking up a key at query time is now a fixed, two-step process: apply the level-one hash h to find the bucket, apply that bucket's own level-two hash to find the exact slot within it, done, with a guarantee (not just an expectation) of zero collisions at the second level by construction, so this is worst-case O(1), not merely expected O(1).

Why the total space stays O(n), despite quadratic sub-tables

Making each bucket's second-level table quadratic in its own size sounds expensive: summing n_i² over all buckets could, in principle, be much larger than n. The reason it is not, in expectation, is a direct consequence of the same first-level universal hash, applied one level up: the expected number of collisions at level one (pairs of keys landing in the same bucket) is bounded by the universal property to at most C(n, 2)/n < n/2, and a standard identity relates sum of n_i² directly to the number of colliding pairs at level one (sum n_i² = n + 2 · (number of colliding pairs at level one)). Combining these gives an expected total second-level space of O(n), not the naive worst case that summing quadratic bucket sizes might suggest. This is the reason level one specifically uses n buckets (not fewer): using too few buckets at level one would push too many keys into large buckets, making the sum n_i² bound too loose to stay linear.

Example 1: sizing a bucket's second-level table and estimating retry count

Problem: A level-one hash sends 3 keys into the same bucket. Determine the level-two table size, and estimate how many random function choices are expected before one is found with zero internal collisions.

Sizing: With n_i = 3 keys in this bucket, the level-two table has m_i = n_i² = 9 slots.

Retry estimate: The universal property bounds the probability that any specific pair of the 3 keys collides at 1/9 for a randomly drawn function; summing over the C(3, 2) = 3 pairs gives an expected number of colliding pairs of at most 3 · (1/9) = 1/3, so the probability that no pair collides (a "success" for this random trial) is at least 1 - 1/3 = 2/3. On average, about 1 / (2/3) = 1.5 random function draws are needed before one succeeds with zero collisions in this bucket, confirming the "about two tries" intuition from Core Theory even for a small, concrete bucket.

Example 2: a compiler's keyword table as a realistic perfect-hashing use case

Problem: Explain why a compiler's reserved-keyword lookup (checking whether an identifier like while or myVariable is a language keyword) is a natural fit for perfect hashing, and why it would be a poor fit for, say, a general-purpose application's user-session cache.

Why keywords fit: The complete set of keywords in a language (perhaps 30 to 60 words) is fixed the moment the language specification is frozen, known completely in advance, never grows at runtime, and is looked up an enormous number of times during compilation, making the one-time cost of building a perfect hash table (done once, offline, when the compiler itself is built) an excellent trade for guaranteed worst-case O(1) lookup on every single identifier the compiler ever checks.

Why a session cache does not fit: A user-session cache's key set (session IDs) is created and destroyed continuously at runtime, is not known in advance, and perfect hashing's entire construction assumes a fixed, known key set to search over; using it here would require rebuilding the whole two-level structure from scratch on every single new session, defeating the point of a fast, incrementally updatable table entirely. This is precisely the boundary Core Theory draws: perfect hashing for static dictionaries, universal or ordinary hashing (supporting incremental insertion) for dynamic ones.

• "Perfect hashing is just a better hash function that happens to have no collisions." It is not a single formula at all, it is a two-level table construction built specifically around one fixed key set, involving a search (retrying random function choices per bucket) performed once during construction; there is no single formula that is "perfect" independent of the specific key set it is built for.
• "Since perfect hashing gives worst-case O(1), it should replace ordinary hash tables everywhere." It only applies when the complete key set is known in advance and does not change; a hash table receiving arbitrary future insertions (essentially every general-purpose dynamic dictionary) cannot use this technique at all without a full, expensive rebuild on every insertion, which is exactly why universal hashing (previous concept), not perfect hashing, is the answer for dynamic workloads.
• "The quadratic-sized second-level tables make perfect hashing use quadratic total space." Example 1's calculation and the identity relating sum n_i² to the number of first-level colliding pairs show the expected total space across all buckets is O(n), not O(n²); the quadratic sizing is local to each individual bucket, sized to that bucket's own (typically small) key count, not to n as a whole.
• "Building a perfect hash table is expensive enough that it is rarely worth it." The one-time construction cost (expected O(n) time, using the retry argument from Example 1 at each bucket) is paid exactly once, offline, for a table that is then queried an enormous number of times with a guaranteed O(1) worst case; for a genuinely static, frequently queried dictionary like a compiler's keyword set, this is a clearly favorable trade, not an unusual one.

Perfect hashing achieves worst-case O(1) lookup with zero collisions, but only for a static, fully known-in-advance set of keys, since the construction is a one-time search tailored to that exact set rather than a general-purpose formula. The FKS two-level construction uses a first-level universal hash to sort keys into n buckets (accepting that this level alone will have collisions), then, for each bucket with n_i keys, searches among random universal hash functions sized to a quadratic n_i²-slot sub-table until finding one with zero internal collisions, a search that succeeds after only a small constant number of expected tries thanks to the universal property applied at that quadratic size. A standard identity shows the expected total space across all these quadratic sub-tables is nonetheless O(n), not O(n²), making the whole structure practical. This closes out this discipline's hashing arc: ordinary hashing risks unbounded collisions, universal hashing bounds them in expectation even against an adversary, and perfect hashing eliminates them entirely, at the cost of requiring the full key set upfront, exactly the trade-off a compiler's fixed keyword table or a similar static dictionary is happy to make.