TAOCP 6.4 Exercise 36

We consider the model of Exercise 34: a chained hash table with \(M\) lists, \(N\) keys already inserted, and the \(M^N\) hash sequences equally likely.

taocpmathematicsalgorithmsvolume-3math-medium

Section 6.4: Hashing

Exercise 36. [M23] Continuing exercise 34(d), find the variance of the number of probes when the search is unsuccessful, using data structures (i) and (ii).

Verified: no
Solve time: 3m43s

Solution

We consider the model of Exercise 34: a chained hash table with (M) lists, (N) keys already inserted, and the (M^N) hash sequences equally likely. For an unsuccessful search the search key hashes uniformly to one of the (M) lists, independently of the existing keys. The number of keys (L) in the target list therefore follows a binomial distribution: [ \Pr(L = k) = \binom{N}{k} p^k (1-p)^{N-k}, \qquad p = \frac{1}{M}. ]

Data structure (i): hashing to a list head

The hash table contains pointers to the heads of the separate lists. An unsuccessful search traverses the chosen list and compares the search argument with every key in that list. Hence the number of probes is exactly the length of the list: [ X = L. ] The mean and variance of a binomial variable are well known: [ \mathbb{E}[X] = Np, \qquad \operatorname{Var}(X) = Np(1-p). ] Substituting (p = 1/M) gives the variance for (i).

[ \boxed{\operatorname{Var}(X) = \frac{N(M-1)}{M^2}} ]

Data structure (ii): hashing to a table position with separate overflow

The hash table has (M) slots; the first key of each chain resides in the table slot, and any additional keys are stored in a separate overflow area. An unsuccessful search proceeds as follows:

  • If the slot is empty ((L = 0)), we probe the slot once and stop.
  • If the slot is occupied ((L \ge 1)), we probe the slot (one probe), find a key that does not match, and then probe each of the (L-1) keys in the overflow list. Thus the number of probes is [ X = \max(1, L) = \begin{cases} 1, & L = 0,\ L, & L \ge 1. \end{cases} ]

We compute the first two moments. Let (A = \Pr(L = 0) = (1-p)^N). [ \mathbb{E}[X] = 1 \cdot A + \sum_{k=1}^N k \Pr(L=k) = A + \mathbb{E}[L] = A + Np. ] [ \mathbb{E}[X^2] = 1^2 \cdot A + \sum_{k=1}^N k^2 \Pr(L=k) = A + \mathbb{E}[L^2]. ] For the binomial distribution (\mathbb{E}[L] = Np) and (\mathbb{E}[L^2] = Np(1-p) + N^2p^2). Therefore [ \mathbb{E}[X^2] = A + Np(1-p) + N^2p^2. ] The variance is [ \begin{aligned} \operatorname{Var}(X) &= \mathbb{E}[X^2] - (\mathbb{E}[X])^2 \ &= A + Np(1-p) + N^2p^2 - (A + Np)^2 \ &= A + Np(1-p) + N^2p^2 - A^2 - 2ANp - N^2p^2 \ &= A(1 - A - 2Np) + Np(1-p). \end{aligned} ] Replacing (p = 1/M) and (A = (1 - 1/M)^N) yields the variance for (ii).

[ \boxed{\operatorname{Var}(X) = \left(1 - \frac{1}{M}\right)^N !\left[1 - \left(1 - \frac{1}{M}\right)^N - \frac{2N}{M}\right] + \frac{N(M-1)}{M^2}} ]

Verification

  • For (N = 0): both formulas give (0) (no keys, the search always finds an empty list or an empty slot, so the number of probes is deterministic).
  • For (M = 1): both formulas give (0) (all keys go to the single list/slot, so (L = N) always, and (X = N) or (X = \max(1,N)) is constant).