Consider a hash table with 100 slots. Collisions are resolved using chaining.…
2014
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)/100^3\) - B.
\((99 × 98 × 97)/100^3\) - C.
\((97 × 96 × 95)/100^3\) - D.
\((97 × 96 × 95)/(3! × 100^3)\)
Attempted by 240 students.
Show answer & explanation
Correct answer: A
Key insight: each insertion independently avoids the first three slots with probability 97/100 because chaining allows collisions.
Probability a single insertion is not in the first three slots: 97/100.
The three insertions are independent, so multiply the probabilities: (97/100) × (97/100) × (97/100) = (97 × 97 × 97)/100^3.
A video solution is available for this question — log in and enroll to watch it.