JDK8 中的 HashMap 链表的长度超过 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左右徘徊,就会频繁的发生树转链表、链表转树,效率会很低。
免责声明
本站提供的一切软件、教程和内容信息仅限用于学习和研究目的;不得将上述内容用于商业或者非法用途,否则,一切后果请用户自负。本站信息来自网络收集整理,版权争议与本站无关。您必须在下载后的24个小时之内,从您的电脑或手机中彻底删除上述内容。如果您喜欢该程序和内容,请支持正版,购买注册,得到更好的正版服务。我们非常重视版权问题,如有侵权请邮件与我们联系处理。敬请谅解!
![]() |
相关文章
-
12-21【排序算法】java实现快排算法
-
12-20Java 中是如何获取 IP 属地的,IP精准定位
-
12-20JVM 调优工具总结篇
-
12-19JVM 性能调优之 jstat
-
12-19JVM 性能调优之 jps
-
12-19JVM 性能调优之 jinfo
-
12-19JVM 性能调优之 jstack
-
12-19JVM 性能调优之 jmap
-
12-18Java 创建线程池的正确姿势: Executors 和 ThreadPoolExecutor 详解
-
12-18Spring Bean的生命周期(一图看懂bean生命周期)