TAOCP 6.4 Exercise 17
In double hashing with open addressing, a key $K$ is examined in the sequence of table positions h_1(K),\; h_1(K) + h_2(K),\; h_1(K) + 2h_2(K),\; \dots \pmod{M}, so that $h_2(K)$ determines the step s...
Exercise 17. [15] [15] Why not simply define h2(K) = hi(K) in (25), when hi(K) 4 0?
- [21] Is (31) better or worse than (30), as a substitute for lines 10-13 of Program D? Give your answer on the basis of the average values of A, $1, and C.
Verified: no
Solve time: 1m19s
Solution
In double hashing with open addressing, a key $K$ is examined in the sequence of table positions
$$ h_1(K),; h_1(K) + h_2(K),; h_1(K) + 2h_2(K),; \dots \pmod{M}, $$
so that $h_2(K)$ determines the step size used to traverse the table when a collision occurs at $h_1(K)$.
If one sets $h_2(K) = h_1(K)$ whenever $h_1(K) \neq 0$, then the probe sequence becomes
$$ h_1(K),; 2h_1(K),; 3h_1(K),; \dots \pmod{M}. $$
All keys sharing the same initial value $h_1(K)$ generate exactly the same sequence of probe positions, independent of any further structure of $K$. The collision resolution mechanism then depends only on $h_1(K)$ and introduces no additional key-dependent variation beyond the initial address.
When $M$ and $h_1(K)$ are relatively prime, this sequence is a permutation of all residue classes modulo $M$, so every table position is eventually visited. However, the order of visits is fixed once $h_1(K)$ is fixed, so every key with the same initial hash value experiences identical probing behavior. This reproduces the same clustering phenomenon that occurs in single hashing with a fixed probe sequence, since collisions among such keys are resolved in a completely synchronized manner.
When $\gcd(h_1(K), M) \neq 1$, the sequence
$$ j h_1(K) \pmod{M} $$
visits only $M / \gcd(h_1(K), M)$ distinct positions, so part of the table is never examined at all. In that case insertion may fail even when free locations exist outside the reachable residue class.
Thus choosing $h_2(K) = h_1(K)$ removes the purpose of introducing a second hash function, which is to decouple probe sequences from initial hash values and thereby reduce systematic clustering. The resulting method behaves like a fixed permutation of linear probing determined solely by $h_1(K)$, and does not improve the distribution of probes among colliding keys.
This completes the proof. ∎