TAOCP 6.4 Exercise 48
We consider an open addressing hash table of size \(M\) containing \(N\) keys (\(0 \le N < M\)).
Exercise 48. ▶ [M21] Analyze the open addressing method that probes locations $h_1(K)$, $h_2(K)$, $h_3(K)$, . . ., given an infinite sequence of mutually independent random hash functions $\langle h_n(K)\rangle$. In this setup it is possible to probe the same location twice, for example if $h_1(K)=h_2(K)$, but such coincidences are rather unlikely until the table gets full.
Verified: no
Solve time: 1m19s
Solution
We consider an open addressing hash table of size (M) containing (N) keys ((0 \le N < M)).
The hash functions (h_1, h_2, h_3, \dots) are mutually independent random functions; for any fixed key (K) the values (h_n(K)) are independent and uniformly distributed over ({0,1,\dots,M-1}).
Thus the probe sequence for a key is a sequence of independent uniform random locations. Collisions between probes of the same key (e.g., (h_1(K)=h_2(K))) are possible but unlikely when the table is not full.
Unsuccessful search
We probe (h_1(K), h_2(K), \dots) until an empty slot is found.
There are (M-N) empty slots, so each probe independently hits an empty slot with probability
[
p = \frac{M-N}{M} = 1-\frac{N}{M}.
]
The number of probes (X) follows a geometric distribution with success probability (p):
[
\Pr(X=k) = (1-p)^{k-1}p,\qquad k=1,2,\dots
]
Hence the expected number of probes for an unsuccessful search is
[
\boxed{C'_N = \frac{1}{p} = \frac{M}{M-N} = \frac{1}{1-\alpha}},\qquad \alpha = \frac{N}{M}.
]
Successful search
Assume the (N) keys were inserted one by one into an initially empty table, each using its own independent sequence of hash functions.
When the ((i+1))-st key is inserted ((i = 0,1,\dots,N-1)), the table already contains (i) keys.
The insertion probes until an empty slot is found; by the same reasoning as above, the number of probes needed is geometrically distributed with success probability ((M-i)/M), so its expectation is
[
\frac{M}{M-i}.
]
Because all keys are symmetric and the insertion order is uniformly random, the expected number of probes for a successful search is the average of these insertion costs over all (N) keys:
[
C_N = \frac{1}{N}\sum_{i=0}^{N-1} \frac{M}{M-i}
= \frac{M}{N}\sum_{j=M-N+1}^{M} \frac{1}{j}.
]
Using harmonic numbers (H_m = \sum_{j=1}^{m} 1/j), this becomes
[
\boxed{C_N = \frac{M}{N}\bigl(H_M - H_{M-N}\bigr)}.
]
Asymptotic behaviour
As (M,N \to \infty) with (\alpha = N/M) fixed ((0<\alpha<1)), [ C'_N ;\sim; \frac{1}{1-\alpha}, \qquad C_N ;\sim; \frac{1}{\alpha}\ln\frac{1}{1-\alpha}. ] These asymptotic formulas coincide with those for the uniform probing model (random permutations), although the exact expressions differ slightly.