in DS edited by
16,845 views
37 votes
37 votes

Consider a hash table with $100$ slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first $3$ slots are unfilled after the first $3$ insertions?

  1. $(97 \times 97 \times 97) / 100^3$
  2. $(99 \times 98 \times 97) / 100^3$
  3. $(97 \times 96 \times 95) / 100^3$
  4. $(97 \times 96 \times 95 / (3! \times 100^3)$
in DS edited by
16.8k views

4 Comments

Important point is 

 Collisions are resolved using chaining

10
10
in this how to approach if linear probing given?

i dont understand below comments about solution of linear probing.
0
0
can someone share the answer we get, using linear probing?
0
0

I think 

C(97,3) / C(100,3)

@Arjun sir please confirm once

1
1

3 Answers

104 votes
104 votes
Best answer
We have $100$ slots each of which are picked with equal probability by the hash function (since hashing is uniform). So, to avoid first $3$ slots, the hash function has to pick from the remaining $97$ slots. And repetition is allowed, since chaining is used- meaning a list of elements are stored in a slot and not a single element.

So, required probability $= \frac{97}{100} \times  \frac{97}{100} \times  \frac{97}{100}$

$= (97 \times 97 \times 97)/100^3$

Correct Answer: $A$
edited by
by

4 Comments

yes, just that you have to do it more formally.
4
4
okay got it sir.
1
1
How to solve this using reverse probability?
0
0
15 votes
15 votes
for the first insertion we have (4-100) 97 slots out of 100 slots for the second insertion also we have (4-100) 97 slots out of 100 because here chaining is used to resolve collision it means 2nd element may also get the slot where the first element already have and 3rd  insertion also have  (4-100) 97 slots out of 100 slots it means 3rd element may also get the slot  first and second elements already have. it is just like repetitions.  so answer should be       97/100 * 97/100 * 97/100

1 comment

@Murali

Completely satisfied by ur approach.

Nice explanation thank you. !

0
0
3 votes
3 votes

Simple Uniform hashing function is a hypothetical hashing function that evenly distributes items into the slots of a hash table. Moreover, each item to be hashed has an equal probability of being placed into a slot, regardless of the other elements already placed. (Source: https://en.wikipedia.org/wiki/SUHA_%28computer_science%29).

Probability that the first 3 slots are unfilled after the first 3 insertions = 
                (probability that first item doesn't go in any of the first 3 slots)*
                (probability that second item doesn't go in any of the first 3 slots)*
                (probability that third item doesn't go in any of the first 3 slots)

                 = (97/100) * (97/100) * (97/100) 

1 comment

Answer:

Related questions