Visual walkthrough — Hash table — structure, open addressing vs chaining

We use only these facts from the parent, restated in plain words below as we need them. Related ideas: Load factor and dynamic resizing / rehashing, Hash functions — properties and design, Amortized analysis.

---

Step 1 — Draw the table and name every symbol

WHAT. A hash table in open addressing is just one flat array of $m$ boxes. Some boxes hold a key, some are empty. Let $n$ be how many boxes are filled.

WHY start here. Every symbol we will ever use ($\alpha$, "probe", "occupied") lives on this one picture. If we don't anchor them to boxes now, the algebra later is meaningless noise.

PICTURE. Look at the row of boxes. Filled boxes are burnt-orange, empty boxes are cream.

Read the fraction out loud: "six of the ten boxes are full." That single number $\alpha$ is the load factor. Nothing else about the table will matter for the average — not which boxes are full, only how many. Note already that $\alpha$ is a fraction between $0$ and $1$ (you cannot fill more boxes than exist) — we will lean on $\alpha <1$ hard later.

---

Step 2 — What "a probe" actually is, and what "unsuccessful search" means

WHAT. A probe = one act of looking inside one box and asking "is this box empty?". An unsuccessful search = we are looking for a key that is not in the table, and we keep probing boxes along a sequence until we hit an empty box — an empty box is the signal "stop, it's not here."

WHY this matters. We are counting unsuccessful searches on purpose: they are the worst honest case (the key genuinely isn't there), and they are the cleanest to analyse because the stopping rule is exactly "hit the first empty box." The number of probes = however many occupied boxes we pass through, plus one final empty box that stops us.

PICTURE. Follow the teal arrow hopping box to box: full, full, full, then EMPTY → stop. That was 4 probes (3 occupied + 1 empty).

---

Step 3 — The one modelling assumption, drawn honestly

WHAT. We assume uniform hashing: the probe sequence of our searched-for key is equally likely to visit the boxes in any order — so each box we look at is, before we look, "just a random box." That means: $P(\text{a probed box is occupied})=\frac{\text{occupied boxes}}{\text{total boxes}}=\frac{n}{m}=\alpha .$

WHY this tool (probability, not exact counting). We cannot know in advance which boxes are full — the table depends on the whole history of inserts. So instead of tracking exact positions, we ask: what fraction of the time is a box full? That fraction is $\alpha$. Probability is the right tool precisely because it lets us replace "unknown specific arrangement" with "known average fraction."

PICTURE. $P$ means "the fraction of times this happens if you tried it many times." Here the burnt-orange slice of the bar is $\alpha$; the cream slice is $1-\alpha$ (the chance of hitting empty and stopping).

So: each box we probe is occupied with chance $\alpha$, and empty (stop!) with chance $1-\alpha$.

---

Step 4 — Turn "keep going" into a chain of chances

WHAT. For our search to still be going after $k$ boxes, the first $k$ boxes we looked at must all have been occupied. Under our assumption each is occupied with chance $\alpha$, and — as an idealisation — independently, so: $P(\text{still probing after passing }k\text{ boxes})=\underset{k\text{ times}}{\underbrace{\alpha \cdot \alpha \cdots \alpha }}={\alpha }^k.$

WHY multiply. "The 1st box is full AND the 2nd is full AND ..." — chained ANDs of independent chances multiply. Each extra full box you demand makes the whole event rarer, which is why ${\alpha }^k$ shrinks as $k$ grows (since $\alpha <1$).

PICTURE. A shrinking staircase: the bar for "having to make probe number 1" is full height $1$; "having to make probe number 2" is $\alpha$; "having to make probe number 3" is ${\alpha }^2$; each step multiplies by $\alpha$, so the bars fade toward zero.

---

Step 5 — Add up all the probes: a geometric sum appears

WHAT. First, one new symbol.

Now we prove the identity we need — why the average equals the sum of "chance each probe happens." We build the total probe count out of tiny yes/no counters.

Two facts glue the derivation together:

1. Total probes = sum of the switches. Every probe that happens flips exactly one switch to $1$, so $\#\text{probes}=X_1+X_2+X_3+\cdots$
2. The average of a $0/1$ switch is its chance of being $1$. If $X_j$ is $1$ a fraction $P(\text{probe }j\text{ happens})$ of the time and $0$ otherwise, its long-run average is exactly that fraction: $E[X_j]=1\cdot P(\text{probe }j)+0\cdot P(\text{not})=P(\text{probe }j\text{ happens}).$

WHY we may add the averages (linearity of expectation). The average of a sum is the sum of the averages — always, even when the switches are tangled up with each other (this needs no independence). So: $E[\#\text{probes}]=E[X_1+X_2+\cdots ]=E[X_1]+E[X_2]+\cdots ={\sum }_{j=1}^{\infty }P(\text{probe }j\text{ happens}).$

From Step 4, probe number $j$ happens exactly when the previous $j-1$ boxes were all full, which has chance ${\alpha }^{j-1}$. Substituting $j=1,2,3,\dots$ gives exponents $0,1,2,\dots$:

$E[\text{probes}]={\sum }_{j=1}^{\infty }P(\text{probe number }j\text{ happens})={\sum }_{j=1}^{\infty }{\alpha }^{j-1}=1+\alpha +{\alpha }^2+{\alpha }^3+\cdots$

WHY this shape. Reading term by term (note: term for probe $j$ carries exponent $j-1$):

• The $1={\alpha }^0$ ::: probe number 1 always happens — we always look at least once. Chance $1$.
• The $\alpha ={\alpha }^1$ ::: probe number 2 happens only if box 1 was full — chance $\alpha$.
• The ${\alpha }^2$ ::: probe number 3 happens only if boxes 1 and 2 were full — chance ${\alpha }^2$.
• ...and so on forever.

PICTURE. Stack the fading bars from Step 4 end to end. Their total length is the expected probe count. Because each bar is $\alpha$ times the previous, this is a geometric series — a sum where each term is a fixed multiple of the one before.

---

Step 6 — Collapse the infinite sum to a single fraction

WHAT. We prove the closed form of the geometric series, valid because $\alpha <1$. Call the sum $S$: $S=1+\alpha +{\alpha }^2+{\alpha }^3+\cdots$ Multiply every term by $\alpha$: $\alpha S=\alpha +{\alpha }^2+{\alpha }^3+\cdots$ Subtract the second line from the first. Every term on the right cancels except the lonely $1$: $S-\alpha S=1⟹S(1-\alpha )=1⟹\boxed{S=\frac{1}{1-\alpha }}$

WHY the subtract trick. The two lines are almost identical — the second is the first shifted one term to the right. Subtracting annihilates the entire infinite tail and leaves one clean equation. This is why we don't need to add infinitely many things by hand. (This cancellation only makes sense because the tail is finite, i.e. $\alpha <1$.)

PICTURE. Two nearly-identical stacks side by side; subtract, watch the tall matching towers vanish, and only the single unit block $1$ survives.

---

Step 7 — Every case: plug in the extremes

WHAT. Now sweep $\alpha$ across its whole range and check the formula against common sense.

$\alpha$ (fraction full)	$\frac{1}{1-\alpha }$	Sanity check
$0$ (empty table)	$1$	First box is always empty → stop instantly. ✓
$0.5$ (half full)	$2$	Half the boxes empty → ~2 tries to hit one. ✓
$0.7$ (rehash threshold)	$\approx 3.33$	Still cheap — this is why we rehash near here. ✓
$0.9$ (crowded)	$10$	1 empty per 10 boxes → ~10 tries. ✓
$\to 1^{-}$ (nearly full)	$\to \infty$	Almost no empty boxes to find → search never stops. ✓

WHY check the extremes. A formula you can't test at its boundaries is a formula you don't trust. The two endpoints — empty table ($\alpha =0$) and full table ($\alpha =1$) — are exactly the degenerate cases the parent warns about.

PICTURE. The curve $y=\frac{1}{1-\alpha }$ from $\alpha =0$ to $\alpha =1$. It hugs $y=1$ on the left, then rockets up as a vertical wall at $\alpha =1$ — the "table full = infinity" cliff.

---

The one-picture summary

WHAT. Everything, on one canvas: probe boxes → each full with chance $\alpha$ → survival ${\alpha }^k$ → geometric stack → collapses to $\frac{1}{1-\alpha }$ → which explodes at $\alpha =1$.

Recall Feynman retelling — the whole walkthrough in plain words

You're looking for a book that isn't on a shelf of numbered slots. You check slots one by one; the moment you hit an empty slot you know the book was never here and you stop.

How many slots do you check? Every full slot you pass is a slot that didn't stop you. If a fraction $\alpha$ of slots are full, then each slot you check is full "$\alpha$ of the time" and empty "$1-\alpha$ of the time." To be forced into probe number $j$, all $j-1$ slots before it had to be full — chance $\alpha \times \alpha \times \cdots ={\alpha }^{j-1}$, a number that shrinks fast (because $\alpha <1$).

Now add up how often each probe happens. A neat trick: give each probe a tiny on/off counter, note the average of an on/off counter is just its chance of being on, and averages of sums always add up. That turns the average probe count into $1+\alpha +{\alpha }^2+\cdots$. This is a shrinking staircase; write it twice, one copy nudged over by one, subtract, and the whole endless tail cancels, leaving $\frac{1}{1-\alpha }$.

Read that answer like a landlord: if only a fraction $1-\alpha$ of slots are empty, you'll wade through about $\frac{1}{1-\alpha }$ slots before finding an empty one. Half empty → 2 tries. One-tenth empty → 10 tries. Zero empty → you never stop. That last cliff is exactly why we rent a bigger array (rehash) long before the table fills up.