0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ math.stackexchange. Basic probabilities. Totally unrelated to hashing. $\endgroup$ – gnasher729 Nov 7 '16 at 7:16
  • 3
    $\begingroup$ @gnasher729 It is clearly related to hashing. The question is whether the fact that the question is phrased in terms of using a uniform hash function rather than randomly throwing balls into bins is enough to make it computer science. Given the close relationship to hashing, it seems OK to me. $\endgroup$ – David Richerby Nov 7 '16 at 8:32
  • $\begingroup$ Every programmer should know how to test a hash function before they are allowed to design one. IMO, of course... $\endgroup$ – Pseudonym Nov 7 '16 at 9:29
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Nov 7 '16 at 10:17
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Now here's an exercise for you. Given a hash table with $M$ slots, how many items do you need to insert into that hash table in order to get a 50% chance of seeing one or more collisions? To put it another way, in the limit as $M\rightarrow \infty$, what should $N$ be to make $P(\hbox{# of items is }0) = \frac{1}{2}$? $\endgroup$ – Pseudonym Nov 7 '16 at 9:31
  • $\begingroup$ I think the first sentence needs elaboration. Why should that be the case? $\endgroup$ – Raphael Nov 7 '16 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.