为什么HashMap桶(链表)的长度超过8才会转换成红黑树

布满荆棘的人生 2021-11-23 09:42 223阅读 0赞

百度了一下，感觉能说清楚的并不多，所以在此记录一下。

首先说一说转换为红黑树的必要性:  
红黑树的插入、删除和遍历的最坏时间复杂度都是log(n)，  
因此，意外的情况或者恶意使用下导致hashCode()方法的返回值很差时，  
性能的下降将会是"优雅"的，只要Key具有可比性。

但由于TreeNodes的大小是常规Nodes的两倍，所以只有桶中包含足够多  
的元素以供使用时，我们才会使用树。那为什么这个数字是8呢？  
我们看看官方文档中的一段描述:

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作为阀值。  
\---------------------  
作者：zycc\_dai  
来源：CSDN  
原文：https://blog.csdn.net/daiyuhe/article/details/89424736  
版权声明：本文为博主原创文章，转载请附上博文链接！

转载于:https://www.cnblogs.com/williamjie/p/11088580.html