If you've written more than a few lines of Python, Java, or C++, you've used a hash table a hundred times without thinking about it. dict in Python, HashMap in Java, unordered_map in C++, same idea, different name. You throw a key at it, you get a value back, and somehow it's instant. O(1), everyone says, like it's magic.
It's not magic. It's a pretty simple trick, layered a few times. Let's actually open it up.
The core idea in one line
A hash table's entire job is this: turn a key into a number, and use that number as an array index.
That's it. That's the whole insight. Everything else, the hash function, the collision handling, the linked lists, exists just to make that one idea actually work in practice.
Step 1: Hashing the key
Say you want to store "apple" → 10. The key is "apple", a string. But arrays don't understand strings, they understand indices (0, 1, 2, 3...). So the first job is to convert "apple" into some integer.
That's what a hash function does.
"apple" → hash function → 328947123
That number, 328947123, is called the hash code. It doesn't mean anything on its own, it's just a big number that's (ideally) unique-ish to that key. A good hash function has a few properties worth remembering:
- Same input always gives same output (deterministic)
- Fast to compute
- Spreads different keys across different numbers pretty evenly (uniform distribution)
Step 2: You can't use that number directly
Here's the obvious problem. If your hash comes out to 328947123, are you going to allocate an array with 328 million slots just to store one apple? Obviously not. That's an absurd amount of wasted memory for a table that might hold ten items.
So we compress that huge number down into something that fits our actual array size. If your table has, say, 16 slots, we do:
index = hash % capacity
328947123 % 16 = 3
Now "apple" lives at table[3]. Simple modulo, done. (In practice, a lot of real implementations use bitwise tricks instead of % when the capacity is a power of two, since it's faster, but conceptually it's the same compression step.)
So the full pipeline so far:
key → hash function → big integer → compress → array index
What's actually sitting inside the array?
This is the part that trips people up, because the natural first guess is wrong. You'd assume the array looks like this:
index 3 → "apple"
Nope. If it were that simple, hash tables would break the moment two keys landed on the same index, and they do land on the same index, all the time. So the array doesn't store the key-value pair directly. It stores a pointer to a linked list.
Every array slot points to the head of a chain of nodes. Most of the time that chain is empty (a null pointer). Sometimes it has one node. Sometimes it has a few.
This chain hanging off an array slot has a name: it's called a bucket. So table[3] and "bucket 3" mean the exact same thing. One is just describing the array position, the other is describing everything attached to it.
Why buckets exist at all: collisions
Here's the thing about hash functions: no matter how good they are, two different keys can absolutely produce the same compressed index. It's just math, you're squeezing a near-infinite space of possible keys into a small, fixed number of slots. Something's gotta overlap eventually.
hash("apple") % 16 = 5
hash("banana") % 16 = 5
Both want to live at table[5]. This is a collision, and it's not a bug or an edge case, it's an expected, routine part of how hash tables function. The whole design has to account for it from day one.
Chaining, the fix
The simplest, most common fix is called separate chaining, and it's exactly what it sounds like: when a collision happens, you don't overwrite the existing entry, you just attach a new node to the same bucket's linked list.
table[5] → (apple, 10) → (banana, 20) → (cherry, 30)
All three of these keys hashed to the same index, and all three now live in the same chain, one after another. This is why the array-to-bucket relationship matters. Without the linked list layer, collisions would just silently destroy data.
Why every node carries the key, not just the value
Say bucket 5 has three entries. If you only stored the values, 10, 20, 30, how would a lookup for "banana" know which of those three numbers belongs to it? It wouldn't. There'd be no way to tell them apart once they're jammed into the same bucket.
So every node in the chain actually stores three things:
- the key
- the value
- a pointer to the next node When you look something up, the table doesn't just jump to the bucket and grab whatever's there. It walks the chain and compares each stored key against the one you're searching for, until it finds a match.
Putting the whole flow together
Insertion and lookup both follow the exact same path, just with a different last step (write vs. compare-and-return):
key
→ hash function
→ large integer
→ compress to index
→ go to table[index]
→ walk the linked list at that bucket
→ compare keys as you go
→ (insert here) or (return the matching value)
Once you see this pipeline, the whole "O(1) lookup" thing stops feeling like magic and starts feeling like, well, obviously fast, as long as the chains stay short.
About that O(1), the fine print
The average-case speed only holds up if the hash function is doing its job and spreading keys out evenly. If somehow every key you insert ends up hashing to the same bucket, your beautiful O(1) hash table quietly degrades into a single, ugly linked list. And now you're doing O(n) work for every lookup.
All three operations, Insert, Lookup, and Delete, are O(1) on average. But if your hash function is bad and everything piles into one bucket, all three drop to O(n). That's the worst case, and it's basically just traversing a linked list at that point.
This is precisely why hash function quality is such a big deal in real implementations, and why languages resize and rehash the table once it gets too full. Fewer collisions per bucket, shorter chains, faster everything.
The one picture worth keeping in your head
Forget the implementation noise. If you remember nothing else, remember this:
A hash table is just an array of linked lists, where a hash function decides which list a key belongs to.
Everything, insertion, lookup, deletion, collisions, buckets, falls out of that one sentence. Once it clicks, it never really un-clicks.