THE LOAD FACTOR — a dart

THE LOAD FACTOR how full is too full

The load factor α = n/m — entries over slots — governs everything. Chaining degrades slowly; open addressing’s cost blows up as α → 1 (like 1/(1−α)). So tables rehash when α crosses a threshold (often 0.75), doubling m. Here 7/8 = 0.875 trips the resize; after doubling to 16, α drops to 0.4375 — amortized O(1) restored.

THE TECHNIQUE α = n/m; rehash when α > 0.75

The demo computes α, trips the resize at 0.875, and shows the new α after doubling: live demo

HISTORY & CREDIT amortized analysis · table doubling

“Rehashing makes hash tables O(n) sometimes, so not O(1).” — the doubling cost is amortized away: each element is copied O(1) times on average. cited

the ratio · α = n/m is the one knob.
the wall · open-addressing probes ~ 1/(1−α) — it explodes near 1.
the fix · double m at a threshold; amortized O(1) (table doubling).

One number decides speed. arithmetic

RECOMMEND FOR I-13 the resize, on the compiler

On i-13 (i-13’s / is real division), 7/8 trips the resize; doubling gives 7/16:

$ i13 run hs_loadfactor.i13 RUN OK · 24 step(s) · peak stack 2 load = 0.875 need_resize = 1 -- > 0.75 newm = 16 newload = 0.4375 resized_below = 1

Recommend as a NULL — arithmetic (B40) + amortized cost. α is a resource ratio and the resize is a performance policy; the stored map is unchanged by when you double. A threshold choice, not a same-function invariant. NULL — how full is too full.