Consider a hash table with 100 slots. Collisions are resolved using chaining.…
2018
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?
- A.
(97 × 97 × 97)/1003
- B.
(99 × 98 × 97)/1003
- C.
(97 × 96 × 95)/1003
- D.
(97 × 96 × 95)/(3! x 1003)
Attempted by 267 students.
Show answer & explanation
Correct answer: A
Under simple uniform hashing, each of the 3 insertions is independent and uniformly distributed across all 100 slots. For the first 3 specific slots to remain unfilled, every insertion must land in one of the remaining 97 available slots. Consequently, the probability is (97/100) × (97/100) × (97/100), which equals (97^3)/100^3.