level 1 · Foundations
Hash Map
Turn a key straight into a location — the structure behind almost everything.
what is it
Start here
Every structure so far makes you search for things. A hash map doesn't. You hand it a key, it does a quick calculation, and it jumps straight to where that key lives. No walking, no comparing your way down — just arithmetic and a jump.
The calculation is called a hash. Here it's as simple as key % 5: the key 17 becomes bucket 2, because 17 divided by 5 leaves a remainder of 2. That remainder is the address. To find 17 again later, you run the exact same sum and land in the exact same bucket.
Sometimes two different keys land in the same bucket — a collision. That's not a bug, it's expected. The fix here is chaining: the bucket just holds a little list, and colliding keys line up in it. As long as the chains stay short, lookups stay almost instant.
This is why hash maps are everywhere: dictionaries, sets, database indexes, caches, counting duplicates, de-duplicating a list. Any time you've thought 'have I seen this before?', a hash map answers it in one step instead of scanning everything.
real-life analogy
Picture it
You hand over your coat and get ticket 42. The attendant doesn't search the whole room — ticket 42 tells them exactly which peg. To get your coat back, the same ticket points to the same peg. If two coats share a peg, they just hang side by side, and the attendant glances at those two rather than the whole room.
interactive visualization
Watch it run
Keys get hashed into 5 buckets. Watch for collisions that share a bucket.
key % 5 → bucket
- 0
- empty
- 1
- empty
- 2
- empty
- 3
- empty
- 4
- empty
A hash map turns a key straight into a location. Instead of searching for where something is, it calculates where it must be — so lookups are almost instant, no matter how much you store.
step 01/17
- checking
- collision · chained
- placed · found
space · play ← → · step
| 1 | const BUCKETS = 5; |
| 2 | |
| 3 | function insert(table, key) { |
| 4 | const i = key % BUCKETS; |
| 5 | table[i].push(key); |
| 6 | } |
| 7 | |
| 8 | function has(table, key) { |
| 9 | const i = key % BUCKETS; |
| 10 | for (const k of table[i]) { |
| 11 | if (k === key) return true; |
| 12 | } |
| 13 | return false; |
| 14 | } |
variables right now
Nothing in play yet — press play.
the dry run · every step, in words
17 stepscomplexity
What it costs
- best case
- O(1)
- average
- O(1)
- worst case
- O(n)
- extra memory
- O(n)
Insert and lookup are O(1) on average — one hash, one jump, a glance at a short chain. The worst case is O(n): if every key collides into one bucket, that bucket becomes a plain list you have to scan. A good hash function keeps that from happening.
- O(1) · this one
- O(log n)
- O(n)
- O(n log n)
- O(n²)
common mistakes
Common traps
Assuming lookups are always O(1).
Only on average. Pile every key into one bucket — a bad hash, or an attacker feeding you worst-case keys — and it degrades to scanning a list, O(n).
Expecting keys to come back in the order you inserted them.
A hash map scatters keys by their hash, not by insertion order. If you need order, that's a different tool (or a linked hash map).
Forgetting to handle collisions.
Two keys will eventually share a bucket. Without chaining (or another scheme), the second one overwrites the first and you silently lose data.
quiz
Check yourself
Three questions. Get them all right to finish the lesson.
+85 XP01How does a hash map find a key so fast?
02Two different keys hash to the same bucket. What is that called, and is it a problem?
03When does a hash map's lookup degrade to O(n)?
practice
Solve it on LeetCode
You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.