面试前夜的复习清单上集合框架总是排在我熟悉与陌生之间。熟悉是因为每个类都能介绍几句陌生是因为一旦被追问“为什么”我的回答就开始打滑。于是这次我放弃背面经把 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 内部就是持有一个 HashMapTreeSet 内部就是持有一个 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 面试。