TAOCP 6.4 Exercise 15
Let the hash table contain $M$ locations and let $N$ be the number of keys currently stored.
Exercise 15. [16] [16] Why is it a good idea for Algorithm L and Algorithm D to signal overflow when N = M, 1 instead of when N = M?
Verified: yes
Solve time: 1m19s
Solution
Let the hash table contain $M$ locations and let $N$ be the number of keys currently stored. In Algorithm L and Algorithm D, search and insertion proceed by following a probing sequence starting at a hash address and moving through a deterministic sequence of locations until either the key is found or an empty location is encountered.
Both algorithms rely on the structural fact that an unsuccessful search terminates upon encountering a location that is known to be empty. This termination criterion is correct only when at least one empty location is guaranteed to exist in the table.
If the condition for overflow were taken to be $N = M$, then the table could enter a state in which every location is occupied. In this situation, a probing sequence starting from any address produces a permutation of the $M$ locations, and no empty location is ever encountered. The algorithm would then have no structural stopping condition based on emptiness and would be forced to detect termination only by recognizing that the probe sequence has returned to its starting point. This requires additional bookkeeping and complicates both Algorithm L and Algorithm D, since neither is designed to test for complete cycle detection at every insertion or search step.
If instead overflow is signaled when $N = M - 1$, then at least one location is always unoccupied during normal operation. For any probing method used in Section 6.4, the probe sequence can be regarded as a walk through a finite directed graph in which every node has outdegree $1$ determined by the hash function and collision resolution rule. Starting from any initial address, the sequence must eventually repeat a location if no empty slot is encountered, but because at least one empty location exists, the sequence must enter an empty location before any repetition can complete a full cycle of length $M$. The presence of an empty location therefore provides a guaranteed termination condition for unsuccessful searches and insertion attempts.
Under this invariant, Algorithm L can always conclude insertion failure precisely upon encountering the empty location that signals overflow, and Algorithm D can maintain deletions without needing to distinguish between a genuinely full table and a cyclic probe failure. The invariant also ensures that no probe sequence must traverse all $M$ locations, so the algorithms avoid the degenerate case in which every location is inspected without finding an empty one.
Thus, signaling overflow at $N = M - 1$ preserves the correctness of the empty-slot stopping rule and prevents probe sequences from degenerating into full-table cycles that require additional cycle-detection logic.
This completes the proof. ∎