Minimal Perfect Hashing

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)$ 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.

Enter up to 10 comma-separated keys below and click Build MPH. The demo uses a two-level scheme: a small pilot table $h_{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">{{hint}}</p>
<div class="input-row">
  <input id="keys-input" type="text" value="apple,banana,cherry,date,elderberry,fig" placeholder="{{keys_placeholder}}" />
  <button id="build-btn" type="button">{{build_btn}}</button>
</div>
<div id="error-msg" class="error-msg"></div>
<div id="result-area" class="result-area" style="display:none">
  <div class="section-label">{{section_hash_table}}</div>
  <div id="slots-grid" class="slots-grid"></div>
  <div class="section-label" style="margin-top:1rem">{{section_verify}}</div>
  <div class="lookup-row">
    <input id="lookup-input" type="text" placeholder="{{lookup_placeholder}}" />
    <button id="lookup-btn" type="button">{{lookup_btn}}</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; }

// Code not found

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.

How efficient can a minimal perfect hash be?

• Lookup is $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!)$ ≈ n $\log_{2}$ n – n $\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)$ expected construction time and $O(1)$ lookup. This is within a small constant of optimal.
• Construction is expected $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.

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)$ 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.

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)$ expected construction and $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.