TAOCP 6.4 Exercise 38

We consider a hash table with \(M\) buckets and \(N\) keys.

taocpmathematicsalgorithmsvolume-3math-hard

Section 6.4: Hashing

Exercise 38. [M32] (Tree hashing.) A clever programmer might try to use binary search trees instead of linear lists in the chaining method, thereby combining Algorithm 6.2.2T with hashing. Analyze the average number of probes that would be required by this compound algorithm, for both successful and unsuccessful searches. [Hint: See Eq. 5.2.1--(15).]

Verified: no
Solve time: 6m20s

Setup

We consider a hash table with (M) buckets and (N) keys. The hash function (h(K)) maps each key uniformly and independently to one of the (M) buckets. Collisions are resolved by maintaining a binary search tree in each bucket; keys are inserted using Algorithm 6.2.2T, so that, given the set of keys in a bucket, the resulting tree is a random binary search tree (all permutations of the keys are equally likely). A “probe” is a comparison with a key during the BST search (i.e., a visit to a BST node).

For a random BST with (k) nodes, the average number of probes for a successful search is [ C_k = 2\Bigl(1+\frac{1}{k}\Bigr)H_k - 3 \qquad\text{(Eq. 5.2.1-(15))}, ] and for an unsuccessful search it is [ C'_k = 2H_k - \frac{2k}{k+1} \quad (k\ge 1),\qquad C'_0 = 0. ] (The latter follows from the external path length formula of Section 5.2.1; see Eq. 5.2.1-(16).)

Solution

A successful search looks for a key chosen uniformly from the (N) keys in the table. The number of other keys that fall into the same bucket is a binomial random variable [ X \sim \mathrm{Binomial}\Bigl(N-1,; \frac{1}{M}\Bigr). ] Hence the bucket size is (k = 1+X). The average number of probes is [ S = \mathbb{E}\bigl[C_{1+X}\bigr] = \sum_{k=1}^{N} C_k \binom{N-1}{k-1} p^{k-1} q^{N-k}, ] where (p = 1/M) and (q = 1-p). Using (\binom{N-1}{k-1} = \frac{k}{N}\binom{N}{k}) and (C_k = \frac{2(k+1)H_k - 3k}{k}), this simplifies to [ \boxed{S = \frac{1}{N}\sum_{k=1}^{N} \binom{N}{k} p^{k-1} q^{N-k}\Bigl(2(k+1)H_k - 3k\Bigr)}. ]

An unsuccessful search hashes a key not present in the table. The number of keys in the bucket it hits is [ Y \sim \mathrm{Binomial}\Bigl(N,; \frac{1}{M}\Bigr). ] The average number of probes is [ U = \mathbb{E}\bigl[C'Y\bigr] = \sum{y=1}^{N} C'y \binom{N}{y} p^{y} q^{N-y}. ] Using (C'y = 2H_y - \frac{2y}{y+1} = 2H_y - 2 + \frac{2}{y+1}) and the identities [ \mathbb{E}[H_Y] = H_N - \sum{i=1}^{N}\frac{q^i}{i}, \qquad \mathbb{E}\Bigl[\frac{1}{Y+1}\Bigr] = \frac{1 - q^{N+1}}{(N+1)p}, ] we obtain [ \boxed{U = 2H_N - 2\sum{i=1}^{N}\frac{q^i}{i} - 2 + \frac{2M}{N+1}\bigl(1 - q^{N+1}\bigr)}. ]

Verification

Boundary cases.

  • (N=1): (S = \frac{1}{1}\binom{1}{1}p^0q^0(2\cdot2\cdot1-3)=1). The single key is always found in one probe.
    (U = 2\cdot1 - 2q - 2 + \frac{2M}{2}(1-q^2) = M(1-q^2)-2q = M(2p-p^2)-2(1-p) = 2-p-2+2p = p = 1/M). Correct: the bucket is non‑empty with probability (1/M), and an unsuccessful search in a one‑node BST costs exactly one probe.
  • (N=2,; M=2): (p=q=1/2).
    (S = \frac{1}{2}\bigl[ \binom{2}{1}\frac{1}{2}(2\cdot2\cdot1-3) + \binom{2}{2}\frac{1}{2}(2\cdot3\cdot\frac{3}{2}-6) \bigr] = \frac{1}{2}\bigl[ 1 + 1.5 \bigr] = 1.25).
    Manual check: both keys in same bucket (prob. (1/2)) → BST of size 2, average successful cost (1.5); different buckets (prob. (1/2)) → cost (1). Overall (1.25).
    (U = 2\cdot\frac{3}{2} - 2\bigl(\frac{1}{2}+\frac{1}{8}\bigr) - 2 + \frac{4}{3}\bigl(1-\frac{1}{8}\bigr) = 3 - 1.25 - 2 + \frac{3.5}{3} = \frac{11}{12} \approx 0.9167).
    Manual: (Y=0) (prob. (1/4), cost 0); (Y=1) (prob. (1/2), cost 1); (Y=2) (prob. (1/4), cost (5/3)). Average = (\frac{1}{2} + \frac{5}{12} = \frac{11}{12}). Matches.

Both formulas satisfy the independent checks. ∎

Notes

The expressions are exact under the uniform hashing assumption and the random‑insertion model for BSTs. For large (M,N) with load factor (\alpha = N/M) fixed, the binomial distributions approach Poisson((\alpha)), yielding asymptotic formulas [ S \sim \sum_{k=1}^{\infty} e^{-\alpha}\frac{\alpha^{k-1}}{(k-1)!},C_k,\qquad U \sim \sum_{k=1}^{\infty} e^{-\alpha}\frac{\alpha^{k}}{k!},C'_k, ] which can be evaluated numerically. The exact finite sums above are the complete analytic answer.