TAOCP 6.4 Exercise 20
In the modified Algorithm D, step D3 sets c\leftarrow0, and each time step D4 is entered, the counter is first increased:
Exercise 20. [M25] [M25] (R. Krutar.) Change Algorithm D as follows, avoiding the hash function he(K): In step D3, set c + 0; and at the beginning of step D4, set c + c+ 1. Prove that if M = 2™, the corresponding probe sequence hi(K), (hi(K), 1) mod M,
Les (hi (K), (*)) mod M will be a permutation of {0,1,...,-, 1}. When this “quadratic probing” method is programmed for MIX, how does it compare with the three programs considered in Fig. 42, assuming that the algorithm behaves like random probing with secondary clustering?
- [20] Suppose that we wish to delete a record from a table constructed by Algorithm D, marking it “deleted” as suggested in the text. Should we also decrease the variable N that is used to govern Algorithm D?
Verified: yes
Solve time: 4m18s
Solution
In the modified Algorithm D, step D3 sets
$$ c\leftarrow0, $$
and each time step D4 is entered, the counter is first increased:
$$ c\leftarrow c+1. $$
Therefore the successive decrements applied to the address are
$$ 1,2,3,\ldots, $$
and the probe sequence becomes
$$ h_1(K),; (h_1(K)-1)\bmod M,; (h_1(K)-(1+2))\bmod M,; (h_1(K)-(1+2+3))\bmod M,\ldots $$
Since
$$ 1+2+\cdots+j=\frac{j(j+1)}2, $$
the $j$th probe is
$$ \left(h_1(K)-\frac{j(j+1)}2\right)\bmod M, \qquad j\ge0. $$
Hence it is enough to show that when $M=2^m$, the residues
$$ T_j=\frac{j(j+1)}2\pmod{2^m}, \qquad 0\le j<2^m, $$
are all distinct.
Distinctness of the triangular numbers modulo $2^m$
Suppose
$$ \frac{a(a+1)}2\equiv\frac{b(b+1)}2\pmod{2^m}, $$
where
$$ 0\le a,b<2^m. $$
Multiplying by $2$ gives
$$ a(a+1)\equiv b(b+1)\pmod{2^{m+1}}, $$
hence
$$ (a-b)(a+b+1)\equiv0\pmod{2^{m+1}}. $$
Therefore
$$ 2^{m+1}\mid(a-b)(a+b+1). $$
We shall prove that this implies $a=b$.
Set
$$ d=a-b. $$
Assume $d\neq0$. Since $0\le a,b<2^m$,
$$ -(2^m-1)\le d\le2^m-1, $$
so
$$ |d|<2^m. $$
Write
$$ d=2^ru, $$
where $u$ is odd and $r=\nu_2(d)$. Because $|d|<2^m$,
$$ r\le m-1. $$
Now
$$ a+b+1=(a-b)+(2b+1) =d+(2b+1). $$
Since $2b+1$ is odd, two cases arise.
Case 1: $r\ge1$
Then $d$ is even. Hence
$$ a+b+1=\text{even}+\text{odd}, $$
which is odd. Therefore
$$ \nu_2(a+b+1)=0. $$
Consequently
$$ \nu_2\bigl((a-b)(a+b+1)\bigr) =\nu_2(a-b) =r \le m-1, $$
which contradicts
$$ 2^{m+1}\mid(a-b)(a+b+1). $$
Thus $r\ge1$ is impossible.
Case 2: $r=0$
Then $d=a-b$ is odd. Hence $a$ and $b$ have opposite parity, so
$$ a+b+1 $$
is even.
Because $a+b+1$ is even, write
$$ a+b+1=2^sv, $$
with $v$ odd and $s\ge1$.
Since $a-b$ is odd,
$$ \nu_2(a-b)=0, $$
and therefore
$$ \nu_2\bigl((a-b)(a+b+1)\bigr)=s. $$
The divisibility condition gives
$$ s\ge m+1. $$
Hence
$$ 2^{m+1}\mid(a+b+1). $$
But
$$ 1\le a+b+1\le(2^m-1)+(2^m-1)+1 =2^{m+1}-1. $$
Thus $a+b+1$ is a positive integer strictly between $0$ and $2^{m+1}$. Such a number cannot be divisible by $2^{m+1}$. This contradiction shows that $r=0$ is impossible.
Both cases lead to contradictions. Therefore $d=0$, so
$$ a=b. $$
Hence
$$ \frac{j(j+1)}2, \qquad 0\le j<2^m, $$
give $2^m$ distinct residues modulo $2^m$. Since there are exactly $2^m$ residues modulo $2^m$, they form a permutation of
$$ {0,1,\ldots,2^m-1}. $$
Therefore the probe sequence
$$ h_1(K),; (h_1(K)-1)\bmod M,; (h_1(K)-3)\bmod M,; (h_1(K)-6)\bmod M,\ldots $$
visits every location exactly once whenever $M=2^m$.
$\square$
Comparison with the MIX programs of Fig. 42
The three programs of Fig. 42 correspond to linear probing, random probing, and double hashing.
For quadratic probing, the address changes are generated recursively. After a collision one executes only
$$ c\leftarrow c+1, $$
followed by subtraction of $c$ from the current address. No second hash value needs to be computed or stored.
Hence:
- Compared with linear probing.
Linear probing uses the simplest address computation, but it suffers from primary clustering. Quadratic probing eliminates primary clustering and produces only secondary clustering. Under the hypothesis of the exercise, its search behavior is essentially that of random probing with secondary clustering, so fewer probes are required when the table becomes heavily loaded. 2. Compared with random probing.
Random probing requires generation or retrieval of a pseudorandom increment at every collision. Quadratic probing replaces this by the deterministic sequence
$$ 1,2,3,\ldots, $$
so the address computation is simpler while, by assumption, the statistical behavior is the same. 3. Compared with double hashing.
Double hashing requires evaluation of a second hash function $h_2(K)$ and addition of multiples of $h_2(K)$. In the MIX programs of Fig. 42 this extra arithmetic accounts for several instructions per collision. Quadratic probing needs only an increment of the counter $c$ and a subtraction from the current address. Thus the per-collision instruction count is smaller.
Therefore, assuming that quadratic probing behaves like random probing with secondary clustering, its average number of probes is essentially the same as that of double hashing, but the address-generation mechanism is simpler. Consequently a MIX implementation of quadratic probing should run slightly faster than the double-hashing program, considerably faster than the random-probing program, and should outperform linear probing whenever primary clustering becomes significant.