⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

No. 1 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

前⾔

14554 字 67 张⼿绘图，详解 29 道 Java 集合框架⾯试⾼频题（让天下没有难背的⼋股），

⾯渣背会这些 Java 容器⼋股⽂，这次吊打⾯试官，我觉得稳了（⼿动 dog）。整理：沉默王

⼆，戳转载链接，作者：三分恶，戳原⽂链接。

亮⽩版本更适合拿出来打印，这也是很多学⽣党喜欢的⽅式，打印出来背诵的效率会更⾼。

2024 年 12 ⽉ 30 ⽇开始着⼿第⼆版更新。

对于⾼频题，会标注在《Java ⾯试指南（付费）》中出现的位置，哪家公司，原题是什

么，并且会加 ，⽬录⼀⽬了然；如果你想节省时间的话，可以优先背诵这些题⽬，尽

快做到知彼知⼰，百战不殆。

区分⼋股精华回答版本和原理底层解释，让⼤家知其然知其所以然，同时⼜能做到⾯试时

的⾼效回答。

结合项⽬（技术派、pmhub）来组织语⾔，让⾯试官最⼤程度感受到你的诚意，⽽不是

机械化的背诵。

No. 2 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

修复第⼀版中出现的问题，包括球友们的私信反馈，⽹站留⾔区的评论，以及 GitHub 仓

库中的 issue，让这份⾯试指南更加完善。

增加⼆哥编程星球的球友们拿到的⼀些 offer，对⾯渣逆袭的感谢，以及对简历修改的⼀

些认可，以此来激励⼤家，给⼤家更多信⼼。

优化排版，增加⼿绘图，重新组织答案，使其更加⼝语化，从⽽更贴近⾯试官的预期。

⻓按识别下⾯的⼆维码，关注⼆哥的公众号，回复【222】即可拉取最新版本。

No. 3 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

当然了，请允许我的⼀点点私⼼，那就是星球的 PDF 版本会⽐公众号早⼀个⽉时间，毕竟星

球⽤户都付费过了，我有必要让他们先享受到⼀点点福利。相信⼤家也都能理解，毕竟在线

版是免费的，CDN、服务器、域名、OSS 等等都是需要成本的。

更别说我付出的时间和精⼒了，⼤家觉得有帮助还请给个⼝碑，让你身边的同事、同学都能

受益到。

No. 4 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

我把⼆哥的 Java 进阶之路、JVM 进阶之路、并发编程进阶之路，以及所有⾯渣逆袭的版本都

放进来了，涵盖 Java基础、Java集合、Java并发、JVM、Spring、MyBatis、计算机⽹络、

操作系统、MySQL、Redis、RocketMQ、分布式、微服务、设计模式、Linux 等 16 个⼤的

主题，共有 40 多万字，2000+张⼿绘图，可以说是诚意满满。

展示⼀下暗⿊版本的 PDF 吧，排版清晰，字体优雅，更加适合夜服，晚上看会更舒服⼀点。

No. 5 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

引⾔

1. 说说有哪些常⻅的集合框架？

推荐阅读：⼆哥的 Java 进阶之路：Java 集合框架

推荐阅读：阻塞队列 BlockingQueue。

No. 6 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

集合框架可以分为两条⼤的⽀线：

①、第⼀条⽀线 Collection，主要由 List、Set、Queue 组成：

List 代表有序、可重复的集合，典型代表就是封装了动态数组的 ArrayList 和封装了链表

的 LinkedList；

Set 代表⽆序、不可重复的集合，典型代表就是 HashSet 和 TreeSet；

Queue 代表队列，典型代表就是双端队列 ArrayDeque，以及优先级队列

PriorityQueue。

②、第⼆条⽀线 Map，代表键值对的集合，典型代表就是 HashMap。

另外⼀个回答版本：

①、Collection 接⼝：最基本的集合框架表示⽅式，提供了添加、删除、清空等基本操作，它

主要有三个⼦接⼝：

List ：⼀个有序的集合，可以包含重复的元素。实现类包括 ArrayList、LinkedList 等。

Set ：⼀个不包含重复元素的集合。实现类包括 HashSet、LinkedHashSet、TreeSet

等。

Queue ：⼀个⽤于保持元素队列的集合。实现类包括 PriorityQueue、ArrayDeque 等。

No. 7 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

②、 Map 接⼝：表示键值对的集合，⼀个键映射到⼀个值。键不能重复，每个键只能对应⼀

个值。Map 接⼝的实现类包括 HashMap、LinkedHashMap、TreeMap 等。

集合框架有哪⼏个常⽤⼯具类？

集合框架位于 java.util 包下，提供了两个常⽤的⼯具类：

Collections：提供了⼀些对集合进⾏排序、⼆分查找、同步的静态⽅法。

Arrays：提供了⼀些对数组进⾏排序、打印、和 List 进⾏转换的静态⽅法。

简单介绍⼀下队列

Java 中的队列主要通过 Queue 接⼝和并发包下的 BlockingQueue 两个接⼝来实现。

优先级队列 PriorityQueue 实现了 Queue 接⼝，是⼀个⽆界队列，它的元素按照⾃然顺序排

序或者 Comparator ⽐较器进⾏排序。

No. 8 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

双端队列 ArrayDeque 也实现了 Queue 接⼝，是⼀个基于数组的，可以在两端插⼊和删除元

素的队列。

No. 9 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

LinkedList 实现了 Queue 接⼝的⼦类 Deque，所以也可以当做双端队列来使⽤。

No. 10 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

⽤过哪些集合类，它们的优劣？

我常⽤的集合类有 ArrayList、LinkedList、HashMap、LinkedHashMap。

1. ArrayList 可以看作是⼀个动态数组，可以在需要时动态扩容数组的容量，只不过需要复

制元素到新的数组。优点是访问速度快，可以通过索引直接查找到元素。缺点是插⼊和删

除元素可能需要移动或者复制元素。

2. LinkedList 是⼀个双向链表，适合频繁的插⼊和删除操作。优点是插⼊和删除元素的时候

只需要改变节点的前后指针，缺点是访问元素时需要遍历链表。

No. 11 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

3. HashMap 是⼀个基于哈希表的键值对集合。优点是可以根据键的哈希值快速查找到值，

但有可能会发⽣哈希冲突，并且不保留键值对的插⼊顺序。

4. LinkedHashMap 在 HashMap 的基础上增加了⼀个双向链表来保持键值对的插⼊顺序。

队列和栈的区别了解吗？

队列是⼀种先进先出（FIFO, First-In-First-Out）的数据结构，第⼀个加⼊队列的元素会成为

第⼀个被移除的元素。

栈是⼀种后进先出（LIFO, Last-In-First-Out）的数据结构，最后⼀个加⼊栈的元素会成为第

⼀个被移除的元素。

No. 12 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

哪些是线程安全的容器？

像 Vector、Hashtable、ConcurrentHashMap、CopyOnWriteArrayList、

ConcurrentLinkedQueue、ArrayBlockingQueue、LinkedBlockingQueue 都是线程安全的。

Collection 继承了哪些接⼝？

Collection 继承了 Iterable 接⼝，这意味着所有实现 Collection 接⼝的类都必须实现

iterator() ⽅法，之后就可以使⽤增强型 for 循环遍历集合中的元素了。

No. 13 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

1. Java ⾯试指南（付费）收录的⽤友⾦融⼀⾯原题：你了解哪些集合框架？

2. Java ⾯试指南（付费）收录的华为⼀⾯原题：说下 Java 容器和 HashMap

3. Java ⾯试指南（付费）收录的⼩⽶暑期实习同学 E ⼀⾯⾯试原题：你了解哪些

集合？

4. Java ⾯试指南（付费）收录的美团⾯经同学 16 暑期实习⼀⾯⾯试原题：知道哪

些集合，讲讲 HashMap 和 TreeMap 的区别，讲讲两者应⽤场景的区别；讲⼀

下有哪些队列，阻塞队列的阻塞是什么含义？

5. Java ⾯试指南（付费）收录的农业银⾏⾯经同学 7 Java 后端⾯试原题：⽤过哪

些集合类，它们的优劣

6. Java ⾯试指南（付费）收录的华为 OD ⾯经同学 1 ⼀⾯⾯试原题：队列和栈的

区别了解吗?

7. Java ⾯试指南（付费）收录的农业银⾏同学 1 ⾯试原题：阻塞队列的实现⽅式

No. 14 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

8. Java ⾯试指南（付费）收录的⼩公司⾯经合集同学 1 Java 后端⾯试原题：Java

容器有哪些？List、Set 还有 Map 的区别？

9. Java ⾯试指南（付费）收录的 360 ⾯经同学 3 Java 后端技术⼀⾯⾯试原题：

java 有哪些集合

10. Java ⾯试指南（付费）收录的华为⾯经同学 11 ⾯试原题：java 中的集合类型？

哪些是线程安全的？

11. Java ⾯试指南（付费）收录的招商银⾏⾯经同学 6 招银⽹络科技⾯试原题：

Java 集合有哪些？

12. Java ⾯试指南（付费）收录的⽤友⾯试原题：集合容器能列举⼏个吗?

13. Java ⾯试指南（付费）收录的⽐亚迪⾯经同学 12 Java 技术⾯试原题：java的

集合介绍⼀下

14. Java ⾯试指南（付费）收录的 OPPO ⾯经同学 1 ⾯试原题：介绍Java的集合框

架

15. Java ⾯试指南（付费）收录的vivo ⾯经同学 10 技术⼀⾯⾯试原题：Java中的

集合有哪些

List

2. ArrayList 和 LinkedList 有什么区别？

推荐阅读：⼆哥的 Java 进阶之路：ArrayList 和 LinkedList

ArrayList 是基于数组实现的，LinkedList 是基于链表实现的。

No. 15 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

ArrayList 和 LinkedList 的⽤途有什么不同？

多数情况下，ArrayList 更利于查找，LinkedList 更利于增删。

①、由于 ArrayList 是基于数组实现的，所以 get(int index) 可以直接通过数组下标获

取，时间复杂度是 O(1)；LinkedList 是基于链表实现的， get(int index) 需要遍历链表，

时间复杂度是 O(n)。

当然， get(E element) 这种查找，两种集合都需要遍历通过 equals ⽐较获取元素，所以时

间复杂度都是 O(n)。

②、ArrayList 如果增删的是数组的尾部，时间复杂度是 O(1)；如果 add 的时候涉及到扩容，

时间复杂度会上升到 O(n)。

但如果插⼊的是中间的位置，就需要把插⼊位置后的元素向前或者向后移动，甚⾄还有可能

触发扩容，效率就会低很多，变成 O(n)。

No. 16 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

LinkedList 因为是链表结构，插⼊和删除只需要改变前置节点、后置节点和插⼊节点的引⽤，

因此不需要移动元素。

如果是在链表的头部插⼊或者删除，时间复杂度是 O(1)；如果是在链表的中间插⼊或者删

除，时间复杂度是 O(n)，因为需要遍历链表找到插⼊位置；如果是在链表的尾部插⼊或者删

除，时间复杂度是 O(1)。

No. 17 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

ArrayList 和 LinkedList 是否⽀持随机访问？

①、ArrayList 是基于数组的，也实现了 RandomAccess 接⼝，所以它⽀持随机访问，可以通

过下标直接获取元素。

No. 18 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

②、LinkedList 是基于链表的，所以它没法根据下标直接获取元素，不⽀持随机访问。

ArrayList 和 LinkedList 内存占⽤有何不同？

ArrayList 是基于数组的，是⼀块连续的内存空间，所以它的内存占⽤是⽐较紧凑的；但如果

涉及到扩容，就会重新分配内存，空间是原来的 1.5 倍。

No. 19 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

LinkedList 是基于链表的，每个节点都有⼀个指向下⼀个节点和上⼀个节点的引⽤，于是每个

节点占⽤的内存空间⽐ ArrayList 稍微⼤⼀点。

ArrayList 和 LinkedList 的使⽤场景有什么不同？

ArrayList 适⽤于：

随机访问频繁：需要频繁通过索引访问元素的场景。

读取操作远多于写⼊操作：如存储不经常改变的列表。

末尾添加元素：需要频繁在列表末尾添加元素的场景。

LinkedList 适⽤于：

频繁插⼊和删除：在列表中间频繁插⼊和删除元素的场景。

不需要快速随机访问：顺序访问多于随机访问的场景。

队列和栈：由于其双向链表的特性，LinkedList 可以实现队列（FIFO）和栈（LIFO）。

链表和数组有什么区别？

数组在内存中占⽤的是⼀块连续的存储空间，因此我们可以通过数组下标快速访问任意元

素。数组在创建时必须指定⼤⼩，⼀旦分配内存，数组的⼤⼩就固定了。

链表的元素存储在于内存中的任意位置，每个节点通过指针指向下⼀个节点。

No. 20 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

1. Java ⾯试指南（付费）收录的京东同学 10 后端实习⼀⾯的原题：ArrayList 和

LinkedList 的时间复杂度

2. Java ⾯试指南（付费）收录的⼩⽶暑期实习同学 E ⼀⾯⾯试原题：你了解哪些

集合？

3. Java ⾯试指南（付费）收录的⼩⽶⾯经同学 F ⾯试原题：ArrayList和LinkedList

的区别和使⽤场景

4. Java ⾯试指南（付费）收录的⽐亚迪⾯经同学 12 Java 技术⾯试原题：数组和

链表的区别

5. Java ⾯试指南（付费）收录的快⼿同学 2 ⼀⾯⾯试原题：ArrayList和LinkedList

区别

6. Java ⾯试指南（付费）收录的得物⾯经同学 9 ⾯试题⽬原题：集合⾥⾯的

arraylist和linkedlist的区别是什么？有何优缺点？

3.ArrayList 的扩容机制了解吗？

了解。当往 ArrayList 中添加元素时，会先检查是否需要扩容，如果当前容量+1 超过数组⻓

度，就会进⾏扩容。

No. 21 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

扩容后的新数组⻓度是原来的 1.5 倍，然后再把原数组的值拷⻉到新数组中。

private void grow(int minCapacity) {

// overflow-conscious code

int oldCapacity = elementData.length;

int newCapacity = oldCapacity + (oldCapacity >> 1);

if (newCapacity - minCapacity < 0)

newCapacity = minCapacity;

if (newCapacity - MAX_ARRAY_SIZE > 0)

newCapacity = hugeCapacity(minCapacity);

// minCapacity is usually close to size, so this is a win:

elementData = Arrays.copyOf(elementData, newCapacity);

}

1. Java ⾯试指南（付费）收录的联想⾯经同学 7 ⾯试原题：Java 集合类介绍，挑

⼀个讲原理。

4.ArrayList 怎么序列化的知道吗？

No. 22 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

在 ArrayList 中，writeObject ⽅法被重写了，⽤于⾃定义序列化逻辑：只序列化有效数据，因

为 elementData 数组的容量⼀般⼤于实际的元素数量，声明的时候也加了 transient 关键字。

为什么 ArrayList 不直接序列化元素数组呢？

出于效率的考虑，数组可能⻓度 100，但实际只⽤了 50，剩下的 50 没⽤到，也就不需要序

列化。

private void writeObject(java.io.ObjectOutputStream s)

throws java.io.IOException {

// 将当前 ArrayList 的结构进⾏序列化

int expectedModCount = modCount;

s.defaultWriteObject(); // 序列化⾮ transient 字段

// 序列化数组的⼤⼩

s.writeInt(size);

// 序列化每个元素

for (int i = 0; i < size; i++) {

s.writeObject(elementData[i]);

}

// 检查是否在序列化期间发⽣了并发修改

if (modCount != expectedModCount) {

throw new ConcurrentModificationException();

}

No. 23 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

}

5.快速失败fail-fast了解吗？

fail—fast 是 Java 集合的⼀种错误检测机制。

在⽤迭代器遍历集合对象时，如果线程 A 遍历过程中，线程 B 对集合对象的内容进⾏了修

改，就会抛出 Concurrent Modification Exception。

迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使⽤⼀个 modCount 变量。集合

在被遍历期间如果内容发⽣变化，就会改变 modCount 的值。每当迭代器使⽤

hashNext()/next() 遍历下⼀个元素之前，都会检测 modCount 变量是否为

expectedmodCount 值，是的话就返回遍历；否则抛出异常，终⽌遍历。

异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发⽣变化时

修改 modCount 值刚好⼜设置为了 expectedmodCount 值，则异常不会抛出。因此，不能依

赖于这个异常是否抛出⽽进⾏并发操作的编程，这个异常只建议⽤于检测并发修改的 bug。

java.util 包下的集合类都是快速失败的，不能在多线程下发⽣并发修改（迭代过程中被修

改），⽐如 ArrayList 类。

什么是安全失败（fail—safe）呢？

采⽤安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，⽽是先复制原有集

合内容，在拷⻉的集合上进⾏遍历。

原理：由于迭代时是对原集合的拷⻉进⾏遍历，所以在遍历过程中对原集合所作的修改并不

能被迭代器检测到，所以不会触发 Concurrent Modification Exception。

缺点：基于拷⻉内容的优点是避免了 Concurrent Modification Exception，但同样地，迭代器

并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那⼀刻拿到的集合拷⻉，在遍历

期间原集合发⽣的修改迭代器是不知道的。

场景：java.util.concurrent 包下的容器都是安全失败，可以在多线程下并发使⽤，并发修改，

⽐如 CopyOnWriteArrayList 类。

6.有哪⼏种实现 ArrayList 线程安全的⽅法？

No. 24 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

常⽤的有两种。

可以使⽤ Collections.synchronizedList() ⽅法，它可以返回⼀个线程安全的 List。

SynchronizedList list = Collections.synchronizedList(new ArrayList());

内部是通过 synchronized 关键字加锁来实现的。

也可以直接使⽤ CopyOnWriteArrayList，它是线程安全的 ArrayList，遵循写时复制的原则，

每当对列表进⾏修改时，都会创建⼀个新副本，这个新副本会替换旧的列表，⽽对旧列表的

所有读取操作仍然在原有的列表上进⾏。

CopyOnWriteArrayList list = new CopyOnWriteArrayList();

通俗的讲，CopyOnWrite 就是当我们往⼀个容器添加元素的时候，不直接往容器中添加，⽽

是先复制出⼀个新的容器，然后在新的容器⾥添加元素，添加完之后，再将原容器的引⽤指

向新的容器。多个线程在读的时候，不需要加锁，因为当前容器不会添加任何元素。这样就

实现了线程安全。

ArrayList 和 Vector 的区别？

Vector 属于 JDK 1.0 时期的遗留类，不推荐使⽤，仍然保留着是因为 Java 希望向后兼容。

ArrayList 是在 JDK 1.2 时引⼊的，⽤于替代 Vector 作为主要的⾮同步动态数组实现。因为

Vector 所有的⽅法都使⽤了 synchronized 关键字进⾏同步，所以单线程环境下效率较低。

No. 25 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

1. Java ⾯试指南（付费）收录的招商银⾏⾯经同学 6 招银⽹络科技⾯试原题：线

程不安全的集合变成线程安全的⽅法？

2. Java ⾯试指南（付费）收录的 ⽐亚迪⾯经同学2⾯试原题：ArrayList 和 vector

的区别

7.CopyOnWriteArrayList 了解多少？

CopyOnWriteArrayList 就是线程安全版本的 ArrayList。

CopyOnWrite ——写时复制，已经明示了它的原理。

CopyOnWriteArrayList 采⽤了⼀种读写分离的并发策略。CopyOnWriteArrayList 容器允许并

发读，读操作是⽆锁的。⾄于写操作，⽐如说向容器中添加⼀个元素，⾸先将当前容器复制

⼀份，然后在新副本上执⾏写操作，结束之后再将原容器的引⽤指向新容器。

No. 26 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

Map

Map 中最重要的就是 HashMap 了，⾯试基本被问出包浆了，⼀定要好好准备。

8. 能说⼀下 HashMap 的底层数据结构吗？

推荐阅读：⼆哥的 Java 进阶之路：详解 HashMap

JDK 8 中 HashMap 的数据结构是 数组 + 链表 + 红⿊树 。

No. 27 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

数组⽤来存储键值对，每个键值对可以通过索引直接拿到，索引是通过对键的哈希值进⾏进

⼀步的 hash() 处理得到的。

当多个键经过哈希处理后得到相同的索引时，需要通过链表来解决哈希冲突——将具有相同

索引的键值对通过链表存储起来。

不过，链表过⻓时，查询效率会⽐较低，于是当链表的⻓度超过 8 时（且数组的⻓度⼤于

64），链表就会转换为红⿊树。红⿊树的查询效率是 O(logn)，⽐链表的 O(n) 要快。

hash() ⽅法的⽬标是尽量减少哈希冲突，保证元素能够均匀地分布在数组的每个位置上。

static final int hash(Object key) {

int h;

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

}

如果键的哈希值已经在数组中存在，其对应的值将被新值覆盖。

HashMap 的初始容量是 16，随着元素的不断添加，HashMap 就需要进⾏扩容，阈值是

capacity * loadFactor ，capacity 为容量，loadFactor 为负载因⼦，默认为 0.75。

No. 28 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

扩容后的数组⼤⼩是原来的 2 倍，然后把原来的元素重新计算哈希值，放到新的数组中。

1. Java ⾯试指南（付费）收录的⼩⽶ 25 届⽇常实习⼀⾯原题：讲⼀讲 HashMap

的原理

2. Java ⾯试指南（付费）收录的华为⼀⾯原题：说下 Java 容器和 HashMap

3. Java ⾯试指南（付费）收录的华为⼀⾯原题：说下 Redis 和 HashMap 的区别

4. Java ⾯试指南（付费）收录的国企⾯试原题：说说 HashMap 的底层数据结

构，链表和红⿊树的转换，HashMap 的⻓度

5. Java ⾯试指南（付费）收录的⼩⽶春招同学 K ⼀⾯⾯试原题：说⼀下 HashMap

数据库结构 和 ⼀些重要参数

6. Java ⾯试指南（付费）收录的腾讯云智⾯经同学 16 ⼀⾯⾯试原题：HashMap

的底层实现，它为什么是线程不安全的？

7. Java ⾯试指南（付费）收录的快⼿⾯经同学 1 部⻔主站技术部⾯试原题：

HashMap 的结构？

8. Java ⾯试指南（付费）收录的百度⾯经同学 1 ⽂⼼⼀⾔ 25 实习 Java 后端⾯试

原题：hashmap 的底层实现原理、put()⽅法实现流程、扩容机制？

9. Java ⾯试指南（付费）收录的腾讯⾯经同学 27 云后台技术⼀⾯⾯试原题：

Hashmap的底层？为什么链表要变成红⿊树？为什么不⽤平衡⼆叉树？

9.你对红⿊树了解多少？

红⿊树是⼀种⾃平衡的⼆叉查找树：

1. 每个节点要么是红⾊，要么是⿊⾊；

2. 根节点永远是⿊⾊；

3. 所有的叶⼦节点都是是⿊⾊的（下图中的 NULL 节点）；

4. 红⾊节点的⼦节点⼀定是⿊⾊的；

5. 从任⼀节点到其每个叶⼦的所有简单路径都包含相同数⽬的⿊⾊节点。

No. 29 / 82

 ⾯渣逆袭集合框架篇V2-让天下所有的⾯渣都能逆袭

为什么不⽤⼆叉树？

⼆叉树是最基本的树结构，每个节点最多有两个⼦节点，但是⼆叉树容易出现极端情况，⽐

如插⼊的数据是有序的，那么⼆叉树就会退化成链表，查询效率就会变成 O(n)。

为什么不⽤平衡⼆叉树？

平衡⼆叉树⽐红⿊树的要求更⾼，每个节点的左右⼦树的⾼度最多相差 1，这种⾼度的平衡保

证了极佳的查找效率，但在进⾏插⼊和删除操作时，可能需要频繁地进⾏旋转来维持树的平

衡，维护成本更⾼。

为什么⽤红⿊树？

链表的查找时间复杂度是 O(n) ，当链表⻓度较⻓时，查找性能会下降。红⿊树是⼀种折中

的⽅案，查找、插⼊、删除的时间复杂度都是 O(log n) 。

1. Java ⾯试指南（付费）收录的携程⾯经同学 1 Java 后端技术⼀⾯⾯试原题：

HashMap 为什么⽤红⿊树，链表转数条件，红⿊树插⼊删除规则

2. Java ⾯试指南（付费）收录的快⼿同学 2 ⼀⾯⾯试原题：为什么HashMap采⽤

红⿊树？

No. 30 / 82