面试前夜的复习清单上，集合框架总是排在我熟悉与陌生之间。熟悉是因为每个类都能介绍几句，陌生是因为一旦被追问“为什么”，我的回答就开始打滑。于是这次我放弃背面经，把 ArrayList、HashMap、TreeSet 的源码逐一翻开，从扩容条件一路读到并发迭代器。说实话，这场重读比刷一百道算法题都让我清醒。
以前准备面试，背的是结论：“ArrayList 基于数组，LinkedList 基于链表”“HashMap 线程不安全”。但面试官真正想听的，从来不是数据结构教科书，而是你在真实项目里因为某个集合特性踩过的坑。面试答案往往只负责让你通过第一轮，源码深挖才能让你在最后一轮活下来。这种深挖不是逐行翻译注释，而是理解每个实现为换取一项能力，究竟牺牲了什么。
数组扩容的体面与狼狈
ArrayList 的扩容逻辑看起来简单：默认容量 10，满了就扩容成原来的 1.5 倍，再把老数组复制过去。很多人把“复制数组”当成性能黑点，却忽略了均摊分析。每次 add 的平均成本仍然接近 O(1)，因为容量翻倍带来的大量空闲槽位，会让后续多次 add 不用动数组。真正的性能杀手不是扩容本身，而是你用错了容器。
比如在列表头部插入，ArrayList 需要把后面的元素全部后移，每次插入都是 O(n)。这时候换 LinkedList 似乎很合理，但如果你同时需要周期性按下标访问元素，LinkedList 的 get 每次都要从头开始遍历，代价也没低到哪去。JVM 下的数组是连续内存，ArrayList 天然享受 CPU 缓存预读；而 LinkedList 每个节点都散落在堆里，迭代时指针反复跳闪。如果你的业务里大量出现随机访问，那么连续内存本身就是性能，而链表已经输在了第一行代码之前。
LinkedList：被高看的“列表”
我复习到 LinkedList 时，越来越觉得它是集合框架里最被高估的角色。它确实实现了 List 接口，也能存 null，但 get(index) 要走到 index 位置，复杂度是 O(n)；一个元素节点除了对象本身，还要存前驱和后继指针，内存开销比数组高出几个量级。更戳破幻想的是，ArrayList 的尾巴插入在绝大多数场景下都比 LinkedList 高效，因为不需要为每个元素建造节点。
许多教程都会写“当你的程序需要频繁插入删除时，应该用 LinkedList”，这句话几乎误导了所有人。你要先知道删除的是哪个节点，而寻找这个节点的遍历成本一样存在。“用 LinkedList 指定删除中间某个元素”是教科书幻觉，因为你还得先从头遍历到那个元素。真正的权衡不是数组还是链表，而是“是否允许 O(n) 的定位开销”以及“缓存局部性对你重要不重要”。
HashMap：碰撞才是默认状态
HashMap 最值得琢磨的不是 get/put 的流程，而是它如何与最坏情况对抗。JDK 8 之前，hash 冲突后用链表兜底；JDK 8 之后，当链表长度达到阈值且 table 容量不小于 64 时，会把链表转成红黑树。这里真正难理解的不是红黑树代码，而是触发条件里蕴含的概率学。
hash() 方法让 key.hashCode() 的高 16 位与低 16 位异或，是为了让高位的随机性也参与进桶位计算。目的不是让数据绝对均匀，而是避免对象低几位巧合一模一样时灾难性碰撞。哈希的目的不是让数据均匀，而是让最坏情况不发生。大多数 HashMap 都不会走到红黑树那一步，因为普通字符串的哈希冲突率很低，可一旦有人恶意构造大量 hash 相同的字符串，红黑树就成了系统最后的救生网。
阈值 8 不是魔法，是泊松分布下的概率妥协——假设负载因子 0.75，桶内链表长度达到 8 的可能性只有千万分之六。所以面试时别只背“链表长度超过 8 转红黑树”，还要说出为什么是 8。这个数字体现出一种思想：完全基于最坏情况设计系统，会让 99.9999% 的请求为那一丁点风险买单；但不考虑最坏情况，又可能在针对性攻击面前瞬间崩溃。
再看扩容，JDK 7 里并发 put 可能导致链表成环，进而死循环。JDK 8 在扩容时把一条链表拆成低位和高位两条，避免节点相互引用。很多人把这件事记为“JDK 8 线程还是不安全，但不会死循环了”。可我不能忽视更底层的一点：所有优化都在减轻并发副作用，却没有让 HashMap 变成线程安全容器。HashMap 的线程不安全从来不是 bug，而是并发语义的缺位，所以别指望加个 synchronized 就能永远安全。
Set 与 Map：本质上是同一道题
HashSet 内部就是持有一个 HashMap，TreeSet 内部就是持有一个 TreeMap。Set 只是把 Map 的 value 部分替换成一个共享的静态对象。这一层抽象并不高级，但它点破了集合框架的核心：唯一性本质上是一种键的约束，而不是一种独立的数据结构。
很多程序员把 Set 当作“不允许重复的 List”，其实 Set 更像是不允许键重复的 Map。面试里问“HashSet 和 HashMap 有什么区别”，最漂亮的回答是：HashSet 是 HashMap 的语法糖，区别只在于你关不关心那一份 value。如果你把源码翻到 HashSet 的 add 方法，会发现它只是调用了 map.put(e, PRESENT)，然后通过返回值是否为 null 来判断重复。
有序不是免费的午餐
TreeMap 必须让键实现 Comparable，或者在构造时传入 Comparator。每一步 put 都要在红黑树上旋转、着色，把查找和插入控制在 O(log n)。这个复杂度看上去比 HashMap 的 O(1) 只差一点，但在大规模数据的写入频繁期，节点比较和颜色翻转的成本会被放大。不要为了某个锦上添花的顺序，让整个系统承担树结构的固定税。
LinkedHashMap 又给出了另一种“有序”：它用双向链表记录插入顺序或访问顺序，但不做全排序。最好的例子是重写 removeEldestEntry 来实现 LRU 缓存——每次访问某个 key，就把这个节点搬到链表尾部，当插入新节点时，链表头部的老节点自然可以淘汰。集合框架的每一层封装都在回答同一个问题：如何用最克制的操作成本，换取你想要的那一种秩序。是全局有序、插入有序，还是访问有序，三个类的代价截然不同。
并发集合的底线不是安全
聊到并发集合，几乎所有资料都会抛出 fail-fast：迭代时检测到 modCount 被修改，就抛出 ConcurrentModificationException。于是很多人得出简单结论：ArrayList、HashMap 在并发下会报错，CopyOnWriteArrayList、ConcurrentHashMap 是线程安全的。但线程安全这个说法太含混，真正的区别在于迭代器语义。
CopyOnWriteArrayList 的迭代器基于快照创建，它不会抛出 ConcurrentModificationException，但也永远看不到快照创建之后发生的修改。ConcurrentHashMap 的迭代器是弱一致性的，允许在遍历过程中看到被其他线程插入的新数据，但不会强制自己处于某个统一时刻的完整状态。迭代器抛出异常的那一秒，才是真正的并发开始——因为在那之前，你只看到了单线程的真空。
把“线程安全”理解成“任何操作都对且实时”，本身就是错位期望。并发集合的设计目标从来不是让你忘掉锁，而是用更精细的粒度减少锁竞争，并在不一致可以容忍的地方，主动松开手。当你面试被问到“ConcurrentHashMap 为什么高效”，与其背“CAS + synchronized + volatile”，不如说：它通过分批锁和弱一致迭代器，把并发世界的混乱控制在语义允许的范围内。
从源码回到面试
重新梳理一遍集合框架，我得到了一个笨拙但可靠的结论：每一个容器都是一组取舍。ArrayList 用连续内存换快速随机访问，选择放弃头部插入的效率；HashMap 用哈希扰动换常数时间的键定位，选择放弃顺序；TreeMap 用红黑树的旋转换全序性，选择放弃常数时间的插入；ConcurrentHashMap 用分段协作换并发吞吐，选择放弃最强的实时一致。
面试官不会因为你记得默认容量是 16 而欣赏你，也不会因为你背出“红黑树是平衡二叉树”而激动。他们真正想知道的，是你在面对一个具体业务时，有没有能力说出“这里不能用 TreeMap，因为读写比例是 100:1，树旋转的成本太奢侈”。集合框架没有银弹，只有适合的场合，以及你为了适应场合而愿意付出的昂贵代价。准备好这份代价清单，才算准备好了一场 Java 面试。
