为什么Map桶中个数超过8才转为红黑树

素颜马尾好姑娘i 2022-02-05 01:23 158阅读 0赞

因为，大部分的文章都是分析链表是怎么转换成红黑树的，但是并没有说明为什么当链表长度为8的时候才做转换动作。本人第一反应也是一样，只能初略的猜测是因为时间和空间的权衡。

要弄明白这个问题，我们首先要明白为什么要转换，这个问题比较简单，因为Map中桶的元素初始化是链表保存的，其查找性能是O(n)，而树结构能将查找性能提升到O(log(n))。当链表长度很小的时候，即使遍历，速度也非常快，但是当链表长度不断变长，肯定会对查询性能有一定的影响，所以才需要转成树。至于为什么阈值是8，我想，去源码中找寻答案应该是最可靠的途径。

8这个阈值定义在HashMap中，如下所示，这段注释只说明了8是bin（bin就是bucket，即HashMap中hashCode值一样的元素保存的地方）从链表转成树的阈值，但是并没有说明为什么是8：

/** 
        * The bin count threshold  for  using a tree rather than list  for a 
        * bin.  Bins are converted  to trees  when adding an element  to a 
        * bin  with at least this many nodes. The value must be greater 
        * than  2  and should be at least  8  to mesh  with assumptions  in 
        * tree removal about conversion back  to plain bins upon shrinkage. 
        */ 
       static final int TREEIFY_THRESHOLD =  8;

我们继续往下看，在HashMap中有一段`Implementation notes`，笔者摘录了几段重要的描述，第一段如下所示，大概含义是当bin变得很大的时候，就会被转换成TreeNodes中的bin，其结构和TreeMap相似，也就是红黑树：

This map usually acts  as a binned (bucketed) hash table, but 
       when bins  get too large, they are transformed  into bins  of TreeNodes, 
       each structured similarly  to those  in java.util.TreeMap

继续往下看，**TreeNodes占用空间是普通Nodes的两倍**，所以只有当bin包含足够多的节点时才会转成TreeNodes，而是否足够多就是由**TREEIFY\_THRESHOLD**的值决定的。当bin中节点数变少时，又会转成普通的bin。并且我们查看源码的时候发现，链表长度达到8就转成红黑树，当长度降到6就转成普通bin。

这样就解析了为什么不是一开始就将其转换为TreeNodes，而是需要一定节点数才转为TreeNodes，说白了就是trade-off，空间和时间的权衡：

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

这段内容还说到：当hashCode离散性很好的时候，树型bin用到的概率非常小，因为数据均匀分布在每个bin中，几乎不会有bin中链表长度会达到阈值。但是在随机hashCode下，离散性可能会变差，然而JDK又不能阻止用户实现这种不好的hash算法，因此就可能导致不均匀的数据分布。不过理想情况下随机hashCode算法下所有bin中节点的分布频率会遵循**泊松分布**，我们可以看到，一个bin中链表长度达到8个元素的概率为0.00000006，几乎是不可能事件。所以，之所以选择8，不是拍拍屁股决定的，而是根据概率统计决定的。由此可见，发展30年的Java每一项改动和优化都是非常严谨和科学的。

*  画外音

笔者通过搜索引擎搜索这个问题，发现很多下面这个答案（猜测也是相互转发）：

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

笔者认为这个答案不够严谨：3相比4有转换的必要，而2.6相比3就没有转换的必要？起码我不敢苟同这个观点。

PS:非常感谢作者,作者的回答也解决了我的问题,我一直同样也认为通过时间复杂度进行简单的计算解释的并不好,因为我们生成红黑树同样需要时间,仅仅只是通过2.6:3就武断他就应该是8进行转换有点太过武断,作者的回答非常中肯,也从概率上进行解析,非常棒的文章

转载来源：[https://blog.csdn.net/sinat\_41832255/article/details/88884586][https_blog.csdn.net_sinat_41832255_article_details_88884586]

[https_blog.csdn.net_sinat_41832255_article_details_88884586]: https://blog.csdn.net/sinat_41832255/article/details/88884586