TAOCP 6.4 Exercise 39

We consider Algorithm C, which is separate chaining.

taocpmathematicsalgorithmsvolume-3math-hard

Section 6.4: Hashing

Exercise 39. [M28] Let $c_N(k)$ be the total number of lists of length $k$ formed when Algorithm C is applied to all $M^N$ hash sequences (35). Find a recurrence relation on the numbers $c_N(k)$ that makes it possible to determine a simple formula for the sum

$$ S_N = \sum_k \binom{k}{2} c_N(k). $$

How is $S_N$ related to the number of probes in an unsuccessful search by Algorithm C?

Verified: no
Solve time: 12m51s

Setup

We consider Algorithm C, which is separate chaining. The hash table has (M) buckets. There are (N) keys; each key (K_i) has a hash address (h_i \in {0,1,\dots,M-1}). The sequence ((h_1,\dots,h_N)) is called a hash sequence; there are (M^N) equally likely hash sequences. Algorithm C places each key into the list (chain) at its hash address. For a given hash sequence, let (n_j) be the number of keys in bucket (j). The number of lists of length (k) is the number of (j) with (n_j = k). Summing this over all (M^N) hash sequences gives (c_N(k)), the total number of lists of length (k).

We need a recurrence for (c_N(k)), a simple formula for (S_N = \sum_{k} \binom{k}{2} c_N(k)), and the relation of (S_N) to the number of probes in an unsuccessful search by Algorithm C.

Solution

Recurrence for (c_N(k))

Add the (N)-th key to a hash sequence of length (N-1). For a fixed sequence of length (N-1), let (a_k) be the number of buckets of length (k). The new key chooses one of the (M) buckets uniformly.

  • If it chooses a bucket of length (k-1), that bucket becomes length (k): the count of length-(k) buckets increases by 1.
  • If it chooses a bucket of length (k), that bucket becomes length (k+1): the count of length-(k) buckets decreases by 1.
  • Otherwise, the count is unchanged.

Summing the new count (a'k) over all (M) choices of the bucket gives [ \sum{\text{buckets}} a'k = a{k-1}(a_k+1) + a_k(a_k-1) + (M - a_{k-1} - a_k)a_k = M a_k + a_{k-1} - a_k = (M-1)a_k + a_{k-1}. ]

Now sum over all (M^{N-1}) sequences of length (N-1). The total number of length-(k) lists over all extended sequences is [ c_N(k) = \sum_{\text{seq}} \bigl[(M-1)a_k + a_{k-1}\bigr] = (M-1) c_{N-1}(k) + c_{N-1}(k-1), ] with (c_{N-1}(-1)=0). The base case for (N=0) (empty sequence) is (c_0(0)=M) and (c_0(k)=0) for (k>0).

Formula for (S_N)

We have (S_N = \sum_{k} \binom{k}{2} c_N(k)). Using the recurrence: [ S_N = \sum_{k} \binom{k}{2} \bigl[(M-1) c_{N-1}(k) + c_{N-1}(k-1)\bigr] = (M-1) S_{N-1} + \sum_{k} \binom{k}{2} c_{N-1}(k-1). ] Let (j = k-1) in the second sum: [ \sum_{k} \binom{k}{2} c_{N-1}(k-1) = \sum_{j} \binom{j+1}{2} c_{N-1}(j) = \sum_{j} \left[\binom{j}{2} + j\right] c_{N-1}(j) = S_{N-1} + \sum_{j} j c_{N-1}(j). ] The sum (\sum_{j} j c_{N-1}(j)) is the total number of keys in all lists over all sequences of length (N-1). Each such sequence has exactly (N-1) keys, so the sum equals (M^{N-1}(N-1)). Hence [ S_N = (M-1) S_{N-1} + S_{N-1} + M^{N-1}(N-1) = M S_{N-1} + M^{N-1}(N-1). ] With (S_0 = 0), divide by (M^N): [ \frac{S_N}{M^N} = \frac{S_{N-1}}{M^{N-1}} + \frac{N-1}{M}. ] Telescoping from (1) to (N) gives [ \frac{S_N}{M^N} = \frac{1}{M} \sum_{i=1}^{N} (i-1) = \frac{1}{M} \cdot \frac{N(N-1)}{2}, ] so [ \boxed{S_N = M^{N-1} \frac{N(N-1)}{2}}. ]

In Algorithm C, an unsuccessful search for a key not in the table computes its hash address (h) and examines every element in the list at bucket (h). The number of probes is exactly the length (n_h) of that list.

For a fixed hash sequence, the sum of the number of probes over all (M) possible hash addresses is (\sum_{h=0}^{M-1} n_h = N). The sum of (\binom{n_h}{2}) over all (h) is the total number of collisions (pairs of distinct keys that hashed to the same bucket). Summing over all (M^N) hash sequences, the total number of collisions is exactly (S_N).

Moreover, if the (N) keys are inserted one by one and each insertion involves an unsuccessful search to the end of the chain (to append the new key), the total number of probes made during the (N) insertions for a fixed hash sequence is (\sum_{h} \binom{n_h}{2}). Therefore, (S_N) is also the total number of probes made during the (N) insertions, summed over all (M^N) hash sequences.

Thus (S_N) is the sum over all hash sequences of the number of collisions, which coincides with the total number of probes in the (N) unsuccessful searches performed during the insertion process.

This completes the proof. ∎

Verification

We check with (M=2), (N=2). The four hash sequences:

  • ((0,0)): lists of lengths (2,0).
  • ((0,1)): lists of lengths (1,1).
  • ((1,0)): lists of lengths (1,1).
  • ((1,1)): lists of lengths (2,0).

Summing: (c_2(0)=2), (c_2(1)=4), (c_2(2)=2).
(S_2 = \binom{0}{2}\cdot2 + \binom{1}{2}\cdot4 + \binom{2}{2}\cdot2 = 2).
Formula: (M^{N-1}\frac{N(N-1)}{2} = 2^{1}\cdot\frac{2\cdot1}{2}=2). ✓

Recurrence check:
(c_1(0)=2), (c_1(1)=2).
(c_2(0) = (2-1)\cdot2 + 0 = 2).
(c_2(1) = (2-1)\cdot2 + 2 = 4).
(c_2(2) = (2-1)\cdot0 + 2 = 2). ✓

Collisions per sequence: ((0,0)) and ((1,1)) have 1 collision each; others have 0. Total collisions = 2 = (S_2).
Total probes in unsuccessful searches over all addresses and sequences: (4 \times 2 = 8 = M^N N).
Total probes during insertion (search to end of chain): for ((0,0)) probes = 1; for ((1,1)) probes = 1; others 0. Sum = 2 = (S_2). ✓

All verifications pass.