无法从Sun文档中理解Hash表的Poisson部分

Question

我试图了解HashMap是如何在Java中实现的。我决定尝试理解这个类的每一行(代码和注释)，显然我很快就遇到了阻力。下面的片段来自HashMap类，并讨论了泊松分布：

 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

我是数学中的一个普通人，我必须明白什么是泊松分布。感谢简单的视频，它解释了这一点。

现在，即使在理解了如何使用Poisson计算概率之后，我也无法理解上面描述的内容。

有人能用更简单的语言解释一下吗?如果可能的话，可以举个例子来解释一下吗？这将使我的任务更加有趣。

Answer 1

HashMap是根据插入的元素的hashCode组织成一个“桶”数组的。每个桶(默认情况下)都是元素的链接列表。每个桶只有很少的元素(理想情况下最多只有一个元素)，因此查找特定元素几乎不需要搜索链接列表。

举一个简单的例子，假设我们的HashMap为容量4，负载因子为0.75 (默认情况下)，这意味着在调整大小之前它最多可以容纳3个元素。理想的将元素分配到桶中的方法如下所示：

bucket | elements
-------+---------
     0 | Z
     1 | X
     2 |
     3 | Y

因此，任何元素都可以立即找到，而无需在桶中进行任何搜索。另一方面，元素的分布很差，如下所示：

bucket | elements
-------+---------
     0 | 
     1 | Z -> X -> Y
     2 |
     3 |

如果所有元素都碰巧散列到同一个桶中，则会发生这种情况，因此搜索元素Y将需要遍历链接列表。

这似乎不是什么大不了的事，但如果你有一个容量为10,000个元素的HashMap，并且链接列表中的单个桶中有7500个元素，那么搜索特定的元素就会降低到线性搜索时间--这正是使用HashMap试图避免的情况。

一个问题是，将元素分发到桶中的hashCode是由对象本身决定的，而对象的hashCode实现并不总是很好。如果hashCode不是很好，那么元素就会聚集在特定的桶中，HashMap就会开始表现不佳。

代码中的注释讨论了在每个桶中出现不同长度的链接列表的可能性。首先，它假设hashCodes是随机分布的--并不总是这样！-我认为它也假定HashMap中的元素数是桶数的50%。在这些假设下，根据泊松分布，有60.6%的桶是空的，30.3%的桶是空的，7.5%的桶是空的，1.2%的桶是空的，等等。

换句话说，考虑到这些(理想的)假设，每个桶中的链接列表通常都会非常短。

在JDK 8中，有一个优化方法将链接列表转换为超过一定阈值大小的树，这样在最坏的情况下，性能至少会下降到O(log )而不是O(n)。问题是，应该选择什么值作为阈值？这就是这次讨论的意义所在。目前的阈值TREEIFY_THRESHOLD是8。同样，在这些理想的假设下，一个链表长度为8的桶只会出现0.000006%的时间。所以，如果我们有这么长的链接列表，显然有些东西是不理想的！例如，这可能意味着存储的对象具有异常糟糕的hashCodes，因此HashMap必须从链接列表切换到树，以避免过度的性能下降。

指向有问题注释的源文件的链接如下：

http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/jdk8-b119/src/share/classes/java/util/HashMap.java

Answer 2

接受的答案很好，但我只想解释为什么使用Poisson分布是合理的，特别是因为我在阅读这段代码时有相同的问题。

如果我们有固定数量的条目，k被插入到固定数量的桶中，那么固定桶中的条目数应该遵循二项分布，并带有k试验和成功概率1 / n。这是很容易看到的；如果散列是随机的，那么每一项都会以概率1 / n的形式放入我们的桶中，并且有k项。

当k较大，二项分布的均值较小时，较好的近似是具有相同均值的泊松分布。在这种情况下，平均值是k / n，哈希表的负载因子。取0.5作为平均值是合理的，因为在调整大小之前，该表的承载系数最多可达0.75，因此该表将被大量使用，负载系数约为0.5。