search
Log In

1 Answer

0 votes

Double hashing = H'(k , i) = (H1(k) + i*H2(k)) mod n

given , H(k) = k mod 11

            H2(k) = 5-(kmod5)

            n denotes The size of the hash table which is 11

            i denotes the collision number

 Insert (16) ---> H'(16,0) = (16 mod 11) + 0*(5-(11 mod 5)) = 5  [ 16 is inserted at index '5']

 Insert (23) ---> H'(23,0) = (23 mod 11) + 0*(5-(23 mod 5)) = 1   [ 23 is inserted at index '1']

 Insert(9) ------> H'(9,0) =   (9 mod 11) + 0*(5-(9 mod 5)) = 9       [ 9 is inserted at index '9']

 Insert(34)------> H'(34,0) = (34 mod 11) + 0*(5-(23 mod 5)) = 1   [  As 23 is already inserted at index '1']

 next prob-sequence (collision no 1)  ---------> H'(34,1) = (34 mod 11) + 1*(5-(34 mod 5)) = 2 ['34 ' is inserted at index '2']

 Insert(12)------> H'(12,0) = (12 mod 11) + 0*(5-(12 mod 5)) = 1   [  As 23 is already inserted at index '1']

 next prob-sequence (collision no 1)  ---------> H'(12,1) = (12 mod 11) + 1*(5-(12 mod 5)) = 4 ['12 ' is inserted at index '4']

 Insert(56)------> H'(56,0) = (56 mod 11) + 0*(5-(56 mod 5)) = 1   [  As 23 is already inserted at index '1']

 next prob-sequence (collision no 1)  ---------> H'(56,1) = (56 mod 11) + 1*(5-(56 mod 5)) = 5 [As 16 is already inserted at       index '5']

 

next prob-sequence (collision no 2)  ---------> H'(56,2) = (56 mod 11) + 2*(5-(56 mod 5)) = 9 ['56 ' is inserted at index '9'].

 

therefore 56 is inserted at index 9 (Location 10)

 

 

 

 

 


edited by
0
but Index 9 is already occupied By key 9

i think option A will be correct

Related questions

2 votes
2 answers
1
573 views
Consider double hashing of the form $h(k,i)=(h_1(k)+ih_2(k)) \text{mod m}$ where $h_{1}(k) = \text{k mod m} \ , \ \ h_{2}(k)=1+(\text{k mod n})$ where $n=m-1$ and $m=701$. For $k=123456$, what is the difference between first and second probes in terms of slots? $255$ $256$ $257$ $258$
asked Jul 2, 2019 in Algorithms Arjun 573 views
0 votes
1 answer
2
71 views asked Jan 17, 2019 in DS kallu singh 71 views
0 votes
0 answers
3
41 views asked Nov 16, 2018 in Operating System kallu singh 41 views
0 votes
1 answer
4
169 views
Question:- Consider the following program fragment a = 0 for (x = 1; x < 31; ++x) for (y = 1; y < 31; ++y) for (z = 1; z < 31; ++z) if (((x + y + z)%3) = =0) a = a + 1; printf("%d”, a); the output of the above given program is Option (A) : 3000 Option (B) : 1000 Option(C) : 27000 Option(D) : None of these
asked Sep 8, 2018 in Programming kallu singh 169 views
...