You have a list of ten thousand IDs and you want to know whether 48213 is in it. You can check every item one by one. Or you can jump straight to the answer, almost instantly, whether the list has ten thousand items or ten million.

That second option sounds like cheating. It's a hash map, and you use one every day: every PHP array, every JavaScript object and Map, every Python dictionary, every cache key. Understanding how it works explains why some code is mysteriously fast, why other code is mysteriously slow, and one of the stranger security bugs in web history.

The coat check

Picture a coat check with a hundred numbered hooks. You hand over your coat and the attendant doesn't put it on the next free hook. Instead, they take your name, run it through a little rule (say, add up the letters and take the last two digits) and get a hook number. Your coat goes on hook 37.

When you come back, they don't search all hundred hooks. They run your name through the same rule, get 37 again, and walk straight to it.

That's the whole idea:

• The hooks are an array of slots, usually called buckets.
• The rule is a hash function: it turns a key into a number, quickly, and always gives the same number for the same key.
• The number, reduced to the size of the array (with a modulo, for example), is the bucket index.

Looking something up doesn't depend on how many items there are. Hash the key, jump to the bucket, done.

A tiny hash map, from scratch

Here's a toy version in JavaScript. Real implementations are far more optimised, but the shape is the same:

class TinyHashMap {
  constructor(size = 8) {
    this.buckets = Array.from({ length: size }, () => []);
  }

  index(key) {
    let h = 0;
    for (const ch of String(key)) h = (h * 31 + ch.charCodeAt(0)) >>> 0;
    return h % this.buckets.length;
  }

  set(key, value) {
    const bucket = this.buckets[this.index(key)];
    const entry = bucket.find(([k]) => k === key);
    if (entry) entry[1] = value;
    else bucket.push([key, value]);
  }

  get(key) {
    return this.buckets[this.index(key)].find(([k]) => k === key)?.[1];
  }
}

Notice that each bucket is a small list, not a single slot. That's because of the one problem every hash map has to solve.

Collisions: two coats, one hook

With a limited number of buckets and an unlimited number of possible keys, two different keys will sometimes land in the same bucket. That's a collision, and it's not a bug. It's guaranteed.

There are two classic ways to handle it:

• Chaining: each bucket holds a short list, and colliding entries share it. Lookup jumps to the bucket, then checks the few items in it. That's what the toy above does.
• Open addressing: if the bucket is taken, try the next one according to some rule until you find a free slot. Python's dictionaries work this way.

Either way, a lookup still has to compare the actual keys at the end, because the hash only tells you where to look, not that you found the right thing.

Why it's "O(1) on average"

Lookups are fast only while buckets stay short. If you keep adding items to a fixed number of buckets, the lists grow and every lookup slows down. So real hash maps track their load factor (items divided by buckets), and when it gets too high, they resize: allocate a bigger bucket array, typically double the size, and re-insert everything.

Resizing is slow when it happens, but it happens rarely, and doubling means the cost spreads out across all the inserts that came before. That's what "amortised O(1)" means: occasionally expensive, cheap on average.

And the worst case? If every key lands in the same bucket, the hash map becomes a slow list, and each lookup is O(n). With a decent hash function and normal data, that essentially never happens by accident.

When it happens on purpose

By accident, no. On purpose, yes. In 2011, security researchers showed that many web platforms used predictable hash functions for request parameters. An attacker could craft a single POST request with thousands of keys that all collided, and the server would spend a long time building one hopelessly slow hash table. Small request, huge CPU cost.

The fixes varied. Many languages moved to hash functions with a random secret seed, so attackers can't predict collisions. PHP's answer at the time was the max_input_vars setting, which caps how many input variables a request can create. That's why that setting exists in your php.ini.

Your PHP array is a hash map

PHP has one array type, and under the hood it's an ordered hash table. Lists, dictionaries, and that associative array your config file returns are all the same structure (PHP has an optimised "packed" mode for plain lists, but it's the same type from your point of view). A few practical consequences:

Key lookups are fast; value searches are not. isset($map[$key]) hashes and jumps. in_array($value, $list) walks the whole array. Inside a loop, that difference is the gap between instant and painfully slow:

// O(n) every time: scans the whole list
in_array($id, $blockedIds);

// O(1) on average: flip once, then hash lookups
$blocked = array_flip($blockedIds);
isset($blocked[$id]);

If you check membership inside a loop over thousands of rows, flipping the array first is one of the cheapest performance wins in PHP.

Keys get normalised. A string key that looks like a plain decimal integer, like "42", is stored as the integer 42. But "042" stays a string. So $a["42"] and $a[42] are the same element, which is usually convenient and occasionally very confusing when IDs come in as strings.

Order is preserved. Unlike a textbook hash map, PHP arrays remember insertion order, which is why foreach gives you items in the order you added them.

And in JavaScript

Plain objects work as hash maps, but their keys are always strings (or symbols), and they come with inherited properties. Map accepts any key type, keeps insertion order, has a size, and is designed for frequent adds and deletes. For a real lookup table, Map is usually the better choice; for a fixed shape like a config object, a plain object is fine.

The short version

• A hash function turns a key into a bucket number; lookups jump straight there.
• Collisions are normal; chaining or open addressing handles them.
• Resizing keeps buckets short, so lookups stay O(1) on average.
• Predictable hashes can be attacked; that's why seeds and max_input_vars exist.
• In PHP, prefer isset on keys over in_array on values in hot loops.

Where did a hash map last save you, or where would one have? I'd love to hear your best in_array-in-a-loop story.