Hashing & Collisions

Say you keep 10,000 user records in a list and need the one for “alice”. Without any structure, you check them one at a time. On average that's 5,000 comparisons, and 10,000 when she isn't there at all. Double the users and every lookup takes twice as long.

Keeping the list sorted helps (binary search needs about 14 comparisons for 10,000 items), but now every insert has to shift everything after it to keep the order. What you actually want is to compute where “alice” lives from the key itself and go straight there. That's what a hash table does: turn the key into an array index, then look in that one slot.

A hash function takes a key and returns a number. Three properties make it useful for a table:

This topic (and the ones after it) uses 32-bit FNV-1a. It starts from a fixed number, and for every byte of the key it XORs the byte in and multiplies by a prime. The multiply smears each byte across all 32 bits:

function fnv1a(key: string): number {
  let hash = 0x811c9dc5;                 // FNV offset basis
  for (const byte of utf8Bytes(key)) {
    hash ^= byte;                        // mix this byte in
    hash = Math.imul(hash, 0x01000193);  // multiply by the FNV prime
  }
  return hash >>> 0;                     // read as an unsigned 32-bit number
}

const bucket = fnv1a(key) % m;

Worked through for one key: fnv1a("apple") is 280767167. With 16 buckets, 280767167 mod 16 = 15, so “apple” always goes in bucket 15. Compare a few more keys, and the “first letter” hash from the simulation next to it:

“apple” and “apply” differ by one letter but land in unrelated buckets under FNV-1a. That's the avalanche effect: flip one input bit and about half the output bits flip. The first-letter hash puts all three “a” words in the same bucket, and it would do the same for any real list of names, where some first letters are much more common than others.

There are billions of possible keys and only m buckets. The pigeonhole principle says that once you store more than m keys, at least two must share a bucket. With a good hash you'll see collisions long before that, too.

That's the birthday paradox. In a room of just 23 people there's a 50.7% chance that two share a birthday, because what matters is the number of pairs (253 of them), not the number of people. Hash tables behave the same way. With 16 buckets, just 5 keys already give a 50.0% chance of a collision, and 8 keys give 87.9%.

So collisions aren't a sign of a broken hash function. Every hash table needs a plan for them, and there are two main ones.

Try both in the simulation with the same keys. Under open addressing, notice how occupied slots bunch into runs. Any key that hashes into a run has to probe to its end, and then makes the run one longer. That's clustering, and it's why open addressing tables resize earlier than chained ones.

The load factor is keys divided by buckets: n / m. It predicts the cost of a lookup. Under chaining with a good hash, the average chain holds n / m keys. Under linear probing it gets worse much faster. Knuth's estimate for a lookup that misses is about ½(1 + 1/(1 − α)²) probes: 2.5 at α = 0.5, 8.5 at 0.75 and 50.5 at 0.9.

So tables pick a threshold and grow once they pass it: 0.75 for Java's HashMap, 2/3 for Python's dict. Growing usually means doubling m, which keeps the average cost per insert constant even though each resize is expensive.

And each resize isexpensive. A key's bucket is hash(key) mod m, so a new m means a new bucket for most keys. Every key has to be hashed again and copied into the new array. Doubling moves about half of them, and going from m to m + 1 moves nearly all of them. Watch the “moved on last resize” counter in the simulation.

A table can only double while memory lasts. Past that there are two ways out: evict (a cache drops its least-recently-used keys instead of growing) or spread the keys across several machines.

In memory a resize is a brief pause. Now imagine the buckets are cache servers and you're adding a fifth one to four. With hash(key) mod N, about 80% of keys suddenly map to a different server, and 80% of your cache misses at once. Moving only the keys that have to move is exactly what Consistent Hashing (planned) is for.

“Hash function” covers several families built for very different goals. The simulation only uses the first one; the rest are here so you can tell them apart.

• Hash maps and sets: every language's dictionary type is the table in this simulation, plus a lot of engineering.
• Database hash indexes and hash joins: jump straight to rows with a given key, or match two tables by hashing one side into buckets first.
• Sharding and partitioning: hash(key) mod N picks which of N machines or partitions owns a key. Kafka's default partitioner does exactly this with MurmurHash2. It inherits the resize problem above whenever N changes.
• Load balancing: IP hash and URL hash send the same client or path to the same backend every time. See it live in the Load Balancer simulation, including what happens when a backend dies.
• Checksums and deduplication: identical content hashes to identical output, so storage systems and backup tools can spot a chunk they already have without comparing it byte by byte.
• Bloom filters: hash a key k different ways to set k bits, and you can answer “definitely not here” without touching the disk. That's the third topic in this series: Bloom Filter (planned).