为什么HashMap使用红黑树而不使用AVL树

柔情只为你懂 2021-09-07 06:11 312阅读 0赞

在Jdk1.8版本后，Java对HashMap做了改进，在链表长度大于8的时候，将后面的数据存在红黑树中，以加快检索速度。

那么很多人就有疑问为什么是使用红黑树而不是AVL树，AVL树是完全平衡二叉树阿？

最主要的一点是：

在CurrentHashMap中是加锁了的，实际上是读写锁，如果写冲突就会等待，如果插入时间过长必然等待时间更长，而红黑树相对AVL树他的插入更快！

## 问题：为什么不使用AVL树而使用红黑树？ ##

红黑树和AVL树都是**最常用的平衡二叉搜索树**，它们的查找、删除、修改都是O(lgn) time

AVL树和红黑树有几点比较和区别：

1.  AVL树是更加严格的平衡，因此可以提供更快的查找速度，一般读取查找密集型任务，适用AVL树。
2.  红黑树更适合于插入修改密集型任务。
3.  通常，AVL树的旋转比红黑树的旋转更加难以平衡和调试。

**总结**：

1.  AVL以及红黑树是高度平衡的树数据结构。它们非常相似，真正的区别在于在任何添加/删除操作时完成的旋转操作次数。
2.  两种实现都缩放为a O(lg N)，其中N是叶子的数量，但实际上AVL树在查找密集型任务上更快：利用更好的平衡，树遍历平均更短。另一方面，插入和删除方面，AVL树速度较慢：需要更高的旋转次数才能在修改时正确地重新平衡数据结构。
3.  在AVL树中，从根到任何叶子的最短路径和最长路径之间的差异最多为1。在红黑树中，差异可以是2倍。
4.  两个都给O（log n）查找，但平衡AVL树可能需要O（log n）旋转，而红黑树将需要最多两次旋转使其达到平衡（尽管可能需要检查O（log n）节点以确定旋转的位置）。旋转本身是O（1）操作，因为你只是移动指针。

往期精彩内容：

[Java知识体系总结（2021版）][Java_2021]

[超详细的springBoot学习笔记][springBoot]

[Java多线程基础知识总结（绝对经典）][Java]

[Java面试题总结（附答案）][Java 1]

[Vue基础知识总结（绝对经典）][Vue]

[常见数据结构与算法整理总结][Link 1]

[Java_2021]: https://blog.csdn.net/guorui_java/article/details/112391105
[springBoot]: https://blog.csdn.net/guorui_java/article/details/104137262
[Java]: https://blog.csdn.net/guorui_java/article/details/107599455
[Java 1]: https://blog.csdn.net/guorui_java/article/details/107803283
[Vue]: https://blog.csdn.net/guorui_java/article/details/106917601
[Link 1]: https://blog.csdn.net/guorui_java/article/details/106217472