Multiple choice

A hash table has space for 100 records. What is the probability of collision before the table is 10% full?

  1. 0.45

  2. 0.5

  3. 0.3

  4. 0.34
Reveal answer Fill a bubble to check yourself
D Correct answer
Explanation

This is a variation of the birthday paradox. The probability of no collision for n items in m slots is (m/m) * ((m-1)/m) * ... * ((m-n+1)/m). For 10 records in 100 slots, the probability of no collision is approx 0.63, meaning the probability of at least one collision is 1 - 0.63 = 0.37, which is closest to 0.34.

Keep practicing — related questions