Java 集合技术深度精讲
一、ArrayList 深度解析
1.1 本质：一个会自动长大的数组
类比：ArrayList 就像一个可以自动扩容的书架。一开始给你 10 个格子，放满了就换一个 15 个格子的新书架，把旧书搬过去。
// 核心字段（JDK8 源码简化版）
public class ArrayList<E> {
transient Object[] elementData; // 存数据的数组
private int size; // 实际元素个数（注意不是数组长度）
}1.2 扩容机制
初始状态（无参构造）：elementData = {}（空数组）
↓
第一次 add：分配默认容量 10
↓
容量不够时：newCapacity = oldCapacity + (oldCapacity >> 1)
即 新容量 = 旧容量 × 1.5（向下取整）
↓
调用 Arrays.copyOf 将旧数组拷贝到新数组扩容过程源码关键逻辑：
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 核心：右移一位 = 除以2，所以新容量 = 旧容量 * 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);
}为什么是 1.5 倍？
- 太小（如 1.25 倍）：扩容太频繁，频繁数组拷贝
- 太大（如 2 倍）：浪费内存。且数学上 2 倍扩容会导致新数组总是大于之前所有数组之和，无法复用之前释放的内存空间
- 1.5 倍是时间和空间的折中
一句话总结：ArrayList 的扩容 = 分配 1.5 倍新数组 + System.arraycopy。预知大小时务必指定初始容量。
1.3 删除元素的代价
删除 index=2 的元素：
[a][b][c][d][e][null][null]
↑
删除这个元素后，后面的全部左移
[a][b][d][e][null][null][null]
↑---↑ System.arraycopy 移动
时间复杂度：O(n)，因为要移动后续元素1.4 fast-fail 机制
// ArrayList 内部有一个 modCount 字段，每次结构性修改（add/remove）都会 modCount++
// Iterator 创建时记录 expectedModCount = modCount
// 每次 next() 都会检查 modCount != expectedModCount → 抛 ConcurrentModificationException
// 这就是为什么遍历时不能直接调用 list.remove()
// 但可以用 iterator.remove()，因为它会同步更新 expectedModCount二、LinkedList 深度解析
2.1 本质：双向链表
┌──────────────────────────────────────┐
│ LinkedList │
│ first ──→ [prev|A|next] ←──→ ... │
│ last ──→ [prev|Z|next] │
│ size = N │
└──────────────────────────────────────┘
每个节点（Node）：
┌──────┬──────┬──────┐
│ prev │ item │ next │
└──────┴──────┴──────┘private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
}2.2 为什么实际项目中几乎不用 LinkedList？
| 对比项 | ArrayList | LinkedList |
|---|---|---|
随机访问 get(i) | O(1) 直接算偏移 | O(n) 从头/尾遍历 |
| 尾部添加 | 均摊 O(1) | O(1) |
| 中间插入 | O(n) 移动元素 | O(1) 插入 + O(n) 定位 |
| 内存占用 | 紧凑，CPU 缓存友好 | 每个节点多两个指针 + 内存不连续 |
| 迭代性能 | 连续内存，预取命中率高 | 内存跳跃，缓存行频繁失效 |
关键洞察：LinkedList 理论上中间插入是 O(1)，但定位到那个位置需要 O(n)。加上 CPU 缓存对连续内存的偏爱，ArrayList 在绝大多数场景下都更快。
一句话总结：LinkedList 的唯一优势场景是”已经持有节点引用，频繁在已知位置插删”——但 Java 的 LinkedList 并不暴露节点引用，所以这个优势也用不上。
三、HashMap 深度解析（重中之重）
3.1 数据结构演进
JDK7：数组 + 链表
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ ← 数组（桶）
└───┴─┬─┴───┴───┴─┬─┴───┴───┴───┘
│ │
↓ ↓
[K1,V1] [K5,V5]
↓ ↓
[K2,V2] [K6,V6] ← 链表（解决哈希冲突）
↓
[K3,V3]
JDK8：数组 + 链表 + 红黑树
┌───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │
└───┴─┬─┴───┴───┴─┬─┴───┴───┴───┘
│ │
↓ ↓
[K1,V1] ┌───┐
↓ │红黑│ ← 链表长度 ≥ 8 且数组长度 ≥ 64 时，转为红黑树
[K2,V2] │ 树 │ 查找从 O(n) 降为 O(log n)
└───┘3.2 hash 扰动函数
// JDK8 的 hash 方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 高 16 位与低 16 位异或，让高位也参与索引计算
// 因为桶索引 = hash & (n-1)，当 n 较小时只有低位参与
// 不扰动的话，高位不同但低位相同的 key 会全部冲突
// 定位桶的公式：
// index = (n - 1) & hash
// 等价于 hash % n（当 n 是 2 的幂时）
// 位运算比取模快得多，这就是为什么 HashMap 容量必须是 2 的幂为什么容量必须是 2 的幂？
假设 n = 16（二进制 10000）
n - 1 = 15（二进制 01111）
hash & (n-1) 相当于取 hash 的低 4 位
这比 hash % n 快得多（一条 AND 指令 vs 除法指令）3.3 put 流程（JDK8）
put(key, value)
│
▼
计算 hash = hash(key)
│
▼
table 为空？──是──→ resize() 初始化（默认 16）
│ 否
▼
计算桶位置 i = (n-1) & hash
│
▼
桶为空？──是──→ 直接放入新节点
│ 否
▼
桶的第一个节点 key 相同？──是──→ 覆盖 value
│ 否
▼
是红黑树节点？──是──→ 走红黑树的插入逻辑
│ 否
▼
遍历链表：
├─ 找到相同 key → 覆盖 value
└─ 到达链尾 → 尾插法插入新节点
│
▼
链表长度 ≥ 8？
├─ 是 → 数组长度 ≥ 64？
│ ├─ 是 → 链表转红黑树（treeifyBin）
│ └─ 否 → resize() 扩容（优先扩容而非树化）
└─ 否 → 结束
│
▼
++size > threshold？──是──→ resize() 扩容
│
结束⚠️ JDK7 是头插法，JDK8 改为尾插法。头插法在多线程 resize 时会形成环形链表，导致死循环。这是经典面试点。
3.4 扩容机制（resize）
扩容条件：size > capacity × loadFactor（默认 16 × 0.75 = 12）
扩容过程：
1. 新建 2 倍大小的数组
2. 遍历旧数组的每个桶：
- 桶里只有一个节点 → 重新计算位置放入新数组
- 桶里是链表 → 拆分为两条链表（低位链表和高位链表）
- 桶里是红黑树 → 拆分为两棵树（可能退化为链表）
关键优化（JDK8）：
旧桶中的元素要么在新数组的【原位置】，要么在【原位置 + 旧容量】
判断方式：(hash & oldCap) == 0 → 原位置，否则 → 原位置 + oldCap
这样不需要重新计算 hash，一次位运算搞定示例：oldCap = 16, newCap = 32
某元素 hash = 0b...0_1010 → 原位置 index = 10
hash & oldCap(16) = hash & 0b10000 = 0 → 留在 index=10
某元素 hash = 0b...1_1010 → 原位置 index = 10
hash & oldCap(16) = hash & 0b10000 = 16 → 移到 index=10+16=263.5 树化与退化
链表 → 红黑树的条件（同时满足）：
1. 链表长度 ≥ 8（TREEIFY_THRESHOLD）
2. 数组长度 ≥ 64（MIN_TREEIFY_CAPACITY）
如果链表长度 ≥ 8 但数组长度 < 64，优先扩容而非树化
红黑树 → 链表的条件：
扩容时，红黑树拆分后节点数 ≤ 6（UNTREEIFY_THRESHOLD）时退化为链表
为什么是 8？
理想情况下（hash 均匀分布），桶中元素个数服从泊松分布
长度达到 8 的概率只有 0.00000006（六千万分之一）
8 是一个在极端情况下才触发的安全阀值，既不浪费树的开销，又能防止链表过长
为什么退化阈值是 6 不是 8？
避免在 7-8 之间频繁树化和退化（抖动），中间留了缓冲3.6 线程不安全的具体表现
1.【JDK7 死循环】
多线程同时 resize → 头插法导致链表形成环 → get() 死循环 → CPU 100%
2.【JDK8 数据丢失】
线程A 和线程B 同时 put，hash 到同一个空桶
线程A 判断桶为空，挂起
线程B 判断桶为空，写入节点
线程A 恢复，直接写入 → 覆盖了线程B的节点 → 数据丢失
3.【size 不准确】
size++ 不是原子操作（读-改-写三步），并发下计数出错一句话总结：HashMap 是面试考得最多的集合类。核心记住：数组+链表+红黑树、扰动函数、2的幂容量、1.5倍不对是1倍（翻倍）扩容、8和64树化阈值、尾插法。
四、ConcurrentHashMap 深度解析
4.1 JDK7：分段锁（Segment）
ConcurrentHashMap (JDK7)
┌─────────────────────────────────────────┐
│ Segment[]（默认 16 个段） │
│ ┌──────┐ ┌──────┐ ┌──────┐ │
│ │Seg[0]│ │Seg[1]│ ... │Seg[15]│ │
│ │(Lock)│ │(Lock)│ │(Lock) │ │
│ └──┬───┘ └──┬───┘ └──┬────┘ │
│ ↓ ↓ ↓ │
│ [HashEntry数组] [HashEntry数组] ... │
│ ↓ ↓ │
│ 链表 链表 │
└─────────────────────────────────────────┘
特点：
- 每个 Segment 是一把 ReentrantLock
- 不同 Segment 的操作互不干扰 → 最多支持 16 个线程并发写
- 先定位 Segment，再定位桶
- 锁粒度：Segment 级别4.2 JDK8：CAS + synchronized
ConcurrentHashMap (JDK8)
┌──────────────────────────────────────┐
│ Node[]（和 HashMap 类似的数组） │
│ ┌───┬───┬───┬───┬───┬───┬───┬───┐ │
│ │ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ │
│ └─┬─┴───┴─┬─┴───┴───┴───┴───┴───┘ │
│ │ │ │
│ ↓ ↓ │
│ CAS写入 synchronized(头节点) { │
│ (空桶) 链表/红黑树操作 │
│ } │
└──────────────────────────────────────┘
put 流程：
1. 计算 hash
2. 桶为空 → CAS 写入（无锁）
3. 桶不为空 → synchronized(桶的头节点) → 链表/红黑树操作
4. 链表长度 ≥ 8 → 树化（和 HashMap 类似）
锁粒度：桶级别（比 Segment 更细，并发度更高）4.3 size() 的实现
// ConcurrentHashMap 的 size() 没那么简单
// 不能简单用一个 volatile int size，因为 put/remove 时 CAS 更新会有激烈竞争
// JDK8 方案：类似 LongAdder 的分段计数
// baseCount + CounterCell[]
//
// 低竞争：CAS 更新 baseCount
// 高竞争：分散到 CounterCell[] 数组的不同槽
// size() = baseCount + Σ CounterCell[i].value
//
// 这也是为什么 ConcurrentHashMap 的 size() 是一个"估算值"
// 它不保证在并发修改时返回精确值一句话总结：JDK7 分段锁、JDK8 CAS+synchronized 锁桶头节点。JDK8 并发度等于桶的数量，远大于 JDK7 的 16。
五、TreeMap 与 LinkedHashMap
5.1 TreeMap：红黑树实现的有序 Map
TreeMap 底层是红黑树，所有操作 O(log n)
┌───[5]───┐ 红黑树特点：
│ (黑) │ 1. 节点非红即黑
┌─[3]─┐ ┌─[7]─┐ 2. 根节点是黑色
│(红) │ │(红) │ 3. 红色节点的子节点必须是黑色
[1] [4] [6] [9] 4. 任意节点到叶子的黑色节点数相同
(黑) (黑) (黑) (黑) 5. 保证最长路径 ≤ 2倍最短路径
适用场景：
- 需要按 key 排序遍历（自然排序或自定义 Comparator）
- 需要范围查询：headMap(toKey), tailMap(fromKey), subMap(from, to)
- 需要获取最大/最小 key：firstKey(), lastKey()// 实际场景：按分数排名
TreeMap<Integer, List<String>> rankMap = new TreeMap<>(Comparator.reverseOrder());
rankMap.computeIfAbsent(95, k -> new ArrayList<>()).add("张三");
rankMap.computeIfAbsent(88, k -> new ArrayList<>()).add("李四");
rankMap.computeIfAbsent(95, k -> new ArrayList<>()).add("王五");
// 遍历时自动按分数降序：{95=[张三, 王五], 88=[李四]}
// 范围查询：获取 80-90 分的
SortedMap<Integer, List<String>> sub = rankMap.subMap(80, 91);5.2 LinkedHashMap：保持顺序的 HashMap
LinkedHashMap = HashMap + 双向链表
HashMap 的数组结构：
┌───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │
└─┬─┴───┴─┬─┴─┬─┘
A B C
双向链表（按插入顺序串联）：
head ←→ A ←→ B ←→ C ←→ tail
遍历 LinkedHashMap 时走的是链表，所以顺序 = 插入顺序
如果 accessOrder=true，每次 get/put 会把元素移到链尾 → LRU一句话总结：TreeMap 用红黑树保证 key 有序，适合范围查询。LinkedHashMap 用双向链表保持插入/访问顺序，适合做 LRU。
六、HashSet 的真相
// HashSet 源码（简化版）
public class HashSet<E> {
private transient HashMap<E, Object> map;
private static final Object PRESENT = new Object(); // 所有 value 共用这个占位对象
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
public boolean contains(Object o) {
return map.containsKey(o);
}
public boolean remove(Object o) {
return map.remove(o) == PRESENT;
}
}就这么简单：
- HashSet 就是一个只用了 key 的 HashMap
- 去重原理 = HashMap 的 key 不可重复 = hashCode() + equals()
- LinkedHashSet = LinkedHashMap 的 key
- TreeSet = TreeMap 的 key
一句话总结：Set 家族是 Map 家族的马甲。理解了 HashMap 就理解了 HashSet。
七、PriorityQueue：最小堆
7.1 数据结构
PriorityQueue 底层是一个数组，逻辑上是完全二叉树（最小堆）
数组：[1, 3, 2, 7, 5, 4, 6]
逻辑结构（最小堆）：
1
/ \
3 2
/ \ / \
7 5 4 6
父子关系（0-based）：
parent(i) = (i - 1) / 2
left(i) = 2 * i + 1
right(i) = 2 * i + 2
堆顶（index=0）始终是最小值7.2 核心操作
offer（插入）：
1. 放到数组末尾
2. siftUp：与父节点比较，小于父节点就交换，直到满足堆性质
时间复杂度：O(log n)
poll（取出堆顶）：
1. 取出 array[0]
2. 把数组末尾元素移到 array[0]
3. siftDown：与较小的子节点比较，大于子节点就交换，直到满足堆性质
时间复杂度：O(log n)
peek（查看堆顶）：O(1)一句话总结：PriorityQueue = 数组实现的最小堆。插入和取出都是 O(log n)，适合 TopK 和优先级调度。
八、fail-fast vs fail-safe
| 特性 | fail-fast | fail-safe |
|---|---|---|
| 代表 | ArrayList, HashMap | CopyOnWriteArrayList, ConcurrentHashMap |
| 检测机制 | modCount 检查 | 无检查（操作副本或分段） |
| 遍历中修改 | 抛 ConcurrentModificationException | 不抛异常 |
| 一致性 | 强一致（不允许脏读） | 弱一致（可能读到旧数据） |
| 性能 | 无额外开销 | 写时复制或分段锁有开销 |
// fail-fast 示例
List<String> list = new ArrayList<>(List.of("a", "b", "c"));
for (String s : list) {
list.remove(s); // 💥 ConcurrentModificationException
}
// fail-safe 示例
List<String> list = new CopyOnWriteArrayList<>(List.of("a", "b", "c"));
for (String s : list) {
list.remove(s); // ✅ 不报错，遍历的是创建 Iterator 时的快照
}一句话总结：fail-fast 是”立即报错”策略，fail-safe 是”读旧数据也行”策略。选哪个取决于你要一致性还是可用性。
九、Comparable vs Comparator
// Comparable：类自身实现，定义"自然排序"
// "我知道我自己怎么排"
public class Student implements Comparable<Student> {
private int score;
@Override
public int compareTo(Student other) {
return Integer.compare(this.score, other.score); // 按分数升序
}
}
Collections.sort(students); // 直接排
// Comparator：外部传入，定义"定制排序"
// "我告诉你怎么排"
students.sort(Comparator.comparing(Student::getScore).reversed()); // 按分数降序
// 两者关系：
// Comparable 是"默认排序规则"，写在类里面，一个类只能有一种
// Comparator 是"临时排序规则"，写在外面，可以有无限种
// TreeMap/TreeSet 构造时可传 Comparator，没传就用 key 的 Comparable设计原则：
- 如果排序规则是实体的”天然属性”（如 Integer 的大小），实现 Comparable
- 如果排序规则多变或不属于实体本身（如按姓名排、按年龄排），传 Comparator
一句话总结：Comparable 是”我自己会排”，Comparator 是”你告诉我怎么排”。实际项目中 Comparator（Lambda 写法）用得更多。
十、集合框架的设计思想
10.1 接口与实现分离
List（接口）→ 定义了"有序集合"的行为规范
├── ArrayList（实现）→ 用数组实现
├── LinkedList（实现）→ 用链表实现
└── CopyOnWriteArrayList（实现）→ 写时复制实现
调用方只依赖接口：
List<String> list = new ArrayList<>(); // ✅ 面向接口编程
ArrayList<String> list = new ArrayList<>(); // ❌ 绑定了具体实现10.2 为什么 Map 不继承 Collection？
Collection 表示"一组元素"，每次操作一个元素
Map 表示"键值对映射"，每次操作一对元素
它们的核心抽象不同：
- Collection.add(element) — 加一个东西
- Map.put(key, value) — 建立一个映射关系
硬要让 Map 继承 Collection 会破坏接口语义
但 Map 提供了三种 Collection 视图：keySet(), values(), entrySet()10.3 迭代器模式
// 为什么用 Iterator 而不是直接暴露内部结构？
// 因为不同集合内部结构不同（数组、链表、树）
// Iterator 提供了统一的遍历方式，屏蔽了底层差异
// for-each 语法糖的本质就是 Iterator：
for (String s : list) { ... }
// 编译后等价于：
Iterator<String> it = list.iterator();
while (it.hasNext()) {
String s = it.next();
...
}10.4 时间复杂度全景
| 操作 | ArrayList | LinkedList | HashMap | TreeMap | HashSet | TreeSet |
|---|---|---|---|---|---|---|
| 随机访问 | O(1) | O(n) | — | — | — | — |
| 头部插入 | O(n) | O(1) | — | — | — | — |
| 尾部插入 | O(1)* | O(1) | — | — | — | — |
| 查找 | O(n) | O(n) | O(1) | O(log n) | O(1) | O(log n) |
| 插入 | — | — | O(1) | O(log n) | O(1) | O(log n) |
| 删除 | O(n) | O(1)** | O(1) | O(log n) | O(1) | O(log n) |
* 均摊 O(1)，扩容时 O(n)
** 已持有节点引用时 O(1)，否则查找仍需 O(n)