The Gateway to Computer Science Excellence
0 votes
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.
in Algorithms by Boss (41.9k points) | 19 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,458 answers
100,256 users