19.集合选型与性能对比

本篇是数据结构系列的综合实践篇，将 List、Map、Set 三大集合家族放在一起，通过真实线上事故、性能基准、内存分析，建立"面对业务需求如何选择最合适的集合"的系统性思维。

目录指引与导读

阅读建议：第 1 次按 §01→§08 顺序通读，§09 思考题与 §10 作业务必动手；之后回看时聚焦 §05.2 业务场景速查表 + §07 设计模式总结。

二级目录

• 01. 从一个工作案例说起
• 02. List选型实战
• 03. Map选型实战
• 04. Set选型实战
• 05. 跨集合类型选型
• 06. 性能优化最佳实践
• 07. 集合的设计模式
• 08. 本篇收获案例回扣
• 09. 思考题深度练习
• 10. 课后作业实战
• 11. 进阶专题与延伸

01. 从一个工作案例说起

1.1 线上事故：一行构造器引发的 QPS 10× 下跌

某电商平台商品搜索服务，代码评审时没人留意这一行：

// 商品结果列表
List<Product> result = new LinkedList<>();
result.addAll(queryFromES(keyword));      // ES 返回 200 条商品

// 前端分页取第 page 页（每页 20 条）
for (int i = 0; i < pageSize; i++) {
    int idx = page * pageSize + i;
    Product p = result.get(idx);           // ← 罪魁祸首
    ...
}

某次大促前性能压测暴露问题：

• P99 耗时从 2ms 飙升到 200ms，单机 QPS 从 5000 掉到 500。
• 火焰图显示 70% 时间花在 LinkedList.get(int) 的链表遍历上。
• 理论分析：get(idx) 是 O(N)，每页 20 次 get → 每请求 20×100 = 2000 次指针跳转。

1.2 修复：改一个类名，性能回归

List<Product> result = new ArrayList<>(200);   // 仅改这一行

修复后 P99 回到 2ms，QPS 回到 5000。一行代码的选型差异 = 10× 性能差距。

1.3 选型的三个核心维度

维度1：操作模式
  你最频繁的操作是什么？读 / 写 / 删 / 遍历 / 排序 / 去重？

维度2：并发要求
  单线程？多线程读？多线程写？读写比例多少？

维度3：约束条件
  数据量多大？内存预算多少？是否需要有序？是否允许 null？

本篇就围绕这三个维度，把 List / Map / Set 全家桶的选型踩坑点讲透。

02. List选型实战

2.1 性能基准测试

以下是在 JDK 17、Apple M1、JMH 基准测试下的典型结果（仅供参考，不同环境有差异）：

测试1：尾部追加 100 万元素

实现	耗时	说明
ArrayList	~25ms	连续内存，偶尔扩容
LinkedList	~120ms	每次 new Node + 修改指针
Vector	~35ms	synchronized 开销
CopyOnWriteArrayList	~超时	每次复制整个数组！

测试2：随机访问 100 万次 get(random)

实现	耗时	说明
ArrayList	~8ms	O(1) 直接定位
LinkedList	~超时	O(N) 每次从头遍历
Vector	~12ms	O(1) + synchronized
CopyOnWriteArrayList	~8ms	O(1) 直接定位

测试3：头部插入 10 万次 add(0, x)

实现	耗时	说明
ArrayList	~1200ms	每次移动所有元素
LinkedList	~8ms	O(1) 修改指针
ArrayDeque	~5ms	O(1) 移动 head 指针

测试4：遍历 100 万元素（for-each）

实现	耗时	说明
ArrayList	~3ms	缓存友好
LinkedList	~15ms	指针跳跃，缓存不友好

2.2 List 选型决策表

场景	推荐	原因
通用场景（90%的情况）	ArrayList	综合性能最优
头尾频繁插入删除	ArrayDeque	比LinkedList更快更省内存
多线程读多写少	CopyOnWriteArrayList	读无锁
多线程读写均衡	Collections.synchronizedList	简单有效
需要队列语义	ArrayDeque 或 LinkedList	ArrayDeque通常更优
绝对不要用	Vector / Stack	已废弃

2.3 一些反直觉的结论

反直觉1：中间插入也是 ArrayList 更快

理论：LinkedList 中间插入 O(1)（已知节点时），ArrayList O(N)
实际：list.add(size/2, element) 两者都需要先定位 → 都是 O(N)

但 ArrayList 的 System.arraycopy 是 native 方法，使用 SIMD 指令；
LinkedList 需要逐个节点跳转，每次跳转可能 cache miss。

测试（10万次中间插入）：
  ArrayList: ~600ms
  LinkedList: ~4000ms  ← 反而更慢！

反直觉2：小数据量下一切区别可忽略

如果集合大小 < 1000，ArrayList 和 LinkedList 的性能差距
在微秒级别，对业务完全没有影响。

此时选型标准应该是：代码可读性 > 性能。

反直觉3：ArrayList 的内存有时比 LinkedList 更"浪费"

ArrayList 扩容后可能有大量空位（如容量1500但只用了1001个）
→ 浪费 499 × 8B = 4KB

LinkedList 没有空位浪费，但每个节点额外开销 32B
→ 1001 × 32B = 31KB 额外开销

结论：大数据量时 ArrayList 内存效率更高（平均浪费 ~25%）
     LinkedList 每个元素固定多 32B，规模越大浪费越多

03. Map选型实战

3.1 性能基准测试

测试1：100 万次 put

实现	耗时	说明
HashMap	~80ms	O(1) 均摊
LinkedHashMap	~100ms	额外维护链表
TreeMap	~800ms	O(log N) 红黑树
ConcurrentHashMap	~120ms	CAS + synchronized
Hashtable	~250ms	全方法 synchronized

测试2：100 万次 get（随机 key）

实现	耗时	说明
HashMap	~35ms	O(1)
LinkedHashMap	~40ms	O(1)
TreeMap	~500ms	O(log N)
ConcurrentHashMap	~40ms	volatile 读，无锁

测试3：遍历 100 万 entry

实现	耗时	说明
HashMap	~25ms	遍历桶数组（可能有空桶）
LinkedHashMap	~15ms	沿链表遍历（无空桶跳过）
TreeMap	~20ms	中序遍历红黑树

3.2 Map 选型决策表

场景	推荐	原因
通用键值存储	HashMap	综合最优
需要插入顺序	LinkedHashMap	有序 + O(1)
需要 LRU 缓存	LinkedHashMap(accessOrder)	天然支持
需要 key 排序/范围查询	TreeMap	红黑树有序
高并发	ConcurrentHashMap	CAS+细粒度锁
key 是枚举	EnumMap	极致性能
需要弱引用缓存	WeakHashMap	自动 GC 清理

3.3 HashMap 容量规划

// 错误：不设初始容量
Map<String, Object> map = new HashMap<>();  // 默认16
// 插入10000个元素 → 扩容: 16→32→64→128→256→512→1024→2048→4096→8192→16384
// 扩容 10 次！每次都要 rehash 所有元素

// 正确：预设容量
int expectedSize = 10000;
// 公式：initialCapacity = expectedSize / loadFactor + 1
int initialCapacity = (int) (expectedSize / 0.75f) + 1;  // 13334
Map<String, Object> map = new HashMap<>(initialCapacity);  
// HashMap 会自动调整为 2 的幂 → 16384
// 零次扩容！

// Guava 的便捷方法：
Map<String, Object> map = Maps.newHashMapWithExpectedSize(10000);

3.4 常见陷阱

陷阱1：可变对象作 key

List<String> key = new ArrayList<>(Arrays.asList("a", "b"));
Map<List<String>, String> map = new HashMap<>();
map.put(key, "value");

key.add("c");  // 修改了 key！hashCode 变了！

map.get(key);              // null！找不到了
map.containsKey(key);      // false！
// 但 map.size() == 1，数据还在，只是永远找不到了 → 内存泄漏

// 预防：用不可变对象作 key（String、Integer、或 unmodifiableList）

陷阱2：HashMap 的 containsValue 是 O(N)

// containsKey → O(1)  走哈希定位
// containsValue → O(N)  遍历所有桶的所有节点！

// 如果需要频繁按 value 查找 → 维护一个反向 Map
Map<String, Long> nameToId = new HashMap<>();
Map<Long, String> idToName = new HashMap<>();  // 反向索引

04. Set选型实战

4.1 性能基准测试

测试：100 万次 add + 100 万次 contains

实现	add 耗时	contains 耗时	说明
HashSet	~80ms	~35ms	O(1)
LinkedHashSet	~100ms	~40ms	O(1) + 链表维护
TreeSet	~800ms	~500ms	O(log N)
EnumSet (30枚举)	~0.1ms	~0.05ms	位运算

4.2 Set 选型决策表

场景	推荐	原因
通用去重	HashSet	O(1) 增删查
去重且保持顺序	LinkedHashSet	O(1) + 插入序
有序集合/范围查询	TreeSet	O(log N) + 有序
枚举值集合	EnumSet	位运算极致性能
并发去重	ConcurrentHashMap.newKeySet()	高并发
超大规模去重	BitSet / BloomFilter	极低内存

4.3 去重方案的选择

数据量 vs 方案：

< 10万：HashSet（内存约5MB）
  → 简单直接，不需要考虑内存

10万 ~ 1亿：HashSet + 合理初始容量
  → 内存约 500MB ~ 5GB，仍可单机处理
  → 注意预设初始容量避免频繁扩容

1亿 ~ 10亿：BloomFilter
  → 内存约 120MB ~ 1.2GB（1%误判率）
  → 或分片到多台机器的 HashSet

10亿+：分布式方案
  → Redis Set / 分片 BloomFilter / HyperLogLog（只需计数）

05. 跨集合类型选型

5.1 "我该用 List、Set 还是 Map？"

你的数据有没有 key-value 关系？
  │
  ├── 有 → Map
  │     ├── key → value 的映射 → HashMap
  │     └── 只需要检查 key 存在 → HashSet（本质就是只用key的Map）
  │
  └── 没有（纯粹的值集合）
        │
        ├── 需要去重？
        │     ├── 是 → Set
        │     └── 否 → List
        │
        ├── 需要有序？
        │     ├── 插入顺序 → List 或 LinkedHashSet
        │     └── 排序顺序 → TreeSet 或先 List 后 sort
        │
        ├── 需要按下标访问？
        │     ├── 是 → List（ArrayList）
        │     └── 否 → 可能 Set 就够了
        │
        └── 允许重复元素？
              ├── 是 → List
              └── 否 → Set

5.2 常见业务场景选型速查

业务场景	推荐集合	关键理由
商品列表展示	ArrayList	随机访问分页
用户ID黑名单	HashSet	O(1) 判断
购物车	LinkedHashMap<商品ID, 数量>	有序 + 按ID查找
排行榜 Top-K	TreeMap 或 PriorityQueue	有序 + 范围查询
消息去重	HashSet / BloomFilter	依数据量选择
配置项	LinkedHashMap	保持顺序
权限集合	EnumSet	极致性能
并发计数	ConcurrentHashMap<K, LongAdder>	原子计数
事件监听器	CopyOnWriteArrayList	读多写少
缓存	LinkedHashMap(LRU) 或 Caffeine	淘汰策略
多对多关系	Map<K, Set>	分组
URL 去重（10亿级）	BloomFilter + 分片存储	内存约束
时间线/日志	ArrayList / ArrayDeque	顺序追加

5.3 Android / iOS 平台特殊选型

Android 平台的内存优化选型：

标准Java         →  Android 优化替代
HashMap<Integer, V>  →  SparseArray<V>（避免int装箱）
HashMap<Integer, Integer>  →  SparseBooleanArray / SparseIntArray
HashMap<K, V>(小数据量)  →  ArrayMap<K, V>（二分查找，省内存）
HashSet<V>(小数据量)  →  ArraySet<V>

为什么？
  HashMap 的每个 Entry 是一个独立对象（~48B 对象开销）
  SparseArray 用两个原始数组存储（keys[] + values[]），零对象开销
  ArrayMap 用两个数组（hash数组 + key-value交替数组），省 ~50% 内存

适用条件：数据量 < 1000 时明显受益，> 1000 时 HashMap 更快

iOS 平台的选型：

NSArray → 类似 ArrayList（有序、可重复）
NSSet → 类似 HashSet（无序、不可重复）
NSDictionary → 类似 HashMap（键值对）
NSOrderedSet → 类似 LinkedHashSet（有序、不可重复）
NSCountedSet → 可重复的 Set（记录每个元素出现次数）
NSCache → 类似 LRU Map（自动淘汰、线程安全）

Swift:
Array / Set / Dictionary → 值类型，自带 COW 优化

06. 性能优化最佳实践

6.1 预设容量

// ❌ 差：频繁扩容
List<String> list = new ArrayList<>();          // 10万次扩容约8次
Map<String, String> map = new HashMap<>();      // 10万次扩容约10次
Set<String> set = new HashSet<>();              // 10万次扩容约10次

// ✅ 好：预设容量
List<String> list = new ArrayList<>(100000);
Map<String, String> map = new HashMap<>((int)(100000 / 0.75) + 1);
Set<String> set = new HashSet<>((int)(100000 / 0.75) + 1);

6.2 选择正确的遍历方式

// ArrayList：下标遍历和迭代器遍历性能几乎一样
for (int i = 0; i < list.size(); i++) { list.get(i); }  // OK
for (String s : list) { }                                 // OK

// LinkedList：绝对不要用下标遍历！
for (int i = 0; i < linkedList.size(); i++) {
    linkedList.get(i);  // 每次 O(N) → 总共 O(N²) → 灾难！
}
for (String s : linkedList) { }  // O(N) → 正确

6.3 批量操作优于逐个操作

// ❌ 差：逐个添加
for (String s : source) {
    target.add(s);
}

// ✅ 好：批量添加
target.addAll(source);
// ArrayList.addAll 只需一次 ensureCapacity + 一次 System.arraycopy

// ❌ 差：逐个检查
for (String s : toRemove) {
    target.remove(s);
}

// ✅ 好：批量删除
target.removeAll(new HashSet<>(toRemove));
// 先将 toRemove 转为 HashSet → contains O(1)
// 总复杂度从 O(N×M) 降到 O(N+M)

6.4 不可变集合的优势

// JDK 9+
List<String> immutableList = List.of("a", "b", "c");
Set<String> immutableSet = Set.of("a", "b", "c");
Map<String, Integer> immutableMap = Map.of("a", 1, "b", 2);

// 优势：
// 1. 线程安全（不可变 = 天然线程安全）
// 2. 内存优化（内部有特殊实现，0-2个元素极省内存）
// 3. 表达意图（明确告诉读者"这个集合不会被修改"）
// 4. 安全性（防止被意外修改）

07. 集合的设计模式

7.1 复用模式总结

模式1：委托模式（Delegation）
  HashSet → 委托 HashMap
  TreeSet → 委托 TreeMap
  Stack → 继承 Vector（反面教材）
  
  设计原则：优先组合（委托），避免继承。
  HashSet 的实现是教科书级别的委托模式应用。

模式2：装饰器模式（Decorator）
  Collections.synchronizedList() → 在 ArrayList 外包一层 synchronized
  Collections.unmodifiableList() → 在 List 外包一层只读限制
  
  优势：不修改原有类，灵活组合功能。

模式3：写时复制（Copy-On-Write）
  CopyOnWriteArrayList / CopyOnWriteArraySet
  
  核心思想：读和写操作在不同的数据副本上进行。
  适用条件：读远多于写。

模式4：标记接口（Marker Interface）
  RandomAccess → 标记支持高效随机访问的 List
  
  让算法可以根据集合的特性选择最优策略。

7.2 Java 集合框架的设计智慧

1. 接口与实现分离
   List（接口）→ ArrayList / LinkedList / CopyOnWriteArrayList（实现）
   面向接口编程，随时切换实现。

2. 失败策略
   fail-fast → ArrayList / HashMap 迭代时检测修改
   fail-safe → CopyOnWriteArrayList 快照迭代
   weakly consistent → ConcurrentHashMap 弱一致性迭代

3. 视图（View）而非副本
   subList()、keySet()、values()、entrySet() 都是视图。
   修改视图 = 修改原集合。省内存，但要注意副作用。

4. 工具类补充
   Collections → 排序、查找、同步包装、不可变包装
   Arrays → 数组操作、asList

08. 本篇收获案例回扣

回到开篇的LinkedList 分页事故：

问题	原因	本篇答案
为什么 get(idx) 这么慢？	LinkedList.get 是 O(N) 链表遍历	§2.1 随机访问基准
为什么 ArrayList 秒杀？	连续内存 + O(1) 下标寻址 + CPU 缓存友好	§2.3 反直觉结论
200 条数据真的有差距？	每页 20 次 get × 每次最多 200 次跳转 = 4000 次 cache miss	§2.1 遍历对比
以后怎么避免？	99% 场景默认 ArrayList；只有头尾频繁增删才考虑 ArrayDeque	§2.2 决策表

本篇核心收获：

• 选型三维度：操作模式 × 并发要求 × 约束条件，缺一不可。
• 反直觉规律：ArrayList 中间插入也比 LinkedList 快（SIMD + 缓存友好）；小数据量一切都不重要（代码可读性优先）。
• 预设容量的价值：HashMap 不设容量 10 万元素要扩容 10 次，预设后 0 次。
• 批量操作优于逐个：addAll / removeAll 比循环快一个数量级。
• 平台特异性：Android 小数据量用 SparseArray / ArrayMap，省 30-50% 内存。
• 设计模式：委托（HashSet→HashMap）、装饰（synchronizedList）、写时复制（COW）、标记接口（RandomAccess）。
• 框架智慧：接口与实现分离、fail-fast/fail-safe/弱一致三种迭代策略、视图而非副本、工具类补充（Collections / Arrays）。

09. 思考题深度练习

由浅入深，建议先独立思考再查阅资料。

1. 基础理解：以下代码有什么性能问题？请按步骤指出并优化。

List<String> result = new LinkedList<>();
for (int i = 0; i < 100000; i++) {
    result.add(0, data[i]);          // 总是在头部插入
}
Collections.sort(result);
for (int i = 0; i < result.size(); i++) {
    process(result.get(i));           // 逐个按下标访问
}

2. 内存计算：500 万用户 ID（Long 类型）的黑名单。分别计算 HashSet<Long>、BitSet（ID 范围 0~1 亿）、BloomFilter（1% 误判）的内存消耗，并推荐方案。

3. 并发选型：实时聊天系统，每个聊天室有"在线用户列表"：(1) 用户加入/退出时更新；(2) 每条消息广播时遍历。预计每秒 100 次广播但只有 2-3 次加入/退出。应选 CopyOnWriteArraySet、ConcurrentHashMap.newKeySet() 还是 Collections.synchronizedSet？给出数据分析。

4. 跨语言思考：Go 没有内置 Set、LinkedList、TreeMap。社区如何解决？"语言内置丰富集合" vs "保持简洁由社区扩展"这两种哲学各有什么优劣？

5. 系统设计：设计"实时词频统计系统"，输入每秒 10 万条文本消息流，需求：(1) 查询任意词的出现次数；(2) 维护 Top-100 高频词。请选合适的集合组合，分析吞吐/延迟，讨论单机瓶颈和分布式扩展方案。

10. 课后作业实战

作业 1：集合选型实战压测

搭建一个 JMH 基准，复现本篇的四组测试（List 尾插/随机访问/头插/遍历），在你的机器上跑一遍，对比结论。要求：

• 同一张表同时给出 ArrayList / LinkedList / ArrayDeque / CopyOnWriteArrayList 四种实现的结果。
• 数据量分别取 1 千 / 10 万 / 100 万，看"小数据量一切无差别"的结论在你机器上从多少开始成立。
• 用 flame graph 分析 LinkedList 中间插入的瓶颈函数。

作业 2：实现一个"集合选型建议器"

输入：数据量 N、主要操作类型（读/写/遍历/排序/去重）、是否并发。 输出：推荐的集合类 + 理由 + 预估内存占用 + 预估单次操作耗时。

提示：把本篇的三张决策表硬编码成规则引擎，额外考虑 Android/iOS 平台变体（SparseArray / ArrayMap）。

作业 3：LeetCode 综合应用

#	题目	考点
146	LRU Cache	LinkedHashMap / 手写双链表+HashMap
460	LFU Cache	两级 Map + 双链表
239	Sliding Window Maximum	Deque + 单调队列
295	Find Median from Data Stream	两个 PriorityQueue
347	Top K Frequent Elements	HashMap + 小顶堆 / 桶排序
380	Insert Delete GetRandom O(1)	HashMap + ArrayList
432	All O'one Data Structure	LinkedHashMap + 双链表桶
895	Maximum Frequency Stack	HashMap + 按频次 Stack
1146	Snapshot Array	TreeMap 版本查询
1172	Dinner Plate Stacks	TreeSet（标记可用位置） + List

要求：每题先独立分析"选哪种集合、为什么"，再动手实现。重点理解"组合使用多种集合"的设计思路。

11. 进阶专题与延伸

前面已经覆盖 Java Collections Framework 的选型主线。本节把视角进一步放宽：跨语言（Go/Rust/Python/C++）、跨平台（Android SparseArray）、跨 JVM 生态（Kotlin/Scala 集合）、以及大数据场景下的集合（Spark Broadcast、Flink State）。

11.1 跨语言集合对照表

抽象	Java	C++ STL	Go	Rust	Python
动态数组	ArrayList	std::vector	[]T (slice)	Vec<T>	list
双端队列	ArrayDeque	std::deque	无（container/list）	VecDeque<T>	collections.deque
单链表	无	std::forward_list	container/list	LinkedList<T> ⚠️	无
哈希表	HashMap	std::unordered_map / abseil flat_hash_map	map[K]V	HashMap<K,V>（hashbrown）	dict
有序表	TreeMap	std::map (RB)	无（社区 btree）	BTreeMap<K,V>	sortedcontainers
集合	HashSet	std::unordered_set	map[T]struct{}（惯用法）	HashSet<T>	set
优先队列	PriorityQueue	std::priority_queue	container/heap	BinaryHeap<T>	heapq

观察要点：

1. Go 的极简哲学：只给 slice + map，其他都让用户自己实现或用社区库
2. Rust 的 BTreeMap 不是红黑树：用 B-Tree（每节点 6-11 key），缓存友好
3. Python 的 dict 保序：3.7+ 明确保证插入顺序（CPython 3.6 起实现），等价 Java 的 LinkedHashMap
4. C++ 有 std::unordered_map 和 std::map：一个哈希一个有序，Java 的 HashMap/TreeMap 几乎一一对应

11.2 Android 平台的特化集合

Android 针对移动端内存敏感场景提供了 JDK 没有的专用容器：

类	底层	适用	对比 HashMap 空间
SparseArray<E>	int[] + Object[] 双数组	key 是 int	省 50%+，无装箱
SparseIntArray	int[] keys + int[] values	key/value 都是 int	省 75%+
SparseLongArray	int[] + long[]	key=int, value=long	省 50%+
ArrayMap<K,V>	int[] hashes + Object[] entries	< 数百个元素	省 30-40%
ArraySet<E>	同 ArrayMap 单列	小规模 Set	省 30-40%

原理：

• SparseArray 用二分查找定位 key（O(log n)），而不是哈希
• 对 < 100 个元素的场景，二分 + 数组的缓存局部性反而比 HashMap 快
• 插入/删除平均 O(n)，所以只适合小规模

Android Studio 的 lint 会主动提示："Use SparseIntArray instead of HashMap<Integer, Integer>"。

11.3 Kotlin / Scala 集合哲学对比

Kotlin：

• 默认区分只读与可变：List<T> 只读，MutableList<T> 可变
• 底层仍是 JDK 集合（listOf 返回 Arrays.ArrayList 视图）
• 扩展函数极其丰富：.filter{}.map{}.groupBy{}.fold{} 链式调用

Scala：

• scala.collection.immutable 和 mutable 两个独立包
• 不可变集合基于 HAMT、Finger Tree、RRB-Tree 等函数式数据结构
• Vector 是 RRB-Tree（改进版 HAMT），O(log₃₂ n) 随机访问
• List 是真·单链表（Lisp 风格）

Java 对比：Java 的"只读"只是接口层面的 unmodifiableList 视图（容易绕过），Kotlin/Scala 在类型系统层面强制分离，更安全。

11.4 Spark / Flink 大数据场景集合

Spark Broadcast 变量 用的不是 JDK 集合：

• 小于 4 MB：直接序列化传给每个 Executor
• 大于 4 MB：BlockManager 分块传输 + 用 Kryo 序列化
• 常用模式：broadcast(smallTable).value.asInstanceOf[Map[K,V]] 做 map-side join

Flink 状态后端（State Backend）：

• MemoryStateBackend：堆内 HashMap
• FsStateBackend：堆内 HashMap + CheckPoint 刷盘
• RocksDBStateBackend：LSM-Tree（第 8 篇讲过），TB 级状态不爆内存

真实场景：实时统计"每个用户最近 1 小时行为"，用 RocksDB state 存 1 亿用户 × 100 事件/人，堆里只留 LRU 热点。

11.5 GC 与集合：大集合的垃圾回收噩梦

ArrayList<Long> 的痛：10 亿个 Long 对象 = 10 亿 * (Long header 16B + value 8B) = 24 GB。Full GC 扫描根引用要遍历所有指针，几十秒起步。

工程应对：

1. 原生类型特化：Fastutil LongArrayList → 10 亿 long = 8 GB（节省 3 倍）+ GC 无对象要扫
2. Off-heap 内存：Chronicle Map、OHC（Off-Heap Cache），用 sun.misc.Unsafe / ByteBuffer.allocateDirect
3. ZGC / Shenandoah：亚毫秒 GC，代价是 10-15% CPU 开销
4. 堆压缩指针 -XX:+UseCompressedOops：小于 32 GB 堆时引用 4 字节而非 8 字节

11.6 集合的 Serialization 性能对比

同一个 100 万元素的 HashMap 做序列化反序列化：

序列化方案	耗时	字节大小	备注
Java 原生 ObjectOutputStream	3200 ms	48 MB	慢且大，但零依赖
Kryo	180 ms	24 MB	Spark/Flink 默认
Protobuf	250 ms	18 MB	要写 schema，跨语言
FlatBuffers	80 ms	32 MB	零拷贝读，大但快
FST (Fast-Serialization)	150 ms	22 MB	Drop-in replacement

业务含义：内部服务间 RPC 优先 Kryo/Protobuf；持久化 + 零拷贝场景选 FlatBuffers；对外 HTTP API 才用 JSON（Jackson 约 500ms）。

11.7 集合相关的经典 BUG 案例

案例 1：HashMap 作 ConcurrentHashMap 用（死循环 / 数据丢失）——第 17 篇已述。

案例 2：subList().clear() 看似无害：

List<Integer> list = new ArrayList<>(List.of(1,2,3,4,5));
list.subList(1, 4).clear();     // 删掉 2,3,4
// list 变成 [1, 5]  ← 对原 list 生效！

这是 Effective Java Item 45 推荐的删除区间技巧，但如果不知道，会引发"莫名其妙被改"的 bug。

案例 3：Arrays.asList(primitive[]) 的陷阱：

int[] arr = {1, 2, 3};
List list = Arrays.asList(arr);
list.size();                      // 1 ❌（不是 3）
// 因为 int[] 整体被当一个 Object

要用 Arrays.stream(arr).boxed().collect(Collectors.toList()) 或 JDK 16+ 的 Arrays.stream(arr).boxed().toList()。

案例 4：HashSet<Long> vs HashSet<long>：JDK 没有 long 泛型，只能装箱，1000 万个 Long 比 long[] 多占 4 倍。生产环境大集合必须上 Fastutil。

案例 5：ImmutableMap.of() 的 null 友好性差：Guava 和 JDK 9+ Map.of key/value 都不能为 null，会 NPE。老代码迁移时要改。

11.8 读源码的推荐顺序

打算深入 JDK 集合的学习路径：

1. AbstractList / AbstractCollection（300 行）：理解模板方法模式
2. ArrayList（1000 行）：最简单、实测最多
3. HashMap（2400 行）：扰动函数、树化、扩容
4. LinkedList（800 行）：双向链表 + Deque
5. TreeMap（1500 行）：红黑树插入/删除的教科书
6. ArrayDeque（1300 行）：循环数组的位运算魔法
7. ConcurrentHashMap（6300 行，JDK 8）：Doug Lea 的并发交响乐
8. CopyOnWriteArrayList（600 行）：volatile + synchronized 经典
9. Collectors（1500 行）：收集器的 DSL
10. Stream（流系列，几千行）：pipeline + split-iterator

阅读技巧：先看 class 级 Javadoc、再看字段声明、再看最核心的 3 个方法（add/get/remove），最后才看辅助方法。

11.9 性能调优的七条军规

1. 初始容量要给：new HashMap<>(expectedSize / 0.75 + 1)，避免反复扩容
2. 加载因子别乱调：0.75 是哈希分析得出的"时间-空间"最优点
3. key/value 不要可变：一旦放进 Map 后改 hashCode，就丢进黑洞了
4. 大 Map 用特化版：Long key 上 Fastutil，减少 4 倍内存
5. 读多写少用 COW：< 1000 元素 + 读写比 >100:1 的黄金场景
6. 迭代用 iterator 不用下标：LinkedList 下标迭代退化 O(n²)
7. 优先 Stream 但别滥用：小集合（<100）的 for 循环比 Stream 快 2-3 倍

11.10 过渡：到思考题篇

至此，数据结构 + 集合的知识体系已完整。接下来 20.思考题和问答分析.md 是本系列的压轴篇，把十八篇里最容易搞错、最易被面试追问的深水区问题集中起来做 Q&A。不只给答案，更要说清"为什么是这个答案"、"错误答案错在哪"。建议通读前先把每题独立思考 5 分钟，再与答案对照。