Cheap and Secure Web Hosting Provider : See Now

Hashing Probabilities

, , No Comments
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.

Asked By : user61018

Answered By : Pseudonym

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!}$$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/65665

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback