TAOCP 6.4 Exercise 71

Let $M$ denote the number of hash addresses and let $N$ denote the number of keys stored, with load factor $\alpha = \frac{N}{M}.$ Algorithm C is the separate chaining method described in Section 6.

taocpmathematicsalgorithmsvolume-3project

Section 6.4: Hashing

Exercise 71. [40] [40] Experiment with the behavior of Algorithm C when it has been adapted to external searching as described in the text.

Verified: yes
Solve time: 1m12s

Setup

Let $M$ denote the number of hash addresses and let $N$ denote the number of keys stored, with load factor

$\alpha = \frac{N}{M}.$

Algorithm C is the separate chaining method described in Section 6.4, where each table entry points to a linked list of records having that hash address. In the external version, each record access corresponds to an external memory transfer.

Assume uniform hashing, so each key is equally likely to hash to any of the $M$ addresses independently. Let $L_i$ be the length of the chain at address $i$.

The external-cost model counts one probe per accessed record, including the initial access to the bucket entry and each subsequent record examined in the chain.

The goal is to describe the behavior of Algorithm C under this external adaptation, in particular the expected number of probes for successful and unsuccessful searches and the effect of clustering as $\alpha$ varies.

Solution

For a fixed bucket $i$, each of the $N$ keys independently hashes to $i$ with probability $1/M$, hence

$L_i \sim \mathrm{Binomial}(N, 1/M).$

Therefore,

$\mathbb{E}[L_i] = \frac{N}{M} = \alpha.$

An unsuccessful search examines the entire chain at the computed address $h(K)$. The number of probes equals $1 + L_i$, since the bucket entry is accessed and then all $L_i$ records are inspected.

Taking expectation,

$\mathbb{E}[\text{unsuccessful probes}] = 1 + \mathbb{E}[L_i] = 1 + \alpha.$

For a successful search, the sought key is equally likely to occupy any position in its chain. Conditioned on chain length $L_i = \ell$, the average position of a key in the list is

$\frac{1 + 2 + \cdots + \ell}{\ell} = \frac{\ell + 1}{2}.$

Thus the number of record probes, excluding the initial bucket access, is $(\ell+1)/2$, and including it is $1 + (\ell+1)/2$.

Taking expectation and using linearity,

= 1 + \frac{\mathbb{E}[L_i] + 1}{2} = 1 + \frac{\alpha + 1}{2} = \frac{\alpha + 3}{2}.$$

External interpretation In external storage, the dominant cost is typically the number of distinct record transfers. Under the model where each node access costs one transfer, the successful search cost grows linearly with $\alpha$ but with smaller coefficient than unsuccessful search. Insertion into Algorithm C places the new record at the head of the chain, so insertion cost is constant: one hash computation and one pointer update, hence one bucket access plus one record write. ### Behavior as $\alpha$ increases As $\alpha$ increases, chain lengths become more variable, with variance

$$\mathrm{Var}(L_i) = N\frac{1}{M}\left(1 - \frac{1}{M}\right) \approx \alpha.$$ Thus fluctuations in external access cost grow as $\sqrt{\alpha}$ in standard deviation, while mean cost grows linearly. This causes long chains to dominate worst-case performance even when average performance remains proportional to $\alpha$. ## Verification The distribution $L_i \sim \mathrm{Binomial}(N,1/M)$ follows directly from independence of key placements under uniform hashing. The expectation computation uses linearity of expectation applied to binomial random variables. The successful-search cost is derived from the identity that the average position in a list of length $\ell$ is $(\ell+1)/2$, which follows from the sum of the first $\ell$ integers. Both expected cost formulas reduce correctly in boundary cases: when $\alpha = 0$, unsuccessful cost is $1$ and successful cost is $3/2$, matching a single-access empty-chain model; when $\alpha$ grows large, both expressions scale linearly in $\alpha$, consistent with collision-dominated behavior. This completes the solution. ∎