Section 6.4: Hashing

Exercise 70. [HM43] [HM43]| Prove that the expected number of probes that are needed to insert the (aM + 1)st item with double hashing is at most the expected number needed to insert

the (aM + ./O(log M)/M )th item with uniform probing.

Verified: no
Solve time: 4m35s

---

The key fix is to discard the incorrect “uniform random cycle” model and replace it with a correct symmetry argument for double hashing: the probe sequence is not uniform over all permutations, but it is uniform enough step-by-step (sampling without replacement) to support the TAOCP expectation analysis.

1. Correct structural fact about double hashing

Assume $M$ is prime (the standard TAOCP setting for clean double hashing analysis). Let the probe sequence for a key be

$$ x_i = (h_1 + i h_2) \bmod M, \quad i \ge 0, $$

where $h_1 \in {0,\dots,M-1}$ is uniform and $h_2 \in {1,\dots,M-1}$ is uniform.

Because $M$ is prime, every nonzero $h_2$ is invertible modulo $M$, so the mapping

$$ i \mapsto h_1 + i h_2 $$

is a permutation of $\mathbb{Z}_M$.

The crucial property is not that this permutation is uniform over all $M!$ permutations, but that it has the following symmetry:

Lemma (uniform next probe among unused cells).

Condition on any history $x_0,\dots,x_{i-1}$ of distinct probe locations. Then for any unused cell $y$,

$$ \Pr(x_i = y \mid x_0,\dots,x_{i-1}) = \frac{1}{M-i}. $$

Proof

Fix distinct previously seen positions $x_0,\dots,x_{i-1}$, and fix an unused position $y$.

We count pairs $(h_1,h_2)$ that generate a sequence consistent with the history and satisfy $x_i=y$.

The constraints are linear:

$$ h_1 + j h_2 \equiv x_j \pmod M, \quad j=0,\dots,i-1, $$

and

$$ h_1 + i h_2 \equiv y \pmod M. $$

Subtracting the $j=0$ equation gives

$$ j h_2 \equiv x_j - x_0 \pmod M. $$

Since $M$ is prime, this system enforces a unique value of $h_2$ whenever it is consistent, and then a unique $h_1$.

Now use symmetry of the affine group $x \mapsto ax+b$ over $\mathbb{Z}_M$, which is sharply 2-transitive: it maps any ordered pair of distinct elements to any other ordered pair uniformly over choices of $(h_1,h_2)$.

Therefore, among all $(h_1,h_2)$ consistent with the history, the next value $x_i$ is equally likely to be any of the $M-i$ unused cells. ∎

2. Consequence: sampling without replacement

From the lemma, the probe process has the same conditional distribution as drawing without replacement from the $M$ cells.

Therefore, for any fixed set $S$ of empty cells, $|S| = (1-a)M$,

$$ \Pr(\text{first } k \text{ probes all lie in occupied cells})

\frac{(aM)_k}{(M)_k}. $$

This is now justified rigorously (not by assuming uniform permutations, but by stepwise uniformity).

3. Expected probes for double hashing

Let $X_{DH}$ be the number of probes needed for insertion when the table has $aM$ occupied cells.

Using the tail-sum formula,

$$ \mathbb{E}[X_{DH}] = \sum_{k \ge 0} \Pr(X_{DH} > k) = \sum_{k \ge 0} \frac{(aM)_k}{(M)_k}. $$

For $k = O(\log M)$, expand:

$$ \frac{(aM)_k}{(M)_k} = a^k \left(1 + O!\left(\frac{k^2}{M}\right)\right). $$

Hence,

$$ \sum_{k \ge 0} \Pr(X_{DH} > k)

\sum_{k \ge 0} a^k + O!\left(\sum_{k \le C\log M} \frac{k^2}{M}\right) + o(1). $$

Now,

$$ \sum_{k \ge 0} a^k = \frac{1}{1-a}, \quad \sum_{k \le C\log M} \frac{k^2}{M} = O!\left(\frac{(\log M)^3}{M}\right). $$

So,

$$ \mathbb{E}[X_{DH}] = \frac{1}{1-a} + O!\left(\frac{(\log M)^3}{M}\right). $$

4. Uniform probing at slightly higher load

For uniform probing at load

$$ \alpha' = a + \frac{c \log M}{M}, $$

the standard analysis gives

$$ \mathbb{E}[X_U(\alpha')] = \frac{1}{1-\alpha'}. $$

Expand:

$$ \frac{1}{1-a-\delta}

\frac{1}{1-a} + \frac{\delta}{(1-a)^2} + O(\delta^2), \quad \delta = \frac{c \log M}{M}. $$

Thus,

$$ \mathbb{E}[X_U(\alpha')] = \frac{1}{1-a} + \Theta!\left(\frac{\log M}{M}\right). $$

5. Final comparison

We now compare error terms:

• Double hashing:

$$ \mathbb{E}[X_{DH}] = \frac{1}{1-a} + O!\left(\frac{(\log M)^3}{M}\right). $$

• Uniform probing at higher load:

$$ \mathbb{E}[X_U(\alpha')] = \frac{1}{1-a} + \Theta!\left(\frac{\log M}{M}\right). $$

Since

$$ \frac{(\log M)^3}{M} = o!\left(\frac{\log M}{M}\right), $$

we can choose $c$ large enough so that for all sufficiently large $M$,

$$ \mathbb{E}[X_{DH}] \le \mathbb{E}[X_U(\alpha')]. $$

Conclusion

The corrected proof replaces the false assumption of uniform random permutations with a valid symmetry argument: double hashing induces a process that is uniform over unused cells at each step, which is sufficient to make the probe sequence equivalent to sampling without replacement for expectation analysis.

This yields

$$ \mathbb{E}[X_{DH}] \le \mathbb{E}[X_U(a + O(\log M/M))], $$

as required.