Introduction to Perfect Hashing

Introduction

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.

Try It

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='Type a key and press Enter or comma (max 12)' maxlength="20" autocomplete="off" />
    <button id="build" type="button">Build perfect table</button>
    <button id="reset" type="button" class="ghost">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="Lookup a key…" maxlength="20" autocomplete="off" />
    <button id="lookupbtn" type="button">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Two-level FKS perfect hashing (simplified / educational).
// Level-1: universal hash h1(k) = ((a1*hash(k) + b1) % P) % M  →  bucket index
// Level-2: for each bucket i with ki keys, a table of size ki² with its own (a2,b2).
// Construction: retry a1/b1 (and per-bucket a2i/b2i) until zero collisions.
// Lookup: two hash evaluations, O(1) worst case.

const P = 1000000007; // large prime
function strHash(s) {
  let h = 0;
  for (let i = 0; i < s.length; i++) h = (Math.imul(31, h) + s.charCodeAt(i)) >>> 0;
  return h;
}
function randAB() { return [Math.floor(Math.random() * (P - 1)) + 1, Math.floor(Math.random() * P)]; }
function h(key, a, b, m) { return ((Math.imul(a, strHash(key) % P) + b) % P + P) % P % m; }

let keys = [];
let table = null; // { M, a1, b1, buckets: [{keys, m2, a2, b2, slots}] }

function buildTable(ks) {
  if (ks.length === 0) return null;
  const M = Math.max(ks.length, 4);
  for (let attempt = 0; attempt < 2000; attempt++) {
    const [a1, b1] = randAB();
    const buckets = Array.from({ length: M }, () => []);
    ks.forEach(k => buckets[h(k, a1, b1, M)].push(k));
    // Condition: sum of ki² ≤ 4n (ensures O(n) total L2 space with high prob)
    const l2total = buckets.reduce((s, b) => s + b.length * b.length, 0);
    if (l2total > 4 * ks.length) continue;
    // Build second-level tables
    let ok = true;
    const builtBuckets = [];
    for (const bk of buckets) {
      if (bk.length === 0) { builtBuckets.push({ keys: [], m2: 1, a2: 1, b2: 0, slots: [null] }); continue; }
      if (bk.length === 1) { builtBuckets.push({ keys: bk, m2: 1, a2: 1, b2: 0, slots: [bk[0]] }); continue; }
      const m2 = bk.length * bk.length;
      let found = false;
      for (let a2 = 0; a2 < 500; a2++) {
        const [a2v, b2v] = randAB();
        const slots = new Array(m2).fill(null);
        let collision = false;
        for (const k of bk) {
          const idx = h(k, a2v, b2v, m2);
          if (slots[idx] !== null) { collision = true; break; }
          slots[idx] = k;
        }
        if (!collision) { builtBuckets.push({ keys: bk, m2, a2: a2v, b2: b2v, slots }); found = true; break; }
      }
      if (!found) { ok = false; break; }
    }
    if (ok) return { M, a1, b1, buckets: builtBuckets };
  }
  return null;
}

function lookup(key) {
  if (!table) return null;
  const bi = h(key, table.a1, table.b1, table.M);
  const bkt = table.buckets[bi];
  if (!bkt || bkt.keys.length === 0) return { found: false, bi, si: -1 };
  const si = h(key, bkt.a2, bkt.b2, bkt.m2);
  return { found: bkt.slots[si] === key, bi, si };
}

// ── UI ──────────────────────────────────────────────────────────────────────
function renderTags() {
  const row = document.getElementById('tag-row');
  row.innerHTML = '';
  keys.forEach((k, i) => {
    const tag = document.createElement('span'); tag.className = 'tag';
    tag.innerHTML = `${k} <span class="rm" data-i="${i}">×</span>`;
    row.appendChild(tag);
  });
  row.querySelectorAll('.rm').forEach(el =>
    el.addEventListener('click', () => { keys.splice(+el.dataset.i, 1); table = null; renderTags(); renderViz(); setStatus(''); document.getElementById('lookup-row').style.display='none'; })
  );
}

function addKey(raw) {
  const k = raw.trim();
  if (!k) return;
  if (keys.length >= 12) { setStatus('Maximum 12 keys.', 'bad'); return; }
  if (keys.includes(k)) { setStatus(fmt('"%k%" already added.', { k: k }), 'bad'); return; }
  keys.push(k); table = null; renderTags(); setStatus('');
}

const inp = document.getElementById('keyinput');
inp.addEventListener('keydown', e => {
  if (e.key === 'Enter' || e.key === ',') {
    e.preventDefault();
    addKey(inp.value.replace(/,/g, '')); inp.value = '';
  }
});
inp.addEventListener('input', () => {
  if (inp.value.includes(',')) { addKey(inp.value.replace(/,/g, '')); inp.value = ''; }
});

document.getElementById('build').addEventListener('click', () => {
  if (keys.length === 0) { setStatus('Add at least one key first.', 'bad'); return; }
  table = buildTable(keys);
  if (!table) { setStatus('Could not build (try fewer keys or retry).', 'bad'); return; }
  renderViz();
  setStatus(fmt('Perfect table built: %length% key %v%, %M% L1 buckets, zero collisions.,  ✓', { length: keys.length, v: keys.length>1?'s':'', M: table.M }), 'ok');
  document.getElementById('lookup-row').style.display = 'flex';
});

document.getElementById('reset').addEventListener('click', () => {
  keys = []; table = null; renderTags(); renderViz(); setStatus('');
  document.getElementById('lookup-row').style.display = 'none';
  document.getElementById('lookupinput').value = '';
});

const li = document.getElementById('lookupinput');
document.getElementById('lookupbtn').addEventListener('click', doLookup);
li.addEventListener('keydown', e => { if (e.key === 'Enter') doLookup(); });

function doLookup() {
  const k = li.value.trim(); if (!k) return;
  const r = lookup(k);
  if (!r) { setStatus('Build the table first.', 'bad'); return; }
  if (r.found) {
    setStatus(fmt('"%k%" found: L1 bucket %bi%, L2 slot %si% ✓', { k: k, bi: r.bi, si: r.si }), 'ok');
    highlightCell(r.bi, r.si);
  } else {
    setStatus(fmt('"%k%" not in table (L1 bucket %bi%, L2 slot %si% is %v%).', { k: k, bi: r.bi, si: r.si, v: table.buckets[r.bi].slots[r.si]===null?'empty':'another key' }), 'bad');
  }
}

function setStatus(t, cls = '') {
  const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls;
}

let highlightTimeout = null;
function highlightCell(bi, si) {
  document.querySelectorAll('.highlight').forEach(el => el.classList.remove('highlight'));
  const cell = document.querySelector(`[data-bi="${bi}"][data-si="${si}"]`);
  if (cell) {
    cell.classList.add('highlight');
    clearTimeout(highlightTimeout);
    highlightTimeout = setTimeout(() => cell.classList.remove('highlight'), 2000);
  }
}

function renderViz() {
  const viz = document.getElementById('viz');
  viz.innerHTML = '';
  if (!table) return;
  // Level 1 row
  const l1label = document.createElement('div'); l1label.className = 'level-label'; l1label.textContent = 'Level 1 — buckets (first hash)'; viz.appendChild(l1label);
  const l1row = document.createElement('div'); l1row.className = 'l1-row';
  table.buckets.forEach((bkt, bi) => {
    const box = document.createElement('div');
    box.className = 'bucket-box' + (bkt.keys.length > 0 ? ' has-keys' : '');
    box.innerHTML = `<div class="b-idx">${bi}</div><div class="b-keys">${bkt.keys.map(k=>`<span class="b-key">${k}</span>`).join('')}</div>`;
    l1row.appendChild(box);
  });
  viz.appendChild(l1row);
  // Level 2
  const l2section = document.createElement('div'); l2section.className = 'l2-section';
  const l2label = document.createElement('div'); l2label.className = 'level-label'; l2label.textContent = 'Level 2 — collision-free slots (second hash per bucket)';
  l2section.appendChild(l2label);
  const l2grid = document.createElement('div'); l2grid.className = 'l2-grid';
  table.buckets.forEach((bkt, bi) => {
    bkt.slots.forEach((val, si) => {
      const cell = document.createElement('div');
      cell.className = 'l2-cell ' + (val ? 'occupied' : 'empty');
      cell.dataset.bi = bi; cell.dataset.si = si;
      cell.textContent = val || '–';
      cell.title = fmt('Bucket %bi%, slot %si%', { bi: bi, si: si });
      l2grid.appendChild(cell);
    });
  });
  l2section.appendChild(l2grid);
  viz.appendChild(l2section);
}

// Seed with demo keys
['apple','grape','mango','fig','plum','kiwi','lime'].forEach(k => keys.push(k));
renderTags();

<div class="ph-wrap">
  <div class="input-row">
    <input id="keyinput" type="text" placeholder='Type a key and press Enter or comma (max 12)' maxlength="20" autocomplete="off" />
    <button id="build" type="button">Build perfect table</button>
    <button id="reset" type="button" class="ghost">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="Lookup a key…" maxlength="20" autocomplete="off" />
    <button id="lookupbtn" type="button">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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Two-level FKS perfect hashing (simplified / educational).
// Level-1: universal hash h1(k) = ((a1*hash(k) + b1) % P) % M  →  bucket index
// Level-2: for each bucket i with ki keys, a table of size ki² with its own (a2,b2).
// Construction: retry a1/b1 (and per-bucket a2i/b2i) until zero collisions.
// Lookup: two hash evaluations, O(1) worst case.

const P = 1000000007; // large prime
function strHash(s) {
  let h = 0;
  for (let i = 0; i < s.length; i++) h = (Math.imul(31, h) + s.charCodeAt(i)) >>> 0;
  return h;
}
function randAB() { return [Math.floor(Math.random() * (P - 1)) + 1, Math.floor(Math.random() * P)]; }
function h(key, a, b, m) { return ((Math.imul(a, strHash(key) % P) + b) % P + P) % P % m; }

let keys = [];
let table = null; // { M, a1, b1, buckets: [{keys, m2, a2, b2, slots}] }

function buildTable(ks) {
  if (ks.length === 0) return null;
  const M = Math.max(ks.length, 4);
  for (let attempt = 0; attempt < 2000; attempt++) {
    const [a1, b1] = randAB();
    const buckets = Array.from({ length: M }, () => []);
    ks.forEach(k => buckets[h(k, a1, b1, M)].push(k));
    // Condition: sum of ki² ≤ 4n (ensures O(n) total L2 space with high prob)
    const l2total = buckets.reduce((s, b) => s + b.length * b.length, 0);
    if (l2total > 4 * ks.length) continue;
    // Build second-level tables
    let ok = true;
    const builtBuckets = [];
    for (const bk of buckets) {
      if (bk.length === 0) { builtBuckets.push({ keys: [], m2: 1, a2: 1, b2: 0, slots: [null] }); continue; }
      if (bk.length === 1) { builtBuckets.push({ keys: bk, m2: 1, a2: 1, b2: 0, slots: [bk[0]] }); continue; }
      const m2 = bk.length * bk.length;
      let found = false;
      for (let a2 = 0; a2 < 500; a2++) {
        const [a2v, b2v] = randAB();
        const slots = new Array(m2).fill(null);
        let collision = false;
        for (const k of bk) {
          const idx = h(k, a2v, b2v, m2);
          if (slots[idx] !== null) { collision = true; break; }
          slots[idx] = k;
        }
        if (!collision) { builtBuckets.push({ keys: bk, m2, a2: a2v, b2: b2v, slots }); found = true; break; }
      }
      if (!found) { ok = false; break; }
    }
    if (ok) return { M, a1, b1, buckets: builtBuckets };
  }
  return null;
}

function lookup(key) {
  if (!table) return null;
  const bi = h(key, table.a1, table.b1, table.M);
  const bkt = table.buckets[bi];
  if (!bkt || bkt.keys.length === 0) return { found: false, bi, si: -1 };
  const si = h(key, bkt.a2, bkt.b2, bkt.m2);
  return { found: bkt.slots[si] === key, bi, si };
}

// ── UI ──────────────────────────────────────────────────────────────────────
function renderTags() {
  const row = document.getElementById('tag-row');
  row.innerHTML = '';
  keys.forEach((k, i) => {
    const tag = document.createElement('span'); tag.className = 'tag';
    tag.innerHTML = `${k} <span class="rm" data-i="${i}">×</span>`;
    row.appendChild(tag);
  });
  row.querySelectorAll('.rm').forEach(el =>
    el.addEventListener('click', () => { keys.splice(+el.dataset.i, 1); table = null; renderTags(); renderViz(); setStatus(''); document.getElementById('lookup-row').style.display='none'; })
  );
}

function addKey(raw) {
  const k = raw.trim();
  if (!k) return;
  if (keys.length >= 12) { setStatus('Maximum 12 keys.', 'bad'); return; }
  if (keys.includes(k)) { setStatus(fmt('"%k%" already added.', { k: k }), 'bad'); return; }
  keys.push(k); table = null; renderTags(); setStatus('');
}

const inp = document.getElementById('keyinput');
inp.addEventListener('keydown', e => {
  if (e.key === 'Enter' || e.key === ',') {
    e.preventDefault();
    addKey(inp.value.replace(/,/g, '')); inp.value = '';
  }
});
inp.addEventListener('input', () => {
  if (inp.value.includes(',')) { addKey(inp.value.replace(/,/g, '')); inp.value = ''; }
});

document.getElementById('build').addEventListener('click', () => {
  if (keys.length === 0) { setStatus('Add at least one key first.', 'bad'); return; }
  table = buildTable(keys);
  if (!table) { setStatus('Could not build (try fewer keys or retry).', 'bad'); return; }
  renderViz();
  setStatus(fmt('Perfect table built: %length% key %v%, %M% L1 buckets, zero collisions.,  ✓', { length: keys.length, v: keys.length>1?'s':'', M: table.M }), 'ok');
  document.getElementById('lookup-row').style.display = 'flex';
});

document.getElementById('reset').addEventListener('click', () => {
  keys = []; table = null; renderTags(); renderViz(); setStatus('');
  document.getElementById('lookup-row').style.display = 'none';
  document.getElementById('lookupinput').value = '';
});

const li = document.getElementById('lookupinput');
document.getElementById('lookupbtn').addEventListener('click', doLookup);
li.addEventListener('keydown', e => { if (e.key === 'Enter') doLookup(); });

function doLookup() {
  const k = li.value.trim(); if (!k) return;
  const r = lookup(k);
  if (!r) { setStatus('Build the table first.', 'bad'); return; }
  if (r.found) {
    setStatus(fmt('"%k%" found: L1 bucket %bi%, L2 slot %si% ✓', { k: k, bi: r.bi, si: r.si }), 'ok');
    highlightCell(r.bi, r.si);
  } else {
    setStatus(fmt('"%k%" not in table (L1 bucket %bi%, L2 slot %si% is %v%).', { k: k, bi: r.bi, si: r.si, v: table.buckets[r.bi].slots[r.si]===null?'empty':'another key' }), 'bad');
  }
}

function setStatus(t, cls = '') {
  const s = document.getElementById('status'); s.textContent = t; s.className = 'status ' + cls;
}

let highlightTimeout = null;
function highlightCell(bi, si) {
  document.querySelectorAll('.highlight').forEach(el => el.classList.remove('highlight'));
  const cell = document.querySelector(`[data-bi="${bi}"][data-si="${si}"]`);
  if (cell) {
    cell.classList.add('highlight');
    clearTimeout(highlightTimeout);
    highlightTimeout = setTimeout(() => cell.classList.remove('highlight'), 2000);
  }
}

function renderViz() {
  const viz = document.getElementById('viz');
  viz.innerHTML = '';
  if (!table) return;
  // Level 1 row
  const l1label = document.createElement('div'); l1label.className = 'level-label'; l1label.textContent = 'Level 1 — buckets (first hash)'; viz.appendChild(l1label);
  const l1row = document.createElement('div'); l1row.className = 'l1-row';
  table.buckets.forEach((bkt, bi) => {
    const box = document.createElement('div');
    box.className = 'bucket-box' + (bkt.keys.length > 0 ? ' has-keys' : '');
    box.innerHTML = `<div class="b-idx">${bi}</div><div class="b-keys">${bkt.keys.map(k=>`<span class="b-key">${k}</span>`).join('')}</div>`;
    l1row.appendChild(box);
  });
  viz.appendChild(l1row);
  // Level 2
  const l2section = document.createElement('div'); l2section.className = 'l2-section';
  const l2label = document.createElement('div'); l2label.className = 'level-label'; l2label.textContent = 'Level 2 — collision-free slots (second hash per bucket)';
  l2section.appendChild(l2label);
  const l2grid = document.createElement('div'); l2grid.className = 'l2-grid';
  table.buckets.forEach((bkt, bi) => {
    bkt.slots.forEach((val, si) => {
      const cell = document.createElement('div');
      cell.className = 'l2-cell ' + (val ? 'occupied' : 'empty');
      cell.dataset.bi = bi; cell.dataset.si = si;
      cell.textContent = val || '–';
      cell.title = fmt('Bucket %bi%, slot %si%', { bi: bi, si: si });
      l2grid.appendChild(cell);
    });
  });
  l2section.appendChild(l2grid);
  viz.appendChild(l2section);
}

// Seed with demo keys
['apple','grape','mango','fig','plum','kiwi','lime'].forEach(k => keys.push(k));
renderTags();

Result

Console

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.

The Real Complexity

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.

Where It Matters

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.

Conclusion

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.

Comments

Loading comments...

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

Cookies & privacy

Perfect Hashing

When every key gets its own slot, forever