TAOCP 6.4 Exercise 66
Assume an open addressing scheme using Algorithm L or Algorithm D.
Exercise 66. [25] [25] (Ole Amble, 1973.) Is it possible to insert keys into an open hash table making use also of their numerical or alphabetic order, so that a search with Algorithm L or Algorithm D is known to be unsuccessful whenever a key smaller than the search argument is encountered?
Verified: no
Solve time: 9m25s
Solution
Assume an open addressing scheme using Algorithm L or Algorithm D. Let the hash function be $h(K)$ and let the probe sequence generated for a key $K$ be denoted by
$$ P(K,0), P(K,1), P(K,2), \dots $$
where $P(K,0)=h(K)$ and subsequent terms follow the rule of linear probing or double hashing.
The requirement states that a search for a key $K$ is declared unsuccessful whenever a key smaller than $K$ is encountered during the probe sequence.
Consider two distinct keys $K_1 < K_2$ such that
$$ h(K_1)=h(K_2). $$
Such a pair exists whenever the table has more keys than hash values, which is the nondegenerate case for hashing.
Insert $K_1$ first using Algorithm L or Algorithm D. During insertion, $K_1$ is placed in the first empty cell of its probe sequence. Since the table is initially empty, $K_1$ occupies the first position encountered in the sequence
$$ P(K_1,0), P(K_1,1), \dots $$
Denote this position by $P(K_1,i)$ for the smallest $i$ such that the cell is empty at insertion time.
Next insert $K_2$. Its probe sequence is identical to that of $K_1$ because both keys have the same initial hash value and the same deterministic probing rule, hence
$$ P(K_2,j)=P(K_1,j) \quad \text{for all } j \ge 0. $$
During insertion of $K_2$, the first occupied cell encountered in its probe sequence is the one containing $K_1$. Since that cell is occupied, Algorithm L or Algorithm D continues probing until it finds the first empty location and stores $K_2$ there.
Now consider a search for $K_2$. The search follows the same probe sequence
$$ P(K_2,0), P(K_2,1), \dots $$
The first nonempty cell encountered is the one containing $K_1$, and since $K_1 < K_2$, the stated rule forces the search to terminate immediately with an unsuccessful result upon encountering $K_1$.
However, $K_2$ is present in the table at a later position in the same probe sequence. The search therefore fails even though the key exists in the table, contradicting correctness.
This contradiction shows that no open addressing scheme using Algorithm L or Algorithm D can guarantee the stated property.
This completes the proof. ∎