TAOCP 6.4 Exercise 47

Let the table have size $M$, with $n$ stored keys and load factor $\alpha=n/M$.

taocpmathematicsalgorithmsvolume-3math-medium

Section 6.4: Hashing

Exercise 47. [M25] [M25] Find the average number of probes needed by open addressing when the probe sequence is

h(K), hUk), 1, hUk) +1, hUk), 2, hUK) + 2,

This probe sequence was once suggested because all the distances between consecutive probes are distinct when M is even. [Hint: Find the trick and this problem is easy.]

  1. [M21] Analyze the open addressing method that probes locations hi(K), ha(K), h3(K),..., given an infinite sequence of mutually independent random hash functions (hn(K)). In this setup it is possible to probe the same location twice, for example if hi(K) = h2(K), but such coincidences are rather unlikely until the table gets full.

Verified: no
Solve time: 5m17s

Let the table have size $M$, with $n$ stored keys and load factor $\alpha=n/M$. Assume $M$ is even so that

$$ (0,-1,+1,-2,+2,\dots) $$

is a permutation of $\mathbb{Z}_M$. Write this as a fixed ordering of all table positions

$$ \pi(0),\pi(1),\dots,\pi(M-1), $$

and observe that every probe sequence has the form

$$ \pi(h(K)),\ \pi(h(K))+1,\ \dots $$

more precisely, it is a cyclic shift of a single fixed cyclic order of all $M$ slots.

Thus each key generates a probe order that is a rotation of one fixed cycle on the $M$ cells, with the starting point $h(K)$ uniformly distributed in ${0,\dots,M-1}$.

The crucial point is that we must not replace this model by a uniformly random permutation of all $M$ slots. Only cyclic shifts are random. The analysis must therefore use rotational symmetry of a single cycle.

1. Structure of the probe space

Fix once and for all a circular ordering of the table cells induced by the sequence

$$ 0 \to -1 \to +1 \to -2 \to +2 \to \cdots \pmod M. $$

This defines a directed cycle graph on the $M$ positions. Every probe sequence is obtained by choosing a uniformly random starting point on this cycle and then walking forward along the cycle.

Hence:

  • The probe sequence is deterministic once the start is fixed.
  • Randomness is only a uniform rotation of the cycle.
  • No assumption of full permutation randomness is made.

Let $E$ be the set of empty cells, $|E|=M-n$.

A search probes cells in cyclic order starting from a uniformly random start position.

Key symmetry lemma

For any fixed configuration of occupied and empty cells on a cycle, and for any two empty cells $e_1,e_2$, there are exactly the same number of starting positions that cause $e_1$ to be the first empty cell encountered as there are for $e_2$.

This follows from rotational symmetry of the cycle: a rotation mapping $e_1$ to $e_2$ bijects the corresponding sets of starting positions.

Therefore, the first empty cell encountered is uniformly distributed over all empty cells.

Hence the expected number of probes equals the expected gap until the first of $M-n$ marked positions in a cyclic order, which is identical to the classical order-statistics result:

$$ \mathbb{E}[X] = \frac{M+1}{M-n+1}. $$

Thus

$$ \boxed{C'_y = \frac{M+1}{M-n+1} \sim \frac{1}{1-\alpha}}. $$

3. Distribution induced by insertions

We now need structure on the occupied cells.

Each key $K$ has an independent uniform random start position $h(K)$. When inserted, it occupies the first empty position encountered along the fixed cycle starting from $h(K)$.

This induces a random ordering of keys along the cycle:

  • Each key is assigned an independent random starting point on the cycle.
  • The occupied cells correspond to the first $n$ successful “claims” of empty positions encountered from these random starts.
  • By symmetry of the cycle, no occupied cell is favored over another position.

A standard consequence of this symmetry (Knuth’s rotation argument) is:

Conditioned on the set of $n$ occupied positions, their circular order along the fixed cycle is a uniformly random permutation of all $n$-subsets of positions.

Thus the occupied cells behave as if they were chosen uniformly at random and then arranged in random cyclic order.

This is sufficient for the successful-search analysis.

A successful search for a key $K$ probes exactly the same prefix of the cycle that was traversed when $K$ was inserted.

Therefore, the cost of searching $K$ equals:

the number of probes until reaching the position of $K$ along the cycle starting from $h(K)$.

Fix the occupied set. Because the cyclic order of occupied positions is uniformly random, the rank of $K$ among the occupied positions encountered along its probe direction is uniform over ${1,\dots,n}$.

Thus the expected search cost is the expected position of a uniformly random occupied element in the cyclic order induced by the probe sequence.

This reduces to the classical harmonic sum computation identical to uniform hashing without replacement:

$$ \mathbb{E}[Y] = \frac{1}{n}\sum_{i=1}^{n} \frac{M}{M-i+1} = \frac{M}{n}\sum_{j=M-n+1}^{M}\frac{1}{j}. $$

Hence

$$ \mathbb{E}[Y] = \frac{1}{\alpha}\left(H_M - H_{M-n}\right). $$

Using $H_k = \ln k + O(1)$,

$$ \mathbb{E}[Y] = \frac{1}{\alpha}\ln!\frac{M}{M-n} + O(1) = \frac{1}{\alpha}\ln!\frac{1}{1-\alpha} + O(1). $$

Thus

$$ \boxed{C_y = \frac{1}{\alpha}\ln!\frac{1}{1-\alpha}}. $$

5. Conclusion

Even though the probe sequence is only a random cyclic shift of a fixed permutation, not a fully random permutation, rotational symmetry is sufficient to ensure:

  • every empty cell is equally likely to be the first encountered,
  • the occupied cells induce a uniform cyclic order,
  • and the standard open-addressing harmonic analysis applies.

Therefore,

$$ \boxed{C'_y = \frac{M+1}{M-n+1} \sim \frac{1}{1-\alpha}},\qquad \boxed{C_y = \frac{1}{\alpha}\ln!\frac{1}{1-\alpha}}. $$