全文浏览约10分钟,从一个错误的结论分析到HashMap链表转化为红黑树的原因。读完对HashMap底层会有更深的理解。
广为流传的错误结论
-
众所周知,Java1.8以后HashMap链表长度大于8数组长度大于64时,链表变为红黑树。
-
网络上有一种错误说法流传甚广,请看分析:
- 链表查找的时间复杂度:分为头查找和尾查找,综合两种查找,时间复杂度是n/2
- 红黑树查找的时间复杂度:log2n
- 分析:当长度为8时,链表查找时间为:8/2 = 4,红黑树查找时间为:log8 = 3
当长度为7时,链表查找时间为:7/2 = 3.5,红黑树查找时间为:log7 = 2.8
- 结论:长度为8时红黑树明显快于链表
-
以上是错误结论,没有弄清楚大O表示法的意义所在。
大O表示法
真正的原因
请看HashMap源码
- HashMap源码里的一段注释,大概是说,Hash函数算出HashCode导致冲突的概率符合泊松分布。
- 个人理解:当链表长度等于8时已经是非常小的小概率事件(0.00000006),而红黑树的维护本就有时间成本,所以为了效率当很不可能出现时(数据量很大时),才转化为红黑树,避免频繁维护红黑树、红黑树变为链表出现的消耗。
本文引用:
Java1.8 Hash、《算法图解》
不忘初心,技术改变世界