【Java 面试合集】HashMap中为什么引入红黑树，而不是AVL树呢

HashMap中为什么引入红黑树，而不是AVL树呢

1. 概述

开始学习这个知识点之前我们需要知道，在JDK1.8 以及之前，针对HashMap有什么不同。

• JDK 1.7的时候，HashMap的底层实现是数组 + 链表
• JDK1.8的时候，HashMap的底层实现是数组 + 链表 + 红黑树

我们要思考一个问题，为什么要从链表转为红黑树呢。

首先先让我们了解下链表有什么不好？？？

2. 链表

上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度

• 增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)
• 删：算法时间复杂度跟增保持一致
• 查：既然是非线性结构，所以查询某一个节点的时候，最起码要遍历一遍，所以时间复杂度为O(n).

所以问题就来了，我们的目的就是优化链表查询效率，结果就是转换数据结构，从而引出了我们的平衡二叉树

3. 平衡二叉树

平衡二叉树是一种结构相对平衡的二叉搜索树。既然是二叉树结构，比较理想的状态如上图所示，节点分布相对平衡

但是还有一种情况：

这种也是一种平衡二叉树的结构，而我们实际的业务中出现这种状态概率很多，而那种理想的平衡二叉树的状态就很少。

所以我们为了保证，如果生成一个平衡二叉树，我们要求这个二叉树无论有多少节点，都一定要保持相对平衡。

所以我们使用了红黑树来满足这个需求