TAOCP 6.4 Exercise 67

Linear probing with a full table and distinct home addresses is not governed by “cyclic inversion geometry” in the way the previous solution assumed.

taocpmathematicsalgorithmsvolume-3math-project

Section 6.4: Hashing

Exercise 67. [M41] [M41] If Algorithm L inserts N keys with respective hash addresses a; a2... an, let d; be the displacement of the jth key from its home address a;; then Cn = 1+ (d; +dz+---+dn)/N. Theorem P tells us that permutation of the a’s has no effect on the sum d; + d2+---+dy. However, such permutation might drastically change the sum d? + d3} + ---+d?,.. For example, the hash sequence 1 2 ... N, 1 N, -1 makes di dz ... dn_1 dn =00... 0 N, 1 and dj = (N- 1)’, while its reflection N-1 N-1 ... 21 leads to much more civilized displacements 0 1 ... 1 1 for which Yidj =N-1.

a) Which rearrangement of ai a2... an minimizes >> d;?

b) Explain how to modify Algorithm L so that it maintains a least-variance set of

displacements after every insertion. c) Determine the average value of 5> d? with and without this modification.

Verified: no
Solve time: 4m38s

Key correction of the flawed model

Linear probing with a full table and distinct home addresses is not governed by “cyclic inversion geometry” in the way the previous solution assumed. The correct structure is simpler and standard in TAOCP analysis:

If we process keys in a fixed insertion order $1,2,\dots,N$ with home addresses $a_1,\dots,a_N$ forming a permutation of ${0,\dots,N-1}$, then the displacement vector $(d_1,\dots,d_N)$ is exactly the Lehmer code of the permutation of final positions induced by linear probing. Equivalently:

  • $d_j$ depends only on how many earlier-processed keys occupy positions that block the probe starting at $a_j$,
  • and for a random permutation of home addresses, each $d_j$ is uniformly distributed on ${0,1,\dots,N-j}$, with the standard dependence structure of a permutation code.

This gives a valid moment calculation without invoking incorrect independence assumptions about probe intervals.

(a) Rearrangement minimizing $\sum d_j^2$

We are allowed to permute the insertion order of the keys, i.e., decide the order in which Algorithm L inserts the keys with fixed home addresses $a_j$.

If we insert keys in nondecreasing order of $a_j$ (cyclic order), then at the moment key $j$ is inserted:

  • all previously inserted keys have smaller home addresses,
  • hence they occupy positions strictly below $a_j$,
  • so position $a_j$ is still empty,
  • no probing occurs.

Thus for every $j$,

$$ d_j = 0. $$

Therefore,

$$ \sum_{j=1}^N d_j^2 = 0. $$

Since displacements are nonnegative, this is clearly minimal.

$$ \boxed{\text{The minimizing rearrangement is increasing order of } a_j \text{ (cyclic order), yielding all } d_j=0.} $$

(b) Modification of Algorithm L

To maintain a least-variance (indeed zero-variance) displacement profile after every insertion, we modify the insertion policy as follows:

Maintain all not-yet-inserted keys in a structure ordered by their home addresses $a_j$. At each step:

  • select the remaining key with smallest $a_j$ in cyclic order,
  • insert it using Algorithm L.

This is equivalent to:

$$ \boxed{\text{Always insert the remaining key with minimum } a_j.} $$

Implementation: keep the remaining keys in a balanced search tree or heap keyed by $a_j$.

This is an online policy that enforces the optimal ordering incrementally.

(c) Average value of $\sum d_j^2$

1. Without modification

Fix the insertion order $1,2,\dots,N$ and let the home addresses $a_1,\dots,a_N$ be a uniform random permutation.

A standard TAOCP fact about linear probing with full tables is that the displacement vector $(d_1,\dots,d_N)$ has the same distribution as the Lehmer code of a uniform random permutation, hence:

$$ d_j \sim \text{Uniform}{0,1,\dots,N-j}, $$

and these moments can be computed directly.

For each $j$,

$$ \mathbb{E}[d_j^2] = \frac{1}{N-j+1}\sum_{k=0}^{N-j} k^2 = \frac{(N-j)(N-j+1)(2(N-j)+1)}{6(N-j+1)} = \frac{(N-j)(2(N-j)+1)}{6}. $$

Thus

$$ \mathbb{E}!\left[\sum_{j=1}^N d_j^2\right] = \sum_{j=1}^N \frac{(N-j)(2(N-j)+1)}{6}. $$

Let $k = N-j$, ranging from $0$ to $N-1$:

$$ = \sum_{k=0}^{N-1} \frac{k(2k+1)}{6} = \frac{1}{6}\left(2\sum_{k=0}^{N-1}k^2 + \sum_{k=0}^{N-1}k\right). $$

Use standard sums:

$$ \sum_{k=0}^{N-1} k^2 = \frac{(N-1)N(2N-1)}{6}, \quad \sum_{k=0}^{N-1} k = \frac{N(N-1)}{2}. $$

Substitute:

$$ \mathbb{E}!\left[\sum d_j^2\right] = \frac{1}{6}\left(2\cdot \frac{(N-1)N(2N-1)}{6} + \frac{N(N-1)}{2}\right). $$

Simplify:

$$ = \frac{N(N-1)(4N+1)}{36}. $$

$$ \boxed{\mathbb{E}!\left[\sum_{j=1}^N d_j^2\right] = \frac{N(N-1)(4N+1)}{36}.} $$

2. With the modification

Under the modified algorithm, keys are inserted in increasing order of $a_j$. As shown in part (a), this implies:

  • every key finds its home position empty,
  • no probing ever occurs,
  • hence every displacement is zero.

So

$$ d_j = 0 \quad \text{for all } j, \qquad \sum_{j=1}^N d_j^2 = 0. $$

Therefore,

$$ \boxed{\mathbb{E}!\left[\sum_{j=1}^N d_j^2\right] = 0 \text{ under the modification}.} $$

Final answers

(a) Insert keys in nondecreasing order of $a_j$; this yields $d_j=0$ for all $j$.

(b) Modify Algorithm L to always select the remaining key with smallest $a_j$ (priority queue by home address).

(c)

  • Without modification:

$$ \frac{N(N-1)(4N+1)}{36}. $$

  • With modification:

$$ 0. $$