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

前⾔ No. 1 / 63

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

前⾔

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

器⼋股⽂，这次吊打⾯试官，我觉得稳了（⼿动 dog）。整理：沉默王⼆，戳转载链接，作者：三分恶，戳原⽂链

接。

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

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

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

录⼀⽬了然；如果你想节省时间的话，可以优先背诵这些题⽬，尽快做到知彼知⼰，百战不殆。

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

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

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

份⾯试指南更加完善。

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

⼤家，给⼤家更多信⼼。

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

No. 2 / 63

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

码，关注⼆哥的公众号，回复【222】即可拉取最新版本。

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

我有必要让他们先享受到⼀点点福利。相信⼤家也都能理解，毕竟在线版是免费的，CDN、服务器、域名、OSS

等等都是需要成本的。

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

No. 3 / 63

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

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

基础、Java集合、Java并发、JVM、Spring、MyBatis、计算机⽹络、操作系统、MySQL、Redis、RocketMQ、分

布式、微服务、设计模式、Linux 等 16 个⼤的主题，共有 40 多万字，2000+张⼿绘图，可以说是诚意满满。

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

No. 4 / 63

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

引⾔

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

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

推荐阅读：阻塞队列 BlockingQueue。

No. 5 / 63

 ⾯渣逆袭集合框架篇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 等。

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

现类包括 HashMap、LinkedHashMap、TreeMap 等。

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

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

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

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

简单介绍⼀下队列

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

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

⽐较器进⾏排序。

No. 6 / 63

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

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

No. 7 / 63

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

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

No. 8 / 63

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

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

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

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

优点是访问速度快，可以通过索引直接查找到元素。缺点是插⼊和删除元素可能需要移动或者复制元素。

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

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

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

冲突，并且不保留键值对的插⼊顺序。

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

队列和栈的区别了解吗？

No. 9 / 63

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

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

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

哪些是线程安全的容器？

像 Vector、Hashtable、ConcurrentHashMap、CopyOnWriteArrayList、ConcurrentLinkedQueue、

ArrayBlockingQueue、LinkedBlockingQueue 都是线程安全的。

Collection 继承了哪些接⼝？

Collection 继承了 Iterable 接⼝，这意味着所有实现 Collection 接⼝的类都必须实现 iterator() ⽅法，之后就

可以使⽤增强型 for 循环遍历集合中的元素了。

No. 10 / 63

 ⾯渣逆袭集合框架篇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 ⾯试原题：阻塞队列的实现⽅式

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的集合介绍⼀下

No. 11 / 63

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

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

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

List

2. ArrayList 和 LinkedList 有什么区别？

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

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

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. 12 / 63

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

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

素。

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

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

No. 13 / 63

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

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

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

素。

No. 14 / 63

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

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

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

ArrayList 是基于数组的，是⼀块连续的内存空间，所以它的内存占⽤是⽐较紧凑的；但如果涉及到扩容，就会重

新分配内存，空间是原来的 1.5 倍。

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

⽐ ArrayList 稍微⼤⼀点。

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

ArrayList 适⽤于：

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

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

No. 15 / 63

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

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

LinkedList 适⽤于：

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

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

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

链表和数组有什么区别？

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

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

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

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. 16 / 63

 ⾯渣逆袭集合框架篇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 怎么序列化的知道吗？

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

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

No. 17 / 63

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

为什么 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();

}

}

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

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

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

Concurrent Modification Exception。

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

容发⽣变化，就会改变 modCount 的值。每当迭代器使⽤ hashNext()/next() 遍历下⼀个元素之前，都会检测

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

No. 18 / 63

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

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

好⼜设置为了 expectedmodCount 值，则异常不会抛出。因此，不能依赖于这个异常是否抛出⽽进⾏并发操作的

编程，这个异常只建议⽤于检测并发修改的 bug。

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

类。

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

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

上进⾏遍历。

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

以不会触发 Concurrent Modification Exception。

缺点：基于拷⻉内容的优点是避免了 Concurrent Modification Exception，但同样地，迭代器并不能访问到修改

后的内容，即：迭代器遍历的是开始遍历那⼀刻拿到的集合拷⻉，在遍历期间原集合发⽣的修改迭代器是不知道

的。

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

CopyOnWriteArrayList 类。

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

常⽤的有两种。

可以使⽤ 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. 19 / 63

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

1. Java ⾯试指南（付费）收录的招商银⾏⾯经同学 6 招银⽹络科技⾯试原题：线程不安全的集合变成线程

安全的⽅法？

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

7.CopyOnWriteArrayList 了解多少？

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

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

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

锁的。⾄于写操作，⽐如说向容器中添加⼀个元素，⾸先将当前容器复制⼀份，然后在新副本上执⾏写操作，结束

之后再将原容器的引⽤指向新容器。

No. 20 / 63

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

Map

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

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

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

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

数组⽤来存储键值对，每个键值对可以通过索引直接拿到，索引是通过对键的哈希值进⾏进⼀步的 hash() 处理得

到的。

No. 21 / 63

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

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

存储起来。

不过，链表过⻓时，查询效率会⽐较低，于是当链表的⻓度超过 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。

扩容后的数组⼤⼩是原来的 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. 22 / 63

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

为什么不⽤⼆叉树？

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

的，那么⼆叉树就会退化成链表，查询效率就会变成 O(n)。

为什么不⽤平衡⼆叉树？

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

率，但在进⾏插⼊和删除操作时，可能需要频繁地进⾏旋转来维持树的平衡，维护成本更⾼。

为什么⽤红⿊树？

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

删除的时间复杂度都是 O(log n) 。

1. Java ⾯试指南（付费）收录的携程⾯经同学 1 Java 后端技术⼀⾯⾯试原题：HashMap 为什么⽤红⿊

树，链表转数条件，红⿊树插⼊删除规则

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

10.红⿊树怎么保持平衡的？

旋转 和 染⾊ 。

①、通过左旋和右旋来调整树的结构，避免某⼀侧过深。

No. 23 / 63

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

②、染⾊，修复红⿊规则，从⽽保证树的⾼度不会失衡。

1. Java ⾯试指南（付费）收录的携程⾯经同学 1 Java 后端技术⼀⾯⾯试原题：HashMap 为什么⽤红⿊

树，链表转数条件，红⿊树插⼊删除规则

memo：2025 年 1 ⽉ 6 ⽇修改到此。

No. 24 / 63

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

11. HashMap 的 put 流程知道吗？

哈希寻址 → 处理哈希冲突（链表还是红⿊树）→ 判断是否需要扩容 → 插⼊/覆盖节点。

详细版：

第⼀步，通过 hash ⽅法进⼀步扰动哈希值，以减少哈希冲突。

static final int hash(Object key) {

int h;

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

}

No. 25 / 63

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

第⼆步，进⾏第⼀次的数组扩容；并使⽤哈希值和数组⻓度进⾏取模运算，确定索引位置。

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length;

if ((p = tab[i = (n - 1) & hash]) == null)

tab[i] = newNode(hash, key, value, null);

如果当前位置为空，直接将键值对插⼊该位置；否则判断当前位置的第⼀个节点是否与新节点的 key 相同，如果相

同直接覆盖 value，如果不同，说明发⽣哈希冲突。

如果是链表，将新节点添加到链表的尾部；如果链表⻓度⼤于等于 8，则将链表转换为红⿊树。

public V put(K key, V value) {

return putVal(hash(key), key, value, false, true);

}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {

Node<K,V>[] tab; Node<K,V> p; int n, i;

// 如果 table 为空，先进⾏初始化

if ((tab = table) == null || (n = tab.length) == 0)

n = (tab = resize()).length;

// 计算索引位置，并找到对应的桶

if ((p = tab[i = (n - 1) & hash]) == null)

tab[i] = newNode(hash, key, value, null); // 如果桶为空，直接插⼊

else {

Node<K,V> e; K k;

// 检查第⼀个节点是否匹配

if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))

e = p; // 覆盖

// 如果是树节点，放⼊树中

else if (p instanceof TreeNode)

e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

// 如果是链表，遍历插⼊到尾部

else {

for (int binCount = 0; ; ++binCount) {

if ((e = p.next) == null) {

p.next = newNode(hash, key, value, null);

// 如果链表⻓度达到阈值，转换为红⿊树

if (binCount >= TREEIFY_THRESHOLD - 1)

treeifyBin(tab, hash);

break;

}

if (e.hash == hash && ((k = e.key) == key || (key != null &&

key.equals(k))))

break; // 覆盖

p = e;

}

}

if (e != null) { // 如果找到匹配的 key，则覆盖旧值

No. 26 / 63

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

V oldValue = e.value;

if (!onlyIfAbsent || oldValue == null)

e.value = value;

afterNodeAccess(e);

return oldValue;

}

}

++modCount; // 修改计数器

if (++size > threshold)

resize(); // 检查是否需要扩容

afterNodeInsertion(evict);

return null;

}

每次插⼊新元素后，检查是否需要扩容，如果当前元素个数⼤于阈值（ capacity * loadFactor ），则进⾏扩

容，扩容后的数组⼤⼩是原来的 2 倍；并且重新计算每个节点的索引，进⾏数据重新分布。

只重写元素的 equals ⽅法没重写 hashCode，put 的时候会发⽣什么?

如果只重写 equals ⽅法，没有重写 hashCode ⽅法，那么会导致 equals 相等的两个对象，hashCode 不相等，

这样的话，两个对象会被 put 到数组中不同的位置，导致 get 的时候，⽆法获取到正确的值。

1. Java ⾯试指南（付费）收录的京东同学 10 后端实习⼀⾯的原题：hashcode 和 equals ⽅法只重写⼀个

⾏不⾏，只重写 equals 没重写 hashcode，map put 的时候会发⽣什么

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

3. Java ⾯试指南（付费）收录的百度⾯经同学 1 ⽂⼼⼀⾔ 25 实习 Java 后端⾯试原题：hashmap 的底层

实现原理、put()⽅法实现流程、扩容机制？

4. Java ⾯试指南（付费）收录的快⼿同学 2 ⼀⾯⾯试原题：HashMap存放元素流程

12.HashMap 怎么查找元素的呢？

通过哈希值定位索引 → 定位桶 → 检查第⼀个节点 → 遍历链表或红⿊树查找 → 返回结果。

No. 27 / 63

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

13.HashMap 的 hash 函数是怎么设计的?

先拿到 key 的哈希值，是⼀个 32 位的 int 类型数值，然后再让哈希值的⾼ 16 位和低 16 位进⾏异或操作，这样能

保证哈希分布均匀。

No. 28 / 63

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

static final int hash(Object key) {

int h;

// 如果 key 为 null，返回 0；否则，使⽤ hashCode 并进⾏扰动

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

}

14.为什么 hash 函数能减少哈希冲突？

快速回答：哈希表的索引是通过 h & (n-1) 计算的，n 是底层数组的容量；n-1 和某个哈希值做 & 运算，相当于

截取了最低的四位。如果数组的容量很⼩，只取 h 的低位很容易导致哈希冲突。

通过异或操作将 h 的⾼位引⼊低位，可以增加哈希值的随机性，从⽽减少哈希冲突。

解释⼀下。

以初始⻓度 16 为例，16-1=15。2 进制表示是 0000 0000 0000 0000 0000 0000 0000 1111 。只取最后 4 位相

等于哈希值的⾼位都丢弃了。

⽐如说 1111 1111 1111 1111 1111 1111 1111 1111，取最后 4 位，也就是 1111。

1110 1111 1111 1111 1111 1111 1111 1111，取最后 4 位，也是 1111。

不就发⽣哈希冲突了吗？

这时候 hash 函数 (h = key.hashCode()) ^ (h >>> 16) 就派上⽤场了。

No. 29 / 63

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

将哈希值⽆符号右移 16 位，意味着原哈希值的⾼ 16 位被移到了低 16 位的位置。这样，原始哈希值的⾼ 16 位和

低 16 位就可以参与到最终⽤于索引计算的低位中。

选择 16 位是因为它是 32 位整数的⼀半，这样处理既考虑了⾼位的信息，⼜没有完全忽视低位原本的信息，从⽽

达到了⼀种微妙的平衡状态。

举个例⼦（数组⻓度为 16）。

第⼀个键值对的键：h1 = 0001 0010 0011 0100 0101 0110 0111 1000

第⼆个键值对的键：h2 = 0001 0010 0011 0101 0101 0110 0111 1000

如果没有 hash 函数，直接取低 4 位，那么 h1 和 h2 的低 4 位都是 1000，也就是说两个键值对都会放在数组的第

8 个位置。

来看⼀下 hash 函数的处理过程。

①、对于第⼀个键 h1 的计算：

原始: 0001 0010 0011 0100 0101 0110 0111 1000

右移: 0000 0000 0000 0000 0001 0010 0011 0100

异或: ---------------------------------------

结果: 0001 0010 0011 0100 0100 0100 0100 1100

②、对于第⼆个键 h2 的计算：

原始: 0001 0010 0011 0101 0101 0110 0111 1000

右移: 0000 0000 0000 0000 0001 0010 0011 0101

异或: ---------------------------------------

结果: 0001 0010 0011 0101 0100 0100 0100 1101

通过上述计算，我们可以看到 h1 和 h2 经过 h ^ (h >>> 16) 操作后得到了不同的结果。

现在，考虑数组⻓度为 16 时（需要最低 4 位来确定索引）：

对于 h1 的最低 4 位是 1100 （⼗进制中为 12）

对于 h2 的最低 4 位是 1101 （⼗进制中为 13）

这样， h1 和 h2 就会被分别放在数组的第 12 个位置和第 13 个位置上，从⽽避免了哈希冲突。

1. Java ⾯试指南（付费）收录的⽀付宝⾯经同学 2 春招技术⼀⾯⾯试原题：为什么要⽤⾼低做异或运算？

为什么⾮得⾼低 16 位异或？

15.为什么 HashMap 的容量是 2 的幂次⽅？

是为了快速定位元素在底层数组中的下标。

HashMap 是通过 hash & (n-1) 来定位元素下标的，n 为数组的⼤⼩，也就是 HashMap 底层数组的容量。

数组⻓度-1 正好相当于⼀个“低位掩码”——掩码的低位最好全是 1，这样 & 运算才有意义，否则结果⼀定是 0。

2 幂次⽅刚好是偶数，偶数-1 是奇数，奇数的⼆进制最后⼀位是 1，也就保证了 hash &(length-1) 的最后⼀位

可能为 0，也可能为 1（取决于 hash 的值），这样可以保证哈希值的均匀分布。

No. 30 / 63