GATE CSE
First time here? Checkout the FAQ!
x
0 votes
109 views
consider the following keys that are hashed into table in the order using giving hash function h(i)=(2i+5)mod11

12,44,13,88,23,94,11,39,20,16,5 Assume hash tables has locations from 0to 10.If hash table uses chaining to handle the collisions what is the probability of new elements'x' fit inside hash table without any collision

I am getting answer 0.5
asked in Algorithms by Active (1.2k points)  
edited by | 109 views

2 Answers

0 votes
The numbers will be hased as:

12 => 7

44 => 5

13 => 9

88 => 5

23 => 7

94 => 6

11 => 5

39 => 6

20 => 1

16 => 4

5 => 4

Hence, Slots that would be occupied will be (1, 4, 5, 6, 7, 9).

So the required probability= 5/11 = 0.45
answered by Active (1.4k points)  

This is the solution provided by ME so i wanted to check if my approach was correct or not

No, I think the answer should be 0.45 only and not 0.2 as given by ME.

It is asked to find out the probability that a new element fits inside the hash table without any collision.

So, Probability= No. of free slots/Total number of slots

       Probability= 5/11 = 0.45

What do you think?
^ u r right .....
@shivangi acc 2 given solution what ll b " probability that a new element fits inside the hash table with collision."= 1-1/5=4/5 ...... does it making any sense ?/
0 votes
Yep i think 0.45 is correct
answered by Active (1.2k points)  


Top Users Aug 2017
  1. Bikram

    4902 Points

  2. ABKUNDAN

    4704 Points

  3. akash.dinkar12

    3480 Points

  4. rahul sharma 5

    3158 Points

  5. manu00x

    3012 Points

  6. makhdoom ghaya

    2480 Points

  7. just_bhavana

    2388 Points

  8. stblue

    2138 Points

  9. Tesla!

    2060 Points

  10. joshi_nitish

    1758 Points


25,014 questions
32,141 answers
74,825 comments
30,185 users