What is a hash table?

A data structure that lets you find, insert, and delete by key in roughly constant time — the workhorse behind dictionaries, sets, and most fast lookup in modern code.

The picture version

Five pictures for a reader who has never thought about how lookup works. The prose below fills in the seams the pictures skip.

Why it exists

Imagine a phone book with a million names, and you need to find “John”. If the book is unsorted, you read every entry — a million comparisons in the worst case. If it’s sorted, binary search drops that to ~20. Better, but the cost still grows with the size of the book.

The deeper question: can lookup be independent of the size of the collection? Can finding “John” in a billion-entry book be just as fast as in a ten-entry book?

The hash table says yes — with one catch we’ll get to. If we can compute, directly from the name itself, the slot where its number lives, we don’t have to search at all. We jump straight there. That’s the entire idea, and it’s why hash tables are everywhere: most languages’ dict and map types, the symbol table inside your compiler, the hash join inside your database.

Keep that phone book in mind — the rest of this post is the story of making “jump straight there” actually work.

Why it matters now

It’s one of the most-used non-trivial data structures in software. When you write users[id] in Python or cache.get(key) in Go, that’s the “jump straight to John” move, productized. (Some keyed collections are only specified to be fast rather than required to be hash tables — JavaScript’s Map is one — but this is the pattern you’re leaning on.) Language interpreters, CDN caches, deduplication, counting unique visitors — all leaning on the same trick. Understanding it pays off every time you reason about performance, collisions, or why your “fast lookup” suddenly isn’t fast.

The short answer

hash table = array + hash function

Picture to keep: a wall of numbered mailboxes where the name itself tells you which box to open. You never search for “John” — you compute John’s box number and open that box.

A hash table stores key-value pairs in an array, using a hash function to turn each key into an array index. To find a value, hash the key, jump to that index, done. Average-case O(1) for insert, lookup, and delete.

It’s like the phone book — except a phone book keeps names in alphabetical order, and a hash table deliberately destroys order: a good hash function scatters names across the boxes as if at random. That’s the price of O(1). (It’s also why sorted structures like balanced trees still exist — ask a hash table for “every name between Anna and Bob” and it can only shrug.)

How it works

The cleanest way to understand a hash table is to try to invent it yourself and watch each attempt fail.

Attempt 1: just compute the slot. Take a small array — say 4 slots. Run the name through a hash function — a deterministic recipe that turns any key into a big integer — and take the remainder:

slot = hash(name) % table_size

hash("John") % 4 = 1, so John’s number goes in slot 1. Lookup is the same computation again. No searching, no scanning. Done?

Not quite. There are far more possible names than slots, so sooner or later two names must land on the same slot. Before reading on, it’s worth actually committing to a guess: what would you do when hash("Mai") % 4 also comes out to 1? There are really only two families of answers.

Fix 1: a collision policy. The two families:

• Chaining — each slot holds a small list; a collision appends to the list, and lookup walks it.
• Open addressing — if the slot is taken, probe other slots by a fixed rule (the next one over, or a jump computed from the key) until you find a free one.

With chaining and our 4-slot table:

hash("John") % 4 = 1  →  slot 1: [(John, 555-0132)]
hash("Anna") % 4 = 3  →  slot 3: [(Anna, 555-0177)]
hash("Mai") % 4 = 1   →  slot 1: [(John, 555-0132), (Mai, 555-0191)]
                                  ↑ collision — append to the chain

Looking up Mai: hash to slot 1, walk the two-entry chain, return 555-0191. Still fast — the chain is short.

But this fix plants the next failure. Keep pouring names into 4 slots and the chains grow: with a million names, each slot holds a list ~250,000 entries long, and “walk the chain” is the linear search we were trying to escape. The O(1) promise silently decays as the table fills.

Fix 2: resize before it decays. Track the load factor — entries ÷ slots. When it passes a threshold (commonly around 70–75%, though the default varies by implementation), allocate a bigger array (usually double the size) and rehash every entry into it. That keeps expected chains short — assuming the hash function keeps spreading keys evenly. Let the table creep toward 95% full instead and collisions pile up; the “jump straight there” story quietly collapses back into list-walking.

Except — rehashing touches every one of the n entries. We just smuggled an O(n) operation into a structure whose entire sales pitch is O(1). Did we break the promise?

Fix 3: amortize. Because the table doubles, resizes get rarer at exactly the rate they get more expensive: a resize that costs n only happens after ~n cheap inserts have accumulated since the last one. Spread the bill across those inserts and the amortized cost per operation is still O(1). The honest fine print: any individual insert might be the unlucky one that pays for a whole resize.

That’s the whole design. Each piece exists as the fix for the previous piece’s failure — and if you remember the chain of failures, you can reconstruct the data structure from scratch.

The seam that remains. The O(1) is average case, and the average assumes the hash function spreads keys evenly. Worst case — every key lands in the same slot — is O(n), and adversaries can trigger it deliberately by crafting keys that collide (a real attack vector, called hash flooding). This is why many modern hash maps salt the hash with a randomized per-process seed (Python and Rust do; others defend differently), making colliding keys much harder to predict from outside.

You opened this post with hash table = array + hash function. Worth pausing before you go: what did the chain of fixes add? — a third ingredient the compression line hides: + a collision policy, plus a resize rule to keep that policy cheap. The famous O(1) isn’t a property of the array or the hash function — it’s a promise those two quiet ingredients keep.

Famous related terms

• Big-O notation — Big-O = how cost grows with input size, ignoring constants — the language we use to say “constant time” precisely.
• Hash function — hash function = deterministic map from arbitrary bytes → fixed-size fingerprint — the math that turns a key into an index. Good ones look random; bad ones cluster and ruin performance.
• Load factor — load factor = entries ÷ slots — too high → slow. Triggers resize.
• Open addressing vs. chaining — collision strategy = probe to next slot OR keep a list per slot — the two ways to resolve hash collisions.
• Balanced tree — balanced tree ≈ sorted dictionary with O(log n) operations — the alternative data structure when you need keys in sorted order (e.g. range queries). O(log n) instead of O(1), but ordered.
• Bloom filter — bloom filter = bit array + k hash functions — a hash-table cousin that answers “have I seen this?” in much less memory, at the cost of false positives.

Going deeper

• Introduction to Algorithms (CLRS), chapter on hash tables — for the precise math behind “expected O(1)” and the analysis this post hand-waved.
• Source code of any standard library HashMap (Java’s, Rust’s std::HashMap, Go’s map) — for how the trade-offs in this post get decided in production code, and surprisingly readable.
• Search “hash flooding DoS” — for how the worst case became a real attack, and how runtimes hardened against it.