Load factor — when to resize, rehashing cost: Worked examples

This page hammers the load-factor and rehashing ideas from the parent note through every case that can appear. Before each answer you'll see a Forecast: line — pause and guess the number first. Guessing then checking is how the ideas stick.

Everything here uses only three symbols from the parent:

$n$ = number of keys currently stored.
$m$ = number of buckets (slots) the table has.
$α = n / m$ = the load factor (how full the table is).

One more piece of notation we will need in Ex 5:

Two flavours of "search cost" appear throughout:

Unsuccessful search — the key is not present; you scan/probe until you prove it's absent.
Successful search — the key is present; you stop as soon as you find it, so on average you do a little less work.

If any of those feel shaky, reread the parent and the prerequisites Separate Chaining, Open Addressing, Amortized Analysis, and Dynamic Arrays first.

The scenario matrix

Every question this topic can throw at you falls into one of these case classes. The worked examples below are labelled with the cell they cover, and together they hit all of them.

#	Case class	What makes it tricky	Covered by
A	Chaining, normal $α$ ( $0 < α \leq 1$ )	cost is $1 + α$ , linear and gentle	Ex 1
B	Open addressing, normal $α$ ( $α < 0.7$ )	cost is $1/ (1 - α)$ , still tame	Ex 2
C	Open addressing, the cliff ( $α \to 1$ )	cost explodes — the danger zone	Ex 3
D	Degenerate: $α = 0$ (empty table)	limiting value, formulas must not break	Ex 4
E	Degenerate: $α = 1$ in open addressing (full)	division by zero — undefined, table is full	Ex 4
F	Amortized doubling — count total rehash work	geometric series $\leq 2 n$	Ex 5
G	The wrong growth (additive) — why it's $O (n^{2})$	contrast case, catastrophe	Ex 6
H	Word problem: pre-sizing for a target $α$	pick $m$ from $n$ and $α_{m a x}$	Ex 7
I	Exam twist: hysteresis / thrashing	grow↔shrink near one boundary	Ex 8
J	Chaining vs open addressing at same $α$	why they resize at different points	Ex 9
K	Successful vs unsuccessful search	successful is a bit cheaper — a symmetric case	Ex 10
L	Chaining overload $α > 1$	more keys than buckets; $1 + α$ still holds	Ex 11

Worked example Ex 1 — Case A: chaining at a normal load factor

A chained hash table (see Separate Chaining) holds $n = 600$ keys in $m = 800$ buckets. Under simple uniform hashing, what is the expected cost of an unsuccessful search?

Forecast: guess — is it closer to 1, or closer to 4?

Compute $α$ . $α = n / m = 600/800 = 0.75$ . Why this step? The whole cost formula is written in terms of $α$ , so we always find it first.
Apply the chaining cost. Expected search $= 1 + α = 1 + 0.75 = 1.75$ . Why this step? In chaining, an unsuccessful search scans an entire chain whose expected length is exactly $α$ (each of the $n$ keys lands in your bucket with probability $1/ m$ , giving $n / m = α$ expected neighbours), plus the constant $1$ for the hash-and-index step.

Verify: $1.75$ is barely above $1$ — chaining stays gentle even at $α = 0.75$ . Units: a "cost" here counts slots/nodes touched, a pure number. Sanity: at $α = 0$ this would give $1$ (just the hash, empty chain), which is correct.

Worked example Ex 2 — Case B: open addressing, comfortable zone

An open-addressing table (see Open Addressing) has $m = 1000$ slots with $n = 500$ occupied. Expected probes for an unsuccessful search, under idealised uniform hashing?

Forecast: more or fewer probes than the chaining answer of Ex 1?

Compute $α$ . $α = 500/1000 = 0.5$ . Why this step? Same first move — the formula needs $α$ .
Apply the open-addressing bound. $E [probes] \leq \frac{1}{1 - α} = \frac{1}{1 - 0.5} = 2$ . Why this step? An unsuccessful search keeps probing until it hits an empty slot. Probe 1 always happens; you need probe $i$ only if the previous $i - 1$ slots were all full (probability $\approx α^{i - 1}$ , which relies on uniform hashing so each probe is an independent fresh slot). Summing $1 + α + α^{2} + \dots$ gives the geometric total $\frac{1}{1 - α}$ . For a real scheme like linear probing the true cost is somewhat higher (see the caveat above), but this bound is the reference point.

Verify: $\frac{1}{1 - 0.5} = 2$ — with the lot half full, you expect to look at 2 slots. Sanity: fewer than Ex 1's chaining? No — comparable. That's fine; the real gap appears near $α \to 1$ (next example).

Worked example Ex 3 — Case C: open addressing on the cliff

The same table now has $n = 990$ of its $m = 1000$ slots filled. Expected unsuccessful probes (idealised uniform hashing)?

Forecast: you doubled-then-doubled the fullness vs Ex 2 — did the cost roughly double, or blow up?

Compute $α$ . $α = 990/1000 = 0.99$ .
Apply the bound. $\frac{1}{1 - 0.99} = \frac{1}{0.01} = 100$ . Why this step? As $α \to 1$ the denominator $1 - α \to 0$ , so the reciprocal explodes. This is the "cliff" the parent warned about. (Linear probing would be worse still, but the cliff is present in every scheme.)

Verify: going from $α = 0.5$ (2 probes) to $α = 0.99$ (100 probes) is a 50× jump for less than double the fullness. The figure below plots cost (vertical axis) against load factor $α$ (horizontal axis) for both strategies: the pale-yellow open-addressing curve $1/ (1 - α)$ is nearly flat until about $α = 0.7$ (dashed line), then rockets upward, while the chalk-blue chaining line $1 + α$ climbs gently. The two marked dots are our Ex 2 point (0.5, 2 probes) and this Ex 3 point (0.99, 100 probes). That vertical explosion is the reason open-addressing tables resize around $α \approx 0.7$ .

Worked example Ex 4 — Cases D & E: the degenerate endpoints

Evaluate both cost formulas at the two extreme load factors: $α = 0$ (empty) and $α = 1$ (full, open addressing).

Forecast: which one gives a finite number, and which one breaks?

$α = 0$ (Case D, empty table).
- Chaining: $1 + α = 1 + 0 = 1$ .
- Open addressing: $\frac{1}{1 - 0} = 1$ . Why this step? An empty table has no collisions, so any search touches exactly the one hashed slot — cost $1$ . Both formulas correctly reduce to $1$ .
$α = 1$ (Case E, open addressing full).
- $\frac{1}{1 - α} = \frac{1}{0}$ → undefined (diverges to $\infty$ ). Why this step? When every slot is full, an unsuccessful search never finds an empty slot — it probes forever. The formula honestly reports $\infty$ . This is why a well-designed open-addressing table must resize before $α$ reaches $1$ ; it is a hard wall, not a soft slowdown.

Verify: limiting behaviour matches intuition: empty ⇒ 1 probe; full ⇒ never terminates. Note chaining has no such wall — at $α = 1$ it costs $1 + 1 = 2$ , still finite, which is exactly why chaining tolerates higher $α$ (see Ex 11 for $α > 1$ ).

Worked example Ex 5 — Case F: total rehash work with doubling

Start with a dynamically resized table of size $m = 1$ , doubling whenever it overflows ( $α_{m a x} = 1$ ). You insert $n = 16$ keys. What is the total number of element-moves caused by rehashing?

Forecast: guess — is total moving work closer to $16$ , $32$ , or $256$ ?

List when rehashes fire. Sizes hit $1, 2, 4, 8, 16$ ; a rehash happens each time we double, moving all current elements. Moves at each doubling: $1, 2, 4, 8$ . Why this step? A rehash re-inserts every existing key. Recall from the definition above that a key's bucket index is $h (k) mod m$ (the hash value wrapped by the table size); when $m$ changes, that index changes, so the cost of a rehash equals the number of keys present at that moment.
Sum the geometric series. Total moves $= 1 + 2 + 4 + 8 = 15$ . Why this step? This is $2^{0} + 2^{1} + 2^{2} + 2^{3} = 2^{4} - 1 = 15$ . In general, letting $t$ be the exponent of the last (largest) doubling — here the last term is $8 = 2^{3}$ , so $t = 3$ — the identity is $1 + 2 + \dots + 2^{t} = 2^{t + 1} - 1$ . Plugging $t = 3$ gives $2^{4} - 1 = 15$ .
Amortize — add in the cheap inserts explicitly. Each of the $16$ keys also costs $1$ unit just to place itself (the "cheap" part of an insert), so cheap-insert work $= n = 16$ . Total work $=$ (cheap inserts) $+$ (rehash moves) $= 16 + 15 = 31$ . Since $15 < 2 n = 32$ , we can bound this as $total \leq n + 2 n = 3 n = 48$ ; either way the total is $Θ (n)$ . Divide across the $n = 16$ inserts: per insert $= \frac{31}{16} \approx 1.94 \leq \frac{3 n}{n} = 3 = O (1)$ . Why this step? The $\leq 3 n$ bound comes from adding the $n$ cheap inserts to the $\leq 2 n$ rehash moves; spreading the occasional $Θ (n)$ rehash over all $n$ inserts is exactly the Amortized Analysis argument.

Verify: rehash moves $15 \leq 2 \cdot 16 = 32$ ✓, and total $31 \leq 3 \cdot 16 = 48$ ✓, matching the parent's " $\leq 2 n$ moves, $\leq 3 n$ total" bounds. The figure below shows, on the horizontal axis each doubling event (size 1->2, 2->4, …) and on the vertical axis the number of moves: pink bars are the elements moved by each individual rehash ( $1, 2, 4, 8$ ), the yellow line is the running cumulative total ( $1, 3, 7, 15$ ), and the blue dashed line marks the bound $2 n = 32$ . The cumulative total stays under the bound — that is the picture of amortization.

Worked example Ex 6 — Case G: additive growth is a catastrophe

Instead of doubling, you grow by a fixed $c = 4$ slots each time the table fills. Exact rule: start at capacity $m = 4$ , empty. Insert one at a time; the instant an insert would exceed the current capacity (i.e. the table is full and a new key arrives), allocate $m + 4$ slots and move all present keys over. Inserting $n = 16$ keys, how many total moves does rehashing cost? Compare to Ex 5's doubling.

Forecast: bigger or smaller than doubling's $15$ ? By how much?

Find when each rehash fires. Capacity is $4$ . It fills after keys $1..4$ . Key $5$ overflows → grow $4 \to 8$ , moving the $4$ present keys. Keys $5..8$ fill it; key $9$ overflows → grow $8 \to 12$ , moving $8$ . Keys $9..12$ fill it; key $13$ overflows → grow $12 \to 16$ , moving $12$ . Keys $13..16$ fit exactly, no more growth. Why this step? Additive growth adds a constant $c = 4$ , so overflows recur at constant intervals — the exact opposite of doubling's exponentially rare overflows.
Sum the moves. Moves $= 4 + 8 + 12 = 24$ . Why this step? Each rehash moves all currently-present keys ( $4$ , then $8$ , then $12$ ); those counts grow linearly, so the sum is a triangular number $\approx n^{2} / (2 c)$ .
See the scaling. $\frac{n ^{2}}{2 c} = \frac{1 6 ^{2}}{2 \cdot 4} = 32$ (order of magnitude; exact count $24$ ). Amortized per insert $= Θ (n^{2}) / n = Θ (n)$ — linear, not constant. Why this step? This is why the parent forbids additive growth: the geometric series that saved us in Ex 5 becomes an arithmetic series here.

Verify: doubling gave $15$ moves; additive-4 gives $24$ for only $16$ keys — and the gap widens without bound as $n$ grows ( $n^{2}$ vs $n$ ). Multiplicative growth wins.

Worked example Ex 7 — Case H: pre-sizing a table (word problem)

A build tool will load a dictionary of $n = 30, 000$ symbols. You want the load factor to stay at $α \leq α_{m a x} = 0.75$ so lookups stay fast. What is the smallest number of buckets $m$ you should allocate up front, and what convenient value would you pick?

Forecast: roughly $30, 000$ , or noticeably more?

Rearrange $α = n / m \leq α_{m a x}$ for $m$ . $m \geq \frac{n}{α _{m a x}} = \frac{30000}{0.75} = 40000$ . Why this step? We know $n$ and the target $α_{m a x}$ ; the only unknown is $m$ , so solve the inequality for it.
Round up to a friendly size. The next power of two above $40000$ is $2^{16} = 65536$ ; a common choice is $m = 65536$ (or a prime near $40000$ if the hash prefers primes — see Hash Functions). Why this step? Powers of two allow fast mod by bit-masking; picking $m$ once up front avoids repeated rehashes during the bulk load.

Verify: at $m = 65536$ , $α = 30000/65536 \approx 0.458 \leq 0.75$ ✓. Even the tight minimum $m = 40000$ gives $α = 0.75$ exactly ✓. Pre-sizing means zero rehashes during load instead of $lo g_{2} (30000) \approx 15$ of them.

Worked example Ex 8 — Case I: exam twist on hysteresis

A table grows when $α > 0.75$ (doubling $m$ ) and shrinks when $α < 0.25$ (halving $m$ ). It currently has $m = 8$ , $n = 6$ . A user repeatedly does insert, delete, insert, delete, …. Does this cause $O (n)$ thrashing? What if the shrink threshold were $0.70$ instead?

Forecast: does the separated-threshold design thrash, or stay quiet?

Check the insert. After inserting, $n = 7$ , $α = 7/8 = 0.875 > 0.75$ → grow to $m = 16$ . Now $α = 7/16 \approx 0.44$ . Why this step? We must see whether a single operation can push $α$ across a resize boundary.
Check the following delete. After deleting, $n = 6$ , $α = 6/16 = 0.375$ . Is $0.375 < 0.25$ ? No → no shrink. Why this step? The whole point of a gap between grow (0.75) and shrink (0.25) is that landing after a grow (near 0.44) sits safely between the two thresholds, so the reverse op can't trigger a shrink.
Now the bad design ( $α_{shrink} = 0.70$ ). After growing, $α \approx 0.44 < 0.70$ → shrink back to $m = 8$ → next insert grows again → grow↔shrink thrash, $O (n)$ per op. Why this step? With thresholds too close, one insert/delete pair straddles both, rehashing every single operation.

Verify: separated thresholds (0.25 / 0.75) leave a "dead zone" ⇒ no thrash ✓; near-touching thresholds (0.70 / 0.75) ⇒ thrash ✓. The lesson: keep a wide hysteresis gap.

Worked example Ex 9 — Case J: chaining vs open addressing at the same

$α$ At $α = 0.9$ , compare the expected unsuccessful-search cost of a chained table versus an (idealised) open-addressing table. Why does this comparison justify their different resize thresholds?

Forecast: at the same fullness $0.9$ , are they close, or wildly apart?

Chaining cost. $1 + α = 1 + 0.9 = 1.9$ .
Open-addressing cost. $\frac{1}{1 - α} = \frac{1}{0.1} = 10$ . Why this step? Same $α$ , two different growth laws: chaining grows linearly in $α$ , open addressing grows like $\frac{1}{1 - α}$ which blows up.
Interpret. At $α = 0.9$ open addressing is already $\approx 5 \times$ slower and heading for the cliff; chaining is barely above 1. Hence chaining resizes near $α \approx 1$ while open addressing resizes near $α \approx 0.7$ . Why this step? The resize threshold is chosen where each cost curve is still cheap — and those points differ because the curves differ.

Verify: ratio $10/1.9 \approx 5.3 \times$ ✓. This matches the parent's "open addressing resizes earlier" rule.

Worked example Ex 10 — Case K: successful search is a little cheaper

Now the symmetric case. At $α = 0.5$ , compare the expected cost of a successful search to the unsuccessful one, for both strategies.

Forecast: successful search — more work, less work, or the same as unsuccessful?

Chaining, unsuccessful vs successful. Unsuccessful scans the whole chain: $1 + α = 1 + 0.5 = 1.5$ . Successful stops at the found key, so on average it scans only half the preceding chain: $1 + \frac{α}{2} = 1 + 0.25 = 1.25$ . Why this step? When the key is present you stop early — expected position within a chain of length $α$ is about $α /2$ , so you do half the extra scanning.
Open addressing, unsuccessful vs successful. Unsuccessful: $\frac{1}{1 - α} = \frac{1}{0.5} = 2$ . Successful: $\frac{1}{α} ln \frac{1}{1 - α} = \frac{1}{0.5} ln 2 = 2 ln 2 \approx 1.386$ . Why this step? A successful probe sequence, averaged over all inserted keys, is shorter than the worst unsuccessful one because early-inserted keys sat in an emptier table; the average works out to $\frac{1}{α} ln \frac{1}{1 - α}$ (again under idealised uniform hashing).

Verify: in both strategies successful < unsuccessful ( $1.25 < 1.5$ and $1.386 < 2$ ) ✓, matching intuition that finding what you seek ends the search sooner. Both reduce to $1$ at $α = 0$ (empty), as they must.

Worked example Ex 11 — Case L: chaining overload,

$α > 1$ A chained table has $n = 2400$ keys but only $m = 800$ buckets — more keys than buckets, so $α > 1$ . What is the expected unsuccessful-search cost, and does the formula still hold?

Forecast: can $α$ even exceed $1$ ? If so, what's the cost?

Compute $α$ . $α = 2400/800 = 3$ . Why this step? Unlike open addressing (which is physically capped at $α < 1$ — one key per slot), chaining stores a whole linked list per bucket, so many keys can share a bucket and $α$ can grow past $1$ freely.
Apply the same formula. Expected unsuccessful search $= 1 + α = 1 + 3 = 4$ . Why this step? The derivation ( $α$ = average chain length) never assumed $α \leq 1$ ; it holds for any non-negative $α$ . With $3$ keys per bucket on average, you walk about $3$ nodes plus the $1$ hash step.

Verify: $1 + 3 = 4$ nodes touched — finite and gentle even though the table is "overloaded" $3 \times$ . Contrast Ex 4 Case E: open addressing at $α = 1$ is already broken, but chaining at $α = 3$ is merely a bit slower. This is precisely why chaining can survive $α > 1$ while open addressing cannot.

Recall Quick self-test (reveal after guessing)

Chaining at $α = 0.75$ , expected unsuccessful search cost? ::: $1 + 0.75 = 1.75$ . Open addressing at $α = 0.5$ , expected probes (idealised)? ::: $1/ (1 - 0.5) = 2$ . Open addressing at $α = 0.99$ , expected probes (idealised)? ::: $1/ (1 - 0.99) = 100$ . Both formulas at $α = 0$ ? ::: Both give $1$ . Open-addressing formula at $α = 1$ ? ::: Undefined / $\infty$ (table full, search never terminates). What does $α_{m a x}$ mean (vs $α$ )? ::: $α_{m a x}$ is the chosen policy threshold we refuse to exceed; $α$ is the table's actual current fullness. Total rehash moves inserting 16 keys with doubling from size 1? ::: $1 + 2 + 4 + 8 = 15$ . Total work (cheap inserts + rehash) for those 16 keys? ::: $16 + 15 = 31 \leq 3 n = 48$ . Additive-4 growth (start capacity 4), total moves for 16 keys? ::: $4 + 8 + 12 = 24$ , scaling as $Θ (n^{2})$ . Minimum $m$ for 30000 keys at $α \leq 0.75$ ? ::: $m \geq 40000$ . Chaining vs open addressing at $α = 0.9$ (unsuccessful)? ::: $1.9$ vs $10$ . Chaining successful search at $α = 0.5$ ? ::: $1 + α /2 = 1.25$ . Open-addressing successful search at $α = 0.5$ ? ::: $2 ln 2 \approx 1.386$ . Why is $1/ (1 - α)$ only an idealised bound? ::: It assumes uniform hashing; real schemes like linear probing cluster and cost more. Chaining at $α = 3$ (overloaded), expected unsuccessful cost? ::: $1 + 3 = 4$ ; the formula $1 + α$ holds for $α > 1$ .