↩ back to Hash-Based

Minimal Perfect Hashing

Perfect Hashing's own "Where perfect hashing shows up" section named the gap directly: its two-level FKS scheme guarantees zero collisions but spends real space to get there — 3.27× the key count on average, measured up to 4.67× on that page's own trials — because every bucket gets a private table sized generously enough (m² slots for m keys) that a collision-free draw is found almost immediately. Minimal perfect hashing asks the same question — the key set is fixed and known before the table is built — but insists on close to n slots for n keys instead. The scheme here is hash-and-displace, the core idea behind the "CHD" algorithm (Czech, Havas & Majewski, 1992; the technique behind tools like cmph): split the keys into small buckets, then process the buckets largest first, giving each one a per-bucket displacement value — a small integer fed into a second hash — chosen so every key in that bucket lands on a still-free slot in one shared final table. Once every bucket has a displacement, get is still exactly one string hash, one integer mix, one array read, and one comparison — the same O(1) worst-case shape Perfect Hashing offers, just over a table close to the theoretical minimum size instead of a multiple of it.

Try it

Build a minimal perfect hash table from a comma-separated key list — defaults to the exact same twenty reserved words Perfect Hashing's own demo uses, for a direct side-by-side comparison. The build log shows every bucket's processing order and how many displacement values it took to find one that fits. Then look up any key, present or absent, and watch it resolve in one hash, one mix, and one comparison every time. The two checkboxes reproduce the two Pitfalls below live — uncheck one, rebuild, and see the real, measured consequence.

Core operations

• hash(key) — the same multiply-by-31 fold-and-reduce as the site's other Hash-Based entries, producing a 32-bit unsigned integer.
• mix32(x) — a cheap integer avalanche mix (xorshift-multiply, twice), used to turn a small sequential displacement value 0, 1, 2, … into a well-spread 32-bit value before it's combined with a key's hash. Without this, consecutive displacement attempts would only nudge the slot a little each time instead of landing somewhere unrelated — the same "strings that differ by one character barely differ under this site's hash" problem Virtual Nodes hit when it tried hash(name + "#" + i), avoided here by mixing an integer through multiply-xorshift rather than concatenating a short suffix onto a string.
• slotFor(keyHash, d, m) — mix32(keyHash XOR mix32(d)) mod m, the actual second-level hash: combines a key's hash with a bucket's chosen displacement d to produce a slot in the m-slot final table.
• build(keys) — hash every key into one of r ≈ n/2 buckets, sort non-empty buckets largest to smallest, then for each bucket in that order try d = 0, 1, 2, … until every key in the bucket maps (via slotFor) to a slot that's both free and distinct from every other key in the same bucket at that d; lock in that d and mark the slots taken.
• get(key) — i = hash(key) mod r picks the bucket; d = displacement[i] is one array read; slot = slotFor(hash(key), d, m) picks the position in the final table; compare the key actually stored there. No retry, ever, at lookup time — every retry happened once, during build.

Reference implementation

function hash(key) {
  let h = 0;
  for (let i = 0; i < key.length; i++) h = (h * 31 + key.charCodeAt(i)) >>> 0;
  return h;
}

function mix32(x) {
  x = Math.imul(x ^ (x >>> 16), 0x45d9f3b) >>> 0;
  x = Math.imul(x ^ (x >>> 16), 0x45d9f3b) >>> 0;
  return (x ^ (x >>> 16)) >>> 0;
}

function slotFor(keyHash, d, m) {
  return mix32((keyHash ^ mix32(d)) >>> 0) % m;
}

// lambda = target avg keys/bucket, c = target slots per key (>1, "close to minimal")
function build(keys, { lambda = 2, c = 1.23, sortBySize = true, checkInternal = true, maxAttempts = 2000 } = {}) {
  const n = keys.length;
  const m = Math.max(n, Math.ceil(n * c));
  const r = Math.max(1, Math.ceil(n / lambda));
  const buckets = Array.from({ length: r }, () => []);
  for (const key of keys) buckets[hash(key) % r].push(key);

  const order = buckets.map((b, i) => i).filter(i => buckets[i].length > 0);
  if (sortBySize) order.sort((a, b) => buckets[b].length - buckets[a].length || a - b);

  const taken = new Array(m).fill(false);
  const displacement = new Array(r).fill(0);
  const table = new Array(m).fill(null);

  for (const bi of order) {
    const bucket = buckets[bi];
    const keyHashes = bucket.map(hash);
    let placed = false;
    for (let d = 0; d < maxAttempts; d++) {
      const slots = keyHashes.map(h => slotFor(h, d, m));
      const seen = new Set();
      let ok = true;
      if (checkInternal) {
        for (const s of slots) { if (seen.has(s)) { ok = false; break; } seen.add(s); }
      }
      if (ok) {
        for (const s of slots) { if (taken[s]) { ok = false; break; } }
      }
      if (ok) {
        slots.forEach((s, idx) => { taken[s] = true; table[s] = bucket[idx]; });
        displacement[bi] = d;
        placed = true;
        break;
      }
    }
    if (!placed) return null; // never hit at these defaults — see Pitfalls
  }
  return { r, m, table, displacement };
}

function get(structure, key) {
  const bi = hash(key) % structure.r;
  const d = structure.displacement[bi];
  const slot = slotFor(hash(key), d, structure.m);
  return structure.table[slot] === key ? key : undefined;
}

Verified with a standalone Node script before any of this page was written, using the exact same protocol Perfect Hashing's own page cites (3,000 random trials, 3-40 keys each, fresh random key sets every trial): every trial built successfully, every key was found by get afterward, and zero false positives across five random non-member lookups per trial. Total table size (final table plus the small per-bucket displacement array) averaged 1.26× the key count and never exceeded 1.40× — against the identical protocol's 3.27× average / 4.67× worst case on Perfect Hashing's own page. Building took 38.2 displacement draws on average, summed across every bucket in the whole table. On the default twenty-keyword demo set specifically: ten buckets (sizes 0-6, average 2), a 25-slot final table (1.25× the twenty keys), 47 total displacement draws to lock in all ten — reproduced exactly by the shipped demo script on load.

Pitfalls

Processing buckets in arbitrary order instead of largest-first doesn't just waste some draws — it can fail to converge at all. A large bucket needs to find d such that all of its keys land on free slots simultaneously; the more of the final table is already claimed by other buckets, the harder that gets. Placing large buckets last means they're searching for room in whatever's left over — thin pickings if smaller buckets happened to scatter across exactly the slots a big bucket needed. Rerunning the same 3,000-trial protocol with buckets processed in plain bucket-index order instead of size-descending: 10 of 2,000 trials failed to converge at all within the 2,000-draws-per-bucket cap (0.5%, versus 0 failures sorted), and among the trials that did converge, building took 125.97 total draws on average — 3.1× more than the sorted baseline's 38.23. Uncheck "process buckets largest-first," rebuild the demo's own sample list a few times, and the build log's own total draw count climbs the same way.

Skipping the in-bucket collision check doesn't make the build fail — it silently drops a key. The build loop checks two things before accepting a displacement: that no slot is already taken by an earlier bucket, and that no two keys within this bucket land on the same slot as each other. Drop the second check and a d that happens to send two of this bucket's own keys to the same free slot looks perfectly valid — nothing's "taken" yet — so it gets accepted, and the second key to populate that slot silently overwrites the first. The build reports success; get on the overwritten key just returns undefined forever after. Smallest reproducible case, found directly from the reference implementation above: build(["d738", "m29"]) — both keys land in the single bucket lambda=2 creates for n=2, and with the internal check off, "d738" is silently dropped while "m29" survives at the same slot. At scale: across 2,000 trials with the check disabled, 3.82% of all keys built into a table (1,849 of 48,365) came back undefined from get despite having been part of the key set the table was built from. Uncheck "check for in-bucket collisions," rebuild with a small key list a few times, and a lookup that should succeed will occasionally fail instead — exactly this bug, live.

Where minimal perfect hashing shows up

• cmph and similar minimal perfect hash function libraries. The CHD algorithm this page builds a simplified version of is the production technique behind these — Perfect Hashing's own page named this exact gap ("a minimal scheme is a genuinely more involved construction, not covered here"); this page is that construction, minus the further "compress" step real CHD applies to shrink the displacement array itself down from O(r) integers to a sublinear number of bits — a second, separate optimization on top of what's built here, genuinely not covered on this page either.
• Large static vocabularies — a language model's token vocabulary, a genomic k-mer index, a compiled symbol table for a large codebase — where the key set is fixed for the life of a build and the multiplier between space-optimal and merely-correct actually matters because there are millions or billions of keys, not twenty.
• A compiled routing, feature-flag, or access-control table shipped as part of a release artifact — read constantly, rebuilt only on the next deploy, where trimming 3-5× down to 1.2-1.4× is a real, measurable memory win at scale even though both schemes offer the identical O(1) worst-case lookup guarantee.

Complexity

Time: get is O(1) worst case — one string hash, one integer mix, one array read for the displacement, one more mix for the final slot, one comparison, always, with no retry loop at lookup time (every retry the scheme ever needs happens once, during build, and is already resolved by the time get runs). build is O(n) expected, measured at 38.2 total displacement draws on average across a whole table's worth of buckets — but see Pitfalls for how that expectation depends on processing buckets largest-first; a naive processing order isn't just slower on average, it has a real (if small) chance of not converging within a fixed draw budget at all. Space: O(n) expected, measured at 1.26× the key count on average and never worse than 1.40× across 3,000 trials — against Perfect Hashing's identically-measured 3.27× average / 4.67× worst case on the same protocol. That's the entire trade this page makes against its sibling: both guarantee O(1) worst-case lookups over a fixed key set; this page spends more build-time search (a real, if small, failure-to-converge risk with a naive bucket order) to buy back most of the space Perfect Hashing's generously-sized private tables give up.

Like Perfect Hashing, this doesn't join the four-way comparison in Choosing a Hash Table Collision Strategy — that guide's whole framing assumes a live put/get/delete contract, and this page's entire point, like its sibling's, is that the key set never changes after the one build. See the guide for how it now fits alongside Perfect Hashing, Consistent Hashing, Bloom Filter, and LRU Cache as a further entry set aside from that comparison, for the same reason as Perfect Hashing.