Visual walkthrough — Load factor — when to resize, rehashing cost

This is the deep-dive companion to the parent note. If a word here feels new, we define it before we use it. Prerequisite ideas live at Hashing, Dynamic Arrays, and Amortized Analysis.

Step 1 — What a hash table is, as a picture

WHAT. A hash table is a row of numbered boxes. We call each box a bucket. The number of buckets is $m$ (think "$m$ = mailboxes"). The number of keys we have actually stored is $n$ (think "$n$ = number of things"). A key is just a thing we want to remember — a name, a number, a word.

WHY start here. Every symbol on this page is one of $m$, $n$, or built from them. If we don't picture the boxes first, the algebra later is meaningless.

PICTURE. Below, the row of white boxes is the table. $m=8$ boxes exist; $n=3$ of them hold an amber key. The rest are empty.

Step 2 — The load factor $\alpha$: how full the row is

WHAT. We define one number that measures "how crowded": $\alpha =\underset{\text{keys stored}}{\underbrace{n}}/\underset{\text{boxes available}}{\underbrace{m}}$ The symbol $\alpha$ (Greek letter "alpha") is just a name for the ratio $n/m$. We earn it here: from now on $\alpha$ always means "filled boxes divided by all boxes."

WHY this ratio and not, say, $n$ alone? Because crowdedness is relative. Three keys in 8 boxes ($\alpha =3/8=0.375$) is roomy; three keys in 4 boxes ($\alpha =0.75$) is tight. Only the ratio captures the feeling of "getting full," which is exactly what will trigger our resize.

PICTURE. Same 8 boxes as before but shaded by how full the row is. The fill bar underneath reads $\alpha =3/8$.

Step 3 — The trigger: when $\alpha$ crosses the threshold, we resize

WHAT. We pick a ceiling for crowdedness, called the max load factor ${\alpha }_{\max }$ (for this walkthrough ${\alpha }_{\max }=1$, the simplest case; real tables use $0.75$). After each insert we check: is $\alpha >{\alpha }_{\max }$? If yes, we build a bigger table.

WHY a threshold at all? In Separate Chaining the expected work per lookup is $O(1+\alpha )$, and in Open Addressing it is about $1/(1-\alpha )$ — both grow with $\alpha$. Keeping $\alpha$ under a fixed ceiling keeps those costs constant. The threshold is the promise that keeps lookups fast.

PICTURE. A gauge: below ${\alpha }_{\max }$ we are in the green "insert normally" zone; the instant we cross it, the needle points to the amber "REBUILD" zone.

Step 4 — Rehashing: why we can't just copy the boxes

WHAT. When we make a bigger table of size $m^{\prime }$, a key $k$ does not stay in the same box number. Its box is computed as $h(k)\mathrm{mod}m$ (see Hash Functions) — the raw hash number wrapped around to fit in $m$ boxes. Change $m$ to $m^{\prime }$ and the wrap changes, so the box changes. Moving every key into its new box is called rehashing.

WHY it costs $\Theta (n)$. There are $n$ keys, and each one must be recomputed and re-placed. That's $n$ pieces of work — linear in the number of stored keys. One insert that triggers this suddenly does $n$ units of work instead of $1$. That is the "scary" step we must tame.

PICTURE. Left: old table of $m=4$, key with $h(k)=13$ sits in box $13\mathrm{mod}4=1$. Right: new table $m^{\prime }=8$, same key now lands in box $13\mathrm{mod}8=5$. The amber arrow shows it moved.

Step 5 — The worry, drawn as a spike

WHAT. Let's plot the cost of each individual insert as we insert one key at a time. Most inserts cost $1$ (drop a key in an empty box). But the inserts that trigger a rehash spike up to the current $n$.

WHY draw it. The picture makes the puzzle vivid: if some inserts cost $n$, how can we ever call this table "$O(1)$ per insert"? The answer is Step 6.

PICTURE. A bar chart of per-insert cost. Flat little bars of height $1$, punctuated by tall amber spikes at inserts $2,3,5,9,\dots$ — exactly the powers of two, where a rehash fires.

Step 6 — Add up ALL the spikes (the key trick)

WHAT. Instead of asking "how bad is one spike?", we add up the total moving work across all $n$ inserts. When we double from size $1$, the rehashes move $1$, then $2$, then $4$, then $8$, … keys — up to $n$. Summing: $\text{Total moves}=\underset{1\to 2}{\underbrace{1}}+\underset{2\to 4}{\underbrace{2}}+\underset{4\to 8}{\underbrace{4}}+\cdots +\underset{\frac{n}{2}\to n}{\underbrace{n}}$

WHY sum instead of max? This is the heart of Amortized Analysis: a cost that is huge once in a while can be cheap on average. To see the average we need the total, then divide by the number of inserts.

PICTURE. Stack the spike heights as nested bars — a staircase where each step is double the one before. The tallest step ($n$) is bigger than all the shorter steps put together. That single visual fact is the whole proof.

Step 7 — Collapse the sum with the geometric series

WHAT. The stacked bars are a geometric series: each term is $2\times$ the last, and the ratio $2$ is fixed. The closed form is $1+2+4+\cdots +n={\sum }_{k=0}^t{2}^k=2^{t+1}-1=2n-1,$ where $t$ is the number of doublings and $2^t=n$. Each symbol: $2^k$ is the keys moved on the $k$-th rehash; the sum runs over every rehash; $2n-1$ is the grand total.

WHY a geometric series is the right tool. We chose to grow by a constant multiplier ($\times 2$). Multiplying by a fixed ratio each time is the exact definition of a geometric progression — so its sum is exactly the geometric closed form $2^{t+1}-1$. No other summation formula applies to "double each time"; this is the tool for "repeated multiplication."

PICTURE. The staircase from Step 6 slotted inside a single box of height $2n$: the whole series just fits, with the top-left corner ($-1$) missing.

Step 8 — The degenerate case: additive growth is a catastrophe

WHAT. Suppose instead of doubling we grow by a fixed amount $c$ (say $+100$) each overflow. Then we rehash every $c$ inserts, moving $c,2c,3c,\dots$ keys. Summing: $c+2c+3c+\cdots =c(1+2+3+\cdots +\frac{n}{c})\approx c\cdot \frac{(n/c{)}^2}{2}=\frac{n^2}{2c}=\Theta (n^2).$

WHY show this. A derivation isn't finished until we show what happens when the key choice (the $\times 2$) is broken. Here the terms grow linearly ($c,2c,3c,\dots$), not geometrically — so their sum is quadratic ($n^2$), and dividing by $n$ gives $O(n)$ per insert. That contrast is the entire reason doubling wins.

PICTURE. Two staircases side by side: doubling (bars race up, sum stays under a $2n$ lid) versus additive (bars climb one-by-one, their total balloons past the frame).

The one-picture summary

Everything above in a single frame: rare-but-tall rehash spikes, whose entire stacked area fits under a lid of height $2n$, so the average height per insert is a flat constant line.

Flashcards