What Actually Happens Inside a Hash Map
A deep dive into hash maps — from the core hash-to-index trick, through collisions and resizing, to how Python, Java, and Go implement them differently.
You have a million contacts in your phone. You type a name, and it appears instantly. Not after scanning a thousand entries. Not after sorting anything. Instantly. The secret is a data structure you use every single day but probably never think about: the hash map.
From Key to Index in One Step
A hash map takes your key — say, the name "Alice" — and feeds it into a hash function. The function scrambles the input into a large number, then reduces it with hash(key) % array_size to get an index. You don't *search* for where Alice lives. You *calculate* it. One operation. Direct access. That's O(1) lookup.
Collisions Are Inevitable
Hash functions map infinite possible keys into a finite number of slots. Eventually, two keys land in the same bucket. The two main strategies for dealing with this:
- Chaining — each bucket holds a linked list. Collisions just extend the chain. Simple, but pointer-chasing means cache misses.
- Open addressing — no lists. You probe for the next empty slot in the array itself. One elegant variant, Robin Hood hashing, swaps entries based on probe distance — stealing from keys close to home and giving to keys that traveled far. The result: roughly equal probe distances for every key.
The Resize Trick
As entries pile up, the load factor (entries divided by buckets) creeps toward a threshold. Different languages draw the line differently:
| Language | Load Factor Threshold |
|---|---|
| Java | 0.75 |
| Python | ~0.67 |
| Go | ~0.80 |
Cross the line and the table doubles. Every entry gets rehashed into a new, larger array. A million entries means a million rehash operations in that one moment.
But it's already paid for. Think of it like a savings account: each insert secretly sets aside extra work credit. When the resize finally hits, every element has enough saved up to cover its own rehash. This is amortized O(1) — any single insert is cheap, and the rare expensive resizes are pre-budgeted.
Battle Scars From Production
Real hash maps carry defenses you won't find in textbooks.
Java's treeification: when a bucket's chain grows to eight nodes, the HashMap silently converts that linked list into a red-black tree. Lookups in that bucket go from O(n) to O(log n).
HashDoS (2011): researchers showed that a single 100KB HTTP request could freeze a web server for 90 seconds by crafting parameter names that all hash to the same bucket. O(1) becomes O(n) for every lookup. The server is pinned.
The fix? Randomized hashing. Python switched to SipHash with a random secret generated at startup. Same string, different hash every time you launch. Go randomizes seeds too. Java added treeification as a safety net.
These protections run silently every time you use a dict or a Map. Most developers never know they're there.
But now you do.
Watch the full animated breakdown: Hash Maps — Every Programmer Should Know This