数据结构 - HashMap 面试题及答案

返回HashMap 面试题索引 第 1/5 章

1.能说一下HashMap的数据结构吗？

JDK1.7的数据结构是数组+链表，JDK1.7还有人在用？不会吧……

说一下JDK1.8的数据结构吧：

JDK1.8的数据结构是数组+链表+红黑树。

数据结构示意图如下：

其中，桶数组是用来存储数据元素，链表是用来解决冲突，红黑树是为了提高查询的效率。

• 数据元素通过映射关系，也就是散列函数，映射到桶数组对应索引的位置
• 如果发生冲突，从冲突的位置拉一个链表，插入冲突的元素
• 如果链表长度>8&数组大小>=64，链表转为红黑树
• 如果红黑树节点个数<6 ，转为链表

点击这里👇🏻获取：企业智能知识库系统、100万QPS短链系统、复杂的商城微服务系统、智能翻译助手AI Agent、SaaS点餐系统、刷题吧小程序、商城系统、秒杀系统、AI项目、代码生成神器、企业智能招聘系统、智能天气播报AI Agent、智能代码审查AI Agent、智能商品推荐系统等 12 个项目的：项目源代码、开发教程和技术答疑

2.你对红黑树了解多少？为什么不用二叉树/平衡树呢？

红黑树本质上是一种二叉查找树，为了保持平衡，它又在二叉查找树的基础上增加了一些规则：

1. 每个节点要么是红色，要么是黑色；
2. 根节点永远是黑色的；
3. 所有的叶子节点都是是黑色的（注意这里说叶子节点其实是图中的 NULL 节点）；
4. 每个红色节点的两个子节点一定都是黑色；
5. 从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点；

之所以不用二叉树：

红黑树是一种平衡的二叉树，插入、删除、查找的最坏时间复杂度都为 O(logn)，避免了二叉树最坏情况下的O(n)时间复杂度。

之所以不用平衡二叉树：

平衡二叉树是比红黑树更严格的平衡树，为了保持保持平衡，需要旋转的次数更多，也就是说平衡二叉树保持平衡的效率更低，所以平衡二叉树插入和删除的效率比红黑树要低。

3.红黑树怎么保持平衡的知道吗？

红黑树有两种方式保持平衡：旋转和染色。

• 旋转：旋转分为两种，左旋和右旋

• 染⾊：

最近建一些几十个工作内推群，各大城市都有，群里目前已经收集了很多内推岗位，大厂、中厂、小厂、外包都有。 欢迎HR、开发、测试、运维和产品加入。

扫描下方微信，备注：网站+所在城市，即可拉你进工作内推群。