Perfect Hashing, in depth: FKS two-level tables, hash-and-displace MPHFs, the 1.44-bit bound and the unknown-key trap

Perfect, minimal, order preserving

Fix a set S of n keys drawn from a large universe U. A function h from U to {0, ..., m-1} is perfect for S if no two keys in S map to the same value. It is minimal (an MPHF) if m = n, so the n keys fill n slots exactly, which lets you store values in a dense array indexed by h(key). It is order preserving if h maps keys to their positions in a given order. Note what the definition does not say: h is free to do anything at all on keys outside S. A perfect hash function is not a membership test.

How small can an MPHF be? Counting arguments (Mehlhorn; Fredman and Komlos) show that any MPHF for a large universe needs about n log2 e, roughly 1.44 bits per key, no matter how clever the construction; practical ones sit a small constant above it. An order-preserving function costs about log2 n bits per key, because it must encode an arbitrary permutation.

So an MPHF of a few bits per key can fit in cache when the keys would not, but because it forgets the keys, queries about keys outside S need stored keys or fingerprints.

FKS: two levels of universal hashing

The first practical scheme with worst-case O(1) lookups and linear space is FKS, from Fredman, Komlos and Szemeredi in 1984. It rests on one fact about universal hash families: if h is drawn from a universal family into m slots, two distinct keys collide with probability at most 1/m. With m = n squared slots the expected number of colliding pairs is under 1/2, so by Markov's inequality a random choice is collision free with probability over 1/2. Quadratic space is too much for the whole set, but fine for small groups.

So FKS hashes twice. Level 1 throws the n keys into n buckets with a universal function; bucket i receives b_i keys. Level 2 gives bucket i its own table of b_i squared slots and its own universal function, retried until that bucket has no collisions. Total space is the sum of b_i squared, and that sum equals n plus twice the number of colliding pairs at level 1, whose expectation is under n. So the expected total is below 2n, and by Markov again the total exceeds 4n with probability under 1/2. Retry level 1 until the sum is at most 4n, then build every bucket. Expected construction time is O(n).

import hashlib, random

P = (1 << 61) - 1                        # Mersenne prime above every key integer

def key_int(key: str) -> int:
    return int.from_bytes(hashlib.blake2b(key.encode(), digest_size=8).digest(), "little") % P

def universal(m, rng):                   # Carter-Wegman: ((a*x + b) mod p) mod m
    a, b = rng.randrange(1, P), rng.randrange(P)
    return lambda x: ((a * x + b) % P) % m

def build_fks(keys, seed=1):
    rng, xs = random.Random(seed), [key_int(k) for k in keys]
    assert len(set(xs)) == len(xs), "duplicate keys (or a 61-bit collision)"
    n = len(xs)
    while True:                          # level 1: retry until sum of b_i^2 <= 4n
        h = universal(n, rng)
        buckets = [[] for _ in range(n)]
        for x in xs:
            buckets[h(x)].append(x)
        if sum(len(b) ** 2 for b in buckets) <= 4 * n:
            break
    tables = []
    for b in buckets:                    # level 2: b^2 slots, retry until collision free
        m = len(b) ** 2
        while True:
            g, slots = (universal(m, rng) if m else None), [None] * m
            for x in b:
                if slots[g(x)] is not None:
                    break
                slots[g(x)] = x
            else:
                tables.append((g, slots))
                break
    return h, tables

def contains(fks, key):
    h, tables = fks
    x = key_int(key)
    g, slots = tables[h(x)]
    return bool(slots) and slots[g(x)] == x   # stored key rejects non-members

Two details carry the correctness. The assertion catches duplicate keys, which would make level 2 retry forever because no function separates equal inputs. The stored key in each slot is what turns the perfect hash into a dictionary that answers false for unknown keys.

Hash and displace: compact minimal perfect hashing

FKS stores every key and spends up to 4n slots, so it is a fast dictionary rather than a compact index. Modern MPHF libraries aim at a few bits per key and no stored keys. The most widely used idea is hash and displace (Belazzougui, Botelho and Dietzfelbinger's CHD in 2009, refined by Pibiri and Trani's PTHash in 2021). Hash every key into one of roughly n/4 small buckets. Process buckets from largest to smallest. For each, search integers 0, 1, 2, ... for a pilot such that hashing every key of the bucket with that pilot lands on distinct, still-free slots. Store only the pilots, compressed. A lookup hashes the key to its bucket, reads one pilot, and hashes again.

Largest first matters: big buckets need many free slots at once, easy only while the table is empty; the small buckets placed last need just one or two.

def h64(key: str, seed: int) -> int:
    return int.from_bytes(hashlib.blake2b(key.encode(), digest_size=8,
                          key=seed.to_bytes(8, "little")).digest(), "little")

def build_mphf(keys, avg_bucket=4, max_pilot=1 << 20):
    n = len(keys)
    nb = max(1, n // avg_bucket)
    buckets = [[] for _ in range(nb)]
    for k in keys:
        buckets[h64(k, 0) % nb].append(k)
    pilots, taken = [0] * nb, [False] * n
    for bi in sorted(range(nb), key=lambda i: -len(buckets[i])):   # biggest first
        for pilot in range(max_pilot):
            pos = [h64(k, pilot + 1) % n for k in buckets[bi]]
            if len(set(pos)) == len(pos) and not any(taken[q] for q in pos):
                for q in pos:
                    taken[q] = True
                pilots[bi] = pilot
                break
        else:
            raise RuntimeError("no pilot found: duplicate keys or a bad seed")
    return nb, pilots

def mphf(index, n, key):
    nb, pilots = index
    return h64(key, pilots[h64(key, 0) % nb] + 1) % n

Other families reach similar results by different routes. BDZ maps each key to an edge of a random 3-hypergraph and peels it, storing 2 bits per vertex. BBHash (Limasset et al., 2017) uses a cascade of bit arrays: keys that collide at level 1 retry at level 2, and the final index is a rank over the set bits; a gamma parameter trades bits per key for faster builds. RecSplit (Esposito, Graf and Vigna, 2020) splits buckets recursively by brute force and gets closest to the 1.44-bit bound at a higher build cost. Published figures depend on parameters and hardware, so benchmark candidates on your own keys.

Worked example: keywords, then twenty thousand keys

Take the 16 C keywords a toy compiler must recognise: if, else, while, for, return, break, continue, switch, case, default, struct, union, enum, typedef, static and const. Running build_fks with seed 1 gave level-1 bucket sizes [3, 1, 0, 1, 2, 2, 0, 0, 0, 1, 2, 0, 1, 2, 0, 1]: sixteen buckets, six of them empty, one holding three keywords. The level-2 tables therefore use 9 + 1 + 1 + 4 + 4 + 1 + 4 + 1 + 4 + 1 = 30 slots, under the 4n = 64 ceiling on the first try. Every keyword was found and the identifier goto, which is not in the set, was correctly rejected by the stored-key comparison.

The same 16 keys through build_mphf used four buckets with pilots [1, 2, 130, 323] and mapped the keywords onto exactly 0..15. Asked about goto, it returned 11, a perfectly valid slot that belongs to some other keyword. That is the membership trap in a single line of output.

Scale exposes the build-time behaviour. With 20,000 synthetic keys at a full load (m = n), one pure-Python run needed a mean pilot of 196 and a worst pilot of 9,494, almost all of the search spent on the last buckets. Giving the table 5 percent slack (m = n / 0.95) cut the mean pilot to 62, the worst to 1,371 and the build time by about a third. That is why PTHash builds below full load, then remaps keys past slot n into the holes.

Unknown keys and fingerprints

Because an MPHF returns a valid slot for every input, any lookup path that can see keys outside S must verify. There are three standard answers. Store the full key in the slot and compare, which is exact and costs the key bytes. Store an f-bit fingerprint of the key, which rejects a non-member with probability 1 - 2^-f: 8 bits gives a false-positive rate of about 0.4 percent, 16 bits about 0.0015 percent. Or guarantee by construction that only members are queried, for example when the MPHF indexes a vocabulary and the caller already tokenized with that vocabulary. The third option is the one teams assume and later violate.

FP_BITS = 16

def fingerprint(key: str) -> int:
    return h64(key, 0xF1F1) & ((1 << FP_BITS) - 1)   # independent seed from the MPHF

def build_index(keys, values):
    idx = build_mphf(keys)
    n = len(keys)
    fps, vals = [0] * n, [None] * n
    for k, v in zip(keys, values):
        i = mphf(idx, n, k)
        fps[i], vals[i] = fingerprint(k), v
    return idx, fps, vals

def get(index, key):
    idx, fps, vals = index
    i = mphf(idx, len(vals), key)
    return vals[i] if fps[i] == fingerprint(key) else None   # 2^-16 false positives

Use an independent seed for the fingerprint. If it reuses the bits that chose the bucket, keys in the same bucket share fingerprint bits and the false-positive rate is far worse than the formula says. The same correlation trap appears in cuckoo filters.

Running it in production

Treat a perfect hash as a build artifact. Build it offline from a deduplicated key list, verify every slot is hit exactly once, and serialize it with the hash algorithm, seeds, bucket count, format version and byte order. Ship it with the value array as one versioned unit and memory-map it at load time.

Track build time and maximum pilot as metrics. A perfect hash has no insert, so key changes mean a rebuild. If your set changes every few minutes, a normal hash table or cuckoo hashing will cost less in engineering than frequent rebuilds. Sharded key spaces can rebuild per shard, routing with a stable function such as consistent hashing so only one shard's artifact changes at a time.

Failure modes

• Unknown keys silently aliased. An MPHF without keys or fingerprints answers every query with someone else's value. Decide the membership policy before choosing the structure.
• Duplicate keys hang the build. No function separates identical inputs, so the pilot search or level-2 retry never succeeds. Deduplicate and cap the search with a clear error.
• Builder and reader disagree. A changed hash library, seed default or endianness produces valid-looking slots that are wrong. Store algorithm and seed in the artifact header and test a sample of keys at load.
• Weak or adversarial hashing. Keys with structure (sequential IDs, common prefixes) defeat poor hash functions and blow up build time. Use a strong seeded hash, and change the seed if a build stalls.
• Full-load tail. At m = n the last buckets dominate build time. Leave slack and remap.

Trade-offs

What to do next

1. Confirm your key set is static between builds and write down how often it changes.
2. Decide the membership policy: stored keys, fingerprints of a chosen width, or a proven members-only caller.
3. Prototype with build_mphf above to understand the moving parts, then pick a maintained library and benchmark bits per key, build time and lookup latency on your keys.
4. Add build-time verification that every key maps to a distinct slot and every slot is used.
5. Version the artifact header with hash algorithm, seeds and layout; check a key sample at load.
6. Export build duration and maximum pilot or retry count; alert on jumps.
7. Keep a plain hash table fallback for the rebuild window if updates must appear immediately.