Collisions and how tables survive them

Collisions are not an edge case; they are guaranteed. With more possible keys than buckets, the pigeonhole principle settles it. The birthday paradox makes it worse than intuition suggests: with 23 keys in 365 buckets, a collision is more likely than not.

Separate chaining

Each bucket holds a list of entries. On collision, append.

class HashMap {
  constructor(buckets = 16) {
    this.buckets = Array.from({ length: buckets }, () => []);
  }

  set(key, value) {
    const chain = this.buckets[hash(key, this.buckets.length)];
    const found = chain.find((entry) => entry.key === key);

    if (found) found.value = value;
    else chain.push({ key, value });
  }

  get(key) {
    const chain = this.buckets[hash(key, this.buckets.length)];
    return chain.find((entry) => entry.key === key)?.value;
  }
}

Simple, tolerant of load factors above 1, and degrades gracefully. Java replaces long chains with balanced trees, capping the worst case at O(log n) per bucket instead of O(n).

Open addressing

Store entries directly in the array; on collision, probe for another slot.

• Linear probing — try the next slot. Cache-friendly, but causes primary clustering.
• Quadratic probing — try 1, 4, 9 slots away. Less clustering.
• Double hashing — a second hash determines the step. Best distribution.

Open addressing uses less memory and has better locality, and it needs tombstones on deletion — a removed entry must leave a marker, or probe chains break.

Hash flooding

If an attacker can choose keys, they can force every one into a single bucket, turning O(1) into O(n) and a request into a denial of service. Real attacks in 2011 took down web frameworks using exactly this.

Defences: seed the hash randomly per process (Python, Ruby, Rust do this), tree-ify long chains (Java), or use a keyed hash such as SipHash. If you ever hash untrusted input into a table, use the platform's map rather than rolling your own.

What this means for you

Quote hash map operations as O(1) average, O(n) worst case. The average holds with a decent hash function and a controlled load factor. Saying only "O(1)" invites the follow-up "and when is it not?" — which you now have the answer to.