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

亦凉 2021-12-11 06:09 203阅读 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）操作，因为你只是移动指针。

--------------------

原文：[https://blog.csdn.net/21aspnet/article/details/88939297][https_blog.csdn.net_21aspnet_article_details_88939297]

[https_blog.csdn.net_21aspnet_article_details_88939297]: https://blog.csdn.net/21aspnet/article/details/88939297