in Algorithms retagged by
13,659 views
24 votes
24 votes
Consider a double hashing scheme in which the primary hash function is $h_1(k)= k \text{ mod } 23$, and the secondary hash function is $h_2(k)=1+(k \text{ mod } 19)$. Assume that the table size is $23$. Then the address returned by probe $1$ in the probe sequence (assume that the probe sequence begins at probe $0$) for key value $k=90$ is_____________.
in Algorithms retagged by
by
13.7k views

4 Comments

$h_1(90) = 90\;mod\;23=21$
$h_2(90)=1+(90\;mod\;19)=1+14=15$
Address returned by probe-1 = $(21+15)\;mod\;23=13$
1
1
Then the address returned by probe 1 in the probe sequence 

 what it means ?

0
0

@Ray Tomlinson It means that address of the 2nd element in that probe sequence (i.e. index is i = 1).

1
1

2 Answers

38 votes
38 votes
Best answer
In double hashing scheme, the probe sequence is determined by $(h1(k) + ih2(k))\mod m$, where $i$ denotes the index in probe sequence and $m$ denotes the hash table size.

Given $h1(k)$ and $h2(k)$, we have to determine the second element of the probe sequence (i.e. $i = 1$) for the key $k = 90$.

$(h1(90) + 1*h2(90))\mod 23 = (21 + 15)\mod 23 = 36\mod 23 = 13$
selected by

4 Comments

Silly mistake done by I ignore initial probe start from 0
5
5
"(assume that the probe sequence begins at probe 0)"

What is the significance of this statement? If probe sequence begins at 0, shouldn't i be equal to 2? Please give some reference material for this topic.
0
0
"(assume that the probe sequence begins at probe 0)"
It is nothing but value of i which represent index no start from 0 of  hashing table
1
1
0
0
10 votes
10 votes
for double hashing,h'(k)=(h1(k)+i*h2(k))modm

where h1(90)=90 mod 23,h1(90)=21

and

h2(90)=1+90mod 19

h2(90)=15

i=1

h'(90)=(21+15)mod 23

h'(90)=13

ans is 13
Answer:

Related questions