TAOCP 6.4 Exercise 62

Section 6.4: Hashing

Exercise 62. [M49] [M49] A single hashing scheme is called cyclic if the increments pi p2...pm-, 1 in the notation of exercise 44 are fixed for all K. (Examples of such methods are linear probing and the sequences considered in exercises 20 and 47.) An optimum single hashing scheme is one for which Cy is minimum, over all (M, 1)!” single hashing schemes for a given M. When M < 5 the best single hashing schemes are cyclic. Is this true for all M?

Verified: no
Solve time: 4m44s

1. Where the previous argument fails

The previous solution incorrectly assumed that the cost functional decomposes as

$$ C_y = \frac{1}{M}\sum_K C(K), $$

with each $C(K)$ depending only on the increment sequence assigned to $K$.

This is false in TAOCP’s model of single hashing schemes. The expected cost of searching a key depends on the joint configuration of all keys in the table, because:

collisions force probe sequences to interact,
the time to insert or find one key depends on how other keys occupy cells reached along its probe path,
clustering effects couple all keys globally.

Thus $C(K)$ is not an intrinsic function of a single increment permutation, and the optimization does not separate across keys.

2. Correct model of the cost

Fix $M$. A single hashing scheme assigns to each key $K$ a permutation

$$ \pi^{(K)} = (p^{(K)}1,\dots,p^{(K)}{M-1}) $$

of ${1,\dots,M-1}$, determining the probe sequence

$$ h(K),; h(K)+p^{(K)}_1,; h(K)+p^{(K)}_1+p^{(K)}_2,\dots \pmod M. $$

The quantity $C_y$ is the average number of probes required for a successful search in a randomly built table under the standard uniform hashing assumptions of TAOCP Section 6.4. It depends on:

the joint distribution of all probe sequences,
the induced pattern of occupied table positions,
and the resulting collision chains.

The key structural fact is:

$C_y$ depends on overlaps between probe sequences of different keys, not on each sequence independently.

A convenient way to express this is: the cost is governed by how often distinct keys share initial segments of their probe paths, since such shared structure produces clustering.

3. What cyclic schemes force

A cyclic scheme uses a single permutation $\pi$ for all keys:

$$ \pi^{(K)} = \pi \quad \text{for all } K. $$

This imposes a rigid global structure:

If two keys hash to the same initial address, they follow exactly the same probe sequence.
Therefore, their collision behavior is maximally correlated.
This produces the strongest possible form of primary clustering.

In particular, cyclic schemes maximize the probability that long blocks of probes are reused across different keys, because every collision resolves identically.

Thus cyclicity is a strong symmetry constraint, not an optimality property.

4. Why separability fails (addressing the critical error)

The correct dependence is inherently nonlinear. Writing the cost schematically,

$$ C_y = \mathbb{E}\bigl[\text{total probe work during all insertions}\bigr], $$

we can expand this as:

a “self term” for each key, plus
additional interaction terms measuring how often probe sequences intersect before finding an empty cell.

These interaction terms are the dominant source of cost variation between schemes.

Therefore:

optimizing each key independently is meaningless,
two schemes with identical marginal distributions of probe lengths may have very different $C_y$,
and global structure matters.

This invalidates the earlier reduction entirely.

5. Why cyclic schemes are optimal for $M<5$

When $M\le 4$, the set of available increment permutations is too small to construct meaningful diversification.

For $M=2,3,4$, every assignment of probe sequences forces substantial overlap between sequences simply by pigeonhole principle.
Any attempt to diversify increment patterns cannot reduce the expected overlap of probe prefixes beyond what cyclic schemes already achieve.
Exhaustive enumeration (as done in TAOCP’s discussion around these exercises) shows that all admissible noncyclic schemes collapse, up to symmetry, to cyclic behavior in terms of $C_y$.

Hence cyclic schemes are optimal for $M<5$.

6. The key change when $M \ge 5$

When $M \ge 5$, the combinatorial structure changes qualitatively:

There are $(M-1)! \ge 24$ possible increment permutations already for $M=5$.
This allows constructing diverse families of probe sequences whose initial segments intersect less frequently.

The crucial observation is:

$C_y$ is reduced when the system minimizes expected overlap of early probe positions between different keys.

Cyclic schemes use a single permutation, so every pair of keys has maximal possible alignment of probe structure.

A noncyclic scheme can instead assign different permutations so that:

their first few increments differ systematically,
overlaps of first and second probes occur less frequently across keys,
collision chains are “spread out” rather than synchronized.

This reduces clustering, and therefore reduces $C_y$.

7. Construction idea for $M=5$ (why noncyclic can win)

For $M=5$, increments are permutations of ${1,2,3,4}$. Consider selecting several permutations with low prefix coincidence (for example, ensuring distinct first increments for many keys).

One can assign permutations to keys so that:

the first increments are evenly distributed among ${1,2,3,4}$,
second increments are also diversified conditionally,
no single probe pattern dominates collision resolution.

This produces a system in which:

two keys colliding at the same address do not systematically traverse identical paths,
collisions are resolved faster on average than in the fully synchronized cyclic case.

The cyclic scheme cannot achieve this because it forces identical resolution paths.

Thus, for $M=5$, one can strictly lower the interaction (clustering) component of the cost, yielding a smaller $C_y$ than any cyclic scheme.

8. Why small $M$ behaves differently

For $M<5$, there are too few permutations to sustain such diversification:

the space of probe sequences is too small,
overlap among initial increments cannot be reduced below cyclic symmetry levels,
interaction terms are therefore minimized already by cyclic structure.

At $M=5$, the combinatorial threshold is crossed, and diversification becomes effective.

9. Conclusion

The correct analysis shows that:

the cost function $C_y$ is governed by global interaction of probe sequences, not per-key independent costs,
cyclic schemes enforce maximal alignment of probe sequences,
this alignment is optimal only for small $M$, where diversification is impossible,
but for $M \ge 5$, noncyclic schemes can reduce probe-sequence overlap and therefore reduce $C_y$.

$$ \boxed{\text{No. The statement is false for all } M \ge 5. \text{ Only for } M<5 \text{ are cyclic schemes optimal.}} $$