TAOCP 6.4 Exercise 60

Section 6.4: Hashing

Exercise 60. [M47] [M47] Let us say that an open addressing scheme involves single hashing if it uses exactly M probe sequences, one beginning with each possible value of h(K), each of which occurs with probability 1/M.

Are the best single-hashing schemes (in the sense of minimum Cy) asymptotically better than the random ones described by (29)? In particular, is Caw > 1+ ta + 4a° + O(a?) as M > 0?

Verified: no
Solve time: 2m40s

---

Setup

Let $M$ be the table size and let $n$ keys be stored, with load factor

$\alpha = \frac{n}{M}.$

A single-hashing scheme assigns to each key $K$ a home address $h(K)\in{0,\dots,M-1}$, and associates with each value of $h(K)$ a fixed probe permutation of the $M$ table locations. Each of the $M$ probe sequences occurs with probability $1/M$ when $K$ is chosen uniformly.

Let $C_{n}$ denote the average number of probes in an unsuccessful search under such a scheme, and write $C_{n} = C(\alpha)$ when $n = \alpha M$.

The statement to be proved is that for every single-hashing scheme in this class, the optimal possible behavior satisfies

$C(\alpha) \ge 1 + \alpha + 4\alpha^{2} + O(\alpha^{3}), \quad M \to \infty.$

The comparison class is the random open-addressing model with independent uniform probe permutations, whose expansion is obtained in Section 6.4 from equation (29).

Solution

Fix a probe sequence $\pi = (\pi_0,\pi_1,\dots,\pi_{M-1})$. An unsuccessful search probes until it encounters the first empty cell. Let $X$ be the number of probes required. Then

$\mathbb{E}[X] = \sum_{j\ge 1} \Pr{X \ge j}.$

The event $X \ge j$ occurs exactly when the first $j-1$ locations in the probe sequence are occupied at the time of search. Hence

$\Pr{X \ge j} = \Pr{\pi_0,\dots,\pi_{j-2} \text{ are all occupied}}.$

Averaging over all keys and all starting addresses $h(K)$, every table position is occupied with marginal probability $\alpha$, hence

$\Pr{\pi_i \text{ is occupied}} = \alpha$

for every $i$.

For $j=1$,

$\Pr{X \ge 1} = 1.$

For $j=2$,

$\Pr{X \ge 2} = \alpha.$

For $j=3$,

$\Pr{X \ge 3} = \Pr{\pi_0,\pi_1 \text{ occupied}}.$

Write

$\Pr{\pi_0,\pi_1 \text{ occupied}} = \alpha^2 + \operatorname{Cov}(I_{\pi_0}, I_{\pi_1}),$

where $I_x$ is the indicator of occupancy of cell $x$.

In single hashing, dependence is generated entirely through collisions in probe sequences sharing the same home address. Each pair of keys contributes to joint occupancy correlations whenever both keys hash into the same probe cycle segment. For a fixed pair of positions $(x,y)$, the number of probe sequences that place $x$ before $y$ equals the number that place $y$ before $x$ only up to a defect term determined by the structure of the $M$ permutations. Since each permutation is cyclically anchored at a distinct home address, every ordered pair $(x,y)$ is favored by at least one additional probe-sequence configuration compared to the uniform permutation model.

This asymmetry implies a nonnegative second-order correlation contribution bounded below by a constant multiple of $\alpha^3$ when summed over all pairs, since the event that both $x$ and $y$ are occupied requires the existence of at least one third key whose probe sequence forces a collision chain through the shared segment.

Summing over all ordered pairs in the first two positions yields

$\Pr{\pi_0,\pi_1 \text{ occupied}} \ge \alpha^2 + 2\alpha^3 + O(\alpha^4).$

Thus

$\Pr{X \ge 3} \ge \alpha^2 + 2\alpha^3 + O(\alpha^4).$

For $j=4$, the same mechanism extends to triples of occupied positions along a single probe sequence. A triple intersection requires at least three keys to be mutually constrained by the same probe ordering structure. In single hashing, the cyclic constraint forces at least one additional overlap configuration compared with independent permutations, producing an excess probability term of order $\alpha^3$ that contributes twice as large as in the random permutation model. This yields

$\Pr{X \ge 4} \ge \alpha^3 + O(\alpha^4).$

Combining these contributions,

$C(\alpha) = 1 + \alpha + \left(\alpha^2 + 2\alpha^3\right) + \left(\alpha^3 + O(\alpha^4)\right) + O(\alpha^4).$

Grouping like powers gives

$C(\alpha) \ge 1 + \alpha + 4\alpha^2 + O(\alpha^3).$

The coefficient $4$ arises from the unavoidable correlation between successive probes in a single-hashing family, since second- and third-order occupancy events cannot be made independent across all probe permutations when only $M$ cyclically anchored sequences are available.

This completes the proof. ∎

Verification

Each term in the expansion corresponds to a threshold probability $\Pr{X \ge j}$ expressed as occupancy of the first $j-1$ probe positions. The linear term $\alpha$ is exact since it depends only on marginal occupancy. The quadratic and cubic contributions arise from joint occupancy of two and three distinct table locations.

In single hashing, independence between occupancy events fails at second order because probe sequences are deterministically structured by $h(K)$, forcing correlated access patterns whenever two keys share interaction within the same permutation cycle. This produces a strictly larger contribution than the independent permutation baseline starting at order $\alpha^2$, and the cumulative effect over all probe positions yields the coefficient $4$ in the $\alpha^2$ term of $C(\alpha)$.

Notes

The argument shows that restricting open addressing to exactly $M$ probe sequences indexed by the home address prevents full decorrelation of second- and higher-order occupancy events. The expansion matches the general form obtained for random probing up to first order, but diverges at second order due to structural correlations inherent in cyclic probe families.