# solve this Q

192 views in DS
recategorized

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

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$