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树,让我考考你关于树的知识

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

(这不简单,经典问题,我给您来段表演)

红⿊树特点:

  1. 每个节点⾮红即⿊;
  2. 根节点总是⿊⾊的;
  3. 每个叶⼦节点都是⿊⾊的空节点(NIL节点);
  4. 如果节点是红⾊的,则它的⼦节点必须是⿊⾊的(反之不⼀定);
  5. 从根节点到叶节点或空⼦节点的每条路径,必须包含相同数⽬的⿊⾊节点(即相同的⿊⾊⾼
    度)。

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树,默认情况下一般使用红黑树。

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

#面试题目#
全部评论
关于最后,有点疑问,查找时间复杂度是O(logn)吧,还有恢复平衡旋转时,是不是红黑树的旋转次数小于AVL树呀,请指教
2 回复
分享
发布于 2021-04-13 11:20
tql,虽然不搞JAVA,但感觉还是得了解下hashMap问啥
点赞 回复
分享
发布于 2021-03-21 10:21
百信银行
校招火热招聘中
官网直投
感谢参与【创作者计划2期·技术干货场】!欢迎更多牛油来写干货,瓜分总计20000元奖励!!技术干货场活动链接:https://www.nowcoder.com/link/czz2jsghtlq(参与奖马克杯将于每周五结算,敬请期待~)
点赞 回复
分享
发布于 2021-03-25 20:02
想问一下,文章最后说,红黑树的添加和删除虽然比AVL树更快,但是红黑树恢复平衡比AVL书慢,而且红黑树的查找比AVL树要慢;综合考虑这两种情况,为啥hashSet和hashMap还要使用红黑树啊😂
点赞 回复
分享
发布于 2021-06-16 21:07

相关推荐

18 82 评论
分享
牛客网
牛客企业服务