A hash map is just an array that computes its own index

A map with a million keys answers a lookup just as fast as a map with ten. No loop. No searching. Your program jumps straight to the answer.

That's not magic, and it isn't a tree. It's one very old trick, plus two failure modes that most people never hear about.

Prefer to watch? Full walkthrough with the bucket animation:

Arrays are the fast part

Start with the one thing computers are genuinely fast at: an array. Ask for item number five and nothing is searched. The machine multiplies the index by the element size, adds it to the start address, and lands on the exact spot in memory. Item five and item five million cost the same.

The catch is that arrays only take positions. You don't think in positions — you want the value stored under "email", or under a user ID, or under a whole string of text.

So the real question is: how do you turn a key like "email" into a position?

The hash function

A hash function takes anything — a word, a sentence, an object — and gives back a number. Two properties matter:

• Deterministic. Same key in, same number out, every time.
• Well spread. Change one letter and the result isn't close to the old one, it's unrecognizable. A hash that put similar keys near each other would pile them up in the same place.

That number is usually huge, much bigger than your array. So you do the simplest possible thing: take the remainder.

hash("email")        = 3,742,909
3,742,909 % 8        = 5

Now you have a position. Each slot of that array is called a bucket.

Look at what just happened. You didn't search for the key — you computed where it lives. Writing is hash, remainder, store. Reading is hash, remainder, load.

The whole idea, in code

const buckets = new Array(8)

const slot = (key) => hash(key) % buckets.length   // "email" → 5

buckets[slot("email")] = "[e-mail]"          // write
buckets[slot("email")]                             // read

There's a problem hiding in that one line. The hash space is huge, the array is small. So sooner or later, two different keys produce the same slot.

Collisions are normal

That's a collision, and it isn't an edge case — with 8 slots it happens almost immediately.

So a bucket doesn't hold a bare value. It holds pairs: the key and the value. On a lookup you jump to the bucket, then compare keys inside it. Usually there's one pair. Sometimes two. That's also why a map has to store your key at all — otherwise it could never tell two collided keys apart.

There are two ways to handle the collision, and languages pick sides:

• Chaining — keep a small list inside the bucket and walk it.
• Open addressing — no list; if the slot is taken, step to the next one until you find a free seat. CPython's dict works this way (see the comment at the top of Objects/dictobject.c — an implementation detail, not a language guarantee).

Either way the shape is the same: land close to the answer, then take a step or two.

So what does "constant time" actually mean?

One hash. One jump. A tiny compare. It isn't zero work — it just doesn't get worse as the map grows. The Java docs put a condition on it: constant-time performance for get and put, assuming the hash function disperses the elements properly among the buckets.

Hold on to that "assuming". It's where both failure modes live.

Load factor: the resize you don't see

Keep adding keys to the same small array and the buckets fill up. Those little lists get long, and comparing one by one stops being cheap. So a map watches how full it is — that ratio is the load factor.

In Java, a HashMap starts with 16 buckets and a load factor of 0.75. Cross that line and the table is rebuilt with roughly twice as many buckets, and every existing key is re-slotted.

Which means one unlucky insert does the work of the entire map. The average stays fast. That one call doesn't. If you know you're about to load a million entries, size the map up front.

When O(1) is a lie

Now the interesting failure. Imagine every key you insert lands in the same bucket. One long list; every lookup walks it. Your constant-time map is now a linear scan.

That can happen by accident with a bad hash — and it can be done to you on purpose. An attacker who knows your hash function can send keys engineered to collide, turning cheap requests into expensive ones. Python's answer is to salt the hash of str and bytes with a random value at startup, explicitly as protection against that denial of service.

The key that disappears

This one is your own fault, and it's a classic.

You store a value under a key. Then you mutate that key object. Its hash changes with it. The map now computes a different slot, looks there, and finds nothing — while your entry sits in the old bucket, unreachable.

Use keys that can't change: a string, a number, a frozen/immutable object.

And no, it has no order

A hash map scatters keys by their hash, not by when you added them, so iteration order is whatever the buckets happen to hold.

Python is the exception you've probably been relying on: since 3.7, a dict preserves insertion order as a language guarantee. Java's HashMap promises nothing of the sort. If you need order, use the type that promises it.

Three rules

• Keys that don't change.
• A hash that spreads keys out.
• Enough room that the map isn't constantly resizing.

Get those right and it behaves like magic. Get them wrong and it quietly becomes a list.

A hash map isn't magic and it isn't a tree — it's an array that already knows where you put things.

What's the worst hash-map bug you've hit — the key that vanished, or the resize that froze your app? Tell me in the comments, I read them.

---

I make Vlad's Stack — how the tools you use every day actually work, for people who write code. The full video walkthrough is above.