1、分布规律

我们看看官方文档中的一段描述:

Because TreeNodes are about twice the size of regular nodes, we
use them only when bins contain enough nodes to warrant use
(see TREEIFY_THRESHOLD). And when they become too small (due to
removal or resizing) they are converted back to plain bins. In
usages with well-distributed user hashCodes, tree bins are
rarely used. 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24123456789101112131415161718192021222324

简单解释一下，理想情况下，在随机哈希代码下，桶中的节点频率遵循
泊松分布，文中给出了桶长度k的频率表。
由频率表可以看出，桶的长度超过8的概率非常非常小。所以作者应该是根据
概率统计而选择了8作为阀值。
2、数学计算

红黑树的平均查找长度是log(n)，长度为8，查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。
还有选择6和8的原因是：
　　中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。

数据少的时候，直接挂在链表后面即可。因为深度不深，遍历整条链表的速度依旧快速。
如果此时就使用红黑树，那么每次插入一个数据，整条树很有可能需要做旋转，已达到平衡。是否值得？从jdk的设计来说，应该是没必要。

首先说一说转换为红黑树的必要性:
红黑树的插入、删除和遍历的最坏时间复杂度都是log(n)，
因此，意外的情况或者恶意使用下导致hashCode()方法的返回值很差时，
性能的下降将会是"优雅"的，只要Key具有可比性。
但由于TreeNodes的大小是常规Nodes的两倍，所以只有桶中包含足够多
的元素以供使用时，我们才会使用树。那为什么这个数字是8呢
在这里总结了两种说法：
1、分布规律

我们看看官方文档中的一段描述:

Because TreeNodes are about twice the size of regular nodes, we
use them only when bins contain enough nodes to warrant use
(see TREEIFY_THRESHOLD). And when they become too small (due to
removal or resizing) they are converted back to plain bins. In
usages with well-distributed user hashCodes, tree bins are
rarely used. 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24123456789101112131415161718192021222324

简单解释一下，理想情况下，在随机哈希代码下，桶中的节点频率遵循
泊松分布，文中给出了桶长度k的频率表。
由频率表可以看出，桶的长度超过8的概率非常非常小。所以作者应该是根据
概率统计而选择了8作为阀值。
2、数学计算

红黑树的平均查找长度是log(n)，长度为8，查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。
还有选择6和8的原因是：
　　中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。

源码中的注释写的很清楚，因为树节点所占空间是普通节点的两倍，所以只有当节点足够多的时候，才会使用树节点。也就是说，节点少的时候，尽管时间复杂度上，红黑树比链表好一点，但是红黑树所占空间比较大，综合考虑，认为只能在节点太多的时候，红黑树占空间大这一劣势不太明显的时候，才会舍弃链表，使用红黑树。

数据少的时候，直接挂在链表后面即可。因为深度不深，遍历整条链表的速度依旧快速。
如果此时就使用红黑树，那么每次插入一个数据，整条树很有可能需要做旋转，已达到平衡。是否值得？从jdk的设计来说，应该是没必要。

在JDK1.8以及以后的版本中，hashmap的底层结构，由原来单纯的的数组+链表，更改为链表长度为8时，开始由链表转换为红黑树，为何大刀阔斧的对hashmap采取这个改变呢，以及为何链表长度为8才转变为红黑树呢，下面结合源码一起来分析一下。

我们都知道，链表的时间复杂度是O(n)，红黑树的时间复杂度O(logn)，很显然，红黑树的复杂度是优于链表的，既然这么棒，那为什么hashmap为什么不直接就用红黑树

源码中的注释写的很清楚，因为树节点所占空间是普通节点的两倍，所以只有当节点足够多的时候，才会使用树节点。也就是说，节点少的时候，尽管时间复杂度上，红黑树比链表好一点，但是红黑树所占空间比较大，综合考虑，认为只能在节点太多的时候，红黑树占空间大这一劣势不太明显的时候，才会舍弃链表，使用红黑树。源码上说，为了配合使用分布良好的hashCode，树节点很少使用。并且在理想状态下，受随机分布的hashCode影响，链表中的节点遵循泊松分布，而且根据统计，链表中节点数是8的概率已经接近千分之一，而且此时链表的性能已经很差了。所以在这种比较罕见和极端的情况下，才会把链表转变为红黑树。因为链表转换为红黑树也是需要消耗性能的，特殊情况特殊处理，为了挽回性能，权衡之下，才使用红黑树，提高性能。也就是大部分情况下，hashmap还是使用的链表，如果是理想的均匀分布，节点数不到8，hashmap就自动扩容了。

在链表转变为红黑树方法中，有这样一个判断，数组长度小于MIN_TREEIFY_CAPACITY，就会扩容，而不是直接转变为红黑树，可不是什么链表长度为8就变为红黑树，要仔细看代码，还有别的条件，

现在回头想想，为啥用8？因为通常情况下，链表长度很难达到8，但是特殊情况下链表长度为8，哈希表容量又很大，造成链表性能很差的时候，只能采用红黑树提高性能，这是一种应对策略。

首先说一说转换为红黑树的必要性:

红黑树的插入、删除和遍历的最坏时间复杂度都是log(n)，

因此，意外的情况或者恶意使用下导致hashCode()方法的返回值很差时，

性能的下降将会是"优雅"的，只要Key具有可比性。

但由于TreeNodes的大小是常规Nodes的两倍，所以只有桶中包含足够多

的元素以供使用时，我们才会使用树。那为什么这个数字是8呢

在这里总结了两种说法：

1、分布规律

我们看看官方文档中的一段描述:

Because TreeNodes are about twice the size of regular nodes, we

use them only when bins contain enough nodes to warrant use

(see TREEIFY_THRESHOLD). And when they become too small (due to

removal or resizing) they are converted back to plain bins. In

usages with well-distributed user hashCodes, tree bins are

rarely used. 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

简单解释一下，理想情况下，在随机哈希代码下，桶中的节点频率遵循

泊松分布，文中给出了桶长度k的频率表。

由频率表可以看出，桶的长度超过8的概率非常非常小。所以作者应该是根据

概率统计而选择了8作为阀值。

2、数学计算

红黑树的平均查找长度是log(n)，长度为8，查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。

还有选择6和8的原因是：

　　中间有个差值7可以防止链表和树之间频繁的转换。假设一下，如果设计成链表个数超过8则链表转换成树结构，链表个数小于8则树结构转换成链表，如果一个HashMap不停的插入、删除元素，链表个数在8左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。

红黑树的平均查找长度是log(n)，长度为8，查找长度为log(8)=3，链表的平均查找长度为n/2，当长度为8时，平均查找长度为8/2=4，这才有转换成树的必要；链表长度如果是小于等于6，6/2=3，虽然速度也很快的，但是转化为树结构和生成树的时间并不会太短。