为什么jdk8的HashMap链表的长度超过8会转换成红黑树？

逃离我推掉我的手 2022-04-25 03:24 177阅读 0赞

首先说一说转换为红黑树的必要性:  
红黑树的插入、删除和遍历的最坏时间复杂度都是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左右徘徊，就会频繁的发生树转链表、链表转树，效率会很低。