Can't understand Poisson part of Hash tables from Sun documentation

user_303517 0
Viewed 1330

I am trying to understand how HashMap is implemented in Java. I decided that I will try to understand every line (of code and comments) from that class and obviously I faced resistance very soon. The following snippet is from HashMap class and talks about Poisson Distribution:

 Ideally, under random hashCodes, the frequency of
 nodes in bins follows a Poisson distribution
 (http://en.wikipedia.org/wiki/Poisson_distribution) with a
 parameter of about 0.5 on average for the default resizing
 threshold of 0.75, although with a large variance because of
 resizing granularity. Ignoring variance, the expected
 occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
 factorial(k)). The first values are:
 0:    0.60653066
 1:    0.30326533
 2:    0.07581633
 3:    0.01263606
 4:    0.00157952
 5:    0.00015795
 6:    0.00001316
 7:    0.00000094
 8:    0.00000006
 more: less than 1 in ten million

I am an average guy in Math and had to understand what Poisson distribution is first. Thanks to the simple video that explained it to me.

Now even after understanding how you calculate probability using Poisson I can't understand what is described above.

Can someone please explain this in simpler language and with an example if possible? It will make my task much more interesting.

poisson hashmap java
2 Answers

The accepted answer is great but I just wanted to fill in why it's reasonable to use a Poisson distribution in particular since I had the exact same question when reading that piece of code.

In the case that we have a fixed number of items k being inserted into a fixed number of buckets n then the number of items in a fixed bucket should follow a Binomial Distribution with k trials and probality of success 1 / n. This is pretty easy to see; if the hash is random then each item is put into our bucket with probability 1 / n and there are k items.

When k is large and the mean of the Binomial Distribution is small then a good approximation is a Poisson Distribution with the same mean. In this case the mean is k / n, the the load factor of the hash table. Taking 0.5 for the mean is reasonable because the table tolerates a load factor of at most 0.75 before resizing so the table will be used a great deal with a load factor of around 0.5.

user_2859150
Related