无法从Sun文档中了解Hash表的Poisson部分
我试图了解如何在Java中实现HashMap。 我决定尝试理解该课程的每一行（代码和评论），显然我很快就遇到了阻力。 以下代码片段来自HashMap类，并讨论泊松分布：
- 理想情况下，在随机hashCodes下，频率为
- 箱中的节点遵循泊松分布
- （ http://en.wikipedia.org/wiki/Poisson_distribution ）带有
- 默认大小调整的平均参数约为0.5
- 阈值为0.75，虽然因为有很大的差异
- 调整粒度。 忽略方差，预期
- 列表大小k的出现是（exp（-0.5）* pow（0.5，k）/
- 阶乘（K））。 第一个值是：*
- 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
- 更多：不到千万分之一
我是数学中的普通人，必须先了解泊松分布是什么。 感谢简单的video向我解释。
现在，即使了解了如何使用Poisson计算概率，我也无法理解上面描述的内容。
有人可以用更简单的语言解释一下，如果可能，请举例说明吗？ 这将使我的任务更有趣。
提前致谢
根据要插入的元素的hashCode，HashMap被组织为“桶”数组。 每个存储桶（默认情况下）是链接的元素列表。 每个桶只有很少的元素（理想情况下，最多只有一个），因此找到一个特定元素只需要很少搜索链表。
举一个简单的例子，假设我们有一个容量为4的HashMap和一个0.75的加载因子（默认值），这意味着它在resize之前最多可以容纳3个元素。 元素到桶中的理想分布看起来像这样：
bucket | elements -------+--------- 0 | Z 1 | X 2 | 3 | Y 因此，任何元素都可以立即找到而无需在桶内进行任何搜索。 另一方面，元素分布非常差，如下所示：
bucket | elements -------+--------- 0 | 1 | Z -> X -> Y 2 | 3 |
如果所有元素都碰巧散列到同一个存储桶中，则会发生这种情况，因此搜索元素Y将需要遍历链接列表。
这可能看起来不是什么大问题，但是如果你有一个容量为10,000个元素的HashMap并且链表上的一个存储桶中有7,500个元素，那么搜索特定元素会降低到线性搜索时间 – 这是使用HashMap试图避免的是什么。
一个问题是用于将元素分配到桶中的hashCode由对象本身确定，并且对象的hashCode实现并不总是非常好。 如果hashCode不是很好，那么元素可以在某些桶中聚集，并且HashMap将开始表现不佳。
代码中的注释是关于每个桶中出现不同长度的链表的可能性。 首先，它假设hashCodes是随机分布的 – 并非总是如此！ – 我认为它还假设HashMap中的元素数量是桶数量的50％。 根据这些假设，根据泊松分布，60.6％的桶将是空的，30.3％将具有一个元素，7.5％将具有两个元素，1.2％将具有三个元素，等等。
换句话说，给定那些（理想的）假设，每个桶中的链表通常非常短。
在JDK 8中，存在一种优化以将链表转换为高于特定阈值大小的树，从而在最坏的情况下至少性能降级为O（log n）而不是O（n）。 问题是，应该选择什么价值作为门槛？ 这就是讨论的全部内容。 当前阈值TREEIFY_THRESHOLD是8.再次，在这些理想假设下，具有长度为8的链表的桶将仅出现0.000006％的时间。 因此，如果我们得到一个很长的链表，那么显然不理想!! 例如，它可能意味着存储的对象具有exception错误的hashCodes，因此HashMap必须从链表切换到树，以避免过度的性能下降。
带有相关评论的源文件的链接如下：
http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/jdk8-b119/src/share/classes/java/util/HashMap.java
接受的答案很好，但我只是想填写为什么使用泊松分布是合理的，因为我在阅读那段代码时遇到了完全相同的问题。
在我们将固定数量的项目k插入到固定数量的桶n中的情况下，固定桶中的项目数应遵循具有k试验和成功概率1 / n的二项分布 。 这很容易看到; 如果哈希是随机的，则每个项目以1 / n概率放入我们的桶中，并且有k项目。
当k很大并且二项分布的平均值很小时，良好的近似是具有相同均值的泊松分布 。 在这种情况下，均值是k / n ，哈希表的加载因子。 取0.5的平均值是合理的，因为在resize之前，表允许最大0.75的负载系数，因此该表将大量使用大约0.5的负载系数。