HashMap夺命连环问面试题分享给需要同学.docx资源-CSDN文库

版权申诉

155 浏览量 2024-09-15 22:30:03 上传评论收藏 21KB DOCX 举报

资源推荐

资源详情

资源评论

# 模拟面试之 HashMap

>所有题必须很熟，这个点基本是必问，需要好好看看源码

## ...\

### 1.HashMap 的底层数据结构是什么？

底层数据结构是哈希表结构（链表散列：数组+单向链表），结合了数组和链表的优点，当链

表长度超过 8 时，链表会转为红黑树。数组中的每一个元素都是链表。总结来说就是 HashMap

在 JDK1.8 之前底层是由数组+链表实现的，在 JDK1.8 开始底层是由数组+链表或者数组+红黑

树实现的。

### 追问：为什么在 1.8 中增加红黑树？

当需要查找某个元素的时候，线性探索是最直白的方式，它会把所有数据遍历一遍直到找到

你所查找的数据，对于数组和链表这种线性结构来说，当链表长度过长（数据有成百上千）

的时候，会造成链表过深的问题，这种查找方式效率极低，时间复杂度是 O(n)。简单来说红

黑树的出现就是为了提高数据检索的速度。

### 追问：链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红

黑树？

二叉树在特殊情况下会变成一条线性结构，这就跟原来的链表结构一样了，选择红黑树就是

为了解决二叉树的缺陷。

红黑树在插入数据的时候需要通过左旋、右旋、变色这些操作来保持平衡，为了保持这种平

衡是需要付出代价的。当链表很短的时候，没必要使用红黑树，否则会导致效率更低，当链

表很长的时候，使用红黑树，保持平衡的操作所消耗的资源要远小于遍历链表锁消耗的效率，

所以才会设定一个阈值，去判断什么时候使用链表，什么时候使用红黑树。

### 追问：讲一下你对红黑树的认识

每个节点非红即黑

根节点总是黑色的

如果节点是红色，则它的子节点必须是黑色（反之不一定）

每个叶子节点都是黑色的空节点

从根节点到叶子节点或者空节点的每条路径必须包含相同数量的黑色节点（黑色节点的深度

相同）

### 2.讲一下 HashMap 的工作原理，put()和 get()的过程分别是怎么样的？

**存储对象时，将 key 和 vaule 传给 put()方法：**

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余7页未读，立即下载

内容反馈

版权申诉

飞翔的佩奇

粉丝: 6088
资源: 1603

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip