Load Factors & Rehashing
Hashmaps & Hash Tables · Data & Hashing track
5 min read
In this module
Balancing Space and Speed
Eight buckets, two entries: plenty of breathing room, lookups fly because most slots are empty. Stuff seven entries into the same eight buckets and the picture changes — collisions everywhere, lookups dragging. The load factor is the number that captures where you sit on that spectrum.
The Load Factor
The load factor is the ratio of entries to buckets:
load_factor = num_entries / num_buckets0.25 means the table is a quarter full. 0.75 means three-quarters. At 1.0 there are as many entries as buckets. For an open-addressing table that means full, but a chained table at 1.0 still has plenty of empty buckets (about 37% of them with a random hash) because others hold two or three entries. With chaining, the load factor can sail past 1 without breaking anything.
As the load factor climbs:
- Separate chaining: average chain length creeps up, and lookup time grows linearly with it.
- Open addressing: probe sequences explode. Even with an idealised probe sequence that never clusters, a lookup for a missing key averages about 1/(1 - load) probes: about 10 at 0.9, around 100 at 0.99. Linear probing clusters, so it does worse: Knuth's estimate puts that same miss at about 50 probes at 0.9.
The load factor (entries / buckets) drives hash table performance. Most implementations resize once it crosses a threshold — 0.75 is the canonical figure. That ceiling keeps chains short and probe runs bounded, which is what preserves the O(1) average case people promise you.
When to Resize
Every implementation picks a maximum load factor threshold. The next insertion that would tip the load factor over that line triggers a resize. A sample of where the major libraries land:
- Java HashMap: 0.75
- Python dict: approximately 0.67
- Go map: 0.875 since Go 1.24 switched to Swiss tables (7 of every 8 slots). The older bucket map used 6.5 entries per 8-entry bucket, about 0.81.
- Rust HashMap: 0.875 (using SwissTable with SIMD)
None of those numbers were plucked from the air. Each one is benchmark-driven, sitting at the sweet spot between wasted memory (too many empty buckets) and slow lookups (too many collisions).
The Rehashing Process
Resizing isn't just allocating a bigger array. Because the bucket index comes from hash(key) % num_buckets, changing the bucket count rewrites the address of every entry in the table. The dance:
- Allocate a new, larger bucket array — usually double the size.
- Walk every entry in the old array and recompute
hash(key) % new_size. - Drop the entry into the new array at its freshly-computed slot.
- Free the old array.
Before (4 buckets):[0]: ("a", 1) hash("a") % 4 = 0[1]: empty[2]: ("b", 2) hash("b") % 4 = 2[3]: ("c", 3) hash("c") % 4 = 3
After resize (8 buckets):[0]: ("a", 1) hash("a") % 8 = 0 (same bucket)[1]: empty[2]: empty[3]: ("c", 3) hash("c") % 8 = 3 (same bucket)[4]: empty[5]: empty[6]: ("b", 2) hash("b") % 8 = 6 (moved!)[7]: emptyNotice "b" jumped from bucket 2 to bucket 6. New modulus, new home.
The table below is stuck at 8 buckets: it never resizes, so it shows you what a table without a threshold turns into. Add keys one at a time and keep an eye on the load bar. The sixth key takes it to exactly 0.75, and the seventh is the insert that would make Java's HashMap double to 16 buckets and rehash everything. Carry on to 12 or so keys and look at how long the chains have grown.
Hash Table Explorer
Amortized O(1)
Rehashing is expensive — it's O(n), since every entry has to be reinserted. So how can we keep claiming hash tables are O(1)?
The answer is amortized analysis. If you double the table on every resize, n cheap O(1) insertions sit between any two resizes. Spread that one O(n) rehash across the n insertions that earned it, and the per-operation cost averages back out to O(1).
Think of moving house. Hundred small trips from your flat to the truck, each one O(1). Then you drive the full truck across town and unload everything in one shot, O(n). Total work, about 2n. Per item, still about O(1).
Shrinking
Some implementations also shrink the table once the load factor sinks too low after a wave of deletions, otherwise you keep paying for memory you no longer use. The shrink threshold sits well below the grow threshold (think 0.1 or 0.25), so the table doesn't ping-pong between growing and shrinking on every other operation.
The Power-of-Two Trick
Plenty of hash tables size themselves to powers of two — 8, 16, 32, 64, and onwards. The reward is replacing the costly modulo with a single bitwise AND:
// These are equivalent when num_buckets is a power of 2:index = hash % num_bucketsindex = hash & (num_buckets - 1)AND beats integer division by a wide margin on most CPUs. Index computation runs on every single hash table operation, so even a one-cycle saving compounds into something real.
Practical Implications
Once you understand load factors and rehashing, a few habits start paying off:
- Pre-size when you can. If you know roughly how many entries you'll end up with, hand that figure to the constructor. The HashMap skips expensive rehashing during bulk inserts.
- Watch for sparse-after-deletion tables. Insert a million entries, delete 950,000, and some implementations cheerfully hold onto the original capacity forever. That memory is wasted.
- Mind the rehash spike in latency-sensitive code. The single insertion that trips a resize can run thousands of times longer than its neighbours. For real-time systems, that jitter is usually unacceptable.