16,845 views

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)$

Important point is

Collisions are resolved using chaining

in this how to approach if linear probing given?

can someone share the answer we get, using linear probing?

I think

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

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$
by

yes, just that you have to do it more formally.
okay got it sir.
How to solve this using reverse probability?
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
by

### 1 comment

@Murali

Completely satisfied by ur approach.

Nice explanation thank you. !

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)