Introduction

Every time software looks up a keyword, a command, or a reserved word, it reaches into a hash table — a structure that maps keys to slots in an array using a mathematical function. Most hash tables are built for the unknown: keys arrive at runtime, so the function has to work for anything. That generality comes at a cost: collisions (two keys landing on the same slot) require extra bookkeeping, and the table must be larger than the key set to keep collisions rare.

But sometimes the key set is fixed in advance. A compiler knows its keywords at build time. A DNS resolver stores a static block of domain names. A router ships with a set of port numbers hardwired into firmware. For these cases, doing the extra work once — at construction time — pays off every time a lookup runs.

A minimal perfect hash function (MPHF) does exactly that: given n distinct keys, it maps each one to a unique slot in {0, 1, …, n-1}. The table has no wasted entries and no collision chains. Every lookup is a single array access in O(1)O(1) time, with zero overhead for collision resolution — the theoretical minimum for a hash-based lookup.

The puzzle is that building such a function is far from obvious. The keys need not be numbers, the slots must be exactly 0 to n-1, and the function must stay fast to evaluate. The answer turns out to involve randomness, graph theory, and a clever multi-level trick.

Try It: Build a Minimal Perfect Hash

Enter up to 10 comma-separated keys below and click Build MPH. The demo uses a two-level scheme: a small pilot table h1h_{1} maps keys to groups; within each group a per-group offset d is chosen so every key in the group lands in a free slot. Every key gets its own unique slot in 0..n-1 — zero collisions, zero gaps.

<p class="hint">Enter up to 10 comma-separated keys, then click <b>Build MPH</b>. Each key gets mapped to a unique slot in 0..n-1 — no collisions, no gaps.</p>
<div class="input-row">
  <input id="keys-input" type="text" value="apple,banana,cherry,date,elderberry,fig" placeholder="key1,key2,key3,..." />
  <button id="build-btn" type="button">Build MPH</button>
</div>
<div id="error-msg" class="error-msg"></div>
<div id="result-area" class="result-area" style="display:none">
  <div class="section-label">Hash table (slot → key)</div>
  <div id="slots-grid" class="slots-grid"></div>
  <div class="section-label" style="margin-top:1rem">Verify a lookup</div>
  <div class="lookup-row">
    <input id="lookup-input" type="text" placeholder="Type a key to look up…" />
    <button id="lookup-btn" type="button">Look up</button>
  </div>
  <div id="lookup-result" class="lookup-result"></div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 15px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .75rem; line-height: 1.45; }
.input-row { display: flex; gap: .5rem; flex-wrap: wrap; }
#keys-input { flex: 1; min-width: 0; padding: .42rem .7rem; border: 1px solid #adb1b8;
  border-radius: 8px; font: inherit; font-size: .9rem; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
  border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; white-space: nowrap; }
button:hover { background: #16294a; }
.error-msg { color: #c92f3c; font-size: .88rem; min-height: 1.3em; margin-top: .3rem; }
.result-area { margin-top: .9rem; }
.section-label { font-size: .8rem; font-weight: 700; text-transform: uppercase;
  letter-spacing: .06em; color: #6b7280; margin-bottom: .4rem; }
.slots-grid { display: flex; flex-wrap: wrap; gap: 6px; }
.slot { display: flex; flex-direction: column; align-items: center; justify-content: center;
  width: 80px; min-height: 60px; border-radius: 10px; border: 1.5px solid #cdd9e3;
  background: #eaf1f7; padding: 4px 6px; text-align: center; transition: background .15s; }
.slot.active { background: #d0f0db; border-color: #4caf7a; }
.slot.highlight { background: #ffe87a; border-color: #c9a800; }
.slot-index { font-size: .72rem; font-weight: 700; color: #6b7280; margin-bottom: 2px; }
.slot-key { font-size: .78rem; font-weight: 600; color: #1d3557; word-break: break-all; line-height: 1.2; }
.lookup-row { display: flex; gap: .5rem; flex-wrap: wrap; }
#lookup-input { flex: 1; min-width: 0; padding: .42rem .7rem; border: 1px solid #adb1b8;
  border-radius: 8px; font: inherit; font-size: .9rem; }
.lookup-result { margin-top: .5rem; font-size: .9rem; font-weight: 600; min-height: 1.4em; }
.lookup-result.ok { color: #0a7d33; }
.lookup-result.miss { color: #c92f3c; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Minimal Perfect Hash — CHD-style two-level construction
// Level 1: a pilot hash h1(key, seed) assigns each key to a "bucket".
// Level 2: for each bucket (sorted by size desc), find an offset d such that
//          h2(key, d) lands in a free slot for every key in the bucket.
// Lookup:  slot = h2(key, d[h1(key, seed)])
//
// This is a simplified CHD (Compress, Hash, Displace).
// All hashing uses a simple polynomial rolling hash modulo n (or bucket count).

function polyHash(str, seed, mod) {
  // Deterministic "random" multiplier from seed
  let h = seed ^ 0xdeadbeef;
  for (let i = 0; i < str.length; i++) {
    h = Math.imul(h ^ str.charCodeAt(i), 0x9e3779b9 + i);
    h ^= h >>> 16;
  }
  h = Math.imul(h ^ (seed * 0x45d9f3b), 0x119de1f3);
  h ^= h >>> 16;
  return ((h >>> 0) % mod + mod) % mod;
}

function buildMPH(keys) {
  const n = keys.length;
  if (n === 0) return null;

  const NUM_BUCKETS = Math.max(1, Math.ceil(n / 2)); // ~n/2 buckets → avg ~2 keys/bucket

  // Try different seeds for the pilot hash until we find one with no empty buckets
  // causing issues. In practice the first seed almost always works for small n.
  let seed = 1, buckets, maxTries = 200;

  outer:
  for (let attempt = 0; attempt < maxTries; attempt++, seed++) {
    buckets = Array.from({ length: NUM_BUCKETS }, () => []);
    for (const k of keys) {
      buckets[polyHash(k, seed, NUM_BUCKETS)].push(k);
    }

    // Sort buckets by size descending (larger buckets are harder; place them first)
    const order = Array.from({ length: NUM_BUCKETS }, (_, i) => i)
      .sort((a, b) => buckets[b].length - buckets[a].length);

    const slots = new Array(n).fill(null); // final table
    const d = new Array(NUM_BUCKETS).fill(0);  // per-bucket offset

    let ok = true;
    for (const bi of order) {
      const bkeys = buckets[bi];
      if (bkeys.length === 0) { d[bi] = 0; continue; }

      let found = false;
      for (let offset = 0; offset < n * 4 + 10; offset++) {
        // Try placing all keys in bucket bi with this offset
        const taken = [];
        let conflict = false;
        for (const k of bkeys) {
          const slot = polyHash(k, offset, n);
          if (slots[slot] !== null || taken.includes(slot)) { conflict = true; break; }
          taken.push(slot);
        }
        if (!conflict) {
          // Commit
          for (let i = 0; i < bkeys.length; i++) slots[taken[i]] = bkeys[i];
          d[bi] = offset;
          found = true;
          break;
        }
      }
      if (!found) { ok = false; break; }
    }
    if (ok) {
      return { seed, d, slots, n, NUM_BUCKETS };
    }
  }
  return null; // failed (shouldn't happen for n ≤ 10)
}

function mphLookup(key, mph) {
  const bi = polyHash(key, mph.seed, mph.NUM_BUCKETS);
  const slot = polyHash(key, mph.d[bi], mph.n);
  return { slot, stored: mph.slots[slot] };
}

// ── UI ──────────────────────────────────────────────────────────────────────
let currentMPH = null;
let currentHighlight = -1;

function renderSlots(highlight = -1) {
  if (!currentMPH) return;
  currentHighlight = highlight;
  const grid = document.getElementById('slots-grid');
  grid.innerHTML = '';
  currentMPH.slots.forEach((key, i) => {
    const div = document.createElement('div');
    div.className = 'slot' + (key ? ' active' : '') + (i === highlight ? ' highlight' : '');
    const idx = document.createElement('div'); idx.className = 'slot-index'; idx.textContent = fmt('slot %i%', { i: i });
    const kd = document.createElement('div'); kd.className = 'slot-key'; kd.textContent = key || '—';
    div.appendChild(idx); div.appendChild(kd);
    grid.appendChild(div);
  });
}

document.getElementById('build-btn').addEventListener('click', () => {
  const raw = document.getElementById('keys-input').value;
  const keys = raw.split(',').map(s => s.trim()).filter(Boolean);
  const errEl = document.getElementById('error-msg');
  const resultArea = document.getElementById('result-area');
  const lookupRes = document.getElementById('lookup-result');

  errEl.textContent = '';
  lookupRes.textContent = '';
  lookupRes.className = 'lookup-result';

  if (keys.length === 0) { errEl.textContent = 'Enter at least one key.'; return; }
  if (keys.length > 10) { errEl.textContent = 'Max 10 keys in this demo.'; return; }
  const uniq = new Set(keys);
  if (uniq.size !== keys.length) { errEl.textContent = 'Keys must be distinct.'; return; }

  const mph = buildMPH(keys);
  if (!mph) { errEl.textContent = 'Construction failed — try different keys.'; return; }

  currentMPH = mph;
  resultArea.style.display = '';
  renderSlots(-1);

  // Verify correctness internally
  let allOk = true;
  for (const k of keys) {
    const { slot, stored } = mphLookup(k, mph);
    if (stored !== k) { allOk = false; break; }
  }
  console.log(fmt('MPH built. n=%length% seed=%seed% allCorrect=%allOk%', { length: keys.length, seed: mph.seed, allOk: allOk }));
  console.log('Slots:', mph.slots.join(', '));
});

document.getElementById('lookup-btn').addEventListener('click', () => {
  if (!currentMPH) return;
  const key = document.getElementById('lookup-input').value.trim();
  const res = document.getElementById('lookup-result');
  if (!key) { res.textContent = 'Enter a key to look up.'; res.className = 'lookup-result'; return; }

  const { slot, stored } = mphLookup(key, currentMPH);
  renderSlots(slot);

  if (stored === key) {
    res.textContent = fmt('✓ "%key%" → slot %slot% (found!)', { key: key, slot: slot });
    res.className = 'lookup-result ok';
  } else {
    res.textContent = fmt('✗ "%key%" → slot %slot% but stored"%v%" — key not in set', { key: key, slot: slot, v: stored || '—' });
    res.className = 'lookup-result miss';
  }
});

// Trigger initial build
document.getElementById('build-btn').click();
Result
Console

Notice that checking is instant: just evaluate h(key) and compare. Building requires a search — for each group, the demo tries offsets d = 0, 1, 2, … until the group's keys all land in free slots. With a good pilot hash the groups are small and the search terminates quickly; with a bad one you must retry with a different seed. This construction phase is what separates a minimal perfect hash from a plain hash table.

The Real Complexity

How efficient can a minimal perfect hash be?

  • Lookup is O(1)O(1): evaluating the function requires a constant number of operations regardless of n. There are no collision chains, no probing sequences, no linked lists.
  • Space lower bound: any data structure that correctly identifies which slot each of n keys maps to must store at least log⁡2(n!)\log_{2}(n!) ≈ n log⁡2\log_{2} n – n log⁡2\log_{2} e ≈ 1.44n bits. This is an information-theoretic floor — you cannot compress a bijection over n items below it.
  • Practical constructions reach ≈ 2.08n bits: the CHD algorithm (Compress, Hash, and Displace — Belazzougui et al., ESA 2009) achieves ~2.08 bits per key with O(n)O(n) expected construction time and O(1)O(1) lookup. This is within a small constant of optimal.
  • Construction is expected O(n)O(n): modern algorithms build the function in linear expected time by choosing random hash seeds and verifying that no group produces a conflict. If a seed fails, a new one is drawn — the probability of needing many retries falls off exponentially.
  • Status: solved. Unlike P vs NP or open combinatorial problems, minimal perfect hashing has tight theoretical bounds and practical constructions that nearly match them. The field is mature; current research focuses on smaller constants and GPU-friendly variants.

The contrast with ordinary pattern matching or graph coloring is instructive: those are NP-hard or NP-complete; minimal perfect hashing is in P, with an elegant linear-time solution.

Where It Matters

Minimal perfect hashing shines wherever a key set is known at build time and lookups must be as fast as possible:

  • Compiler and interpreter internals: every language keyword (if, while, class, …) is hashed at compile time. An MPHF turns the keyword table into a single array dereference with no collision overhead — critical in parsers that may tokenize millions of lines per second.
  • Network routing: forwarding tables and access-control lists in routers can be frozen into MPHFs. A packet lookup then costs one memory read, important at line rates of 100 Gbps or more.
  • Search engines and databases: inverted index lookup, spell-check dictionaries, and stop-word filters operate on static word lists. An MPHF lets the engine skip hash-collision logic entirely, shaving milliseconds off query latency at scale.
  • Embedded and firmware systems: microcontrollers with kilobytes of RAM use MPHFs to look up configuration tables without allocating spare slots, because wasted memory can be prohibitive.
  • Content-addressable storage: deduplication systems store a fixed set of content hashes in an MPHF so membership queries take O(1)O(1) space-optimal storage — no bloom filter false positives, no wasted slots.

In every case the trade-off is the same: invest construction time once, amortize it over a huge number of lookups. Whenever queries outnumber inserts by orders of magnitude, a minimal perfect hash wins over every dynamic alternative.

Conclusion

Minimal perfect hashing is one of those rare cases in computer science where theory and practice meet cleanly. The information-theoretic lower bound says you need at least ~1.44n bits to encode any bijection over n keys. Modern algorithms like CHD reach ~2.08n bits with O(n)O(n) expected construction and O(1)O(1) lookup — close enough to optimal that the gap matters only in the most extreme memory-constrained settings.

The key insight is that knowing the key set in advance transforms a hard general problem into a tractable one. You trade off a one-time construction cost for a structure that answers every subsequent query in the fastest possible way, with no wasted space and no collision overhead.

Hash tables are everywhere, but most of them are quietly over-engineered for a dynamic world they'll never see. When the keys are fixed, a minimal perfect hash is the right tool — and the theory guaranteeing it exists and can be built efficiently is both elegant and complete.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/minimal-perfect-hashing/Content licensed under CC BY-NC 4.0.