TAOCP 6.4 Exercise 16
The computation performed by Program L does not fail arithmetically when $K = 0$.
Exercise 16. [10] [10] Program L says that K should not be zero. But doesn’t it actually work even when K is zero?
Verified: yes
Solve time: 1m02s
The computation performed by Program L does not fail arithmetically when $K = 0$. The arithmetic steps that transform $K$ into a hash address still produce a well-defined value, and any subsequent indexing or comparison operations remain syntactically valid.
The restriction $K \neq 0$ is imposed because the value $0$ is typically reserved as a structural marker in the representation used by Algorithm L, commonly indicating an empty table position or a null link. If $K = 0$ were allowed as a legitimate key, the algorithm could not distinguish a stored key equal to zero from an unused location, and search or insertion would become ambiguous. This breaks the correctness condition that each occupied location must be unambiguously identifiable during retrieval. ∎