Minimal Perfect Hashing for Static Key Sets

A hash table answers “is this key present, and where is its value” by storing the keys. The keys are needed for the final comparison, because the hash maps many keys to the same slot. If the key set is known in advance and never changes, the comparison can be eliminated: a function can be constructed that maps each key to a distinct slot, so the mapping itself is the proof of membership. A minimal perfect hash function goes further and maps n keys onto exactly n slots, so the table is as small as the data and the lookup is a computation followed by one array access.

The trade is stark. Construction is expensive and must see the whole key set. Insertion of a new key is impossible without rebuilding. In exchange, a lookup is a fixed number of arithmetic operations with no probing, no comparison, and a table of n entries.

Why a perfect function exists at all

A random function from a key set of size n to m slots produces a collision with probability about n²/2m. Setting m = n² makes the expected number of collisions constant, which is the basis of the classic two-level scheme: hash into n buckets with a first-level function, then give each bucket a second-level table sized to the square of its occupancy, and find a displacement that makes the second-level function injective on that bucket.

The square is what makes the second level work. A bucket of size b gets a table of b² slots. For a random function into b² slots, the probability of no collision among b keys is about e^(−1/2) ≈ 0.607. So a constant number of displacement attempts — trying successive values of a single additive offset — finds a collision-free one with probability one after a few tries, and the expected number of attempts is bounded by a small constant. The total space is Σ b_i², whose expectation is O(n) because the bucket sizes concentrate around their mean.

That construction is from Fredman, Komlós and Szemerédi, and it gives O(1) worst-case lookup with O(n) words of space. The word count is the problem: O(n) words is tens of bits per key, not the two bits that the information-theoretic bound suggests.

The information-theoretic floor

The number of distinct ways to map n keys onto n slots bijectively is n!. A description of one such mapping therefore needs log₂(n!) bits, which by Stirling’s approximation is n·log₂(n/e) + O(log n) — about n·log₂ n − 1.44n bits. The 1.44n term is where the widely quoted target of log₂ e ≈ 1.4427 bits per key comes from: a minimal perfect function costs about 1.44 bits per key beyond the information the key set already carries, and every practical scheme is judged by how close its space per key comes to that constant.

Real constructions land within a few tenths of a bit of that floor. Getting there requires abandoning the two-level table for something whose space is proportional to the entropy of the bucket structure rather than its word count.

Displacement, and how a bucket becomes one number

The mechanism that makes this practical is displacement hashing. Each bucket is described not by a table but by a single integer: the offset added to the second hash before taking the modulus. Lookup computes

slot = (h₂(key) + displacement[bucket(key)]) mod table_size

with table_size chosen so that every key lands in a distinct slot across the whole table, not just within its bucket. The search for a displacement is a small constraint problem: for each key in the bucket, compute h₂(key) mod table_size and check whether the resulting slots are distinct and unused by previously placed buckets. If they are, the displacement is the value that makes it so; if not, increment and retry.

The displacement values are the only stored data, and they are small. A table of n keys has about n/λ buckets for average bucket size λ, so the displacement array has n/λ entries. The largest displacement needed is set by the last buckets placed, which see a table that is nearly full: the probability that a random displacement is collision-free for a bucket of size b over a table of size m is about (1 − c/m)^{b(b−1)/2} for c keys already placed, so the number of attempts grows as the table fills and the maximum displacement is an order of magnitude larger than the typical one. Storing the values as fixed-width integers therefore wastes most of their range, and the practical compression is to store them bit-packed at the width of the largest value in the block, or as a sequence of gaps.

Recursive splitting

RecSplit takes a different route to the same target. Instead of one flat bucket layer, it recursively splits the key set until every part is a singleton. A split of a set of size n into two parts of sizes n₁ and n₂ is described by the choice of split point, and the number of such choices is the binomial coefficient C(n, n₁). Encoding each split with ⌈log₂ C(n, n₁)⌉ bits and recursing gives a total description length that telescopes to log₂(n!) plus a small overhead — that is, close to the theoretical floor by construction rather than by compression.

The recursion also makes construction cheap in a different currency: each level is a small independent problem, and the splits can be evaluated with a few hash computations. The practical difference from displacement schemes is the shape of the lookup: a recursive scheme walks a tree of splits, so the number of hash evaluations per lookup grows with the depth — about log₂ n levels in the worst case, though the depth of a balanced split is far smaller — while a displacement scheme needs exactly two.

MASK = (1 << 64) - 1

def mix(x, seed):
    """splitmix64-style finaliser; distinct seeds give independent functions."""
    z = (x + seed * 0x9E3779B97F4A7C15) & MASK
    z = ((z ^ (z >> 30)) * 0xBF58476D1CE4E5B9) & MASK
    z = ((z ^ (z >> 27)) * 0x94D049BB133111EB) & MASK
    return z ^ (z >> 31)

def build(keys, size, nbuckets, seed1, seed2):
    """Returns a displacement per bucket, or None if this seed pair fails."""
    groups = [[] for _ in range(nbuckets)]
    for k in keys:
        groups[mix(k, seed1) % nbuckets].append(k)

    used = bytearray(size)
    disp = [0] * nbuckets
    # Largest buckets first: they have the fewest valid displacements.
    for b in sorted(range(nbuckets), key=lambda i: -len(groups[i])):
        for d in range(size):
            slots = set()
            for k in groups[b]:
                s = (mix(k, seed2) + d) % size
                if used[s] or s in slots:
                    break
                slots.add(s)
            else:                       # every key got a distinct free slot
                for s in slots:
                    used[s] = 1
                disp[b] = d
                break
        else:
            return None                 # retry the whole build with new seeds
    return disp

The example is the displacement half of the construction only. RecSplit’s selection and rank-encoding steps are a separate mechanism: the first finds a value that splits the set evenly by hash rank, the second writes the split point in the arithmetic-coding sense of a binomial coefficient. A real displacement implementation replaces the per-bucket lists with in-place partitioning, because the repeated filtering allocates a new list per bucket.

What a lookup costs

The evaluation cost is two or three multiplications and a modulo per level. Modulo by a non-power-of-two is a division, which costs roughly twenty to forty cycles on current x86 cores; the standard trick is to multiply by a precomputed reciprocal and shift, which turns it into two multiplications. Implementations therefore store the modulus’s reciprocal alongside the displacement array.

The memory access pattern is the second cost, and it is where a minimal perfect hash beats a comparison-based structure outright. A lookup touches the displacement array — small, and resident in cache for a modest key set — and then one slot in the value array, which is a single random access. There is no probe sequence, so there is no second miss on collision, and there is no comparison of stored keys, so the value array can be laid out as densely as the value type allows.

The absence of stored keys is also the technique’s most dangerous property. A minimal perfect hash function answers “where would this key go”, not “is this key a member”. For a key that is not in the set, the function still returns a slot, and that slot holds some other key’s value. Membership testing therefore requires either storing the keys (which defeats the space advantage) or storing a fingerprint per slot — a few bits of the key’s hash — and accepting a false-positive rate determined by the fingerprint width. An 8-bit fingerprint gives a false-positive probability of about 1/256 per query, which is the same trade a Bloom filter makes, but with a fixed per-slot cost rather than a per-query probe count.

Where the structure earns its construction cost

Three properties must hold for a minimal perfect hash to be the right answer: the key set is static, the keys are known before the first query, and the query rate is high enough that a constant-factor improvement in lookup cost matters.

The classic habitat is a read-only index: a file format’s symbol table, a compressed dictionary’s word list, a routing table baked into a firmware image, a set of identifiers in a query engine’s catalog. In each case the table is built once at compile or index time and queried many times afterwards, and the space saving is real because the alternative is storing every key.

The structure is a poor fit when the key set changes. There is no incremental insertion, and even deletion of a single key invalidates the displacement of its bucket. Rebuilding costs O(n) hash evaluations plus the displacement search, and the search itself is the expensive term: it retries values until every bucket is placed, and the last buckets see a nearly full table. The cost is therefore superlinear in practice even though the hash evaluations are linear. A workload that adds keys steadily is better served by open addressing with a good probe sequence, which pays a little per lookup and supports insertion.

There is also a subtler constraint on the hash functions. Displacement search assumes that the second-level hash behaves randomly and independently of the first. If the two functions are correlated — for example, if both are truncations of the same 64-bit hash with overlapping bits — then a bucket’s keys may be unresolvable no matter what displacement is tried, and construction loops forever. The fix is to derive independent functions from independent seeds, or to use a mixing finaliser between them. This is the same requirement that makes the address bits in extendible hashing behave as designed, and it fails in the same way when the hash’s bits are not independent.

Finally, the space figures quoted for these schemes are for the index, not the data. A minimal perfect hash of a million keys at two bits per key is about 250 KiB of displacement and encoding data, plus whatever the values occupy. If the values are large, the index’s contribution is negligible and the technique’s advantage over a plain sorted array with binary search over a half-open interval is the difference between one random access and twenty. If the values are a single bit each, the index dominates and the space arithmetic matters more than the lookup.