A hash table's load factorα = items ÷ slots. The single number that governs how expensive lookups are. Keep it below about 0.7 for open addressing, or rehashing becomes cheaper than suffering the probes. α is items ÷ slots. With open addressingProbing: on a collision, scan forward (or quadratically, or via double-hashing) until you find an empty slot. One contiguous array, great cache behaviour — but α must stay below 1, and the probe count blows up before you get there., the average probes per lookup follow 1/(1−α) — the very same cliff as a queue near 100% busy — which is why tables resize around 70% full, long before they're "full". Separate chainingChaining: each slot holds a linked list of items that hash there. Allows α > 1, and lookup cost grows linearly — but pointer indirection kills cache locality. only sags, linearly.
load factor α = 0.75
At α = 0.75, a failed lookup probes 8.5 slots on average. Push toward full and it runs off a cliff — the same 1/(1−α)² shape as a busy queue, only steeper.
| Load factor α | Hit probes | Miss probes |
|---|---|---|
| 0.50 | 1.5 | 2.5× |
| 0.70 | 2.2 | 6.1× |
| 0.80 | 3 | 13× |
| 0.90 | 5.5 | 51× |
| 0.95 | 10 | 200× |
| 0.99 | 50 | 5000× |
For open addressing, the miss cost is the same 1/(1−α) cliff — squared, even — as a queue at high utilisation. That is exactly why hash tables grow and rehash around α ≈ 0.7, well before they're full. Chaining degrades gracefully (linear in α) but spends memory on pointers and loses cache locality. The same math as the queue cliff, a different domain.