Hash Maps

An array is fast because position is arithmetic. Element 5 lives at start + 5 × size, so the computer jumps straight there without looking at anything else.

That only works if your key is a position. What if you want to look things up by name?

The idea

Turn the key into a number, and use that number as the position.

const index = hash('alice') % buckets.length;   // e.g. 7

A hash function takes anything — a string, an object — and produces a number. Take that modulo the array size and you have a slot. Now 'alice' behaves like an index.

Collisions are guaranteed, not unlucky

There are infinitely many possible strings and only, say, 64 buckets. So different keys must sometimes land on the same one. This is not a flaw to engineer away; it is arithmetic.

So each bucket holds a small list, and lookup scans it:

function get(key: string): Value | undefined {
  const index = hash(key) % buckets.length;

  // Everything that landed in this bucket, scanned one by one. Short if the
  // hash spreads well; the entire table if it does not.
  for (const entry of buckets[index]!) {
    if (entry.key === key) return entry.value;
  }
  return undefined;
}

“O(1) on average” is a claim about how full it is

That loop is only fast if the bucket is short. With $n$ keys spread over $m$ buckets, the average bucket holds $n/m$ entries — the load factor.

Drag the sliders and watch the chains grow:

Break the condition and everything degrades to scanning a list: $O(n)$ per lookup, with nothing reporting an error.

When the spread fails on purpose

This is not hypothetical.

If an attacker can choose your keys and predict your hash function, they can send thousands of keys that all collide. Every bucket but one stays empty, every request scans a huge list, and your server falls over under a trivial amount of traffic. It is called hash flooding, and it hit PHP, Python, Ruby, Java and Node within months of each other in 2011–2012.

The fix is a hash the attacker cannot predict: SipHash, seeded randomly when the process starts. Slightly slower than what it replaced, and that cost buys a worst case nobody can trigger deliberately.

What you give up

Order. A hash map has none. Iteration follows bucket layout, which is essentially arbitrary and can change when the table grows.

If you need range queries — “everything between 10 and 20”, or “the smallest key above 15” — you want a tree-shaped structure, and you pay $O(\log n)$ for it.

The pattern it unlocks

Hash maps turn a nested loop into one pass by trading memory for time. Where two pointers needs the array sorted, a hash map needs nothing:

const seen = new Map<number, number>();
for (const [i, value] of values.entries()) {
  const need = target - value;
  if (seen.has(need)) return [seen.get(need)!, i];   // saw the partner earlier
  seen.set(value, i);
}

One pass, $O(n)$ time, $O(n)$ space, no precondition. That is usually the right default — reach for two pointers when the data is already sorted, or when the extra memory genuinely matters.