哈喽哈喽大家猴，我是把代码写成 bug 的大头菜。公众号：大头菜技术 (bigheadit)。原创不易，但欢送转载。
前言
有网友指出《面试 Java——汇合之 HashMap 和 ConcurrentHashMap》一文，对于为什么是 8，还能够加一句合乎泊松散布。于是我理解一下泊松散布后，的确和网友说的统一，同时非常感谢网友指出文章存在的瑕疵。接下来的内容，大头菜将试图用泊松散布来论证 HashMap 的链表变树的阈值为什么是 8 。
泊松散布
首先，什么是泊松散布？
维基百科官网解释：
泊松散布（法语：loi de Poisson，英语：Poisson distribution）又称 Poisson 散布、帕松散布、布瓦松散布、布阿松散布、普阿松散布、波以松散布、卜氏散布、帕松小数法令（Poisson law of small numbers），是一种统计与概率学里常见到的离散概率分布，由法国数学家西莫恩·德尼·泊松在 1838 年时发表。
泊松散布适宜于形容单位工夫内随机事件产生的次数的概率分布。如某一服务设施在肯定工夫内受到的服务申请的次数，电话交换机接到呼叫的次数、汽车站台的候客人数、机器呈现的故障数、自然灾害产生的次数、DNA 序列的变异数、放射性原子核的衰变数、激光的光子数散布等等。
泊松散布的概率品质函数为：
我总结一下，简略点来说： 泊松散布就是形容单位工夫内，独立事件产生的次数。
简略举个例子，让大家相熟一下：
比方：某医院均匀每小时出世 3 个婴儿，请问下一个小时，会出世几个？
有可能出世 6 个，也有可能一个都不出世，这是咱们没法晓得的。
如果尝试用泊松散布来示意：等号的右边，P 示意概率，N 示意某种函数关系，t 示意工夫，n 示意数量，1 小时内出世 3 个婴儿的概率，就示意为 P(N(1) = 3)。等号的左边，λ 示意事件的频率。
接下来两个小时，一个婴儿都不出世的概率是 0.25%，根本不可能产生。
接下来一个小时，至多出世两个婴儿的概率是 80%。
泊松散布的图形大略是上面的样子。
能够看到，在频率左近，事件的产生概率最高，而后向两边对称降落，即变得越大和越小都不太可能。每小时出世 3 个婴儿，这是最可能的后果，出世得越多或越少，就越不可能。
看完例子后，你应该对泊松散布有一个大略的意识了。接下来，咱们尝试应用泊松散布去剖析 HashMap 的链表变树。
HashMap 的链表变树阈值为什么是 8
依据泊松散布：单位工夫内，独立事件产生的次数。
HashMap 的 key 碰撞问题，每次 key 的碰撞，都能够认为是一次独立事件。与上次或下次是否产生 key 碰撞，都无关系。
因而，用泊松散布尝试示意：P 示意概率，N 示意某种函数关系，t 示意工夫，n 示意数量，每 1 秒 key 发送碰撞的次数为 k，就示意为 P(N(1) = k)。等号的左边，λ 示意事件的频率。对于一个 key 是否产生碰撞的概率为 0.5。
- e^-0.5 = 0.6065
把相应数值代入泊松散布公式：
$P(N(1)=k) = 0.6065*(0.5^k)/k!$
- 当 k = 0 时，P= 0.6065
- 当 k = 1 时，p= 0.3032
- 当 k = 2 时，p= 0.0758
- 当 k = 3 时，p= 0.0126
- 当 k = 4 时，p= 0.0015
- 当 k = 5 时，p= 0.0001
- 当 k = 6 时，p= 0.000013
- 当 k = 7 时，p= 0.0000009
- 当 k = 8 时，p= 0.00000006
- 当 k = 9 时，p= 0.000000003
有没有发现上述的后果有点相熟：
比照一下 HashMap 的正文：
* 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当 k = 9 时，也就是产生的碰撞次数为 9 次时，概率为亿分之三，碰撞的概率曾经有限靠近为 0。
如果设置为 9，意味着，简直永远都不会再次发生碰撞，换句话说，链表的长度此时为 8，要产生碰撞才会从链表变树。但永远都不会变树，因为概率太小了。因而设置为 9，切实没必要。
这就是链表变树的阈值为 8 的起因。
参考资料
- 维基百科
- 阮一峰的网络日志——《泊松散布和指数分布：10 分钟教程》
絮叨
非常感谢你能看到这里，如果感觉文章写得不错 求关注 求点赞 求分享 (对我十分十分有用)。
如果你感觉文章有待进步，我非常期待你对我的倡议，求留言。
如果你心愿看到什么内容，我非常期待你的留言。
各位的捧场和反对，是我创作的最大能源！