Files before a hash table hits its first clash

Question

A hash table has 8000 slots, and each file lands in a slot chosen uniformly at random and independently. What is the smallest number of files inserted before a collision becomes more likely than not?

Accepted Answer

Find the smallest n with P(	ext{all distinct}) \le 	frac12. Each of the \binom{n}{2} pairs of files collides with probability 1/8000, so P(	ext{all distinct}) \approx e^{-\binom{n}{2}/8000}. Set this to 	frac12: \frac{\binom{n}{2}}{8000} \approx \ln 2 = 0.693 \implies \binom{n}{2} \approx 5545 \implies n \approx 106. The exact product confirms it: at n = 105 the collision probability is about 0.496, and at n = 106 it is about 0.503. So n = 106. The rule of thumb n \approx 1.18\sqrt{d} gives 1.18\sqrt{8000} \approx 105.3, rounding up to 106. Note that filling only about 1.3\% of the table …

Files before a hash table hits its first clash

Your answer

Discussion

Learn the concepts

Related questions