上一节，我们介绍了 HashMap 的底层实现原理，其中提到 2 个特殊的值，一个是链表树化阈值 8，另一个是默认装载因子 0.75，本节我们就继续深入分析一下这两个特殊值的由来
1、默认装载因子
上一节中，我们讲到，装载因子的默认值为 0.75，那么 0.75 这个值是从何而来的呢？默认值为啥不是 0.6、0.8 等其他值呢？
我们先来看 Java 本身对这个值的解释。如下所示。以下内容来自 JDK 8 中 HashMap 源码中的注释
* <p>As a general rule, the default load factor (.75) offers a good
* tradeoff between time and space costs. Higher values decrease the
* space overhead but increase the lookup cost (reflected in most of
* the operations of the <tt>HashMap</tt> class, including
* <tt>get</tt> and <tt>put</tt>). The expected number of entries in
* the map and its load factor should be taken into account when
* setting its initial capacity, so as to minimize the number of
* rehash operations. If the initial capacity is greater than the
* maximum number of entries divided by the load factor, no rehash
* operations will ever occur.
在注释中，HashMap 的开发者给出了一些选择 0.75 为装载因子默认值的理由，意思大概是说，这个值是权衡时间效率和空间效率之后的结果
如果装载因子太小，会导致空间浪费太大
如果装载因子太大，会导致各个操作的执行效率太低
那么，对于装载因子来说，多小才算是太小？多大才算是太大呢？
尽管我们无非给出一个标准的答案，但是，按照常理，我们可以预估一个范围，装载因子应该处于 0.5 ~ 1 之间，小于等于 0.5 就算太小，大于等于 1 就算太大
为什么这么说呢？我们进一步解释
如果装载因子为 0.5，那么当数组大小为 n，存储元素超过 n / 2 时，就会触发扩容，永远都只有一半的空间可用，一半的空间被浪费
如果 n 比较大，那么浪费的空间就相当可观了，所以，从感性认识上来讲，0.5 这个值应该是装载因子的底线了
如果装载因子为 1，n 个元素存储到长度为 n 的数组中，那么哈希表中发生冲突的概率会非常高
你可能会说，即便存在一些冲突，又有什么关系呢？冲突的数据会放入链表，链表很短的情况下，对 HashMap 性能的影响似乎不大
在《数据结构与算法之美》中，我们讲到两种解决冲突的常用方法：链表法和开放寻址法
对比两种方法，链表法确实会比开放寻址法，对冲突的容忍度更高
采用开放寻址法解决冲突的哈希表，装载因子最大值为 1
当装载因子接近 1 时，各个操作的执行速度就已经非常慢了
但对于链表法解决冲突的哈希表来说，即便装载因子设置为大于 1 的值，比如 2，也只不过会导致链表的平均长度变为 2 而已，增删改查各个操作的时间复杂度仍然是 O(1) 的
不过，时间复杂度只能粗略表明执行效率，对于 HashMap 这种非常常用的容器来说，其性能的优化应该做到极致
如果链表平均长度变为 2，那么，尽管增删改查的时间复杂度未变，但粗略估算，执行时间将会变为原来的 2 倍，性能下降为原来的 1 / 2，显然是不容忽视的
实际上，不管是用链表来解决冲突，还是链表树化，这些措施都只是无奈之举
万一出现了哈希冲突、链表过长这些极端情况，我们可以通过链表和红黑树来兜底解决
在设计 HashMap 时，我们追求的理想情况是几乎没有冲突，也就说，链表平均长度不超过 1，这样性能才能达到最高
为了做到这一点，即便 HashMap 采用链表法解决冲突，装载因子也不能超过 1
综上所述，我们已经明确了，装载因子必须在 0.5 ~ 1 之间
那么，HashMap 的开发者为什么选择了其中的 0.75 而非其他值作为装载因子的默认值呢？
尽管有资料解释，0.75 这个值可以利用二项分布的概率计算公式来求得，但是其推导过程做了不合理的假设：每次插入数据，发生冲突和不发生冲突的概率相同，均为 0.5
假设都不合理，推导和结论就更无正确可言
所以，这里我们就不展开讲解利用二项分布的概率计算公式的推导方法了
至于为什么选择 0.75 作为装载因子的默认值，我觉得很有可能就如 HashMap 源码中的注释所说："As a general rule ..."，0.75 这个值可能也只不过是作者在一个合理范围内随意选择的值
不过，我们也可以大胆猜测一下，这里随意可能也并没那么随意
我们前面讲到，table 数组的大小为 2 的幂次方，也就是 2、4、8、16 ... 这样的数，默认 table 数组大小 n 为 16，当然，我们也可以将其改为其他 2 的幂次方值
触发扩容的阈值 threshold 是由公式 n * loadFactor 计算得到的，如果要保证 threhold 的值在任何情况下都为整数，那么 0.5 ~ 1 之间（不包含 0.5 和 1），我们只能选择 0.75 作为 loadFactor 的值
你可能说，如果 table 数组的大小 n 被设置为 2，即便 loadFactor 为 0.75，threshold 也不为整数，这种情况改该怎么办？实际上这种情况不可能发生，没人会将 table 数组大小设置为 2
2、链表树化阈值
装载因子限定的是链表的平均长度，用来保证 HashMap 的整体性能，链表树化限定的是链表长度的最大值，用来保证 HashMap 的最差情况下的性能
不过，链表树化比较耗时，并且红黑树的节点包含左右两个指针，而链表的节点只包含 next 指针，存储同样多的数据，红黑树占用的空间要比链表大，所以，我们希望链表树化这种情况极少发生
上一节中，我们讲到，链表树化的阈值为 8，只有链表中节点的个数大于等于 8 时，才会触发树化操作
那么这里的 8 是如何得来的呢？为什么不是 5、6、7 等其他值呢？
要解释 8 的由来，我们需要用到一个统计学的知识：泊松分布
泊松分布用来表示在某个单位时间内（比如一天、一周、一小时，可以随意定义），某个事件发生的频率对应的概率分布，我们举例解释一下
一个月内一台机器发生事故的平均次数是 5 次，但 5 只是平均值，有的月份事故会多点，有的月份事故会少点，一般来讲，事故发生的频率对应的概率分布如下图所示
事故发生 5 次的概率最大，事故发生次数远大于 5 或者远小于 5 的概率会很低
虽然我们知道大概的概率分布图，但是如果我们想要知道，一个月内机器发生 k 次事故的概率具体是多少，该如何计算呢？这时候泊松分布就出场了
科学家发现，在单位时间内很多事件发生的频率对应的概率分布具有相同的特点，如上图所示，比如一天内出生孩子的个数、一周内下雨天数等等
科学家将这类概率分布，叫做泊松分布，并且为它设计了概率计算公式，让我们能够通过公式，轻松计算出某件事情发生 k 次对应的概率
泊松分布的概率计算公式如下所示
其中，e 为数学常数，值约等于 2.71828，λ 为事件发生的平均次数
如果我们要计算一个月内机器发生3次的概率，那么将 k = 3，λ = 5 套入公式，如下所示，最终计算得到的概率约为 0.14
了解了泊松分布之后，我们回过头来看链表树化阈值问题
实际上，对于一个 HashMap 来说，链表的长度各式各样，有的为 1，有的为 2，还有的为 0 ...... 链表的长度对应的概率分布也符合泊松分布
因此，我们就可以通过泊松分布的概率计算公式，来计算链表长度为 k 对应的概率
公式中的 λ 值对应的是链表长度的平均值，那么，链表长度的平均值是多少呢？
我们知道，HashMap 的默认装载因子为 0.75，只有当即将扩容时，链表的平均长度才为 0.75，所以，在大部分情况下，链表的平均长度都小于 0.75，我们选择 0.5 作为大部分情况下链表的平均长度，也就是说 λ 等于 0.5
当然，这里的 0.5 是预估值，因为我们无法给出链表平均长度的精确值
将 λ 带入泊松分布的概率计算公式，我们得到链表长度对应的概率的计算公式，如下所示
我们将 k = 0、1、2 ... 8 依次带入上述公式，得到链表长度分别为 0、1、2 ... 8 对应的概率值，如下所示
从中我们可以发现，链表长度达到8这种情况发生的概率为千万分之六，已经非常低了
也就是说，在哈希函数设计合理（比如哈希值比较随机）、装载因子设置合理（比如 0.75）的情况下，链表长度大于等于 8 这种情况极少发生
为了尽可能避免链表树化，于是，我们选择 8 作为链表树化的阈值
链表长度: 概率值
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
你可能会说，链表长度为 9 的概率会更低，为什么不选择 9 作为树化阈值呢？这是因为链表长度越长，HashMap 的性能就越低，在避免树化的同时，链表的最大长度（也就是树化阈值）要尽量小
所以，8、9 概率都很低的情况下，我们肯定选择较小的那一个 8 了
3、课后思考题
请编程测试 HashMap 在装载因子为 0.75 和 2 时的性能差距