Why do production hash tables grow at roughly 0.6-0.75 occupancy instead of waiting until every bucket is used?

## The threshold is a dial, not a law A hash table's growth threshold — the maximum load factor it tolerates before allocating a bigger bucket array — is a **policy choice**. Nothing breaks at 0.76 and nothing is guaranteed at 0.74. The number lives where it does because of the shape of two curves that move in opposite directions. ## Curve one: cost per operation rises with occupancy Load factor is the mean number of entries per bucket, so it is directly the expected amount of extra work a lookup must do after landing on a bucket. - **Chaining**: expected work per lookup is proportional to `1 + alpha` — one bucket access plus a walk of the expected chain. At 0.75 you expect to inspect well under one extra entry; at 3.0 you expect three. The curve is a straight line, so chaining degrades gracefully. - **Open addressing**: entries live in the bucket array, so a collision forces the key into another key's slot, and lookups walk a probe sequence. Here the expected probe count rises **superlinearly** and diverges as occupancy approaches 1: the last few percent of slots are the expensive ones to find and to fill. Both curves are gentle in the 0.5-0.75 band and unpleasant above it. Setting the threshold inside the gentle region means the table is never operated on the steep part of its own cost curve. ## Curve two: memory saved by running fuller is small Suppose you hold `n` entries. Buckets needed is `n / threshold`: | threshold | bucket slots per entry | |---|---| | 0.50 | 2.00 | | 0.75 | 1.33 | | 0.95 | 1.05 | Going from 0.75 to 0.95 removes about 21% of the bucket slots. But a slot is usually a single pointer or index; an **entry** carries a key, a value, and often a cached hash or a next-pointer. In a table of substantial entries the bucket array is frequently a minority — sometimes a small minority — of total footprint. So the memory you buy back by running hot is a fraction of a fraction, while the latency you pay lands on every single lookup. That asymmetry is the whole argument: **you are trading a cheap resource for an expensive one, so you buy generously.** ## Why "resize when full" is the wrong rule Two separate reasons, and interviewers like both: 1. **For open addressing it is not even reachable.** "Full" means no free slot; the final insertions each scan enormous stretches of the array, and the last one has nowhere to go. The scheme requires headroom to function, not merely to be fast. 2. **For chaining it is undefined.** A chained table has no full — you can always append to a chain. Its cost simply keeps rising linearly. Without a threshold, the structure silently degenerates into an array of linked lists. And the opposite rule — resize on the first collision — is equally wrong, because collisions begin at tiny occupancies. With `m` buckets, the first collision among randomly distributed keys is expected after roughly `1.25 × sqrt(m)` insertions; a 16,384-bucket table sees one around the 160th key. A collision-triggered rule would grow forever. ## Why the band is 0.6-0.75 specifically Several pressures converge there: - Below ~0.5 the memory waste doubles the bucket array for a barely measurable latency gain. - Above ~0.8 the tail of the cost distribution starts to matter even under chaining: the longest chain, not the mean, is what a p99 latency number sees. - **Hash quality is never ideal.** The clean curves above assume uniform scattering. Real keys are structured and real hash functions mix imperfectly, so the effective occupancy in the hot buckets is worse than the scalar suggests. Choosing a threshold below where theory bites leaves headroom for that discrepancy. - The threshold also has to survive **growth granularity**: bucket counts usually double, so occupancy oscillates between roughly half the threshold and the threshold itself. Average realised occupancy is therefore well below the number you configure — another reason the configured number does not need to be aggressive. Mainstream runtimes disagree within this neighbourhood precisely because they resolve collisions differently: a widely used chained table in the Java standard library grows at 0.75, Python's open-addressed dictionaries grow at about two thirds, and C++'s unordered containers permit a maximum load factor of 1.0 by default, leaning on chaining's linear degradation. Same concept, three defensible answers. ## The answer in one breath "Because the expensive resource is time on the lookup path and the cheap resource is bucket slots. Cost rises with occupancy — linearly under chaining, far worse under open addressing — while running from 0.75 up to 0.95 only removes about a fifth of an array of pointers. And 'full' is not a usable trigger: open addressing cannot reach it and chaining has no such point."