Chaining — linked lists in buckets, load factor, resizing: Visual walkthrough

Step 1 — Draw the table and name every symbol

WHAT. A hash table is just an array of $m$ slots, numbered $0, 1, \dots, m - 1$ . Into it we have already dropped $n$ keys. Each key was sent to a slot by a rule called the hash function $h$ : feed it a key $k$ , it hands back a slot number $h (k)$ .

WHY start here. Before we can say "the search is fast," we must fix what we are counting. We are counting how many keys sit in the slot we land on — because a chained search walks exactly that slot's list, one node at a time.

PICTURE. Below: $m = 5$ slots (the boxes), $n = 8$ keys (the dots) already dropped in. The slot we will search — call it slot $i$ — is marked in red. The little tower of dots above it is the linked list we must walk.

Figure — Chaining — linked lists in buckets, load factor, resizing

Step 2 — The one assumption that makes counting possible

WHAT. We assume every key, when dropped, is equally likely to land in any of the $m$ boxes, and the keys don't influence each other. This is called Simple Uniform Hashing.

WHY this assumption and not another. Without some rule about where keys land, an enemy could throw all $n$ keys into one box and there'd be nothing to prove. "Equally likely, independent" is the cleanest statement of "a good hash spreads keys evenly" — it is exactly what Hash Functions tries to achieve in practice. It lets us treat each drop like rolling a fair $m$ -sided die.

PICTURE. One key facing $m$ boxes, each door the same width, each with the same chance $\frac{1}{m}$ written on it. The red door is slot $i$ — but it is no more likely than any other.

Step 3 — Turn "is it in the box?" into a number you can add

WHAT. For each key $k$ we invent a tiny counter that is $1$ if $k$ landed in box $i$ , and $0$ otherwise. Call it $X_{k}$ . This is an indicator variable — a switch that reports "yes/no" as " $1$ / $0$ ".

WHY do this. We want the total pile height in box $i$ . If every key waves a flag showing $1$ (I'm here) or $0$ (I'm not), then adding all the flags gives the pile height. Turning a yes/no question into a $1/0$ number is the trick that lets us use plain addition.

PICTURE. The eight keys, each carrying a flag: red flag $= 1$ (landed in box $i$ ), black flag $= 0$ (landed elsewhere). Summing the red flags = height of the red tower.

Step 4 — Add the switches to get the expected pile height

WHAT. Let $L_{i}$ = the length of box $i$ 's chain = the sum of all the switches. Take its average.

WHY. The pile height changes from run to run (randomness), so we ask for the average height. A beautiful rule — the average of a sum is the sum of the averages — lets us add the $n$ tiny averages instead of wrestling with the whole pile at once. This rule is called linearity of expectation, and its magic is that it does not require the switches to be independent: even if knowing one flag told you something about another, the average of their sum still equals the sum of their averages. So we may add them freely.

PICTURE. $n$ flags of value $\frac{1}{m}$ being poured into one bucket; the bucket's reading settles at $n \cdot \frac{1}{m}$ . That reading gets its own name: $α$ .

Step 5 — The unsuccessful search: walk the whole pile, plus one

WHAT. We search for a key $x$ that is not in the table. We compute $h (x)$ (one step), jump to that box, and scan the entire chain because $x$ is never found.

WHY "whole pile plus one". The " $+ 1$ " is unavoidable no matter what: you must compute the hash and touch one box even if it's empty. The " $α$ " is the average number of nodes you then flip through. Because $x$ is absent, you cannot stop early — you walk to the end.

PICTURE. A red pointer computing $h (x)$ (cost $1$ ), landing on a box, then stepping through every node of the chain (cost = its length, averaging $α$ ).

Step 6 — The successful search: count the nodes you pass before stopping

WHAT. Now $x$ is in the table. You do not scan the whole chain — you stop the instant you reach $x$ . The cost is $1$ (the hash) plus the number of nodes you touch up to and including $x$ . We now derive that number by counting, exactly as in Steps 3–4.

WHY count "who came before whom". Insertion prepends at the head, so a node sits in front of $x$ in its chain exactly when it was inserted after $x$ and hashed to the same box. So the nodes you must pass before reaching $x$ are precisely the keys added later that collided with $x$ . Counting those, key by key, is the whole job.

PICTURE. Chain drawn head-to-tail. $x$ glows red. Every node inserted after $x$ (the ones nearer the head) is shaded — those are the ones you step over. Nodes inserted before $x$ sit behind it and are never touched.

Step 7 — The edge cases: empty box, giant pile, and the adversary

WHAT. We must not leave a scenario undrawn. Three extremes:

Empty box ( $L_{i} = 0$ ): cost is just the $1$ — compute hash, find nothing, done.
Balanced table ( $α \leq$ constant, e.g. $0.75$ ): $1 + α$ is a constant → expected $O (1)$ . This is the whole reason chaining resizes to hold $α$ down.
Adversarial collapse (all $n$ keys in one box): the uniform assumption of Step 2 is violated; the pile is height $n$ , so a search is $O (n)$ . This is the true worst case.

WHY show all three. The formula $1 + α$ is an average under Step 2's assumption. When that assumption holds you get $O (1)$ ; when it is broken you get $O (n)$ . A reader must see both ends.

PICTURE. Three tables side by side: an empty red box (cost $1$ ), a short-and-even table ( $O (1)$ ), and one red skyscraper chain holding all $n$ keys ( $O (n)$ ).

The one-picture summary

Read it left to right: a key faces $m$ equal doors ( $Pr = \frac{1}{m}$ ) → $n$ keys pour in, so a box averages $α = n / m$ dots → a search pays $1$ to reach the box plus $α$ to walk it → total $1 + α$ . Keep $α$ small and that whole chain of pictures reads " $O (1)$ ".

Recall Feynman retelling — the whole walk in plain words

Picture a wall of $m$ mailboxes and $n$ letters. A fair rule scatters letters so each box has the same chance, $1/ m$ , of catching any given letter. Give every letter a flag: raise it if the letter landed in your box. Add the raised flags to get how tall the pile in your box is — since each letter raises its flag $1/ m$ of the time and there are $n$ letters, the average pile is $n / m$ , which we call the load factor $α$ . To find a letter you walk to its box (that costs $1$ ) and flip through the pile. If the letter isn't there you flip the whole pile ( $1 + α$ ). If it is there you stop when you reach it — on average after flipping only half the pile ( $1 + α /2$ ), because only the letters dropped in after it sit in front of it. If the box is empty you still paid $1$ . Only if a cheating rule dumps every letter in one box does the pile become $n$ tall and the search slow. That single "fair scatter" assumption is what turns a wall of mailboxes into a machine that answers in constant time.

Recall Predict then verify

Where does the " $1$ " in $1 + α$ come from? ::: Computing the hash and touching one box — paid even if the box is empty. Where does the " $α$ " come from? ::: Summing $n$ indicator switches, each averaging $1/ m$ , gives $n / m = α$ expected nodes to walk. In a successful search, why does the $\frac{α}{2}$ appear? ::: You only pass keys inserted after the target; averaging over targets turns the triangular sum $\frac{n ( n - 1 )}{2}$ into a half. Why is successful search also $O (1 + α)$ ? ::: Big-O ignores the constant $\frac{1}{2}$ , so $1 + \frac{α}{2} - \frac{α}{2 n}$ sits in the same class. Which step breaks in the worst case? ::: Step 2 (uniform hashing); an adversary makes one pile of height $n$ , giving $O (n)$ .

Connections

Chaining — linked lists in buckets, load factor, resizing — the topic this derivation supports.
Hash Functions — supplies the "fair scatter" of Step 2; break it and the proof collapses.
Linked Lists — the pile we walk in Steps 5–6.
Pigeonhole Principle — why collisions (piles taller than one) must exist at all.
Open Addressing — the rival scheme, which instead dies at $α = 1$ .
Amortized Analysis — defines big-O rigorously and keeps $α$ small via resizing.
Dynamic Arrays — same doubling logic that bounds $α$ .