一、为什么要转换
- 每次遍历一个链表,平均查找的时间复杂度是 O(n),n 是链表的长度
- 链表还不是很长,O(n) 和 O(log(n)) 的区别不大
- 如果链表越来越长,那么这种区别便会有所体现
- 为了提升查找性能,需要把链表转化为红黑树的形式
二、为什么要经历转换过程
- TreeNodes 需要占用的空间大约是普通 Nodes 的两倍
- 只有当包含足够多的 nodes 时才会转成 TreeNodes
- 是否足够多就是由 TREEIFY_THRESHOLD 的值决定的
- 当桶中节点数由于移除或者 resize 变少后,又会变回普通的链表的形式
- 默认链表长度达到8就转成红黑树,而当长度降到6就转换回去
- 如果 hashCode 分布良好 红黑树这种形式很少会被用到
- 当长度为 8 的时候 概率仅为 0.00000006,这是一个小于千万分之一的概率 通常我们的 Map 里是不会存储这么多的数据的
- 防止用户自己实现了不好的哈希算法时链表过长,导致查询效率低
- 转为红黑树是一种保底策略,用来保证极端情况下查询的效率
- 通常情况下并没有必要转为红黑树,所以就选择了概率非常小,也就是长度为 8 的概率
- 如果平时开发中发现 HashMap 或是 ConcurrentHashMap 内部出现了红黑树的结构 往往就说明我们的哈希算法出了问题
网友评论