Visual walkthrough — Open addressing — linear probing, quadratic probing, double hashing

We assume nothing except: you can count, and you know what "a fraction" means. Every symbol is earned before it is used.

Step 1 — What is a "slot", a "key", and a "probe"?

WHAT. Picture a row of numbered boxes. Each box is a slot. A key is a number we want to store (like a house address we must file away). When we try to look inside one slot to check "empty or full?", that single act of looking is one probe.

WHY start here. The whole result is a count of probes. If we do not pin down exactly what one probe is, the number $\frac{1}{1-\alpha }$ is meaningless. A probe = one glance into one slot.

PICTURE. Below, a row of $m=8$ boxes. Green boxes are empty, filled boxes hold keys. The red pointer is doing one probe — one glance.

Step 2 — What is the load factor $\alpha$?

WHAT. Suppose $n$ of the $m$ boxes are already full. The fraction of full boxes is $\alpha =\underset{\text{full boxes}÷\text{total boxes}}{\underbrace{\frac{n}{m}}}.$

• $n$ = how many keys are stored right now,
• $m$ = how many slots exist in total,
• $\alpha$ (Greek letter "alpha") = the resulting fraction, always between $0$ and $1$.

WHY this quantity. When we drop a new key and its home is taken, we start glancing at other slots. The chance any one glance hits a full box is exactly the fraction of full boxes — which is $\alpha$. So $\alpha$ is literally "the probability one probe fails." That is the engine of the whole derivation.

PICTURE. Same row, now with $n=6$ full out of $m=8$, so $\alpha =6/8=0.75$. The shaded portion of the bar underneath is $\alpha$.

Step 3 — The "uniform hashing" idealisation

WHAT. We pretend that each probe lands on a fresh, independent, uniformly random slot — as if every glance were a new dice roll that ignores where we glanced before.

WHY pretend? Real probe sequences (linear, quadratic, double) are not truly random — but this idealisation is (a) simple enough to compute by hand, and (b) an excellent approximation for Double hashing-quality sequences. We choose randomness because independence is the one property that turns "count the probes" into a clean multiplication. Without independence, the probabilities would tangle together.

PICTURE. Two ways to think of a probe. Left: the true sequence follows a fixed path. Right: our model treats each probe as an independent coin/dice throw with $P(\text{full})=\alpha$.

Step 4 — The probability that we need more than $i$ probes

WHAT. We are doing an unsuccessful search: we probe until we finally land on an empty slot, then stop. Let $X$ be the number of probes this takes.

Because every search makes at least one glance (you must look at the home slot before you can know it is full), $X$ takes values in $\{1,2,3,\dots \}$ — never $0$. In particular before we start we are certainly "still going," so $P(X>0)=1$: this is the reason the $i=0$ term of our upcoming sum equals $1$.

We now ask: what is the chance $X$ is bigger than $i$ — i.e. the first $i$ probes were all full?

$P(X>i)=\underset{\text{probe 1 full}}{\underbrace{\alpha }}\times \underset{\text{probe 2 full}}{\underbrace{\alpha }}\times \cdots \times \underset{\text{probe }i\text{ full}}{\underbrace{\alpha }}={\alpha }^i.$

• $X$ = total probes until first empty slot (a random number in $\{1,2,3,\dots \}$),
• $P(X>i)$ = probability we are still going after $i$ probes,
• ${\alpha }^i$ = $\alpha$ multiplied by itself $i$ times (Step 3's independence made this legal); at $i=0$ the empty product is ${\alpha }^0=1$, matching $P(X>0)=1$.

WHY this exact event. "More than $i$ probes needed" happens precisely when the first $i$ slots we glanced at were all occupied — because the moment we hit an empty one we stop. Each of those $i$ glances is full with probability $\alpha$, independently, so their product is ${\alpha }^i$.

PICTURE. A shrinking staircase: at $i=0$ we are certainly still going (height $1$); after 1 probe, height $\alpha$; after 2, height ${\alpha }^2$. Each step is the previous times $\alpha$.

Step 5 — Turning "survive past $i$" into the average count

WHAT. We want the expected value $E[X]$ — the long-run average number of probes. For a random variable $X$ taking values in $\{1,2,3,\dots \}$ there is a clean identity: $E[X]={\sum }_{i=0}^{\infty }P(X>i).$

• $E[X]$ = the average of $X$ over many searches,
• ${\sum }_{i=0}^{\infty }$ = "add up the following for $i=0,1,2,3,\dots$ forever,"
• $P(X>i)$ = the survival probability from Step 4 (the $i=0$ term is $P(X>0)=1$).

WHY this identity holds — a two-line proof. Every positive whole value $X$ can be written as a stack of $1$'s: $X=\underset{X\text{ times}}{\underbrace{1+1+\cdots +1}}={\sum }_{i=0}^{\infty }1[X>i]$, where $1[X>i]$ is $1$ when $X$ is still bigger than $i$ and $0$ once we have counted past it. Take the average (expected value) of both sides; averaging is additive, so it slides inside the sum, and the average of an indicator is just the probability of its event: $E[1[X>i]]=P(X>i)$. Hence $E[X]={\sum }_{i=0}^{\infty }E[1[X>i]]={\sum }_{i=0}^{\infty }P(X>i).$ That is the whole justification — no calculus, just "a number is a stack of ones."

WHY not just $\sum i\cdot P(X=i)$? That definition also works, but it forces us to know each individual $P(X=i)$. The tail-sum instead reuses the survival probabilities ${\alpha }^i$ we already have from Step 4, so it is the shorter road.

PICTURE. The staircase area sliced two ways. Vertical slices = $\sum iP(X=i)$; horizontal slices = ${\sum }_{i}P(X>i)$. Same shaded area, easier arithmetic on the right.

Step 6 — Summing the geometric tower

WHAT. Substitute $P(X>i)={\alpha }^i$ into the tail-sum: $E[X]={\sum }_{i=0}^{\infty }{\alpha }^i=1+\alpha +{\alpha }^2+{\alpha }^3+\cdots .$ This is a geometric series — each term is the one before it times the same ratio $\alpha$. Its closed value (for $0\le \alpha <1$) is $1+\alpha +{\alpha }^2+\cdots =\frac{1}{1-\alpha }.$

• the left side = infinite sum of shrinking pieces,
• $\frac{1}{1-\alpha }$ = its finite total, because the pieces shrink fast enough to converge.

WHY it collapses. Call the sum $S$. Multiply by $\alpha$: $\alpha S=\alpha +{\alpha }^2+{\alpha }^3+\cdots$. Subtract: $S-\alpha S=1$ (everything cancels except the leading $1$). So $S(1-\alpha )=1$, giving $S=\frac{1}{1-\alpha }$. We use this trick because it needs no calculus — just careful cancellation.

PICTURE. Nested bars: a full bar of length $1$, then a piece $\alpha$, then ${\alpha }^2$… glued end to end they fill a total length $\frac{1}{1-\alpha }$, marked by the dashed line.

Step 7 — Reading the curve (and the two edge cases)

WHAT. Plot $\frac{1}{1-\alpha }$ against $\alpha$ and check the endpoints.

• Empty table, $\alpha =0$: $\frac{1}{1-0}=1$. Exactly one probe — your home slot is always free. ✅ sanity check passes.
• Half full, $\alpha =0.5$: $\frac{1}{0.5}=2$ probes on average.
• Ninety percent, $\alpha =0.9$: $\frac{1}{0.1}=10$ probes.
• Approaching full, $\alpha \to 1^{-}$: the denominator $1-\alpha \to 0^{+}$, so $\frac{1}{1-\alpha }\to \infty$. The cost explodes.

WHY the two edges matter. The $\alpha =0$ case proves our formula is not nonsense (it must cost one probe). The $\alpha \to 1$ blow-up is the reason we rehash: see Load factor and rehashing. We never let the table crawl toward full.

PICTURE. The curve stays gentle until about $\alpha =0.7$, then rockets skyward — a "hockey stick." The dots mark $0,0.5,0.9$.

The one-picture summary

Everything above in a single frame: a probe glance (with fail-chance $\alpha$) feeds the survival tower ${\alpha }^i$, whose tail-sum stacks into the geometric bar of total length $\frac{1}{1-\alpha }$, which finally traces the hockey-stick curve.