第3章 集合框架与数据结构
面试中集合类是必考模块，核心考察底层数据结构、线程安全策略和并发集合的使用。本章梳理 List/Map/Set 原理、并发集合 原理及 线程安全选择 的完整回答框架。
集合实现类核心对比
| 集合接口 | 实现类 | 底层结构 | 线程安全 | 适用场景 |
|---|---|---|---|---|
| List | ArrayList | Object[] 动态数组 | 否 | 随机访问多，尾部增删 |
| List | LinkedList | 双向链表 | 否 | 头部/中间频繁增删 |
| Map | HashMap | 数组+链表/红黑树 | 否 | 单线程高效KV存储 |
| Map | ConcurrentHashMap | 分段锁/CAS+synchronized | 是 | 高并发读写 |
| Set | HashSet | 基于HashMap | 否 | 去重且无序 |
| Set | CopyOnWriteArraySet | 基于CopyOnWriteArrayList | 是 | 读多写少 |
面试问答卡片
🎯 面试问题：HashMap 底层原理（1.7 vs 1.8）
面试官考察点：是否理解数组+链表/红黑树结构，扩容机制，以及版本差异背后的性能考虑。
回答框架：
- 整体结构：数组（Node[]） + 链表/红黑树，初始容量16，负载因子0.75。
- put流程：计算 hash → 找 bucket → 链表插入（1.7头插 / 1.8尾插）→ 超过 TREEIFY_THRESHOLD=8 转红黑树。
- 扩容：容量翻倍，rehash 重新分配元素（1.7 可能死锁 / 1.8 优化为高低位迁移）。
示例回答：
HashMap 底层是数组+链表+红黑树。1.8 之前采用头插法，多线程下扩容可能形成环形链表导致死循环；1.8 改为尾插法，且链表长度 ≥8 时转为红黑树，降低查询复杂度从 O(n) 到 O(log n)。扩容时使用高低位迁移，避免 rehash 带来的性能损耗。
可能追问：
- 为什么负载因子是 0.75？
- 红黑树转化阈值为什么是 8？
- HashMap 的 key 如何保证唯一？
⚠️ 避坑：不要笼统回答“无顺序”，要区分 HashMap / LinkedHashMap / TreeMap 的不同；回答死循环问题时强调“仅在 1.7 及以前的多线程场景”，1.8 已修复但非线程安全。
🎯 面试问题：ConcurrentHashMap 实现原理（1.7 vs 1.8）
面试官考察点：是否熟悉分段锁和 CAS + synchronized 两种方案，以及并发性能优化思路。
回答框架：
- 1.7 分段锁：Segment 数组继承 ReentrantLock，每段独立加锁，降低锁粒度。
- 1.8 放弃分段锁：采用 CAS 控制节点插入，synchronized 锁定链表/树头节点，进一步细化锁。
- 并发能力：支持高并发读写，size 使用 baseCount + CounterCell 累加。
示例回答：
1.7 采用 Segment 数组 + 分段锁，默认 16 个 Segment，每个 Segment 独立加锁，最多支持 16 个线程并行写。1.8 放弃分段锁，改用 CAS 插入桶节点，仅在发生冲突时对链表头加 synchronized，粒度更细；同时引入红黑树避免长链表。并发度从 16 提升到理论上的桶数。
可能追问：
- ConcurrentHashMap 的 get 需要加锁吗？
- size() 方法如何计算？
- 为什么 1.8 比 1.7 性能更好？
⚠️ 避坑：不要只说“分段锁”，1.8 已不再是分段锁；回答时强调版本的演进；避免和 Hashtable 的全局锁混为一谈。
🎯 面试问题：ArrayList 和 LinkedList 如何选择？
面试官考察点：是否理解数据结构底层对性能的影响，能否根据实际场景做合理选择。
回答框架：
- ArrayList：数组实现，连续内存，O(1) 随机访问；尾部增删快，中间插入/删除需移动元素 O(n)。
- LinkedList：双向链表，O(n) 随机访问；头尾增删 O(1)，中间插入/删除需遍历 O(n)。
- 选择原则：按接口（随机访问 vs 频繁增删）、内存（ArrayList 空间局部性好）判断。
示例回答：
日常开发优先使用 ArrayList。随机访问多、尾部追加数据用 ArrayList；头部或中间频繁插入/删除用 LinkedList。但实际业务中随机访问场景占 80% 以上，且 ArrayList 内存连续对 CPU 缓存友好，所以大多数情况 ArrayList 更优。若涉及大量头插，可考虑 ArrayDeque。
可能追问：
- ArrayList 的扩容机制？
- LinkedList 的迭代器支持快速失败吗？
- 为什么说 LinkedList 随机访问慢？
⚠️ 避坑：不要只说“ArrayList 查询快，LinkedList 增删快”，中间增删 LinkedList 也是 O(n)；避免忽略内存碎片和缓存局部性问题。