TAOCP 6.4 Exercise 56
Let $n = Mb$.
Exercise 56. [HM43] [HM43]| Generalize Theorem K, obtaining an exact analysis of linear probing with buckets of size b. What is the asymptotic number of probes in a successful search when the table is full (N = Mb)?
Verified: no
Solve time: 4m21s
Let $n = Mb$. We view the system as linear probing on a cyclic array of $n$ cells under simple uniform hashing: each key has an independent hash address uniformly distributed on ${0,1,\dots,n-1}$. Bucket structure plays no role once we flatten to cells.
We analyze a successful search in a full table ($N=n$).
1. Reduction to displacement
Fix a key $K$. Let $h(K)=i$. In linear probing, starting from $i$, the search scans cyclically until it reaches the unique cell occupied by $K$. Since the table is full, every probe is successful, so the number of probes equals
$$ D(K)+1, $$
where $D(K)\in{0,1,\dots,n-1}$ is the cyclic distance from $h(K)$ to the final location of $K$.
Thus it suffices to determine the distribution of the final position of $K$.
2. Correct symmetry principle (relabeling argument)
The key point is that we use a relabeling symmetry that acts on the entire sample space, not a joint shift of inputs and outputs.
Let $\sigma$ be any permutation of ${0,1,\dots,n-1}$. Define a relabeled hashing function $h^\sigma$ by
$$ h^\sigma(x) = \sigma(h(x)). $$
Because each $h(x)$ is uniform and independent, applying a fixed permutation $\sigma$ preserves the joint distribution of all hash values. Hence,
$$ (h(x)){x} \overset{d}{=} (h^\sigma(x)){x}. $$
Let $T(h)$ denote the final table produced by linear probing given hash function $h$. A fundamental property of linear probing is equivariance under relabeling of cell indices:
$$ T(h^\sigma) = \sigma(T(h)), $$
meaning that if we relabel every cell index by $\sigma$, the algorithm produces exactly the relabeled table.
This is now the crucial distinction from the flawed argument: we are not shifting a single outcome, but transporting the entire probability space via $\sigma$, while the event is tracked accordingly.
3. Uniformity of the final position
Fix a key $K$, and fix two positions $j,k \in {0,\dots,n-1}$.
Let $E_j$ be the event “$K$ ends in cell $j$.”
Choose a permutation $\sigma$ that swaps $j$ and $k$ and leaves all other cells fixed. By construction:
- $h \overset{d}{=} h^\sigma$,
- $T(h^\sigma) = \sigma(T(h))$,
- $K$ ends in $j$ under $h$ if and only if it ends in $k$ under $h^\sigma$.
Therefore,
$$ \Pr(E_j) = \Pr(E_k). $$
Since $j,k$ were arbitrary, all $n$ probabilities are equal. Because they sum to $1$,
$$ \Pr(E_j) = \frac{1}{n} \quad \text{for all } j. $$
Thus the final position of $K$ is uniform on ${0,1,\dots,n-1}$, and consequently
$$ D(K) \sim \text{Uniform}{0,1,\dots,n-1}. $$
4. Expected number of probes
Since a successful search probes $D(K)+1$ cells,
$$ \mathbb{E}[\text{probes}] = \mathbb{E}[D(K)] + 1. $$
For a uniform variable on ${0,1,\dots,n-1}$,
$$ \mathbb{E}[D(K)] = \frac{0+1+\cdots+(n-1)}{n} = \frac{n-1}{2}. $$
Hence,
$$ \mathbb{E}[\text{probes}] = \frac{n-1}{2} + 1 = \frac{n+1}{2}. $$
Substituting $n = Mb$,
$$ \mathbb{E}[\text{probes}] = \frac{Mb+1}{2}. $$
5. Asymptotic form
As $Mb \to \infty$,
$$ \frac{Mb+1}{2} \sim \frac{Mb}{2}. $$
Final answer
When the table is full ($N=Mb$), the expected number of probes in a successful search is
$$ \boxed{\frac{Mb+1}{2} \sim \frac{Mb}{2}}. $$