Perfect Hashing

Every programmer has hit it: you insert a key and it lands in the same slot as another. A collision. The usual fixes — chaining, open addressing — keep lookups fast on average, but the worst case can still drag to $O(n)$.

Perfect hashing sidesteps the problem entirely. If you know the complete set of keys in advance and that set never changes, you can build a hash table with zero collisions — every key maps to a unique slot, and every lookup takes exactly $O(1)$ time, no matter what.

The scheme was made rigorous in 1984 by Michael Fredman, János Komlós, and Endre Szemerédi (the FKS scheme), who proved you can achieve this in $O(n)$ space and construct the table in expected $O(n)$ time. That result sits at a remarkable intersection: a data structure whose worst-case guarantee matches the theoretical lower bound for the problem.

Enter up to twelve short keys below (words, numbers, anything). Click Build perfect table and watch the two-level FKS scheme place every key in its own collision-free slot.

<div class="ph-wrap">
  <div class="input-row">
    <input id="keyinput" type="text" placeholder='{{ph_key_input}}' maxlength="20" autocomplete="off" />
    <button id="build" type="button">{{btn_build}}</button>
    <button id="reset" type="button" class="ghost">{{btn_clear}}</button>
  </div>
  <div id="tag-row" class="tag-row"></div>
  <div id="lookup-row" class="lookup-row" style="display:none">
    <input id="lookupinput" type="text" placeholder="{{ph_lookup}}" maxlength="20" autocomplete="off" />
    <button id="lookupbtn" type="button">{{btn_lookup}}</button>
  </div>
  <div id="status" class="status"></div>
  <div id="viz" class="viz"></div>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #1d2b3a; margin: 0; font-size: 14px; }
.ph-wrap { padding: 4px 0; }
.input-row { display: flex; gap: 6px; flex-wrap: wrap; margin-bottom: 6px; }
input[type=text] { flex: 1; min-width: 0; padding: .4rem .6rem; border: 1px solid #c0c8d2;
  border-radius: 7px; font: inherit; font-size: 13px; }
button { padding: .4rem .9rem; border: 1px solid #1d3557; background: #1d3557;
  color: #fff; border-radius: 7px; cursor: pointer; font: 600 13px system-ui; white-space: nowrap; }
button.ghost { background: #fff; color: #1d3557; }
.tag-row { display: flex; flex-wrap: wrap; gap: 5px; min-height: 22px; margin-bottom: 6px; }
.tag { background: #e2eaf3; border: 1px solid #b5c7d9; border-radius: 5px;
  padding: 2px 7px; font-size: 12px; display: flex; align-items: center; gap: 4px; }
.tag span.rm { cursor: pointer; color: #888; font-size: 14px; line-height: 1; }
.tag span.rm:hover { color: #c92f3c; }
.lookup-row { display: flex; gap: 6px; margin-bottom: 6px; }
.status { font-size: 13px; font-weight: 600; min-height: 1.3em; margin-bottom: 6px; }
.status.ok { color: #0a7d33; } .status.bad { color: #c92f3c; } .status.info { color: #1d3557; }
.viz { display: flex; flex-direction: column; gap: 8px; }
.level-label { font-size: 11px; font-weight: 700; text-transform: uppercase;
  letter-spacing: .06em; color: #5a7088; margin-bottom: 2px; }
.l1-row { display: flex; gap: 4px; flex-wrap: wrap; }
.bucket-box { border: 1.5px solid #b5c7d9; border-radius: 8px; padding: 5px 7px;
  min-width: 52px; text-align: center; background: #f4f7fa; position: relative; }
.bucket-box.has-keys { border-color: #4a90d9; background: #e9f2fc; }
.bucket-box.collision { border-color: #e08000; background: #fff7e6; }
.b-idx { font-size: 10px; color: #8a9bb0; margin-bottom: 3px; }
.b-keys { display: flex; flex-direction: column; gap: 2px; align-items: center; }
.b-key { background: #1d3557; color: #fff; border-radius: 4px; padding: 1px 5px;
  font-size: 11px; font-weight: 600; font-family: ui-monospace, monospace; }
.l2-section { margin-top: 4px; }
.l2-grid { display: flex; gap: 3px; flex-wrap: wrap; margin-top: 3px; }
.l2-cell { border: 1.5px solid #b5c7d9; border-radius: 5px; min-width: 44px; height: 32px;
  display: flex; align-items: center; justify-content: center;
  font-size: 11px; font-family: ui-monospace, monospace; background: #f9fbfc; }
.l2-cell.occupied { border-color: #0a7d33; background: #e6f7ee; color: #0a7d33; font-weight: 700; }
.l2-cell.empty { color: #c0c8d2; }
.highlight { outline: 2.5px solid #f5a623; outline-offset: 1px; border-radius: 5px; }

// Code not found

Notice that the first level assigns keys to buckets, and each bucket that holds more than one key gets its own tiny second-level table sized to avoid collisions within that bucket. Lookup any key and the table reaches it in exactly two hash evaluations — first-level bucket, second-level slot — with zero possibility of collision.

How does the math hold up?

• $O(1)$ worst-case lookup is the headline. Once built, every query takes exactly two hash evaluations — no chains, no probing sequences, no bad cases.
• $O(n)$ space is tight. A naïve approach — one big table of size $n^{2}$ — also avoids collisions but wastes space. The FKS trick keeps the total second-level space to $O(n)$ by sizing each bucket's inner table proportional to the square of that bucket's load, then choosing a first-level hash that keeps buckets small.
• Construction in expected $O(n)$ time. The tables are built by sampling random hash functions from a universal family. The probability that any two keys collide under a randomly chosen function is at most 1/m (where m is table size). A birthday-paradox argument shows the expected total collisions across all buckets is $O(n)$, so only a constant number of resamples are needed before a collision-free assignment is found.
• Proven optimal. Any comparison- or RAM-model lookup structure for n keys needs Ω(1) time per query; perfect hashing matches this bound with a direct-address scheme. The $O(n)$ space is also optimal up to a constant.

Perfect hashing is therefore a solved problem in the strongest sense: both the time and space bounds are tight. It contrasts with pattern matching or sorting lower bounds, where tight bounds require significantly deeper arguments.

Whenever a key set is fixed at build time and reads vastly outnumber writes, perfect hashing delivers the maximum possible guarantee:

• Compiler keyword tables: every language has a fixed set of reserved words (if, while, return, …). Compilers tokenize millions of identifiers against this set; a perfect hash table makes every check $O(1)$.
• Network routing (TCAM alternatives): IP prefix tables used in routers are increasingly replaced by perfect or minimal perfect hash structures, cutting memory and lookup latency.
• Static dictionaries and spell-checkers: a dictionary of 200 000 words never changes. Build once, query billions of times — perfect hashing eliminates every wasted cycle.
• Read-only databases and configuration tables: embedded systems and game engines that bake data at compile time use minimal perfect hashing to turn any fixed record set into a zero-overhead lookup.
• Security: password hashing is not this: worth clarifying — cryptographic password hashing (bcrypt, Argon2) is a different concept designed to be slow. Perfect hashing is purely about speed and space for data lookup.

The common thread is static + read-heavy. Add mutations and you're back to dynamic hashing — but for the enormous class of problems where the keys don't change, perfect hashing gives you the fastest possible answer with a mathematical proof attached.

Perfect hashing is one of those elegant corners of computer science where the problem is genuinely solved: for a fixed key set you can build a table that never collides, answers every query in $O(1)$ worst-case time, uses only $O(n)$ space, and can be constructed in expected $O(n)$ time. Every bound is tight.

The FKS result from 1984 remains the canonical answer, and its core idea — two levels of universal hashing, with inner tables sized to eliminate collisions — is simple enough to implement from scratch yet rigorous enough to carry a proof. The next time you reach for a dictionary in a performance-critical path and the keys are fixed, you no longer have to accept average-case luck: perfect hashing gives you a certainty.