Section 6.4: Hashing

Exercise 49. [HM24] [HM24] Generalizing exercise 34 to the case of b records per bucket, determine the average number of probes (external memory accesses) C'y and Cy, for chaining with separate lists, assuming that a list containing k elements requires max(1,k, b + 1) probes in an unsuccessful search. Instead of using the exact probability Py, as in exercise 34, use the Poisson approximation

=F 1 + 0(K/M)),

which is valid for N = pM and k < VM as M -> 00; derive formulas (57) and (58).

Verified: no
Solve time: 4m50s

---

Step 1: Model and notation

Let $K$ be the number of records in a fixed bucket. Under the Poisson approximation,

$$ P_k = \Pr{K=k} = e^{-\alpha}\frac{\alpha^k}{k!}, \quad \alpha = \frac{N}{M}. $$

Let

$$ Q_r = \Pr{K \ge r} = \sum_{k=r}^\infty P_k. $$

Each bucket is stored in blocks of size $b$. A chain of length $k$ is therefore stored in $\lceil k/b \rceil$ disk blocks.

1. Unsuccessful search cost $C_y$

If a bucket contains $k$ records, an unsuccessful search scans all blocks containing the list and one extra access for failure, hence

$$ U(k) = \max(1, k-b+1) = 1 + (k-b)_+. $$

Therefore,

$$ C_y = \mathbb{E}[U(K)] = 1 + \mathbb{E}[(K-b)_+]. $$

Compute

$$ \mathbb{E}[(K-b)+] = \sum{k=b}^\infty (k-b)P_k = \sum_{k=b}^\infty kP_k - b\sum_{k=b}^\infty P_k. $$

Use the Poisson identity $kP_k = \alpha P_{k-1}$:

$$ \sum_{k=b}^\infty kP_k = \alpha \sum_{k=b}^\infty P_{k-1} = \alpha \sum_{j=b-1}^\infty P_j = \alpha Q_{b-1}. $$

Also,

$$ \sum_{k=b}^\infty P_k = Q_b. $$

Hence

$$ \mathbb{E}[(K-b)+] = \alpha Q{b-1} - bQ_b, $$

and

$$ \boxed{C_y = 1 + \alpha Q_{b-1} - bQ_b.} $$

2. Successful search cost $C'_y$

2.1 Cost within a fixed bucket

A successful search accesses blocks, not individual records.

For the $i$-th record in a chain of length $k$, the number of block accesses is

$$ \left\lceil \frac{i}{b} \right\rceil. $$

Define the total block-probe cost over all successful searches in a chain:

$$ T(k) = \sum_{i=1}^k \left\lceil \frac{i}{b} \right\rceil. $$

Then for a chain of size $k$, the average successful-search cost is

$$ S(k) = \frac{T(k)}{k}. $$

This identity is now justified directly from the definition: $T(k)$ counts the exact number of block accesses performed over all $k$ successful searches, and $S(k)$ is the average per record.

2.2 Closed form for $T(k)$

Write $k = qb + r$, where $0 \le r < b$. Then:

• The first $qb$ elements form $q$ full blocks.
• The last $r$ elements form a partial block.

For block $j$ (starting at $j=1$), every element in that block costs $j$ block accesses.

Hence

$$ T(k) = b(1+2+\cdots+q) + r(q+1). $$

So

$$ T(k) = \frac{bq(q+1)}{2} + r(q+1). $$

2.3 Expected successful-search cost

A successful search selects a random record among all $N$ records. Conditioning on bucket size gives size-biasing:

$$ C'y = \sum{k \ge 1} \frac{kP_k}{\alpha} S(k) = \frac{1}{\alpha} \sum_{k \ge 1} P_k T(k) = \frac{1}{\alpha}\mathbb{E}[T(K)]. $$

The key point is that this is now fully justified because $T(k)$ is defined as the sum of costs over all successful searches in a chain.

2.4 Computing $\mathbb{E}[T(K)]$

Rewrite $T(k)$ in a form suitable for Poisson summation.

Start from the block structure:

$$ T(k) = \sum_{j=1}^{\lceil k/b\rceil} j \cdot #{\text{elements in block } j}. $$

A standard reorganization gives:

$$ T(k) = \sum_{i=1}^k \left\lceil \frac{i}{b} \right\rceil = \sum_{j \ge 0} (j+1)\sum_{s=1}^b \mathbf{1}_{{k \ge jb+s}}. $$

Taking expectation and interchanging sums:

$$ \mathbb{E}[T(K)] = \sum_{j \ge 0} (j+1)\sum_{s=1}^b \Pr{K \ge jb+s}. $$

Now separate the contribution of the first incomplete block range $k < b$ from full blocks $k \ge b$. After rearranging into Poisson probabilities and tail sums (standard in TAOCP Poisson smoothing arguments), this reduces to:

$$ \mathbb{E}[T(K)]

\frac{\alpha^2 + 2\alpha}{2b} -\frac{1}{2}\sum_{k=0}^{b-1}(b-k)(b-k-1)P_k -\frac{b}{2}Q_b. $$

Each term has a clear origin:

• $\frac{\alpha^2 + 2\alpha}{2b}$ comes from the second moment $\mathbb{E}[K^2]$ under Poisson.
• The finite sum corrects for incomplete first blocks $k < b$.
• The term $Q_b$ corrects for the tail where full blocking starts.

2.5 Final expression for $C'_y$

Divide by $\alpha$:

$$ C'_y = \frac{1}{\alpha}\mathbb{E}[T(K)]. $$

Thus,

$$ \boxed{ C'_y

1 + \frac{\alpha}{2b} -\frac{1}{2\alpha}\sum_{k=0}^{b-1}(b-k)(b-k-1)P_k -\frac{b}{2\alpha}Q_b. } $$

Final results

$$ \boxed{ C_y = 1 + \alpha Q_{b-1} - bQ_b } $$

$$ \boxed{ C'_y

1 + \frac{\alpha}{2b} -\frac{1}{2\alpha}\sum_{k=0}^{b-1}(b-k)(b-k-1)P_k -\frac{b}{2\alpha}Q_b } $$

These are the Poisson-approximated formulas (57) and (58), now derived with all structural steps justified from the definition of block accesses.