HashMap 存了一百万条然后 OOM，通常不是因为"HashMap 太占内存"，而是因为没人算过它要占多少。选型出错的代价往往隔很久才显现：某个接口在数据量上万后突然变慢、某处偶发 ConcurrentModificationException、某个缓存悄悄泄漏。这篇只给判据，不逐个讲 API。
1. 第一问不是性能，是语义
| 语义需求 | 候选 | 判据 |
|---|---|---|
| 保持插入顺序 | ArrayList、LinkedHashMap、LinkedHashSet |
是否需要可复现的输出 |
| 需要按 key 排序遍历 | TreeMap、TreeSet、ConcurrentSkipListMap |
比较器是否稳定 |
| 去重 | HashSet、LinkedHashSet、TreeSet |
是否同时要顺序 |
| 允许 null 键值 | HashMap、LinkedHashMap |
并发容器一律不允许 |
| 多线程读写 | 并发容器或外部加锁 | 见第 6 节 |
| 迭代期间可修改 | CopyOnWriteArrayList、ConcurrentHashMap |
写少读多才成立 |
性能是第二问。语义选错，性能再好也是错的；语义选对，性能差还能换实现补。反过来不成立。
2. ArrayList 与 LinkedList 的真实差异
| 操作 | ArrayList |
LinkedList |
|---|---|---|
| 按下标取 | O(1)，连续内存 | O(n)，需遍历节点 |
| 尾部追加 | 均摊 O(1)，扩容时复制 | O(1)，但要分配节点 |
| 中间插入 | O(n) 移动元素 | 定位 O(n) + 改指针 O(1) |
| 迭代 | 顺序访问，缓存友好 | 指针跳转，缓存不友好 |
| 内存 | 一个数组 + 冗余容量 | 每元素一个节点，含两个引用与对象头 |
"LinkedList 插入快"只在已经持有节点引用时成立。按索引插入要先走 O(n)，而这一段比 ArrayList 的数组移动慢得多——节点散布在堆上，每次跳转都可能缺页。
// 已持有迭代器位置时的插入：LinkedList 才有优势
ListIterator<String> it = list.listIterator();
while (it.hasNext()) {
if (predicate(it.next())) it.add("x"); // 摊还 O(1)
}
随机访问的下限是内存层次，不是算法：ArrayList 的顺序遍历通常比 LinkedList 快数倍，量级随数据规模与 JVM 版本变化，按实测核对。
3. HashMap 的扩容与初始容量估算
HashMap 的容量是 2 的幂，负载因子默认 0.75。元素数超过 容量 × 0.75 触发扩容，容量翻倍并重新分布——一次扩容要把所有元素重新计算桶位置。
| 元素数 | 默认构造的扩容次数 | 建议初始容量 |
|---|---|---|
| 100 | 3～4 次 | 128 |
| 1,000 | 6～7 次 | 2,048 |
| 100,000 | 十余次 | 262,144 |
// 常用估算：capacity = (int) (expected / 0.75f) + 1，再由 HashMap 向上取 2 的幂
int expected = 1_000_000;
Map<Long, Order> m = new HashMap<>((int) (expected / 0.75f) + 1);
注意两个版本差异：JDK 8 之后链表长度超过 8 且容量 ≥ 64 时转红黑树，退化查询从 O(n) 变成 O(log n)；Map.of() 与 Map.copyOf() 生成的是不可变实现，元素数有上限且不接受 null。容量按 JDK 版本行为核对。
能预知规模却不给容量，是最常见也最容易修的一处浪费。
4. TreeMap 与 LinkedHashMap 的场景
| 需求 | 选择 | 说明 |
|---|---|---|
| 按 key 有序遍历、范围查询 | TreeMap |
subMap/headMap 是视图，不是拷贝 |
| 最近最少使用淘汰 | LinkedHashMap + removeEldestEntry |
访问顺序模式 |
| 保持插入顺序输出 | LinkedHashMap |
序列化、快照、可复现测试 |
| 需要并发且有序 | ConcurrentSkipListMap |
无锁读、跳表实现 |
class Lru<K, V> extends LinkedHashMap<K, V> {
private final int cap;
Lru(int cap) { super(cap, 0.75f, true); this.cap = cap; } // true = 访问顺序
@Override protected boolean removeEldestEntry(Map.Entry<K, V> e) {
return size() > cap;
}
}
这个 LRU 只在单线程成立：LinkedHashMap 的访问顺序本身是一次写操作，并发访问会改坏结构而不报错。
5. HashSet 与 TreeSet：比较器一致性
TreeSet 用比较器（或 compareTo）判等，HashSet 用 equals/hashCode 判等。两者不一致时，同一个元素在两个集合里的"是否重复"结论不同。
| 情况 | HashSet 行为 |
TreeSet 行为 |
|---|---|---|
equals 相等、compareTo 不等 |
视为重复 | 视为不同元素 |
compareTo 返回 0，equals 为 false |
视为不同 | 视为重复，后者被丢弃 |
hashCode 未覆写 |
桶分散，去重失效 | 不受影响（若 compareTo 正确） |
// 反例：BigDecimal 的 equals 区分 1.0 与 1.00，compareTo 不区分
Set<BigDecimal> a = new HashSet<>(); // 两个都进
Set<BigDecimal> b = new TreeSet<>(); // 只进一个
TreeSet 还会把"比较器认为相等"的元素静默丢弃，不抛异常。集合变小了却没有任何报错，这是最难发现的一类数据丢失。
6. 并发容器的四个与各自的读写权衡
| 容器 | 读 | 写 | 适合 |
|---|---|---|---|
ConcurrentHashMap |
无锁，近似 O(1) | 分段/CAS，弱一致迭代 | 高并发键值缓存、注册表 |
CopyOnWriteArrayList |
无锁，快照 | 每次写全量复制 | 监听器列表、极少写 |
BlockingQueue 家族 |
阻塞取 | 阻塞放，可设容量 | 生产者消费者、任务队列 |
ConcurrentSkipListMap |
无锁 | 跳表插入，比 CHM 慢 | 需要有序与并发 |
// 复合操作必须用原子方法，而不是 get 后再 put
map.computeIfAbsent(key, k -> new Counter()).inc();
// 反例：先 containsKey 再 put，两步之间可能被别人插入
ConcurrentHashMap 不允许 null 键值，size() 在并发下只是估计值，iterator 是弱一致的——迭代期间不抛 ConcurrentModificationException，但也可能看不到新元素。
7. Collections.unmodifiableX 只是视图
List<String> src = new ArrayList<>(List.of("a"));
List<String> view = Collections.unmodifiableList(src);
src.add("b");
view.size(); // 2 —— 视图跟着原集合变
unmodifiableList 阻止的是通过该引用修改，不是阻止别处修改。真正的不变需要拷贝：List.copyOf(src)、List.of(...)、Collections.unmodifiableList(new ArrayList<>(src))。
不可变集合的收益在并发与安全发布：构造完成后状态不再变化，可以被任意线程共享而不需要同步，也不用担心被调用方改坏。代价是每次"修改"都要新建，元素多时复制成本明显。
8. ConcurrentModificationException 的机制
for (String s : list) {
if (s.isEmpty()) list.remove(s); // CME
}
迭代器创建时记 modCount，每次 next() 比对，结构被外部修改就抛。它不是线程安全检测——单线程用错方法一样抛，多线程里往往抛不出来。
| 做法 | 结果 |
|---|---|
iterator.remove() |
安全 |
list.removeIf(...) |
安全，内部走迭代器 |
for (int i...) 倒序删除 |
可用，但易错 |
遍历 CopyOnWriteArrayList |
安全，遍历的是快照 |
并发改 ArrayList |
可能抛 CME，也可能得到错误结果或数组越界 |
最后一行才是重点：并发下 CME 是"运气好时的报警"，没抛不代表没坏。
9. equals/hashCode 不一致的后果
| 症状 | 机制 |
|---|---|
contains 返回 false 但元素确实在 |
哈希不同，落到了别的桶 |
HashSet 出现"重复"元素 |
同上，去重失效 |
HashMap 取不到刚放的值 |
同上 |
| 内存只增不减 | 键对象不可变字段被改，桶位置失效，旧条目再也访问不到 |
remove 无效 |
同上，删除时找的是新哈希 |
// 作为键的对象必须不可变，或至少哈希相关字段不可变
record TenantId(String value) { } // record 自动生成 equals/hashCode
10. 装箱与原始类型集合
| 结构 | 每元素开销 | 100 万 int 的粗略量级 |
|---|---|---|
int[] |
4 字节 | 约 4 MB |
ArrayList<Integer> |
引用 4/8 字节 + Integer 对象（16 字节起） |
数十 MB 量级 |
HashMap<Integer, X> |
上述再加 Node 对象与表数组 | 上百 MB 量级 |
| 第三方原始集合（如 fastutil） | 接近数组 | 与 int[] 同量级 |
// 数值密集场景：先考虑数组，再考虑原始类型集合，最后才是包装类型集合
int[] counts = new int[N];
// 需要 map 语义时：Int2IntOpenHashMap 之类，注意 `-1` 与 null 的语义差异
-128..127 的 Integer 有缓存，小范围测不出差异；超出缓存区间每次装箱都新建对象，基准要用大数值。
11. 流式操作与集合的选用
| 关注点 | 流 | 集合操作 |
|---|---|---|
| 求值时机 | 惰性，终止操作才执行 | 立即 |
| 短路 | findFirst、anyMatch 可提前结束 |
需手写循环 |
| 复用 | 一次性，用过的流不能再消费 | 可反复遍历 |
| 调试 | 断点难放，栈深 | 直观 |
| 副作用 | 应避免，peek 不是给副作用用的 |
明确 |
// 短路的价值：百万条里找一个就停
boolean hit = list.stream().anyMatch(this::matches);
// 反例：先 filter 到 List 再判断非空，白跑一遍全量
12. 排错
| 现象 | 原因 | 处理 |
|---|---|---|
| 数据量上万后接口变慢 | 默认容量的 HashMap 反复扩容 |
按预期规模给初始容量 |
偶发 ConcurrentModificationException |
遍历时结构被改 | 用 removeIf 或并发容器 |
contains 判断错 |
equals/hashCode 未同时覆写 |
用 record 或成对实现 |
| 缓存条目只增不减 | 键的哈希相关字段被修改 | 键改不可变 |
TreeSet 元素莫名少了 |
比较器把不同元素判为相等 | 检查 compareTo 与 equals 一致性 |
| 内存超预期 | 包装类型集合 + 大量节点 | 换原始类型集合或数组 |
| 有序遍历结果不稳定 | 用了 HashSet/HashMap |
换 LinkedHashSet 或 TreeMap |
13. 边界
| 场景 | 更直白的选择 | 理由 |
|---|---|---|
| 元素在千级以内 | ArrayList + 线性查找 |
常数因子比复杂度更影响结果 |
| 性能不敏感 | HashMap 默认构造 |
可读性优先 |
| 团队不熟悉并发容器 | 外部加锁的普通集合 | 用错的并发容器比不用更危险 |
| 需要持久化顺序 | 数据库 order by |
集合不承担存储语义 |
| 只是临时聚合 | 流 + toList() |
不必设计结构 |
14. 自测
- 集合选型的第一问为什么是语义而不是性能？
LinkedList的插入优势在什么前提下才成立？- 预期存 100 万条，初始容量该给多少，依据是什么？
Collections.unmodifiableList与List.copyOf的区别是什么？compareTo返回 0 但equals为 false，放进TreeSet会发生什么？- 并发修改普通
ArrayList时没抛 CME，能说明没问题吗？