Probability of No Hash Collisions

Assign buckets to keys one at a time and track how many buckets remain unused.

Multiply the probabilities that each successive key avoids all previously used buckets.

1. 1. Assign buckets sequentially

   The first key can go anywhere. The second must avoid 1 used bucket (probability $99/100$), the third must avoid 2 used buckets (probability $98/100$), and so on down to the tenth key avoiding 9 used buckets (probability $91/100$).

2. 2. Multiply the probabilities

   The overall probability is the product of these ten factors.

   $$P=\frac{100\times 99\times \cdots \times 91}{100^{10}}\approx 0.628157$$

Answer: (100*99*...*91)/100^10