704 views
2 votes
2 votes
In a hash table of size 6 currently the locations 0,2,4 and 5 are occupied. The probability of a new record going into location 1 with a hash function resolving collisions by linear probing is (assume uniform hashing)
a)2/3
b)1/3
c)1
d) 1/6

2 Answers

Best answer
4 votes
4 votes

OPTION A

With uniform probability 1/6 ,it may go to any of the slot numbered 1 , 0 , 4, 5  {In any of these case it will end up in slot 1 , with linear probing.}

So, total probability  = $\frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} = \frac{4}{6} = \frac{2}{3}$

selected by
2 votes
2 votes
Maximum path it can visit is 4,5,0,1

So, prob of new record goes to location 1 is 4/6 =2/3

No related questions found