“Hash tables are O(1)” is true in the same way “the average human has one testicle” is true. The constant factor and the worst case are where programs actually live, and both are governed by how you handle collisions — two keys landing in the same slot.

Why Collisions Are Inevitable

A hash function maps a huge key space into a small array of buckets. By the pigeonhole principle, distinct keys will share buckets. With even a decent hash, the birthday paradox means collisions start appearing far earlier than intuition suggests — you don’t need the table to be full.

The fraction of slots used is the load factor (α = entries / buckets), and it’s the single number that governs collision rate.

Two Ways to Resolve Them

Chaining — each bucket holds a linked list of entries:

text
   [0] → (key1) → (key4)
   [1] →
   [2] → (key2) → (key7) → (key9)   ← collisions chain here

Simple and degrades gracefully, but each chain hop is a pointer chase to a random address — a likely cache miss. A “found in 3 comparisons” lookup can mean three cache misses, which dwarfs the comparisons.

Open addressing — entries live in the array itself; on collision you probe to the next slot:

text
   [0][k1][k4][ ][k2][ ][ ]   ← k4 wanted slot 1, probed to slot 2

Everything stays in contiguous memory, so probes are cache-friendly. The price: performance falls off a cliff as the table fills, because probe sequences get long. Open addressing needs a lower load factor (often kept under ~0.7).

The Cost You Forgot: Resizing

When the load factor crosses a threshold, the table doubles and every entry is rehashed into the new array — an O(n) operation. It’s rare, so amortized cost stays O(1), but any single insert can stall:

text
   insert, insert, insert, ... , INSERT(resize: rehash all n) , insert, ...
                                  └─ one slow op hidden in the average

For latency-sensitive code, that occasional spike matters. Preallocate with the expected size to dodge it.

What Actually Makes Them Fast

  • Keep the load factor sane. High α means long chains or long probes.
  • Mind cache behavior. Open addressing usually beats chaining in practice purely because it stays in contiguous memory.
  • Use a good hash. A weak hash clusters keys into the same buckets and turns your O(1) table into an O(n) linked list — the basis of algorithmic-complexity denial-of-service attacks.

Takeaways

  • Collisions are unavoidable; the load factor controls how often they happen.
  • Chaining degrades gracefully but pays cache misses; open addressing is cache-friendly but needs a lower load factor.
  • Resizing rehashes everything — amortized O(1) hides a real per-op spike, so preallocate when latency matters.
  • A bad hash collapses O(1) into O(n); pick a strong one.