Why does a hash table need to grow before it is completely full?

A hash table is grown early because the quantity that sets lookup cost is the ratio of items to positions, not the number of positions. Left to fill, lookups stop being lookups and become scans: a table at ninety per cent full examines about twenty times as many slots per lookup as the same table at half full, and it still has a tenth of its positions free.

Write $x$ for the fullness, the number of items divided by the number of positions. In an open-addressed table, where a collision means stepping along to the next free position, the number of slots examined by a search that finds nothing averages $\frac{1}{2}\left(1 + \frac{1}{(1-x)^2}\right)$. Plug in values. At $x = 0.5$ the term $1 - x$ is $0.5$, its square is $0.25$, and $1/0.25 = 4$, so the average is $(1+4)/2 = 2.5$ slots. At $x = 0.75$ the same arithmetic gives $1 - 0.75 = 0.25$, squared $0.0625$, reciprocal $16$, and $(1+16)/2 = 8.5$ slots. At $x = 0.9$ it gives $0.01$, reciprocal $100$, and $(1+100)/2 = 50.5$. At $x = 0.95$: $0.0025$, reciprocal $400$, average $200.5$. At $x = 0.99$: $0.0001$, reciprocal $10{,}000$, average $5000.5$. Nothing in that expression is the number of positions.

Start at 8 positions with a threshold of two thirds. The sixth insertion takes fullness from $5/8 = 0.63$ to $6/8 = 0.75$, past the threshold, so a table of 16 positions is allocated and all 6 keys are put into it: 6 moves. The eleventh insertion gives $11/16 = 0.69$, past it again, so 32 positions and 11 moves. The twenty-second gives $22/32 = 0.69$, so 64 positions and 22 moves. Across the whole history, 22 insertions caused $6 + 11 + 22 = 39$ moves, which is $39/22 = 1.77$ moves per item.

The sum stays small because of the doubling: reading backwards from a final size of $n$, each earlier rebuild moved half as many items as the one after it, and that series adds to less than twice the last term. So the rebuilding work, spread over all the insertions, is under two moves each, and the cost per insertion keeps its fixed bound. Growing by a fixed hundred positions instead gives a different series. With the same two thirds threshold, the table rebuilds at sizes 100, 200, 300 and up, and the rebuild at size $100k$ moves $\frac{2}{3}(100k)$ items. Reaching 100,000 keys means $K = 1000$ rebuilds, so the total is $\frac{2}{3}(100)(1 + 2 + \cdots + 1000) = \frac{2}{3}(100)(500{,}500) = 33{,}366{,}667$ moves, which is 334 moves per inserted key. The same table stopping at 1000 keys moves $\frac{2}{3}(100)(55) = 3667$ items, or 3.7 per key, so the per-item cost is growing with the table rather than standing still.

All of this counts on the hash spreading keys evenly. If it does not, fullness is a fiction: a table that is thirty per cent full with every key in one cluster behaves like a linked list of length $0.3m$ whatever the ratio says, and no threshold saves it. The average is also not the worst case. The single insertion that crosses the threshold pays for moving every item present, and at ten million keys that pause is visible in a latency measurement even though the average insertion is cheap; systems with deadlines rehash a little at a time instead of all at once. And the threshold can be set too low as easily as too high: at one third full the probing formula gives $(1 + 1/(4/9))/2 = 1.625$ slots against 5 at two thirds, a saving of about three slots for twice the memory.