hashMap面试引出红黑树与AVL树常见面试题及其深入思考

当你自信满满背好八股进入面试官的直播间，向尊敬的面试官大佬致敬后，面试官转头给你甩了一道找出数组中重复数字的算法题，

你一看这不是leetcode原题改编嘛，直接hashMap仍上去解决。

面试官：好小子，那我来考考你hashMap的一些问题

hashMap底层使用了什么数据结构？

就JDK8来说，hashMap的底层使用了数组加链表加红黑树来实现。

桶数组上的链表什么时候转为红黑树？

链表会在阈值为8（JDK中）的情况下进化为红黑树，红黑树在阈值6的情况下退化为链表

为什么要有这样的安排？为什么不完全采用红黑树呢？

从三个角度分析，一是hash函数，二是数据结构的读写效率，三是内存资源使用情况

第一点，hashMap的哈希函数能尽量减少哈希冲突发生的概率，一般情况下不会有太多的元素产生哈希冲突，这个原因导致桶上不会有太多的元素

第二点，
从读方面考虑：
链表查询的时间复杂度O（n），红黑树的复杂度为O（logn）；
从写方面考虑：
链表删除时间复杂度为O（n），红黑树的时间复杂度为O（n）；
链表的添加为O（1），红黑树的添加为O（logn）；
从写方面考虑，链表的添加性能是极其优异的（得益于头插法与尾插法）
从内存资源使用情况考虑：
链表节点需要维护的属性少于红黑树节点，相对红黑树更轻便，占用的内存空间更小

综合以上三个角度，在桶上元素较少的时候，如果直接维护红黑树，尽管我们可以获得不错的读写性能，但其更重，不适合在元素较少时使用，更重要的一点，元素较少时O（n）与O（logn）的时间复杂度相差不大，但链表的添加可以做到O（1）的时间复杂度，显然更胜红黑树。

至于8与6，我认为这个取决于开发者的设计，JDK官方可能通过一些统计证明了设计这两个阈值的能取得更好的效率。

面试官：这小子可以啊，回答得很系统，也有一定的深度，由红黑树联想到AVL树，让我考考你关于树的知识

红黑树与平衡二叉树有什么区别？

（这不简单，经典问题，我给您来段表演）

红⿊树特点:

每个节点⾮红即⿊；
根节点总是⿊⾊的；
每个叶⼦节点都是⿊⾊的空节点（NIL节点）；
如果节点是红⾊的，则它的⼦节点必须是⿊⾊的（反之不⼀定）；
从根节点到叶节点或空⼦节点的每条路径，必须包含相同数⽬的⿊⾊节点（即相同的⿊⾊⾼
度）。

AVL树特点：

AVL树是一棵"严格"的平衡树, "被插入元素"到"根元素"的路径每个节点的左子树和右子树的高度差不能大于1.

红黑树与AVL树的应用场景

（好家伙）

在JDK中，hashSet、hashMap用到了红黑树这种数据结构；C++的STL同样也能见到红黑树的身影

而windows对进程地址空间的管理用到了AVL树。

为什么hashSet、hashMap用了红黑树而不用AVL树

写在前面，其实这个问题我没有找到很好的解答，如果有更好的解答欢迎评论区指正，我最近看了一篇测评文章，文章里面的测评数据显示AVL树在添加删除上确实慢于红黑树，但AVL树在查找上花的时间更少，平均来看AVL树的性能与红黑树并不差多少，这是我看的文章https://www.zhihu.com/question/19856999

既然我们要对比两个数据结构，从资源角度分析，红黑树节点比起AVL树节点仅需多维护一个颜色属性，总体来说相差不大，因此我仅从读写的角度进行分析：

读：红黑树是非严格的平衡树，根据前面介绍的特点，我们可以知道存储相同数据的情况下，红黑树的高度大小一般大于AVL树，从查找的角度分析，尽管他们的时间复杂度都为O（1），但红黑树的查找效率更差；

写：同样由于红黑树的性质，红黑树在增加删除节点时，恢复平衡需要付出的代价比AVL树更大

综上所述，在读多的环境下，最好使用AVL树，默认情况下一般使用红黑树。

面试官：小伙子你不错，分析问题有理有据，咱们二面见

#面试题目#