美文网首页
为什么Map的桶中超过8个才转为红黑树

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

作者: Travis_Wu | 来源:发表于2020-12-12 12:29 被阅读0次

    一、为什么要转换

    • 每次遍历一个链表,平均查找的时间复杂度是 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 内部出现了红黑树的结构 往往就说明我们的哈希算法出了问题

    相关文章

      网友评论

          本文标题:为什么Map的桶中超过8个才转为红黑树

          本文链接:https://www.haomeiwen.com/subject/pcbegktx.html