集合选型与常见问题
集合选型是工程经验的体现。选错集合不一定马上报错，但会在性能、顺序、并发、去重语义和可维护性上埋坑。
这一节从开发场景出发，总结常见集合的选型规则和面试高频问题。
# 1. 选型决策树
需要 key-value 吗？
├─ 是：Map
│ ├─ 需要 key 排序：TreeMap
│ ├─ 需要插入/访问顺序：LinkedHashMap
│ ├─ 需要并发：ConcurrentHashMap
│ └─ 默认：HashMap
│
└─ 否：Collection
├─ 允许重复且按位置访问：ArrayList
├─ 不允许重复：Set
│ ├─ 需要排序：TreeSet
│ ├─ 需要插入顺序：LinkedHashSet
│ └─ 默认：HashSet
└─ 按进出规则处理：Queue/Deque
├─ 普通队列/栈：ArrayDeque
├─ 优先级：PriorityQueue
└─ 并发生产消费：BlockingQueue
# 2. 常见集合速查
| 需求 | 推荐 | 原因 |
|---|---|---|
| 普通列表 | ArrayList | 访问快，内存紧凑 |
| 频繁头尾入队出队 | ArrayDeque | 双端操作高效 |
| 快速去重 | HashSet | 基于哈希，平均 O(1) |
| 去重保留顺序 | LinkedHashSet | HashSet + 顺序链表 |
| 去重排序 | TreeSet | 红黑树排序 |
| 普通 key-value | HashMap | 平均 O(1) |
| key-value 保序 | LinkedHashMap | 维护插入或访问顺序 |
| key-value 排序 | TreeMap | key 有序和范围查询 |
| 并发 key-value | ConcurrentHashMap | 分段/节点级并发控制 |
| 读多写少列表 | CopyOnWriteArrayList | 读无锁，写复制 |
| 生产消费 | BlockingQueue | 阻塞等待和线程协作 |
# 3. ArrayList 还是 LinkedList
默认选 ArrayList。
| 场景 | 更合适 |
|---|---|
| 按下标访问 | ArrayList |
| 大量遍历 | ArrayList |
| 尾部追加 | ArrayList |
| 头尾双端操作 | ArrayDeque |
| 已有迭代器位置附近插入删除 | LinkedList 可考虑 |
很多“频繁增删用 LinkedList”的说法不完整。中间插入删除前通常要定位元素，定位仍然是 O(n)。
# 4. HashMap 还是 TreeMap
| 需求 | 推荐 |
|---|---|
| 只按 key 查找 | HashMap |
| 遍历保持插入顺序 | LinkedHashMap |
| key 排序 | TreeMap |
| 范围查询 | TreeMap |
| 最近大于/小于某 key | TreeMap |
不要为了“输出看起来有顺序”依赖 HashMap 的偶然遍历结果。
# 5. HashSet 还是 TreeSet
| 需求 | 推荐 |
|---|---|
| 只去重 | HashSet |
| 去重并保留原顺序 | LinkedHashSet |
| 去重并排序 | TreeSet |
HashSet 判断重复依赖 equals/hashCode。TreeSet 判断重复依赖比较器或 compareTo。
# 6. Queue 还是 List
如果业务语义是“排队处理”，使用 Queue，不要用 List 模拟。
不推荐：
List<Task> tasks = new ArrayList<>();
Task task = tasks.remove(0); // 头部删除要移动元素
推荐：
Queue<Task> tasks = new ArrayDeque<>();
Task task = tasks.poll();
集合类型应该表达业务语义。
# 7. 并发场景选型
| 场景 | 推荐 |
|---|---|
| 并发 Map | ConcurrentHashMap |
| 并发 Set | ConcurrentHashMap.newKeySet() |
| 读多写少 List | CopyOnWriteArrayList |
| 生产消费 | BlockingQueue |
| 只读共享 | 不可变集合 |
| 简单低并发同步 | Collections.synchronizedXxx |
不要用 HashMap 加一点“经验判断”硬扛并发写入。并发问题通常不是稳定可复现的，越难复现越危险。
# 8. null 处理
| 集合 | null 支持 |
|---|---|
ArrayList | 支持多个 null |
LinkedList | 支持多个 null |
HashSet | 支持一个 null |
HashMap | 支持一个 null key，多个 null value |
TreeMap | 自然排序下不支持 null key |
ArrayDeque | 不支持 null |
PriorityQueue | 不支持 null |
List.of | 不支持 null |
ConcurrentHashMap | 不支持 null key/value |
并发集合不支持 null，一个重要原因是避免 get(key) == null 时无法区分“不存在”和“值为 null”。
# 9. equals/hashCode 常见问题
使用哈希集合时：
HashMap key
HashSet element
LinkedHashMap key
LinkedHashSet element
都依赖 equals/hashCode。
常见错误：
- 重写
equals忘记重写hashCode。 - 使用可变字段计算 hash。
equals不满足对称性或传递性。- Lombok 生成的
equals/hashCode包含不该参与比较的字段。
建议：
- key 对象尽量不可变。
- 明确业务唯一标识。
- 单元测试覆盖相等对象放入 HashMap/HashSet 的行为。
# 10. 集合返回值设计
方法返回集合时：
推荐：
return Collections.emptyList();
不推荐：
return null;
调用方更容易写：
for (User user : queryUsers()) {
process(user);
}
如果不希望调用方修改返回集合：
return List.copyOf(users);
或：
return Collections.unmodifiableList(users);
注意两者区别：copyOf 是不可变副本，unmodifiableList 是只读视图。
# 11. 集合与内存
集合会带来额外结构开销。
ArrayList
└─ Object[] 引用数组
LinkedList
└─ 每个元素一个 Node，包含 item/prev/next
HashMap
└─ Node[] + 每个键值对一个 Node
内存敏感场景要注意：
- 预估容量，减少扩容。
- 避免把大量临时集合长期持有。
- 大集合分页处理，不要一次性加载全部。
- 使用基本类型专用结构时可考虑第三方库。
- 清理不用的集合引用，避免缓存无限增长。
# 12. 面试高频问题
# 12.1 HashMap put 过程
计算 hash
│
▼
定位桶
│
├─ 空桶：插入
└─ 非空：
├─ key 相同：覆盖
├─ 链表：尾插并可能树化
└─ 红黑树：树插入
│
▼
超过阈值扩容
# 12.2 HashMap 为什么线程不安全
并发写入没有同步保护，多个线程可能同时修改桶、链表、树、size 和 table，导致数据丢失、状态不一致等问题。
# 12.3 ArrayList 扩容
容量不足时创建更大数组，并复制旧元素。常见实现中新容量约为旧容量 1.5 倍。
# 12.4 fail-fast 原理
集合维护 modCount，迭代器维护 expectedModCount，遍历时发现不一致就抛 ConcurrentModificationException。
# 12.5 TreeMap 和 HashMap 区别
HashMap 基于 hash，平均 O(1)，不保证顺序；TreeMap 基于红黑树，O(log n)，按 key 有序并支持范围查询。
# 13. 开发检查清单
提交代码前可以问自己：
- 是否真的需要顺序。
- 是否真的需要排序。
- 是否允许重复。
- 是否需要并发安全。
- 是否允许
null。 - key 或元素的相等语义是否正确。
- 是否可能大批量扩容。
- 是否在遍历时修改集合。
- 是否把可变对象放进 Set 或作为 Map key。
- 是否对外暴露了可修改的内部集合。
# Tips 快问快答
Q：普通列表默认选什么？
A：默认选 ArrayList。
Q：普通 Map 默认选什么？
A：默认选 HashMap。
Q：需要遍历顺序稳定选什么 Map？
A：按插入顺序用 LinkedHashMap，按 key 排序用 TreeMap。
Q：需要去重并保持原顺序怎么做？
A：使用 LinkedHashSet。
Q：为什么不要返回 null 集合？ A：调用方容易空指针，返回空集合更友好。
Q：不可变副本和只读视图有什么区别？ A：不可变副本不受原集合变化影响，只读视图会反映原集合变化。
Q：并发 Map 为什么不用 HashMap？
A：HashMap 并发写入没有同步保护，可能数据错乱。
Q：可变对象能作为 Map key 吗？
A：不推荐，尤其不要修改参与 equals/hashCode 的字段。
Q：集合容量要不要预估？ A：大批量添加时建议预估，减少扩容成本。
Q：面试回答集合问题最重要是什么？ A：说清数据结构、复杂度、适用场景、边界条件和常见坑。