Cheap and Secure Web Hosting Provider : See Now

# Hashing Probabilities

, ,
Problem Detail:

I'm not too sure about how to calculate hashing probabilities, and can't find much documents online to help me with it. Am looking to solve this question "If we hash N items into M buckets using a simple uniform hash, what is the expected number of buckets that have exactly 1 item? What is the expected number of buckets with at least 2 items? What is the expected number of buckets with exactly k items?", so will appreciate any help with respect to hashing probabilities.

For sufficiently large $M$, the size distribution of hash slots with good uniform hash functions follows a Poisson distribution.

Let $\lambda = \frac{N}{M}$ be the load factor. Then the expected proportion of buckets with exactly $k$ items in it is:

$$P(\hbox{# of items in the bucket is } k) = \frac{e^{-\lambda} \lambda^k}{k!}$$