GATE CSE
First time here? Checkout the FAQ!
x
0 votes
96 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 | 96 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.3k 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 Jun 2017
  1. Bikram

    3704 Points

  2. Hemant Parihar

    1484 Points

  3. junaid ahmad

    1432 Points

  4. Arnab Bhadra

    1408 Points

  5. Niraj Singh 2

    1311 Points

  6. Rupendra Choudhary

    1194 Points

  7. rahul sharma 5

    1132 Points

  8. Debashish Deka

    994 Points

  9. srestha

    932 Points

  10. Arjun

    930 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 19 - 25
  1. Bikram

    1960 Points

  2. Niraj Singh 2

    1306 Points

  3. junaid ahmad

    502 Points

  4. sudsho

    410 Points

  5. akankshadewangan24

    388 Points


23,355 questions
30,066 answers
67,371 comments
28,382 users