Probability

Question

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

Answer 1

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}$

Comments

There are 4 possibility map to location 1

1. directly key goes to 1st slot=1/6

2.map to 0 so goes to 1st means total prob=not map to 0 *  map to 1st slot=5/6*1/6

and so on for 3rd and 4th case also

So total prob=1/6+(1/6*5/6)+(5/6*5/6*1/6)+(5/6*5/6*5/6*1/6)

where I have done mistake please clarify me

---

2. map to 0 so goes to 1st means total prob=not map to 0 *  map to 1st slot=5/6*1/6

Can u explain this ?

---

Map to particular slot=1/6

Not map to particular slot=5/6

Answer 2

Maximum path it can visit is 4,5,0,1

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

Comments

@ srestha goel 

Here uniform probability is given so it may happen that element goes to exact position ie at 1 so how to account this thing into finding probability