Minimal perfect hashing

Deep dive

How it works

In: a key from the build set (any 64-bit hash of it) · Out: a unique index in 0..n-1 · State: one small pilot (seed) per bucket, about 2.4-4.3 bits per key · Cost: O(1), one pilot read (about one cache miss) plus two hash mixes PTHash (the code below, with 16-bit pilots):

1. Hash each key once to 64 bits. Map it to one of m = n/λ buckets (λ = average bucket size, 4 here). Skew: 60 % of the keys go to the first 30 % of the buckets, which creates some big buckets.
2. Sort buckets by size, largest first: big buckets are placed while the table is nearly empty, small ones fill the gaps at the end.
3. For each bucket, try pilots p = 0, 1, 2, … until every key's slot reduce(mix(h ⊕ mix(p)), slots) is free and the keys don't collide with each other. Mark the slots taken and store p.
4. Table size slots = n/α, α = 0.99: the 1 % spare makes the last single-key buckets cheap to place. Afterwards, the few keys that landed at slot ≥ n are remapped to the holes below n (PTHash stores this list with Elias-Fano).
5. Query: hash, bucket, read one pilot, compute the slot, and remap if it is ≥ n.

key ─hash─► h ─► bucket b ─► pilot[b] ─► slot = reduce(mix(h ^ mix(pilot)), n/α)
                                             └─ ≥ n? → remap[slot - n]

Code

/// PTHash/PtrHash-style minimal perfect hash for u64 keys (hash strings to u64 first).
/// Keys go to buckets; each bucket stores one 16-bit "pilot" that moves all its keys
/// to free slots. Slots >= n (alpha = 0.99 leaves 1 % spare) are remapped into the holes < n.
pub struct Mph { seed: u64, n: u64, slots: u64, buckets: u64, pilots: Vec<u16>, remap: Vec<u32> }

const LAMBDA: f64 = 4.0; // average keys per bucket: bigger = smaller, slower build

#[inline] fn mix(mut z: u64) -> u64 { // SplitMix64 finaliser: good avalanche, 3 muls
    z = (z ^ (z >> 30)).wrapping_mul(0xBF58476D1CE4E5B9);
    z = (z ^ (z >> 27)).wrapping_mul(0x94D049BB133111EB);
    z ^ (z >> 31)
}
#[inline] fn reduce(h: u64, n: u64) -> u64 { ((h as u128 * n as u128) >> 64) as u64 } // [0, n), no division

impl Mph {
    #[inline] fn hash(&self, key: u64) -> u64 { mix(key ^ self.seed) }
    /// Skewed bucket choice (PTHash): 60 % of keys go to 30 % of buckets, so the big
    /// buckets are placed first, while the table is still empty.
    #[inline] fn bucket(&self, h: u64) -> usize {
        let dense = self.buckets * 3 / 10;
        let r = h.rotate_left(21); // bits not used by the dense/sparse test
        (if h < (u64::MAX / 10) * 6 { reduce(r, dense) }
         else { dense + reduce(r, self.buckets - dense) }) as usize
    }
    #[inline] fn slot(&self, h: u64, pilot: u16) -> u64 {
        // second, independent hash of the key xor a hash of the pilot
        reduce(mix(h ^ mix(pilot as u64 + 1)), self.slots)
    }
    pub fn build(keys: &[u64]) -> Mph {
        let n = keys.len() as u64;
        for seed in 1u64.. {
            let mut m = Mph { seed: mix(seed), n, slots: n + n / 100 + 1,
                buckets: (n as f64 / LAMBDA).ceil() as u64 + 1, pilots: vec![], remap: vec![] };
            if m.try_build(keys) { return m; } // fails only if a bucket needs a pilot > 65535
        }
        unreachable!()
    }
    fn try_build(&mut self, keys: &[u64]) -> bool {
        let mut hashes: Vec<(u32, u64)> = keys.iter()
            .map(|&k| { let h = self.hash(k); (self.bucket(h) as u32, h) }).collect();
        hashes.sort_unstable();                     // groups keys by bucket
        if hashes.windows(2).any(|w| w[0] == w[1]) { return false; } // 64-bit hash clash: reseed
        let mut start = vec![0usize; self.buckets as usize + 1];
        for &(b, _) in &hashes { start[b as usize + 1] += 1; }
        for b in 0..self.buckets as usize { start[b + 1] += start[b]; }
        let mut order: Vec<usize> = (0..self.buckets as usize).collect();
        order.sort_by_key(|&b| std::cmp::Reverse(start[b + 1] - start[b])); // largest first
        self.pilots = vec![0; self.buckets as usize];
        let mut taken = vec![false; self.slots as usize];
        let mut pos = Vec::new();
        for b in order {
            let group = &hashes[start[b]..start[b + 1]];
            if group.is_empty() { break; }          // sorted by size: the rest are empty
            let found = (0..=u16::MAX).find(|&p| {
                pos.clear();
                for &(_, h) in group {
                    let s = self.slot(h, p) as usize;
                    if taken[s] || pos.contains(&s) { return false; }
                    pos.push(s);
                }
                true
            });
            let Some(p) = found else { return false };
            self.pilots[b] = p;
            for &s in &pos { taken[s] = true; }
        }
        // Keys that landed at slot >= n are sent to the free slots < n, in order.
        let mut holes = (0..self.n as usize).filter(|&s| !taken[s]);
        self.remap = (self.n as usize..self.slots as usize)
            .map(|s| if taken[s] { holes.next().unwrap() as u32 } else { u32::MAX }).collect();
        true
    }
    /// Index in [0, n), distinct for every key of the build set; arbitrary for other keys.
    #[inline] pub fn index(&self, key: u64) -> u64 {
        let h = self.hash(key);
        let s = self.slot(h, self.pilots[self.bucket(h)]);
        if s < self.n { s } else { self.remap[(s - self.n) as usize] as u64 }
    }
    pub fn bits_per_key(&self) -> f64 {
        (self.pilots.len() * 16 + self.remap.len() * 32) as f64 / self.n as f64
    }
}

Tested on 10⁷ random u64 keys (Apple M-series): build 2.0 s (order of 200 ns/key), 4.32 bits/key (16 for each pilot / λ = 4, plus 0.32 for the remap), and lookups in a sequential loop at order of 3 ns. Pilots are mostly small: their entropy here is 1.9 bits/key, which is what PTHash's compressed pilot encodings recover.

Complexity and constants

• Query: two hash mixes, one pilot read (a random access into m pilots), and on a 1 % path one remap read. The pilot array is n·bits/8 bytes: 10⁹ keys at 2.4 bits/key is 300 MB, so each query costs about one DRAM miss. Batching queries hides it (PtrHash streams at about 8 ns/key).
• Build: expected O(n), dominated by the bucket sort and by the pilot search for the last buckets. Raising λ shrinks the function and slows the build roughly exponentially; PTHash's α = 0.99 instead of 1.0 cuts build time by 25-35 %.
• Space by family:

Efficiency

• Cost: a query is two hash mixes and one pilot read, so about one DRAM miss: PtrHash streams at order of 8 ns/key on 10⁹ keys (Groot Koerkamp 2025); the code above measured order of 3 ns on 10⁷ keys in a sequential loop (M-series). Memory is 1.5-4 bits per key, e.g. 300 MB for 10⁹ keys at 2.4 bits. Build is order of 200 ns/key here. Bound: memory latency.
• Levers:
  • batch queries with prefetch — hides the pilot miss, streaming near RAM throughput (PtrHash) — bulk lookups
  • raise bucket size λ — fewer bits per key, build slows roughly exponentially (PTHash) — build time is free
  • α = 0.99 instead of 1.0 — build time cut by 25-35 % (PTHash) — always
  • partition keys by hash and build chunks in parallel — parallel and external-memory build (PTHash, BBHash) — 10⁸+ keys
  • 8-16-bit fingerprint per key — rejects non-members at 2⁻⁸ to 2⁻¹⁶ false positives — queries may use unknown keys
• Naive → standard → state of the art:
  • hash table storing keys · full key bytes plus load slack per entry
  • BBHash, CHD · about 2-3.7 bits per key
  • PtrHash (fast), RecSplit / ShockHash (small) · 2.4 bits at order of 8 ns, or 1.49-1.56 bits with slow build

Implementation notes

• Hash once, mix twice: compute one strong 64-bit hash of the key (strings: wyhash, xxh3, see fast hash functions). Bucket and slot are derived from it with cheap mixes, and the build works only on the 64-bit hashes. A clash between two distinct keys makes a perfect function impossible, so reseed; with 64-bit hashes this is about n²/2⁶⁵ (order of 3 % at 10⁹ keys).
• reduce instead of %: (h as u128 * n) >> 64 maps to [0, n) with one multiply (Lemire's fast range).
• Pilot encodings: plain u8 (PtrHash, which places its pilots with cuckoo-style eviction so 8 bits always suffice), fixed-width compact, a dictionary of distinct pilots plus small indices, or Elias-Fano (rank/select bitvectors). Trade a few ns of decoding for 1-2 bits/key.
• Values: store the values in an array indexed by the result. For a membership check, store an 8-16-bit fingerprint per key: false positives become 2⁻⁸-2⁻¹⁶.
• Order-preserving needs: an MPH cannot give each key a chosen index. Add a permutation array of log₂ n bits per key, or use a static function (retrieval data structure) instead.
• Parallel and external build: partition keys by hash into chunks of order of 10⁵-10⁶ keys and build one function per chunk, with a prefix sum of the chunk sizes (PTHash's partitioned build, BBHash's levels).

Pitfalls

• Querying with a key outside the build set and trusting the result: you get some other key's value. Keep fingerprints.
• Weak hashes (identity on integer keys, h % m on low bits): bucket sizes become skewed, the pilot search fails, and the build reseeds forever. Always mix.
• Bucket mapping that reuses the same bits as the dense/sparse test: only part of the bucket range is used, buckets get too big and the build stalls (this bug happened while testing the code above).
• Building from duplicate keys: identical hashes never separate. Deduplicate first.
• Measuring lookups in a loop over the keys in their own array order: memory-level parallelism hides the miss. Benchmark with dependent queries if your real access is dependent.

Variants and alternatives

In production

• Databases: PostgreSQL's PerfectHash.pm generates its keyword lookup at build time.
• Genomics: BBHash in bioinformatics k-mer indexes.
• Compilers and tooling: gperf-style generators for compile-time keyword sets (perfect, not minimal).
• Libraries: pthash (C++), ptr_hash and boomphf (Rust), Sux4J (Java: GOV functions), sux (C++: RecSplit), cmph (C: CHD, BDZ and others).

Implementations

Sources

• Edward A. Fox, Qi Fan Chen, Lenwood S. Heath, A Faster Algorithm for Constructing Minimal Perfect Hash Functions, SIGIR 1992. paper
• Djamal Belazzougui, Fabiano C. Botelho, Martin Dietzfelbinger, Hash, Displace, and Compress, ESA 2009. paper
• Antoine Limasset, Guillaume Rizk, Rayan Chikhi, Pierre Peterlongo, Fast and Scalable Minimal Perfect Hashing for Massive Key Sets, SEA 2017. arXiv · code
• Emmanuel Esposito, Thomas Mueller Graf, Sebastiano Vigna, RecSplit: Minimal Perfect Hashing via Recursive Splitting, ALENEX 2020. arXiv
• Giulio Ermanno Pibiri, Roberto Trani, PTHash: Revisiting FCH Minimal Perfect Hashing, SIGIR 2021. paper · arXiv · code
• Hans-Peter Lehmann, Peter Sanders, Stefan Walzer, ShockHash: Towards Optimal-Space Minimal Perfect Hashing Beyond Brute-Force, ALENEX 2024. arXiv · code
• Ragnar Groot Koerkamp, PtrHash: Minimal Perfect Hashing at RAM Throughput, SEA 2025. arXiv · code