Exercise 11.4.4

$\star$ Suppose that we use double hashing to resolve collisions ­ that is, we use the hash function $h(k,i) = (h_1(k) + ih_2(k)) \bmod{m}$. Show that if $m$ and $h_2(k)$ have greatest common divisor $d \ge 1$ for some key $k$, then an unsuccessful search for key $k$ examines $(1/d)$th of the hash table before returning to slot $h_1(k)$. Thus, when $d = 1$, so that $m$ and $h_2(k)$ are relatively prime, the search may examine the entire hash table. (Hint: See Chapter 31.)