edited by
9,004 views

2 Answers

Best answer
3 votes
3 votes

ASSUMING that "the hash function is fair & uniformly distributes the universe of keys to all the 10 locations",

the probability should be $6/10$.

Due to uniform distribution, the probability that the new record will be placed to any location $i$ will be same for any $i \ \epsilon \ (1, 2, 3, 4, 5, 6, 7, 8, 9, 10)$ & will be equal to $\frac{1}{10}$.

Now if the hash function will try to place the new record into any of the locations $1, 7, 8, 9, 10$, the record will be redirected to location $2$ due to collision resolution by linear probing. 

And if the hash function will try to place the new record into $2$, since location $2$ is available, the record will go to location $2$.

So The probability of going new record into location $2$, will be same as probability that the output of hash function is any one of $(1, 2, 7, 8, 9, 10)$ out of $(1, 2, 3, 4, 5, 6, 7, ,8 ,9, 10)$, where each location is equally likely.

So the chances will be $\frac{6}{10}$.

0 votes
0 votes

The concept of linear probing is that collisions are resolved by sequentially scanning the array until an empty location is found.
In this case we need to store at Location 2 , so we can go to that location only if we receive locations to be 7,8,9,10,1 ( these locations are already filled so it will scan for an empty location i.e. 2 ) and location 2 of course.

So probability would be = favorable locations/total locations
=6/10
=0.6

Related questions