乐鱼电竞

    教育行业A股IPO第一股（股票代码 003032）

    全国咨询/投诉热线：400-618-4000

    树化的意义是什么？【java面试题】

    更新时间:2022年02月15日18时14分 来源:乐鱼电竞 浏览次数:

    树化的意义：

    红黑树用来避免 DoS 攻击，防止链表超长时性能下降，树化应当是偶然情况，是保底策略。

    hash 表的查找，更新的时间复杂度是 $O(1)$，而红黑树的查找，更新的时间复杂度是 $O(log_2?n )$，TreeNode 占用空间也比普通 Node 的大，如非必要，尽量还是使用链表。

    hash 值如果足够随机，则在 hash 表内按泊松分布，在负载因子 0.75 的情况下，长度超过 8 的链表出现概率是 0.00000006，树化阈值选择 8 就是为了让树化几率足够小。

    树化规则：

    当链表长度超过树化阈值 8 时，先尝试扩容来减少链表长度，如果数组容量已经 >=64，才会进行树化。

    退化规则：

    情况1：在扩容时如果拆分树时，树元素个数 <= 6 则会退化链表。

    情况2：remove 树节点时，若 root、root.left、root.right、root.left.left 有一个为 null ，也会退化为链表。




    猜你喜欢：

    什么是冒泡排序？手写一段冒泡排序的代码

    Javascript猜数游戏怎么实现？【含游戏源码】

    lock和synchronized有什么区别？

    Java线程优先级：Thread类的优先级常量

    乐鱼电竞JAVA开发工程师培训

    0 分享到：
    和我们在线交谈！
    【网站地图】【sitemap】