HashMap 的源码实现
jdk1.8 起 hashmap 中链表长度大于 8 时，为啥是红黑树，不是平衡二叉树, 64 是怎么起作用。不是超过 8 就变红黑树了？
来源：云原生后端社区
展开
收起
1
条回答
写回答
写回答
-
红黑树 插入的时候，最多翻转两次,最差是 全部都要翻转,红黑树的增删改查的复杂度显然是O(logn)级别的，通常说红黑树是统计性能更优的树结构。为什么说统计性能更优呢？因为若是单纯的读操作，AVL树的性能比红黑树强一些，红黑树不是严格的平衡树，它是保持“黑平衡”的树。对于红黑树，最坏的情况，是树中最左侧的节点的左子树都是红色的节点，即对应2-3树中的“3节点”，所以这时红黑树的高度就是2logn（除了logn个黑色节点外，还有logn个红色节点），红黑树要比AVL树要高一些。所以从单纯的查询性能来说，红黑树的性能并没有AVL树强。对于插入删除操作来说，红黑树相比于AVL树减少了左旋转或右旋转的次数，所以红黑树的插入删除的性能比AVL树强一些。综合增删改查各方面的性能，红黑树的综合性能比较高。
来源：云原生后端社区2020-04-25 15:30:19赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
问答排行榜
最热
最新
推荐问答
