Hash Tables

The 10-second versionCopy Anchor Link

An array gives you O(1) access — if your key is a small integer like 0, 1, 2, …. A hash table makes that work for any key: names, URLs, objects. You run the key through a hash function that scrambles it into one of a fixed number of slots (called buckets), then store the value there. Lookup runs the same function and jumps straight to the bucket. Average cost: O(1). The catch is that different keys can scramble to the same bucket — a collision — and how you handle those is the whole art (that's the next page).

Why this existedCopy Anchor Link

By the early 1950s, IBM was building machines to search large files of records — patents, chemicals, literature. The standard tool was the inverted index: a big table mapping terms to the places they appear. But the table was enormous, and searching it meant either scanning or an expensive ordered walk.

• 1953 — Hans Peter Luhn, working at IBM, devises hash coding: instead of storing a key at its "natural" position, compute a short number from the key and store it there. He uses it for fast document and term retrieval.
• The word "hash" — Luhn's term comes straight from the kitchen sense of hashing: you chop and mix the characters of a key into a jumble, the same way you hash meat and potatoes. The name stuck, and "hash" has meant "scramble" in computing ever since.
• 1957 onward — the technique spreads through information-retrieval papers into compilers (symbol tables), operating systems (file caches), and eventually every language's dictionary type.

Why it mattered: it broke the O(log n) speed limit of ordered structures. With hashing, "find this key" no longer depends on how many keys you stored — that single change reshaped databases, compilers, and every map you use today.

Inside the inventor's headCopy Anchor Link

Start from the array. If your keys were the integers 0…n-1, you'd just use the key as the index — instant lookup. Luhn's problem was that his keys were words. The naive fix is to address by the key's numeric value:

The pivot is accepting the impossible. You cannot give every possible key its own slot — the key space is effectively infinite. So you stop trying to be perfect and instead fold the key into a small range, and you plan for the day two keys fold to the same place.

// Naive: use the key's own value as the index into a giant array.// Only sane if keys are tiny, dense integers — hopeless for words.function lookup(table, key) {  return table[key];           // how big must table be? unbounded.}

// Compute a small bucket index from an integer key.const CAP = 1024;const bucket = (key) => Math.abs(key) % CAP;          // always 0..CAP-1

Now no matter how big the key space is, everything lands in one of CAP buckets — and we only ever touch those.

The final approachCopy Anchor Link

The memory pictureCopy Anchor Link

A table with a small number of buckets, each holding a chain of entries that hashed there:

cat and car collided into bucket 3 and sit in the same chain; dog landed alone in bucket 4. The array of buckets is the speed; the chains are the collision insurance.

The algorithmCopy Anchor Link

The invariantsCopy Anchor Link

• A key always hashes to the same bucket. The hash function is deterministic — that's the one non-negotiable rule. Same key in, same bucket out, every time.
• Equal keys live in the same bucket. So a lookup only ever has to inspect one chain, never the whole table.
• Collisions are expected, never an error. The function maps a huge key space into a small range, so sharing buckets is guaranteed (by the pigeonhole principle). We manage it; we don't wish it away.

It in codeCopy Anchor Link

class Table {  #buckets = Array.from({ length: 16 }, () => []);   // a chain per bucket  #hash(key) {    let h = 5381;    for (let i = 0; i < key.length; i++)      h = (h * 33 + key.charCodeAt(i)) >>> 0;        // chop & mix    return h % this.#buckets.length;  }  put(key, val) {    const chain = this.#buckets[this.#hash(key)];    const hit = chain.find((e) => e.key === key);    if (hit) hit.val = val;                           // update    else chain.push({ key, val });                    // add to the chain  }  get(key) {    const chain = this.#buckets[this.#hash(key)];    const hit = chain.find((e) => e.key === key);    return hit ? hit.val : undefined;                 // undefined if absent  }}

A worked traceCopy Anchor Link

Let's use a toy hash — first letter's position in the alphabet, mod 8 — so the collisions are easy to see. Insert four keys:

Buckets 3 is now car → cat. Ask for car: hash it, land on bucket 3, walk the chain, compare car == car → found. Ask for cow: hash to 3, walk the chain, compare against car and cat, no match → absent. Notice we never looked at buckets 0, 1, or 4 — that's the O(1) average. The real hash function (djb2-style, above) spreads keys far more evenly than "first letter."

ComplexityCopy Anchor Link

The worst case is O(n) because, in the pathological case, every key can land in one bucket and the "table" degenerates into a single linked list. Good hash functions and a sane load factor make that vanishingly unlikely — which is exactly what the next page is about.

Where you meet it todayCopy Anchor Link

• Dictionaries everywhere. Python's dict, JavaScript's Map/objects, Java's HashMap, Rust's HashMap, C++'s unordered_map — all hash tables under the hood.
• Caches. A memoization table keyed by arguments is a hash map: "have I solved this subproblem already?"
• Deduplication and sets. HashSet turns "is this a duplicate?" from an O(n) scan into an O(1) membership test.
• Databases and compilers. Hash joins, hash indexes, and the symbol table a compiler keeps for your variables are all hashing.

// Return the first id that repeats, or null if all are unique.function firstRepeat(ids) {  const seen = new Set();  for (const id of ids) {    if (seen.has(id)) return id;        // O(1) average lookup    seen.add(id);  }  return null;}

RecapCopy Anchor Link

• A hash table maps any key → a bucket index with a hash function, giving O(1) average lookup instead of O(log n).
• The word "hash" comes from chopping and mixing a key, exactly like the kitchen sense. Hans Peter Luhn at IBM pioneered it in 1953.
• Collisions are inevitable — a huge key space squeezed into a small number of buckets — so each bucket keeps a small chain of entries.
• Average is O(1), worst case O(n) when the hashing goes bad. Keeping it O(1) in practice is the subject of the next page.

Next up: Hashing Internals: Collisions & Load Factor — chaining vs probing, load factor, rehashing, and why "average" and "worst" diverge.