# So Much for O(1)
> I'd known the theory for years but couldn't have built one from scratch. So I did, with interactive demos you can poke at.
March 25, 2026 · 34 min read · https://yasint.dev/hash-maps-under-the-hood/
Tags: data-structures, interactive
---
`HashMap`, `dict`, `Map`, `object`, whatever your language calls it, you probably use one every day. I definitely do.
I'd known the theory for years. Hashing, buckets, O(1), sure. If you'd asked me to walk through what actually happens when you call `map.get("email")`, I would've hand-waved about hashing and buckets and moved on. I knew it was "O(1)" because that's what you say in interviews and everyone nods. Could I have built one? No.
So I did. And honestly? It's not that complicated. It's just _really_ clever.
This article walks through the whole thing with interactive demos you can poke at. By the end you'll understand hash maps better than most people who use them daily.
---
## It all starts with arrays
OK so here's the thing. Arrays have this one superpower that makes everything else possible: **instant access by index**. When you do `arr[3]`, the CPU doesn't search for anything. It just calculates `base_address + 3 * element_size` and jumps straight there. O(1). Done. No questions asked.
That's the magic trick we want for our hash map.
Our keys aren't numbers though. They're strings like `"email"` and `"name"` and `"age"`. You can't just do `arr["email"]` (well, you can in JavaScript, but that's a whole different rabbit hole). Arrays need _numbers_.
So we need something that takes any key and turns it into a number. A number we can use as an array index.
That something is called a **hash function**.
## Turning gibberish into numbers
A hash function takes any input (a string, a number, whatever) and spits out an integer. Same input, same output, every time. Different inputs _usually_ give different outputs.
That "usually" is going to bite us later. Keep it in the back of your mind.
Here's a real one. It's called **djb2**, first reported by [Dan Bernstein](https://en.wikipedia.org/wiki/Daniel_J._Bernstein) in `comp.lang.c` many years ago. Not the best hash function by modern standards, but fast, simple, and perfect for understanding the concept:
```c
unsigned long hash(unsigned char *str) {
unsigned long hash = 5381;
int c;
while (c = *str++)
hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
return hash;
}
```
Each iteration multiplies hash by 33 (that's what `(hash << 5) + hash` does) and adds the next character. Dead simple. The interactive demos below use a JavaScript port of the same algorithm.
Why 33? According to [oz's classic hash function page](https://web.archive.org/web/2024/http://www.cse.yorku.ca/~oz/hash.html), "the magic of number 33 — why it works better than many other constants, prime or not — has never been adequately explained." Why 5381? [Nobody really knows](https://stackoverflow.com/questions/10696223/reason-for-5381-number-in-djb-hash-function). Bernstein picked these constants and they just work. Sometimes engineering is just vibes and benchmarks.
The raw hash is a massive number, way bigger than our array. So we squeeze it into range with modulo: `hash % capacity`. If we have 8 slots, `djb2("email") % 8` gives us a number between 0 and 7. That's our index. (Technically the hash function itself is O(key length), not O(1), but keys are usually short so we treat it as constant.)
Go ahead, type anything in here and watch it get hashed:
## Where stuff actually goes
Cool, so now we have a function that turns any string into a number between 0 and 7. Now what?
We make an array (usually called a **bucket array**) and use that number to decide _which slot_ each key-value pair lands in. You want to store `"name": "Alice"`? Hash `"name"`, get a bucket index, drop the entry there. If the key already exists, just update its value. That's it.
Let me walk you through it. Hit "Next" to step through each insertion one by one:
Three insertions, three different buckets. Each lookup is just: hash the key, jump to the bucket, grab the value. O(1). This is the happy path.
Remember that "usually" from earlier? Yeah. Time to deal with that.
## When things go wrong (kind of)
Here's a fact that might make you uncomfortable: we have 8 buckets and an _infinite_ number of possible strings. There is literally no way to guarantee every key gets its own slot. This is the [pigeonhole principle](https://en.wikipedia.org/wiki/Pigeonhole_principle): more pigeons than holes means at least two pigeons are sharing. Math doesn't care about your feelings.
So what happens when `"name"` and `"city"` both hash to bucket 6? Does it just... break?
Nope. The simplest solution is called **chaining**. Instead of each bucket holding one entry, it holds a _list_ (a chain) of entries. On lookup, you hash to the bucket, then walk the chain comparing keys until you find yours. It's a tiny linear search, but only within that one bucket.
This is way easier to see than to explain. Step through it:
So a collision doesn't break anything. It just adds one extra comparison per chained entry. As long as the chains stay short (one or two entries) you barely notice.
Wait. What _stops_ the chains from getting long? If I keep cramming entries in, won't everything pile up into a few long chains and basically become a linked list? At that point our "O(1)" hash map is just an O(n) list with extra steps. So much for constant time.
Turns out the people who designed this thought of that.
## When the table says "I'm full"
The **load factor** is dead simple: `entries / capacity`. It tells you the average number of entries per bucket. With a good hash function, keeping the load factor bounded keeps chain lengths bounded too. That's the whole trick.
[Java](https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html) draws the line at **0.75**. Other languages choose differently: [Python](https://github.com/python/cpython/blob/main/Objects/dictobject.c) uses ~0.67, [Rust](https://github.com/rust-lang/hashbrown/blob/master/src/raw.rs#L182) ~0.875, [C++](https://en.cppreference.com/w/cpp/container/unordered_map/max_load_factor) defaults to 1.0. Lower means more wasted space, higher means more collisions before a resize.
Cross the threshold, and the hash map _doubles_ its size and **rehashes every single entry** into the new, larger array.
This blew my mind when I first got it. The old bucket indices are completely invalid after a resize because `hash % 4` gives a totally different result than `hash % 8`. So _every_ entry has to be re-placed. It's expensive, but it happens rarely enough that the math works out.
Keep pressing "Insert" here and watch the load factor bar creep up. When it crosses the line, watch closely:
See what happened there? The table doubled, every entry found a new home, and the load factor dropped back down. Chains got shorter. Performance restored.
This is why people say hash maps have **amortized** O(1) performance. _Most_ operations are instant. Every now and then, one unlucky insert triggers a resize that costs O(n). Each resize doubles the capacity, so you need _n_ more cheap inserts before the next expensive one. The total cost of all resizes is n + n/2 + n/4 + ... which is less than 2n. Spread across n inserts, that's O(1) each.
Pay a little now, save a lot later.
---
## Go break it
OK, theory's done. Here's a full hash map sandbox. You can `put`, `get`, and `del` keys. Try to cause a collision on purpose (hint: try `"name"` and `"city"`). Fill it up until it resizes. Look up a key that's buried deep in a chain and watch it traverse.
Or hit "flood bucket 0" and watch what happens when an attacker crafts keys that _all_ land in the same bucket. Your O(1) map becomes a linked list. This is a real attack vector: web frameworks parse query strings, JSON, and form data into hash maps, so an attacker controls the keys by controlling the HTTP request.
The fix is using a keyed hash function (like SipHash) with a per-process random secret, so an attacker can't predict which keys collide. Python added [hash randomization](https://www.ocert.org/advisories/ocert-2011-003.html) in 3.3 (2012) after a disclosure in late 2011, then switched to [SipHash in 3.4](https://en.wikipedia.org/wiki/SipHash#Usage) (2014).
The whole thing in one line:
> **key → hash(key) → index = hash % capacity → bucket[index] → walk chain → value**
Everything above is just unpacking this pipeline.
## What I left out (the rabbit hole goes deep)
What I showed you is **chaining**, the simplest collision strategy. Most production hash maps today actually use a different approach, and the optimizations go deep:
**Open addressing** is what most modern hash maps use instead of chaining. When there's a collision, you don't build a linked list, you just look for the next empty slot in the array itself. This has way better [cache locality](https://en.wikipedia.org/wiki/Locality_of_reference) because you're scanning contiguous memory instead of chasing pointers all over the heap. The tradeoff: deletion requires tombstones and is genuinely tricky, which is part of why chaining persisted as long as it did. [Robin Hood hashing](https://programming.guide/robin-hood-hashing.html) is a particularly beautiful variant that "steals from the rich" by letting entries with longer probe distances bump out entries with shorter ones. Cute name, clever algorithm.
(Java's `HashMap` still uses chaining but converts long chains into red-black trees at length 8, so its worst case is O(log n) not O(n). Clever hybrid.)
**SIMD probing** is what Google's [Swiss Table](https://abseil.io/about/design/swisstables) design does (implemented in Abseil C++ and, independently, in Rust's [hashbrown](https://github.com/rust-lang/hashbrown) which backs its standard `HashMap`). It uses CPU vector instructions to check 16 slots' metadata bytes in a single operation, then only does full key comparison on matches. Extremely fast. If you want to go deep, [Matt Kulukundis's CppCon talk](https://www.youtube.com/watch?v=ncHmEUmJZf4) is an absolute banger.
**Power-of-two sizing** is a neat trick: when your capacity is always a power of 2, you can replace the expensive modulo with a bitwise AND: `hash & (capacity - 1)` does the same thing, way faster. Most modern implementations do this.
**Better hash functions** fall into two camps. [SipHash](https://en.wikipedia.org/wiki/SipHash) is a keyed PRF designed for adversarial resistance: give it a per-process secret key and an attacker can't predict collisions. [xxHash](https://cyan4973.github.io/xxHash/) and [wyhash](https://github.com/wangyi-fudan/wyhash) are built for raw speed and better distribution, not security. Different tools for different problems.
---
The core idea never changes though: hash the key, find the bucket, handle collisions, resize when it gets full.
I wish I'd looked inside sooner.