Important point is

Collisions are resolved using chaining

Dark Mode

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?

- $(97 \times 97 \times 97) / 100^3$
- $(99 \times 98 \times 97) / 100^3$
- $(97 \times 96 \times 95) / 100^3$
- $(97 \times 96 \times 95 / (3! \times 100^3)$

0

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$

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

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

Correct Answer: $A$

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

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)