How Hash Maps Actually Work

Almost every language ships with some kind of key-value store. JavaScript has Map and plain objects, Python has dict, Go has map. You put a value in under a key, and later you get it back:

const sounds = new Map();sounds.set("cat", "meow");sounds.get("cat"); // "meow"

What's remarkable is how fast get is. Whether the map holds ten entries or ten million, finding a key takes roughly the same amount of time. In this post, we'll build our own hash map to see how that's possible.

The slow way#

Let's start with the simplest thing that could work: a list of pairs.

const entries = [];function set(key, value) {  entries.push([key, value]);}function get(key) {  for (const [k, v] of entries) {    if (k === key) return v;  }}

This works, but get has to walk through the entries one by one. Double the data and, on average, you double the work.

Arrays are fast#

There is one lookup computers do instantly: reading an array by index. array[5] doesn't scan anything — the computer calculates where item 5 lives in memory and jumps straight there.

So here's the idea. What if we could turn any key into an array index? Then storing and finding a key would both be a single jump.

Hash functions#

A hash function does exactly that. It takes a key and turns it into a number. To keep things simple, our hash function adds up the character codes of the key, then uses the remainder operator % to squeeze the result into the range of our array:

const BUCKETS = 8;function hash(key) {  let sum = 0;  for (const char of key) {    sum += char.charCodeAt(0);  }  return sum % BUCKETS;}

Each slot in the array is called a bucket. The same key always produces the same number, so it always lands in the same bucket. Try it out:

Collisions#

If you tried setting act, you'll have noticed a problem: it lands in the same bucket as cat. The letters are the same, so the sums are the same. This is called a collision, and with only a handful of buckets, collisions are guaranteed.

The fix we're using here is called separate chaining: each bucket holds a short list, and colliding entries simply share it.

const buckets = Array.from({ length: BUCKETS }, () => []);function set(key, value) {  const bucket = buckets[hash(key)];  const entry = bucket.find(([k]) => k === key);  if (entry) entry[1] = value;  else bucket.push([key, value]);}function get(key) {  const bucket = buckets[hash(key)];  return bucket.find(([k]) => k === key)?.[1];}

We're back to scanning a list — but only a tiny list. Instead of every entry in the map, we check only the few that share a bucket.

Keeping buckets small#

A hash map is only fast while its buckets stay short. The ratio of entries to buckets is called the load factor. As it creeps up, real implementations resize: they allocate a bigger array (usually twice the size) and move every entry into its new bucket.

Resizing is slow, but it happens rarely enough that, averaged over many insertions, each set is still effectively constant time.

And that's the secret behind every Map, dict and object you've ever used: a hash function to pick the bucket, an array to jump to it, and a short list to handle the rest.