Expected colliding pairs in a hash table

Question

You hash 200 files into a table of 10000 buckets, each file landing in a uniformly random bucket independently. On average, how many pairs of files collide (land in the same bucket)?

Accepted Answer

Use linearity of expectation, adding up the per-pair collision chances. Number of pairs of files: \binom{200}{2} = \frac{200 \cdot 199}{2} = 19900 	ext{ pairs}. Each pair collides with probability 1/10000 (once one file's bucket is fixed, the other must match). So the expected number of colliding pairs is E[	ext{colliding pairs}] = 19900 	imes \frac{1}{10000} = 1.99. So on average about two pairs of files share a bucket, even though the table is only 2\% full. Takeaway. Expected collisions are \binom{n}{2}/d. With 200 files and 10000 buckets that is 1.99, a reminder that clashes appear wel…

Expected colliding pairs in a hash table

Your answer

Discussion

Learn the concepts

Related questions