How many hash buckets get used?

Question

You hash 50 emails into 64 buckets, each email landing in a uniformly random bucket independently. On average, how many buckets end up non-empty (used by at least one email)?

Accepted Answer

Take one bucket at a time and add up, using linearity of expectation. A given bucket stays empty only if all 50 emails miss it: P(	ext{bucket empty}) = \left(\frac{63}{64}ight)^{50} \approx 0.455. So the chance a bucket is used is 1 - 0.455 = 0.545. With 64 buckets, the expected number used is E[	ext{used buckets}] = 64 	imes \left(1 - \left(	frac{63}{64}ight)^{50}ight) \approx 64 	imes 0.545 \approx 34.9. So about 35 buckets hold something. Since 50 emails land in only about 35 buckets, roughly 15 emails' worth of items are sharing a bucket with others, which is where collisions p…

How many hash buckets get used?

Your answer

Discussion

Learn the concepts

Related questions