Introduction

Imagine a library where, instead of walking the shelves, a formula tells you the exact shelf a book sits on. You compute, you walk straight there, you grab it. That is a hash table: it runs the key through a hash function that spits out a number, and that number is the bucket where the value lives.

This is the magic behind the dictionaries, maps and sets you use every day. Insert, look up, delete — all in roughly constant time, no matter how big the table grows. No scanning, no sorting, just one arithmetic jump.

But the magic has a crack. Two different keys can hash to the same bucket — a collision — and when they pile up, that one-step lookup quietly starts to crawl. Understanding when and why is the whole story of hashing.

Try It: Fill the Table

Below is a tiny hash table with a handful of buckets. Each key you add is run through a simple hash function and dropped into a bucket. When two keys land in the same bucket they chain together — that is a collision.

<p class="hint">Type a key and <b>Insert</b> it. The hash function picks a bucket; keys landing in the same bucket <b>chain</b> together — that is a collision. Watch the <b>load factor</b> climb, then <b>Resize</b> to double the buckets and re-hash.</p>
<div class="row">
  <input id="key" type="text" placeholder="key e.g. cat" maxlength="12" />
  <button id="ins" type="button">Insert</button>
  <button id="rand" type="button">Insert 5 random</button>
  <button id="resize" type="button" class="ghost">Resize ×2</button>
  <button id="reset" type="button" class="ghost">Clear</button>
</div>
<div class="stats" id="stats"></div>
<div id="table" class="table"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .7rem; line-height: 1.45; }
.row { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .6rem; }
input { font: 500 14px system-ui, sans-serif; padding: .4rem .6rem; border: 1px solid #adb1b8;
        border-radius: 8px; width: 130px; }
button { font: 600 13px system-ui, sans-serif; padding: .42rem .8rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.stats { font-size: .92rem; font-weight: 600; margin: .3rem 0 .7rem; display: flex; gap: 1.2rem; flex-wrap: wrap; }
.stats .warn { color: #c92f3c; }
.stats .good { color: #0a7d33; }
.table { display: flex; flex-direction: column; gap: 4px; }
.bucket { display: flex; align-items: center; gap: 6px; }
.idx { width: 34px; height: 34px; flex: none; display: flex; align-items: center; justify-content: center;
       font: 700 14px ui-monospace, monospace; background: #e8eef3; color: #1d3557;
       border: 1px solid #cdd9e3; border-radius: 8px; }
.chain { display: flex; gap: 4px; flex-wrap: wrap; min-height: 34px; align-items: center; }
.chip { padding: .28rem .55rem; font: 600 13px system-ui, sans-serif; border-radius: 7px;
        background: #c9ccd1; border: 1px solid #adb1b8; }
.bucket.collide .chip { background: #e63946; border-color: #c92f3c; color: #fff; }
.bucket.collide .idx { background: #f7d6d9; border-color: #e0a8ad; }
.arrow { color: #888; font-size: .8rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// A hash table with separate chaining. The hash function maps a string key to a bucket index; collisions (two keys, same bucket) are stored in a per-bucket list. Average lookup is O(1) while the load factor a = items / buckets stays small; let it grow and chains lengthen toward O(n). Resizing doubles buckets and re-hashes everything, restoring short chains. This is solved, classic data-structure theory.
let buckets = 4;
let table = Array.from({length: buckets}, () => []);
let count = 0;

// Simple deterministic string hash (polynomial rolling), then mod #buckets.
function hash(key, m) {
  let h = 0;
  for (let i = 0; i < key.length; i++) h = (h * 31 + key.charCodeAt(i)) >>> 0;
  return h % m;
}
function insert(key) {
  key = key.trim();
  if (!key) return;
  const b = hash(key, buckets);
  if (table[b].includes(key)) return; // no duplicates
  table[b].push(key);
  count++;
  render();
}
function resize() {
  const old = table;
  buckets *= 2;
  table = Array.from({length: buckets}, () => []);
  for (const chain of old) for (const key of chain) table[hash(key, buckets)].push(key);
  render();
}
function reset() {
  buckets = 4;
  table = Array.from({length: buckets}, () => []);
  count = 0;
  render();
}
function maxChain() { return table.reduce((m, c) => Math.max(m, c.length), 0); }

function render() {
  const alpha = count / buckets;
  const longest = maxChain();
  const cls = alpha > 1 ? 'warn' : 'good';
  document.getElementById('stats').innerHTML =
    fmt('<span>Items: %count%</span><span>Buckets: %buckets%</span><span class="%cls%">Load factor &alpha; = %alpha%</span><span>Longest chain: %longest%</span>', { count: count, buckets: buckets, cls: cls, alpha: alpha.toFixed(2), longest: longest });
  const t = document.getElementById('table');
  t.innerHTML = '';
  table.forEach((chain, i) => {
    const row = document.createElement('div');
    row.className = 'bucket' + (chain.length > 1 ? ' collide' : '');
    const idx = document.createElement('div');
    idx.className = 'idx'; idx.textContent = i;
    const c = document.createElement('div');
    c.className = 'chain';
    chain.forEach((k, j) => {
      if (j > 0) { const a = document.createElement('span'); a.className = 'arrow'; a.textContent = '→'; c.appendChild(a); }
      const chip = document.createElement('span');
      chip.className = 'chip'; chip.textContent = k; c.appendChild(chip);
    });
    row.appendChild(idx); row.appendChild(c);
    t.appendChild(row);
  });
}
const WORDS = ['cat','dog','sun','map','key','red','sky','owl','fox','ant','bee','ice','oak','pen','jam'];
document.getElementById('ins').addEventListener('click', () => {
  insert(document.getElementById('key').value); document.getElementById('key').value = '';
});
document.getElementById('key').addEventListener('keydown', e => { if (e.key === 'Enter') document.getElementById('ins').click(); });
document.getElementById('rand').addEventListener('click', () => {
  for (let i = 0; i < 5; i++) insert(WORDS[Math.floor(Math.random() * WORDS.length)] + Math.floor(Math.random() * 90));
});
document.getElementById('resize').addEventListener('click', resize);
document.getElementById('reset').addEventListener('click', reset);
render();
Result
Console

Watch the load factor (items ÷ buckets) climb as you insert. While it stays low, almost every bucket holds one item and lookup is effectively one step. Push it past 1 and chains grow, so a lookup must walk a list — drifting toward O(n)O(n). Hit Resize and the table doubles its buckets, re-hashes everything, and the chains melt away. That trade — extra space for fast access — is hashing in one move.

The Real Complexity

How fast is a hash table, really? The honest answer has two numbers.

  • Average case: O(1)O(1). If the hash spreads keys evenly and the load factor α (items ÷ buckets) is kept bounded, the expected chain length is about α, so insert, find and delete all run in expected constant time. This is solved, well-understood textbook theory — not an open problem.
  • Worst case: O(n)O(n). Nothing stops every key from hashing to the same bucket. Then the table collapses into one long chain and a lookup scans all n items, just like an unsorted list.
  • Collisions are unavoidable. By the birthday problem, collisions appear far sooner than intuition says: with only ~23 keys in a 365-bucket table the odds of some collision already exceed 50%. Hashing never promises no collisions — only that they stay rare and cheap.
  • The defense is randomness. Universal hashing (Carter & Wegman, 1979) picks the hash function at random from a family, so no fixed set of keys can be engineered to always collide — turning the worst case into a bad-luck event with provably low probability.

So O(1)O(1) is a statement about the average under a good hash and a controlled load factor. Keep α small and you live in the fast world; let it grow, or let an adversary pick your keys, and you slide toward the slow one. It is a vivid lesson in why P vs NP and complexity classes care about worst case versus average case.

Where It Matters

"Find this exact thing, fast" is one of the most common demands in computing, and hashing is the default answer:

  • Dictionaries and sets: every dict, map, HashMap or Set in your language is a hash table under the hood.
  • Databases and indexes: hash indexes give O(1)O(1) equality lookups; joins and grouping lean on hashing to bucket matching rows.
  • Caches and deduplication: content is keyed by hash so identical data is stored once and found instantly (Git, build caches, CDNs).
  • Compilers and interpreters: symbol tables map variable names to information through hashing on every single line you compile.
  • Bloom filters and probabilistic structures: hashing also underpins compact membership tests where a little error buys huge space savings — see bloom filters.

Learn how a hash table degrades and recovers and you understand the load-factor knob behind nearly every fast data store you will ever touch.

Conclusion

Hashing is one of computing's best bargains: spend a little extra memory and a clever formula, and you get lookup that barely cares how much data you hold. The catch is honest and simple — that speed is an average, propped up by keeping collisions rare. Let the load factor climb, and the one-step jump degrades into a walk down a chain.

The fix is equally simple: watch α, resize in time, and pick a hash that scatters keys well. Do that and the table keeps its promise. It is a small structure with a big lesson — the gap between the typical cost and the worst cost, the same gap that runs through all of P vs NP and the study of algorithms.

Share this article

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

Comments

Loading comments...

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