19 views
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))$ $mod$ $m$.Show that if $m$ and $h_2(k)$ have greatest common divisor $d\geq 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.
| 19 views