Java 基础核心复习笔记 (Day 03) —— 集合框架源码解析与实战

1. 集合框架总览 (The Big Picture)

Java 集合框架主要分为两大派系：Collection (单列集合) 和 Map (双列/键值对集合)。

1.1 List, Set, Queue, Map 的核心区别

接口	核心特性	典型实现	现实类比
List (列表)	有序、可重复	`ArrayList`, `LinkedList`	排队领号：有序号，张三可以领完再领一次。
Set (集合)	无序、唯一	`HashSet`, `TreeSet`	一袋弹珠：倒出来是乱的，且不能有两个完全一样的弹珠。
Queue (队列)	有序、先入先出	`ArrayDeque`, `PriorityQueue`	海底捞排队：先来的先吃，插队（优先级）看情况。
Map (映射)	键值对、Key 唯一	`HashMap`, `TreeMap`	字典/查户口：身份证号(Key)是唯一的，对应一个人(Value)。

1.2 集合框架继承关系全图

【Collection 体系】
Iterable (接口)
   └── Collection (接口)
          ├── List (接口)
          │     ├── ArrayList (实现类)  <-- AbstractList
          │     ├── LinkedList (实现类) <-- AbstractSequentialList
          │     └── Vector (古老实现类，线程安全)
          │
          ├── Set (接口)
          │     ├── HashSet (实现类)    <-- AbstractSet (底层是 HashMap)
          │     │     └── LinkedHashSet (子类)
          │     └── TreeSet (实现类)    <-- SortedSet (底层是 TreeMap)
          │
          └── Queue (接口)
                ├── PriorityQueue (实现类)
                └── Deque (双端队列接口)
                      ├── ArrayDeque (实现类)
                      └── LinkedList (它既是 List 也是 Queue!)

【Map 体系】
Map (接口)
   ├── HashMap (实现类)       <-- AbstractMap
   │     └── LinkedHashMap (子类)
   ├── TreeMap (实现类)       <-- SortedMap
   ├── Hashtable (古老实现类，线程安全)
   └── ConcurrentHashMap (JUC并发包)

🔥 大厂面试通关检查 (Section 1)

Q1: Collection 和 Collections 有什么区别？

A: 这两个概念经常被混淆，但它们完全不同。

Collection: 是 Java 集合框架的 顶层接口（Root Interface）。它是 List、Set 和 Queue 的父接口，定义了集合通用的方法，如 add(), remove(), size(), iterator() 等。注意，Map 不是继承自 Collection，它们是平级的。

Collections: 是一个 工具类（Utility Class），它位于 java.util 包下，提供了一系列 静态方法 来操作集合。常用功能包括：

排序: Collections.sort(list)。

搜索: Collections.binarySearch(list, key)。

线程安全包装: Collections.synchronizedList(list)，将普通 List 包装成线程安全的（虽然性能不如 JUC 包下的类）。

不可变包装: Collections.unmodifiableList(list)，返回一个只读视图，防止数据被篡改。

Q2: 哪些集合类是线程安全的？

A: 这个问题要分三类来回答，体现演进过程：

古老实现（JDK 1.0/1.1）: 如 Vector, Stack, Hashtable。它们通过在每个方法上加 synchronized 关键字实现线程安全。缺点是锁的粒度太粗，所有操作串行化，性能极差，现在基本已被淘汰，不推荐使用。

JUC 并发包（JDK 1.5+）: 这是推荐的方案。

ConcurrentHashMap: 使用 CAS + synchronized (JDK8) 或分段锁 (JDK7) 实现高并发读写。

CopyOnWriteArrayList: 适用于读多写少的场景，通过写时复制保证读操作无锁。

ArrayBlockingQueue: 线程池常用的阻塞队列，底层基于锁。

包装类: Collections.synchronizedList/Map。它仅仅是用一个简单的互斥锁（mutex）把普通集合的方法包了一层，并发性依然不高，但在不得不包装现有 List 时可以使用。

注意: 我们常用的 ArrayList, HashMap, HashSet 全都是线程不安全的，多线程并发扩容时可能导致死循环（JDK7 HashMap）或数据丢失。

Q3: 迭代器 (Iterator) 是什么？有什么特点？

A: Iterator 是 迭代器设计模式 的实现，它的核心作用是解耦。

统一遍历: 它提供了一种标准的方式来遍历任何实现了 Iterable 接口的集合（List, Set, Queue），无论底层是数组还是链表，使用者都不需要关心底层细节，只需要调用 hasNext() 和 next()。

安全删除: 这是面试重点。在遍历集合时，如果直接使用集合自己的 list.remove() 方法，会破坏数组索引或链表结构，导致 modCount 变化，从而触发 Fail-Fast 机制，抛出 ConcurrentModificationException。

原理: 而 Iterator.remove() 方法会在删除元素的同时，同步更新迭代器内部的 expectedModCount 和游标（cursor），保证遍历的安全性。这是在循环中删除元素的唯一正确姿势。

2. ArrayList 深度剖析 (The King of Collections)

ArrayList 是 Java 中最常用的集合，没有之一。它的本质是 动态数组。

2.1 ArrayList vs Array (数组)

🛠️ 图解：内存结构对比

1. 数组 (Array) int[] arr = new int[4];
   [ 10 | 20 | 30 | 0 ]  <-- 内存连续，长度锁死为 4

2. ArrayList list = new ArrayList<>();
   [ elementData 指针 ] ----> [ Object[] 数组: 10 | 20 | null | ... ]
                                     ^
                                     |
                             (容量不够时，自动换个更大的数组)

2.2 ArrayList 核心源码解析 (扩容机制) —— 逐行注释版

🔥 完整扩容链路解析 (JDK 1.8):

// 1. 入口：添加元素
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // 检查容量，不够则扩容
    elementData[size++] = e; // 赋值
    return true;
}

// 2. 内部容量检查
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 第一次 add，容量初始化为 10
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

// 3. 【核心】扩容方法 grow
private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    // 新容量 = 1.5 倍旧容量
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    // 边界修正
    if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity);
    
    // 物理扩容：数据搬移
    elementData = Arrays.copyOf(elementData, newCapacity);
}

🔥 大厂面试通关检查 (Section 2)

Q1: Arrays.asList() 获得的 List 有什么坑？

A: 这是一个经典的面试坑点，被称为 “假 List”。

本质: Arrays.asList() 返回的并不是 java.util.ArrayList，而是 java.util.Arrays 类内部定义的一个静态内部类，名字也叫 ArrayList（Arrays$ArrayList）。

缺陷: 这个内部类继承自 AbstractList，但没有重写 add() 和 remove() 方法。因为它的底层直接引用了原始数组，长度是固定的。

后果: 如果你对这个 List 调用 add 或 remove，会直接抛出 UnsupportedOperationException 运行时异常。

关联: 此外，因为它是原数组的视图（View），如果你在外部修改了原数组（例如 arr[0] = 99），List 里的数据也会跟着变，反之亦然。

解决: 如果需要一个可操作的 List，必须包装一层：new ArrayList<>(Arrays.asList(arr))。

Q2: ArrayList 的 subList 结果可以直接强转成 ArrayList 吗？

A: 绝对不可以，会报 ClassCastException。

原理: subList 返回的是 ArrayList 的一个内部类 SubList。它并不是一个新的独立的 ArrayList 对象，而是一个 视图 (View)。它内部持有原数组的引用 root，以及偏移量 offset 和 size。

类型: SubList 和 ArrayList 都是 AbstractList 的子类，它们是兄弟关系，不是父子关系，所以无法强转。

并发坑点: 因为是视图，对 SubList 的修改（如 add/remove）会直接反映到原 List 上。更危险的是，如果在生成 SubList 之后，你直接修改了 原 List 的结构（比如删了一个元素），那么 SubList 就会检测到 modCount 不一致，再次使用 SubList 时会立刻抛出 ConcurrentModificationException。这在实际开发中非常容易导致 Bug。

Q3: 为什么 ArrayList 频繁扩容会影响性能？如何优化？

A: 扩容是 ArrayList 最大的性能杀手。

时间成本: 扩容的核心操作是 System.arraycopy。虽然这是 Native 方法，但在堆内存中开辟一块巨大的新连续内存，并将老数据一个个拷贝过去，依然是非常耗时的 CPU 密集型操作。

空间成本: 扩容过程中，内存中会同时存在“老数组”和“新数组”。数据搬完后，老数组变成垃圾对象。频繁扩容会产生大量临时的大对象，导致 JVM 频繁触发 Young GC，甚至因为空间碎片触发 Full GC，造成系统停顿（STW）。

优化方案: 如果你在编码时能够预估数据的大致数量，一定要使用带参数的构造方法 new ArrayList<>(initialCapacity) 来指定初始容量。例如从数据库查 1000 条数据，就直接 new 1000，避免从 10 -> 15 -> 22 … 一路扩容上来。

3. ArrayList vs LinkedList 终极对决

3.1 核心操作源码对比

3.2.1 随机访问对比 (`get(index)`)

ArrayList:

public E get(int index) {
    rangeCheck(index);
    return elementData(index); // O(1) 直接内存寻址
}

LinkedList:

Node<E> node(int index) {
    // 虽然有折半查找优化，但本质还是循环遍历
    // O(N)
    if (index < (size >> 1)) { ...从头找... } 
    else { ...从尾找... }
}

3.2.2 元素删除对比 (`remove`)

ArrayList:

1 2	// O(N) - 需要搬移数组 System.arraycopy(elementData, index+1, elementData, index, numMoved);

LinkedList:

1
2
3

// O(1) - 仅修改指针 (前提是已找到节点)
prev.next = next;
next.prev = prev;

🔥 大厂面试通关检查 (Section 3)

Q1: 既然 LinkedList 插入删除只需要 O(1)，为什么实际上大厂开发规范推荐尽量用 ArrayList？

A: 这是一个典型的 理论 vs 工程实践 的差距。虽然理论上链表插入只需改指针，但在现代计算机架构下，ArrayList 往往完胜：

CPU 缓存亲和性 (Cache Locality): 这是最关键的。ArrayList 内存连续，CPU 加载数据到 L1/L2 缓存时，会预读取后续数据（Cache Line）。遍历数组时缓存命中率极高。而 LinkedList 节点散落在堆内存各处，CPU 只能频繁访问主存，导致大量 Cache Miss，性能断崖式下跌。

查找成本: 这里的 O(1) 是指“已拿到节点”后的操作。但如果要在第 N 个位置插入，LinkedList 必须先花 O(N) 的时间遍历找到那个位置，这抵消了指针操作的优势。

内存开销: LinkedList 每个节点除了存数据，还要存 prev 和 next 两个指针。在 64 位 JVM 上，这额外消耗了 16 字节。如果存 100 万个 Integer，链表光指针就要多吃几百 MB 内存，极其浪费。

Q2: ArrayList 和 LinkedList 遍历时，分别用什么方式效率最高？

A: 选错遍历方式会导致严重的性能事故。

ArrayList: 实现了 RandomAccess 接口，意味着它支持快速随机访问。使用 普通 for 循环 (for (int i=0; i<size; i++)) 配合 get(i) 效率最高，因为它直接通过数组下标定位，没有任何额外开销。

LinkedList: 绝对禁止使用普通 for 循环。因为 LinkedList.get(i) 需要从头遍历。如果你写了 for(i) 循环，每次 get(i) 都要重头数，时间复杂度会变成恐怖的 O(N^2)。

LinkedList 正解: 必须使用 迭代器 (Iterator 或 foreach)。迭代器内部维护了当前节点的引用，next() 操作只是指针后移，复杂度是 O(1)，整体遍历是 O(N)。

Q3: LinkedList 是线程安全的吗？如何实现线程安全？

A: LinkedList 和 ArrayList 一样，都是 线程不安全 的。

问题: 多线程并发 add 时，可能发生节点覆盖、指针断裂（形成环），或者 size 计数不准确。

解决方案:

包装: 使用 Collections.synchronizedList(new LinkedList<>())。这相当于给所有方法加了一把大锁，并发度低。

替代方案 (推荐): 如果需要并发队列，应该直接使用 JUC 包下的专用队列：

ConcurrentLinkedQueue: 基于 CAS 的无锁非阻塞队列，性能极高。

LinkedBlockingQueue: 基于锁的阻塞队列，适合生产者-消费者模型。

4. 集合的 Fail-Fast 与 Fail-Safe

4.1 Fail-Fast (快速失败)

原理: 迭代器遍历时检查 modCount == expectedModCount。
源码: checkForComodification()。

4.2 Fail-Safe (安全失败)

原理: COW (Copy-On-Write)，写副本，读旧数据。

🔥 大厂面试通关检查 (Section 4)

Q1: CopyOnWriteArrayList (COW) 有什么缺点？

A: COW 虽然解决了并发读写问题，但代价是沉重的：

内存占用翻倍: 它的写操作核心是 Arrays.copyOf。每次执行 add 或 set，都需要把整个原数组复制一份到新数组。如果数组很大（比如 100MB），瞬间内存占用会翻倍，极易触发 Young GC 甚至 Full GC。

写性能极差: 因为全是深拷贝，写操作的时间复杂度是 O(N)。它只适合 读多写少 的场景（如配置列表、白名单），绝不适合写操作频繁的场景。

数据最终一致性: 它是 Fail-Safe 的，迭代器遍历的是“快照”数据。如果在遍历期间有新数据写入，迭代器是看不到的。这意味着你读到的数据可能已经过时了。

Q2: 为什么 JUC 包下的集合（如 ConcurrentHashMap）通常是 Fail-Safe 的？

A: 这体现了高并发场景下的设计权衡：可用性 > 一致性。

Fail-Fast: 如果像 HashMap 那样，一发现并发修改就抛 ConcurrentModificationException 程序崩溃，那在高并发系统中，服务将完全不可用。

Fail-Safe: JUC 集合（如 ConcurrentHashMap）采用了弱一致性迭代器。它们的迭代器原理不是基于 modCount，而是基于特定的遍历算法（如遍历链表/红黑树节点）。即使在遍历过程中链表头节点变了，或者树结构旋转了，迭代器依然能保证不崩溃、不陷入死循环，尽可能遍历完所有数据。虽然可能读到脏数据（漏掉刚插入的或读到已删除的），但保证了系统的稳定运行。

Q3: 在 foreach 循环中删除元素，为什么一定要用 Iterator.remove()？

A: 这是一个关于 Java 语法糖的陷阱。

现象: 编写 for (String s : list) { list.remove(s); } 会抛出 ConcurrentModificationException。

原理: foreach 编译后就是 Iterator。

调用 list.remove(s) 时，ArrayList 内部的 modCount 增加了。

但是，Iterator 对象内部维护的 expectedModCount 没有变。

下次循环调用 iterator.next() 时，第一行代码就是 checkForComodification()，发现两者不一致，直接抛异常。

正确做法: iterator.remove() 方法是特权的。它在删除元素后，会手动同步更新 expectedModCount = modCount，让迭代器知道“这次修改是我自己干的，不是别人干扰的”，从而继续安全遍历。

5. Queue 与 Set 简析

5.1 ArrayBlockingQueue vs LinkedBlockingQueue

ABQ: 数组，一把锁。
LBQ: 链表，两把锁。

5.2 Set 三剑客

HashSet: HashMap 的 Key。

🔥 大厂面试通关检查 (Section 5)

Q1: HashSet 如何判断两个对象是否相等？(去重原理)

A: HashSet 的去重完全依赖于 HashMap 的 Key 机制。判断流程如下：

HashCode 过滤: 首先调用对象的 hashCode() 计算哈希值，并经过扰动函数计算出在数组中的索引位置。如果该位置为空，说明没有重复，直接插入。

HashCode 比较: 如果位置不为空（哈希冲突），则遍历链表/红黑树。先比较当前元素的 Hash 值与链表中元素的 Hash 值是否相等。如果不等，肯定不是同一个对象。

Equals 确认: 只有在 Hash 值相等的情况下，才会调用 equals() 方法进行最终的内容比对。如果 equals 返回 true，则视为重复，新元素会覆盖旧元素（或被忽略）。

结论: 存入 Set 的对象必须同时严格重写 hashCode 和 equals，否则去重会失效。

Q2: PriorityQueue 是有序的吗？底层原理是什么？

A: 很多同学以为遍历 PriorityQueue 会得到有序结果，这是错的。

原理: PriorityQueue 底层是基于数组实现的 二叉堆（通常是小顶堆）。堆的特性只保证 堆顶（根节点/数组[0]） 是最小元素，且任意父节点小于子节点。但是，兄弟节点之间、跨层节点之间是没有顺序关系的。

现象: 当你使用 iterator 或 foreach 遍历时，其实是直接遍历底层的数组，输出的顺序看起来是乱序的。

正确用法: 只有通过不断调用 poll() 方法，每次取出并移除堆顶元素，并触发堆的调整（siftDown），才能得到一个有序的序列。

Q3: BlockingQueue 中 add, offer, put 的区别？

A: 这三个方法在队列满时的行为截然不同，这在线程池任务拒绝策略中非常关键：

add(e): 暴力。如果队列满了，直接抛出 IllegalStateException: Queue full 异常。这可能导致业务逻辑中断。

offer(e): 友好。如果队列满了，它不会抛错，而是返回 false。通常配合 if (!queue.offer(e)) 来做降级处理（如丢弃任务或记录日志）。还有一个重载方法 offer(e, time, unit) 可以等待一段时间。

put(e): 阻塞。这是阻塞队列的核心。如果队列满了，当前线程会被 挂起（Block），进入等待状态，直到队列有空位才会被唤醒。这在生产者-消费者模型中用于实现“背压”（Backpressure），防止生产者生产过快压垮消费者。

6. 思考题答案与深度解析

6.1 代码纠错题：遍历中删除

题目复现:

List<String> list = new ArrayList<>();
list.add("a");
for (String s : list) {
    if ("a".equals(s)) {
        list.remove(s); // 这里会发生什么？
    }
}

深度解析: 这是一道非常经典的“陷阱题”。许多人知道会报错，但说不清原理和正确姿势。

为什么会报错？（源码级分析）
- 语法糖拆解: for (String s : list) 在编译后，实际上变成了 Iterator 的遍历模式。
- 罪魁祸首: 当代码执行 list.remove(s) 时，它调用的是 ArrayList 自身的 remove 方法。这个方法会执行 modCount++，表示集合结构发生了一次修改。
- Fail-Fast 触发: 循环进入下一次，调用迭代器的 it.next() 方法获取下一个元素。next() 方法的第一行代码就是 checkForComodification()。
- 崩溃现场: checkForComodification 检查发现 modCount（已被 list.remove 修改为 N+1）与迭代器自己保存的 expectedModCount（依然是 N）不一致！于是，它判定集合在遍历期间被“非法”修改了，立即抛出 ConcurrentModificationException。
正确做法是什么？
- 方案一：使用 Iterator 的 remove (推荐)
  1
  2
  3
  4
  5
  6
  Iterator<String> it = list.iterator();
  while (it.hasNext()) {
  if ("a".equals(it.next())) {
  it.remove(); // 关键：调用迭代器的 remove
  }
  }
  - 原理: it.remove() 方法不仅会删除元素，还会同步更新 expectedModCount = modCount。这样下一次 next() 检查时，两个值依然相等，就不会报错了。
- 方案二：Java 8 的 removeIf (优雅)
  1
  list.removeIf(s -> "a".equals(s));
  - 底层原理其实也是使用了迭代器，但写法更简洁，语义更清晰。
多线程下的坑:
- 即使使用了 Iterator.remove()，也只能保证单线程下的安全。如果此时有另一个线程 B 也在修改 List，modCount 依然会变，Fail-Fast 依然会触发。多线程环境下必须使用 CopyOnWriteArrayList 或加锁。

6.2 架构设计题：用 Java 模拟 Redis List

题目: 如果让你实现一个由 Redis 支持的 List，你会怎么设计？

深度解析: 这道题不仅考察对 Java 集合的熟悉程度，还考察对 Redis 数据结构特性的理解。

接口选型：为什么是 Deque 而不是 List？
- Redis 的 List 本质上是一个 双端队列。它的核心命令是 LPUSH (左进), RPUSH (右进), LPOP (左出), RPOP (右出)。
- Java 的 java.util.List 接口主要侧重于索引访问 (get(i)), 虽然也能模拟栈和队列，但不如 java.util.Deque (Double Ended Queue) 语义精准。
- 结论: 我的类应该实现 Deque 接口，或者同时实现 List 和 Deque（像 LinkedList 那样）。
底层数据结构选型：LinkedList vs ArrayDeque
- 方案 A: LinkedList
  - 优点: 天然的双向链表，完美映射 Redis List 的早期实现（Adlist）。支持 null 元素。
  - 缺点: 内存开销极大（每个节点多两个指针），缓存局部性差。
- 方案 B: ArrayDeque (推荐)
  - 优点: 基于循环数组。头尾插入效率极高 (O(1))，内存占用小（没有 Node 对象），CPU 缓存友好。这更符合 Redis 现代版本（QuickList/ZipList）追求内存效率的设计理念。
  - 缺点: 不支持 get(i) 随机访问（如果需要模拟 LINDEX 命令，这是个短板）。
- 最终决策: 如果主要模拟消息队列场景（LPUSH/RPOP），首选 ArrayDeque。如果需要模拟完整的 Redis List（包括 LINDEX, LSET），则必须使用支持索引的结构，或者自己实现一个 分段数组（类似 Redis 的 QuickList），结合了数组的紧凑和链表的灵活性。
核心命令映射表:
- LPUSH key value -> deque.addFirst(value) / deque.offerFirst(value)
- RPUSH key value -> deque.addLast(value) / deque.offerLast(value)
- LPOP key -> deque.removeFirst() / deque.pollFirst()
- RPOP key -> deque.removeLast() / deque.pollLast()
- LLEN key -> deque.size()
- LRANGE key 0 -1 -> new ArrayList<>(deque) (全量复制) 或迭代器遍历。