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 Aditi Tiwari asked Dec 18, 2015 Aditi Tiwari 731 views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
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}$ Himanshu1 answered Dec 18, 2015 • selected Dec 19, 2015 by Aditi Tiwari Himanshu1 comment Share Follow See all 3 Comments See all 3 3 Comments reply Sourabh Kumar commented May 2, 2016 reply Follow Share 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 0 votes 0 votes Himanshu1 commented May 2, 2016 reply Follow Share 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 ? 0 votes 0 votes Sourabh Kumar commented May 4, 2016 reply Follow Share Map to particular slot=1/6 Not map to particular slot=5/6 0 votes 0 votes Please log in or register to add a comment.
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 srestha answered Dec 18, 2015 srestha comment Share Follow See 1 comment See all 1 1 comment reply Aditi Tiwari commented Dec 18, 2015 reply Follow Share @ 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 0 votes 0 votes Please log in or register to add a comment.