↩ back to Hash-Based

Perfect Hashing

Every other Hash-Based entry on this site assumes the key set keeps moving — keys arrive and leave, and put/get/delete all have to keep working on a live table. The site's chaining hash table, cuckoo hashing, and Robin Hood hashing pages are three different answers to "how do I resolve a collision while the set can still change." Perfect hashing asks a genuinely different question: what if the whole key set is already known, in full, before the table is ever built? A language's reserved keywords, a fixed list of country codes, a compiled routing table, a build's set of interned strings — in every one of these the set is settled first and queried many times after. Given that, it's possible to build a table where a single get is guaranteed O(1) in the worst case, not just on average — no chain to walk, no eviction cycle to worry about, no "richer neighbor" to swap with, ever, at lookup time.

The scheme here is two-level hashing (Fredman, Komlós & Szemerédi, 1984 — "FKS hashing"). Level one: hash all n keys into n buckets with a randomly chosen hash function, same as an ordinary hash table — except the function is only kept if the resulting buckets are provably well-balanced (formally: the number of colliding pairs across all buckets is at most n); a bad draw is thrown away and a fresh one tried. Level two: for each bucket that ends up holding m keys, build a private hash table sized m² slots with its own randomly chosen hash function, again redrawn until that one small table has zero internal collisions — a table with m² slots for m keys makes a collision-free draw likely on almost every try (the birthday bound), so this converges fast. Once both levels are locked in, get is exactly two hash computations and one comparison, always — hash into a bucket, hash again inside that bucket's own private table, compare the key stored there.

Try it

Build a perfect hash table from a comma-separated key list (defaults to twenty reserved words a language keyword table might hold). The build log shows every attempt at each level — how many random draws it took to get a balanced first-level split, and how many it took to get a collision-free private table for each bucket. Then look up any key, present or absent, and watch it always take exactly two hash computations, no matter how the table was built or how many keys it holds. The two checkboxes reproduce the two Pitfalls below live — uncheck one, rebuild, and see the real, measured consequence rather than just reading about it.

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.
• universal(x, a, b, m) — the actual hash used at both levels: ((a·x + b) mod p) mod m for a prime p larger than any 32-bit value (4294967311, the smallest prime above 2³²) and freshly random a, b on every attempt. This is a family of hash functions, not one fixed function — the whole scheme works by trying members of this family until one behaves well enough, then locking it in.
• build(keys) — draw random (a₁, b₁), hash every key into one of n buckets, and check whether the buckets are balanced (colliding pairs ≤ n); redraw until they are. Then, per bucket of size m, draw random (aᵢ, bᵢ) for an m²-slot private table and redraw until every key in that bucket lands in its own slot.
• get(key) — i = universal(hash(key), a₁, b₁, n) picks the bucket; slot = universal(hash(key), aᵢ, bᵢ, sizeᵢ) picks the position inside that bucket's private table; compare the key actually stored at slot. Found or not, that's the whole lookup — O(1) worst case, not amortized, not average.

Reference implementation

const P = 4294967311n; // smallest prime greater than 2^32

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

// x, a, b are ordinary numbers below 2^32; the multiply happens in BigInt
// so it can't silently lose precision the way `(a * x) % p` would past 2^53.
function universal(x, a, b, m) {
  const r = (BigInt(a) * BigInt(x) + BigInt(b)) % P;
  return Number(r) % m;
}

function randCoeff() { return 1 + Math.floor(Math.random() * (Number(P) - 1)); }
function randOffset() { return Math.floor(Math.random() * (Number(P) - 1)); }

function buildLevel2(keys, size, maxAttempts) {
  for (let attempt = 1; attempt <= maxAttempts; attempt++) {
    const a = randCoeff(), b = randOffset();
    const table = new Array(size).fill(null);
    let ok = true;
    for (const key of keys) {
      const slot = universal(hash(key), a, b, size);
      if (table[slot] !== null) { ok = false; break; }
      table[slot] = key;
    }
    if (ok) return { a, b, table, attempts: attempt };
  }
  return null; // never hit in practice — see Pitfalls for how bad this can still get
}

function build(keys, { balanced = true, square = true, maxAttempts = 500 } = {}) {
  const n = keys.length;
  let a1, b1, buckets, level1Attempts = 0;
  for (let attempt = 1; attempt <= maxAttempts; attempt++) {
    a1 = randCoeff(); b1 = randOffset();
    buckets = Array.from({ length: n }, () => []);
    for (const key of keys) buckets[universal(hash(key), a1, b1, n)].push(key);
    level1Attempts = attempt;
    if (!balanced) break; // Pitfall: accept the first draw, no matter how skewed
    const collidingPairs = buckets.reduce((s, b) => s + (b.length * (b.length - 1)) / 2, 0);
    if (collidingPairs <= n) break;
  }

  const level2 = [];
  for (const bucket of buckets) {
    if (bucket.length <= 1) { level2.push({ table: bucket, size: 1 }); continue; }
    const size = square ? bucket.length * bucket.length : bucket.length;
    const built = buildLevel2(bucket, size, maxAttempts);
    if (!built) return null;
    level2.push({ ...built, size });
  }
  return { a1, b1, n, buckets, level2, level1Attempts };
}

function get(structure, key) {
  const x = hash(key);
  const i = universal(x, structure.a1, structure.b1, structure.n);
  const bucket = structure.level2[i];
  if (bucket.size === 1) return bucket.table[0] === key ? key : undefined;
  const slot = universal(x, bucket.a, bucket.b, bucket.size);
  return bucket.table[slot] === key ? key : undefined;
}

Verified with a standalone Node script before any of this page was written: 3,000 random trials (3–40 keys each, fresh random key sets every trial) built successfully every time with the default settings, with every one of the keys found by get afterward and zero false positives across five random non-member lookups per trial. Level-1 needed a fresh draw on average 1.01 times (max observed: 2); level-2 needed 1.36 draws on average per bucket (max observed: 8) — both close to the theoretical expectation of "usually the first try, rarely a second." Total table size (level 1 plus every level-2 table combined) averaged 3.27× the number of keys and never exceeded 4.67× across the 3,000 trials, consistent with the scheme's O(n) space guarantee. The maxAttempts cap of 500 is a safety valve for a demo running in a browser tab, not a real limit the algorithm needs — see Pitfalls for what it takes to actually threaten it.

Pitfalls

Skipping the level-1 balance check removes the only thing standing between "expected O(n)" and "however bad the draw happens to be." The random draw at level one usually spreads keys out reasonably on the first try — that's what the "avg 1.01 attempts" figure above is really measuring — but nothing about picking a and b at random guarantees it. The most extreme version makes this concrete without needing luck at all: set the multiplier a to 0 and the hash becomes b mod n for every single key, regardless of what the key is — every key lands in the same bucket. Run that through the reference implementation above with 10 keys: one bucket of size 10, the other nine empty, a collision-pair count of 45 against the balance check's own threshold of 10, and that one bucket alone needs a 100-slot private table — 10× the space of 10 keys, not the roughly 3–5× the balanced version measures. The balance check exists specifically to reject draws partway toward this outcome, not just the a = 0 extreme, before they're ever locked in — uncheck "keep level-1 buckets balanced" and rebuild the demo's own sample list a few times to see real (smaller, since 20 random keys rarely collide as badly as a deliberately degenerate hash does) but non-zero versions of the same effect.

Shrinking a bucket's private table from m² down to m slots doesn't cost "a bit more time" — it changes how often the retry loop succeeds at all. A throwaway measurement script isolated one bucket size at a time, forcing exactly m keys into a table of the given size and counting draws to zero collisions, 2,000 trials per size:

The birthday-bound argument behind this page's m² choice guarantees a collision-free draw more than half the time on any attempt, which is why the square-size column barely moves as bucket size grows. Drop to m slots — exactly enough room for the keys, no more — and the same birthday argument runs the other way: a handful of keys sharing m slots collides more often than not, so the loop keeps redrawing, sometimes for dozens of tries, and the demo's own 500-attempt cap is no longer some arbitrary-feeling number once bucket sizes climb past what the table above shows. Uncheck "square-size level-2 tables," rebuild with a larger key list, and the build log's own per-bucket attempt counts show this directly, not just the table above.

A key that wasn't in the original set can't just be added afterward. Both levels are sized and hashed for exactly the keys known at build time — a bucket's private table has precisely m² slots for that bucket's m keys, no spare capacity reserved for a future arrival, and a new key might not even hash into a bucket that has room to grow into. There's no cheap put the way the site's other three Hash-Based entries have one; adding a key means rebuilding (at minimum, the one affected bucket's private table; in the worst case, redoing the level-1 split as well if the new key changes which buckets are even balanced). That's the trade this whole page makes: give up cheap membership changes, get a lookup guarantee none of chaining, cuckoo hashing, or Robin Hood hashing can offer.

Where perfect hashing shows up

• GNU gperf. Generates a perfect hash function in C source code for a fixed set of strings supplied at build time — the classic use is a compiler or interpreter recognizing its own reserved keywords (if, while, return, and so on) without a chain of string comparisons or a general-purpose hash table that has to tolerate keys it will never actually see.
• Minimal perfect hash function libraries (such as the CHD algorithm used in tools like cmph) apply the same "the key set is fixed, spend build time to buy lookup time" idea to much larger static sets — big language-model vocabularies, genomic k-mer indices, compiled symbol tables — usually packing keys into close to n slots rather than this page's simpler O(n)-with-a-larger-constant scheme (this page is perfect — guaranteed zero collisions — but not minimal; a minimal scheme is a genuinely more involved construction, not covered here).
• Any read-mostly lookup table that's rebuilt rarely and read constantly — a compiled routing or access-control table, a DNS zone file loaded once and queried millions of times before the next reload — is a natural fit for trading a one-time, more expensive build for a lookup guarantee that never degrades no matter how the table was built or how full it is.

Complexity

Time: get is O(1) worst case, always exactly two hash computations and one comparison — the one guarantee none of the site's other Hash-Based entries make unconditionally; cuckoo hashing comes closest with a worst-case bound of two probes, but still has to check both before concluding "not found," and pays for the guarantee with expected-only O(1) insert and real eviction-cycle risk (see that page's own Pitfalls). build is O(n) expected — both levels' retry loops succeed within a small constant number of draws on average, as the measured 1.01/1.36-attempt figures above show. Space: O(n) expected, measured at 3.27× the key count on average and no worse than 4.67× across 3,000 random trials — more than the roughly n-slot tables the site's other three entries use, the direct cost of the level-2 tables' m² sizing.

This is a fourth entry in Hash-Based, but it doesn't join the three-way collision-resolution comparison in Choosing a Hash Table Collision Strategy — that guide's whole framing assumes a live put/get/delete contract, and perfect hashing's entire point is that the key set never changes after the one build. See the guide for how it now fits alongside Consistent Hashing, Bloom Filter, and LRU Cache as a fourth entry set aside from that comparison, each for its own distinct reason.