TAOCP 6.4 Exercise 35
We consider the model of Exercise 34: \(N\) distinct keys are hashed independently and uniformly into \(M\) separate lists.
Exercise 35. [M24] Continuing exercise 34, what is the average number of probes in an unsuccessful search when the individual lists are kept in order by their key values? Consider data structures (i), (ii), and (iii).
Verified: no
Solve time: 12m05s
Solution
We consider the model of Exercise 34: (N) distinct keys are hashed independently and uniformly into (M) separate lists. The length (L) of a given list follows the binomial distribution [ P_{Nk} = \Pr(L = k) = \binom{N}{k}\left(\frac{1}{M}\right)^k\left(1-\frac{1}{M}\right)^{N-k}, \qquad 0 \le k \le N. ] The probability generating function is [ P_n(z) = \sum_{k=0}^N P_{Nk} z^k = \left(1-\frac{1}{M}+\frac{z}{M}\right)^N. ]
For an unsuccessful search we take a key (K) not in the table; its hash value is uniformly distributed over the (M) lists, independent of the already stored keys. The keys in the chosen list are kept in increasing order. Because all (N+1) keys (the (N) stored keys plus (K)) are distinct and their relative order is uniformly random, the rank (r) of (K) among the (L+1) keys in its list is uniformly distributed over ({1,2,\dots,L+1}).
The number of probes (key comparisons) depends on the data structure.
Conditional expectation for a list of length (L)
-
Variant (i) - separate chaining (Fig. 38):
The hash table contains only pointers to the list heads. If (L=0) the list is empty and no key is examined: probes (= 0).
If (L\ge 1) we compare (K) with the first element; if (K) is smaller we stop (1 probe), otherwise we continue through the list until we find an element larger than (K). The number of probes is (\min(r, L)). Hence [ \mathbb{E}[\text{probes}\mid L] = \begin{cases} 0, & L=0,\[2mm] \displaystyle\frac{1}{L+1}\Bigl(\sum_{r=1}^{L} r + L\Bigr) = \frac{L(L+3)}{2(L+1)}, & L\ge 1. \end{cases} ] -
Variants (ii) and (iii) - first element in the table (Fig. 40):
The hash table has (M) slots; each slot either is empty ((L=0)) or holds the smallest key of the list ((L\ge 1)). The remaining keys are in a separate overflow area (ii) or in the same hash table (iii). In both cases the search first examines the table slot. If (L=0) the slot is empty - this examination counts as one probe. If (L\ge 1) the process is exactly the same as in (i): we compare (K) with the table key (the smallest) and then, if necessary, with the subsequent keys in order. Thus for (L\ge 1) the number of probes is again (\min(r, L)). Consequently [ \mathbb{E}[\text{probes}\mid L] = \begin{cases} 1, & L=0,\[2mm] \dfrac{L(L+3)}{2(L+1)}, & L\ge 1. \end{cases} ]
Overall averages
Using the distribution (P_{Nk}) we obtain the average number of probes for each variant.
Variant (i): [ U_1 = \sum_{k=1}^N P_{Nk},\frac{k(k+3)}{2(k+1)}. ]
Variants (ii) and (iii): [ U_2 = U_3 = P_{N0} + \sum_{k=1}^N P_{Nk},\frac{k(k+3)}{2(k+1)}. ]
We simplify the sum using the generating function (P_n(z)). Notice that [ \frac{k(k+3)}{2(k+1)} = \frac{k+2}{2} - \frac{1}{k+1}. ] Hence [ \sum_{k=1}^N P_{Nk}\frac{k(k+3)}{2(k+1)} = \frac{1}{2}\sum_{k=1}^N P_{Nk}(k+2) - \sum_{k=1}^N\frac{P_{Nk}}{k+1}. ] We have [ \sum_{k=1}^N P_{Nk}(k+2) = \sum_{k=1}^N P_{Nk}k + 2\sum_{k=1}^N P_{Nk} = P_n'(1) + 2(1-P_{N0}) = \frac{N}{M} + 2(1-P_{N0}). ] For the second sum, [ \sum_{k=0}^N \frac{P_{Nk}}{k+1} = \int_0^1 P_n(z),dz, ] so [ \sum_{k=1}^N \frac{P_{Nk}}{k+1} = \int_0^1 P_n(z),dz - P_{N0}. ] Substituting, [ \sum_{k=1}^N P_{Nk}\frac{k(k+3)}{2(k+1)} = \frac{1}{2}\Bigl(\frac{N}{M} + 2(1-P_{N0})\Bigr) - \Bigl(\int_0^1 P_n(z),dz - P_{N0}\Bigr) = 1 + \frac{N}{2M} - \int_0^1 P_n(z),dz. ] Therefore [ \boxed{U_1 = 1 + \frac{N}{2M} - \int_0^1 P_n(z),dz} ] and [ \boxed{U_2 = U_3 = 1 + \frac{N}{2M} - \int_0^1 P_n(z),dz + P_{N0}}, ] where (P_{N0} = P_n(0) = (1-1/M)^N).
The integral can be evaluated explicitly: [ \int_0^1 P_n(z),dz = \int_0^1 \Bigl(1-\frac{1}{M}+\frac{z}{M}\Bigr)^N dz = \frac{M}{N+1}\Bigl[1 - \Bigl(1-\frac{1}{M}\Bigr)^{N+1}\Bigr]. ]
This completes the proof. ∎