说起来有点不好意思我在团队里被问得最多的问题不是微服务怎么做熔断也不是高并发怎么扛流量反而是“这个场景到底该用 ArrayList 还是 LinkedList”“HashMap 的容量为什么要搞成 2 的幂”——这些集合框架里的基础问题恰恰是线上代码里最容易埋雷、又最容易被忽视的地方。我之前改过一个性能问题二话不说就定位到某段代码用了高频头插的 LinkedList还有一次 OOM 的根因是一个 HashMap 忘了设初始容量在超大循环体里反复扩容了几十次。集合框架就这么点东西但选对了是润物细无声选错了就是事故现场。这篇文章不是贴 API 文档也不是把 Java 代码抄一遍给你看而是基于我这些年实际开发、排查线上故障、刷面试题和带新人的真实经验把 Java 集合框架的总览、数据结构本质、源码关键点、并发场景选型和避坑经验一次性讲透。无论你是刚入门 Java 基础的小白还是已经被八股文折磨过的中高级开发这篇都能当工具书翻尤其适合面试前临时抱佛脚或者做技术评审时快速对照选型依据。1. 集合框架全景图先把容器按“数据组织方式”分清楚1.1 Collection 与 Map 两条主线的本质差异很多人一上来就背“Collection 是单列集合Map 是双列集合”但这么记有一个坏处你记住了分类却理解不了设计者的意图。更务实的理解方式是Collection 系列解决的是“一堆元素的组织和访问”问题而 Map 系列解决的是“通过一个键快速定位一个值”的问题——这两种东西的数据结构底座完全不同前者主要依赖数组、链表和树后者在哈希表、红黑树和跳表之间做选择。这两条主线里Collection 又细分出 List、Set、Queue 三个分支。List 强调有序、可重复、可通过下标访问Set 强调唯一性常用来去重Queue 则是为生产者-消费者模型准备的讲究先进先出或按优先级出队。很多人问“Set 是不是就是去重的 List”这个理解方向对了但不精确因为 Set 在底层玩的是哈希和比较而 List 底层玩的是索引两者对元素的约束和处理机制完全不同。1.2 先分清“接口、实现和算法”三个层次看集合框架总览最容易乱的地方是把接口和实现混在一起。比如你写代码时用的是List但真正干活的可能是ArrayList也可能是LinkedList。接口层次看的是“能干什么”实现层次看的是“怎么干的”。接口里有List、Set、Map、Queue这些抽象约束实现里有ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap、ConcurrentHashMap、PriorityQueue这些具体数据结构。另外算法层次很容易被忽略——比如Collections.sort()、Collections.binarySearch()、Collections.shuffle()这些工具方法把排序、查找、洗牌这类通用算法从集合里抽离出来。你不用自己手写快排和二分查找但不代表可以不懂它们的复杂度因为选型的时候你要判断的就是“我这个数据规模下哪种数据结构的增删改查最划算”。1.3 Map 家族四兄弟的分工一张表说清楚很多面试题爱问 HashMap 和 Hashtable 的区别、HashMap 和 TreeMap 的区别。我先给一张宏观对照表后面再详细展开各家的底层机制实现类底层结构是否允许 null键/值线程安全性核心适用场景HashMap数组 链表 红黑树键和值都允许非线程安全90% 的键值对存储需求读多写少的单线程场景LinkedHashMap哈希表 双向链表键和值都允许非线程安全需要保持插入顺序或 LRU 顺序的缓存场景TreeMap红黑树键不允许 null非线程安全需要按 key 排序、范围查询ConcurrentHashMap数组 链表 红黑树 CAS synchronized键和值都不允许 null线程安全并发环境下的全局键值存储我见过很多项目不管三七二十一所有 Map 一律new HashMap()结果遇到需要排序的需求又自己在外面套一层 Comparator 对 entrySet 排序代码绕了一大圈。这种问题的根源不是不会用 TreeMap而是脑子没有先形成选型意识——选 Map 实现之前先问自己三个问题要不要排序要不要保持插入顺序要不要线程安全三个问题一旦回答完用哪个实现基本就定死了。2. ArrayList 与 LinkedList 的选择逻辑从底层数据结构推导真实性能差异2.1 数组和链表的本质差别连着索引一起讲ArrayList 的底层是Object[]它在内存里是连续的一块空间所以访问第 i 个元素只需要一次“数组首地址 偏移量”计算时间复杂度是 O(1)。LinkedList 的底层是双向链表每个节点上挂着前后指针你要找第 i 个节点就得从头一个一个往后跳虽然它有 first 和 last 两头但平均还是要走一半时间复杂度是 O(n)。别小看这个差别。我见过有人用 LinkedList 存了一个五万元素的列表然后天天按 index 遍历功能是没跑错但每次 get 都在从头到尾游走肉眼可见的卡顿。反过来用 ArrayList 做频繁的头部插入每次插入都要把后面所有元素平移一位五万元素的数组插一次就是五万次数组复制CPU 直接烧穿。2.2 实测下来什么场景 LinkedList 才真正胜出很多人只知道 LinkedList 的优势在“插入删除快”但这个结论误导了太多人。链表在插入删除时快的是“已经拿到节点引用”的那一次 O(1) 操作比如你知道要删的是第 index 个节点且你已经有该节点的引用。但更多时候你是先要找到这个位置——抱歉这个查找本身就是 O(n)提前就把优点抵消了。我在实际项目里测过对 10 万条数据做“在头部反复插入 1 万次”ArrayList 耗时要到几十毫秒量级LinkedList 只要几毫秒。但换一个场景随机位置插入 1 万次两者差距就急剧缩小甚至 ArrayList 因为 CPU 缓存的友好性反而更快。所以我的选型经验是只有“已知节点的头尾插入删除 不需要按下标访问”这种明确场景才选 LinkedList否则一律 ArrayList。LinkedList 被 JDK 官方都标注为“通常应优先考虑 ArrayList”你还纠结什么2.3 ArrayList 初始容量是我做性能调优时最先检查的点ArrayList 的扩容机制是当元素个数超过当前数组长度时新数组长度约等于旧长度的 1.5 倍然后把旧数组复制到新数组。如果你在循环里向 ArrayList 分批添加数据它就会在这期间反复扩容、反复复制。我建议所有确定数据规模的场景都直接指定初始容量。// 反例反复扩容 ListString list new ArrayList(); for (int i 0; i 100000; i) { list.add(item- i); } // 正例指定初始容量提前分配 ListString list new ArrayList(100000); for (int i 0; i 100000; i) { list.add(item- i); }第一个例子表面上没问题但底层数组可能扩容了十几次每一次扩容都触发一次Arrays.copyOf这可不是几纳秒完事的事。经验数据是5 万条数据指定初始容量之后添加耗时能下降一个数量级。这个优化的性价比高到不值得你忽略。当然容量也非越大越好初始容量过大会浪费内存所以“可预估就指定不可预估也别设一个无厘头的几十万”。3. HashMap 源码级拆解哈希、扩容、红黑树和并发死循环3.1 为什么 HashMap 要把 hash 值右移 16 位再异或面试题的经典起手式。HashMap 的hash()方法不是直接拿 key 的hashCode()来用而是把高 16 位和低 16 位异或目的是让高位信息也参与低位计算。因为哈希桶的下标是用(n - 1) hash算出来的n 是数组长度所以当 n 较小时只有低几位生效高位信息会被丢弃。如果 key 的 hashCode 只在高位有差异就容易形成哈希碰撞。这个异或有个高大上的名字叫“扰动函数”。你可以不必背名词但要理解意图尽量让每个 key 对应的桶位分布均匀减少堆链表。我自己做映射表时也会刻意选择字段组合来保证 hash 分布不然一个糟糕的 hashCode 会让 HashMap 退化成一个长链表查询从 O(1) 变成 O(n)。3.2 负载因子 0.75时间和空间的折中值HashMap 默认容量是 16默认负载因子是 0.75意思是当元素个数达到 16 × 0.75 12 个时触发扩容数组变两倍32然后所有元素重新散列。负载因子越大比如 1.0意味着数组越填越满才扩容空间利用率高但碰撞概率上涨查询效率下降负载因子越小比如 0.5空间浪费严重但 hash 冲突少查询效率高。0.75 这个数字是 JDK 作者从时间和空间两个维度折中的结果。实操上我要说一个坑不要以为调大负载因子就能省内存大量碰撞导致的链表查询效率下降才是更严重的后果。反过来如果你对某张 HashMap 的读性能有极致要求且内存不敏感可以把负载因子设成 0.5~0.6。我在本地缓存里这么干过读性能有明显改善。3.3 链表转红黑树的阈值为什么是 8HashMap 的源码里有两个经典阈值链表长度达到 8 时转红黑树树大小为 6 时退化为链表。为什么不直接一刀切因为红黑树的节点是链表节点的两倍大如果频繁地插入删除导致链表长度在 6~8 之间波动反复树化和退化会造成不必要的开销所以设计了两个阈值制造缓冲。至于为什么选 8源码注释里写得很清楚基于泊松分布在随机哈希码且负载因子 0.75 的情况下链表长度达到 8 的概率已经低到千万分之一。也就是说转树是防极端情况不是常态。这里顺带纠正一个面试高频误区HashMap 的默认容量 16 并不是因为 16 好看而是因为它正好是 2 的 4 次方。HashMap 要求容量必须是 2 的幂所以当你传入一个非 2 的幂的初始容量时它会被转成大于等于该值的最近 2 的幂比如传 17实际容量为 32。用位运算代替取模唯一目的就是快。3.4 高并发下的 HashMap 死循环JDK7 的老事故JDK8 也没完全平息JDK7 的 HashMap 在多线程扩容时因为采用头插法可能把链表倒置形成循环引用get 时进入死循环。这在当时是线上事故的经典教材。JDK8 改成尾插法之后扩容时的死循环问题基本消失但并发下丢数据、数据覆盖的问题依旧存在。这里我想说一句可能被喷的话面试题让你背 JDK7 死循环但实际工作中真没人会在多线程场景下用裸 HashMap。真正要记住的是即使在 JDK8 下HashMap 的 put 也没有原子性两个线程同时触发扩容时可能丢失部分元素。解决办法从来不是“小心点用”而是直接换 ConcurrentHashMap。这也是为什么阿里规约会强制你在高并发场景禁用 HashMap 的深层原因。4. Set 去重的底层契约hashCode 与 equals 缺一不可4.1 为什么两个“内容相同”的对象HashSet 依然存了两个HashSet 去重的本质是依赖 HashMap 的 key 不可重复。当你往 HashSet 里 add 一个对象时它先计算对象的 hashCode 定位桶再在桶里用 equals 判断是否存在相同对象。问题来了如果两个对象的 hashCode 不同HashSet 认为它不是同一个对象equals 根本不会被调用于是内容相同的对象被存进了两个桶。我的经验是自定义对象要放进 Set 或者作为 Map 的 key 时hashCode 和 equals 必须同时重写且满足一致性——两个对象 equals 为 truehashCode 必须相同反过来不要求。我见过一个真实案例团队里只重写了 equals没重写 hashCode结果用户 ID 作为 key 存储时同一个用户被当成不同 key数据全乱套。Lombok 的Data注解默认会生成 hashCode 和 equals能省不少事但前提是你理解它生成的逻辑是否符合业务语义。4.2 去重的正确姿势HashSet vs Stream distinct说到去重很多人以为只有 Set 一条路。其实 Java 8 的 Stream 也提供了distinct()。两者的适用边界完全不同Set 是“全量去重保留集合”适合需要后续继续用这个集合做判断、遍历、存储的场景Stream distinct 是“管道内去重数据可能很大”适合流式处理中顺手去重不影响原数据源。// Set 去重结果可复用 SetInteger uniqueIds new HashSet(idList); // Stream 去重流式处理 ListInteger uniqueIds idList.stream().distinct().collect(Collectors.toList());这里要提醒一个性能陷阱如果 idList 是几十万条new HashSet(idList)的构造过程没有指定初始容量HashSet 内部同样会经历扩容。先对这个 list 预估规模new HashSet(list.size())可能不够精确因为 HashSet 自带负载因子会放大容量但至少比默认值靠谱得多。4.3 TreeSet 和 LinkedHashSet同一件事不同的有序性HashSet 不保证顺序LinkedHashSet 保证插入顺序TreeSet 保证自然顺序或自定义排序。三个都去重但耗的底层功夫完全不同。LinkedHashSet 额外维护了一条双向链表来记录插入顺序TreeSet 底层是红黑树每次插入都要做 O(logn) 的比较和旋转。所以“有序去重”从来不是白来的你要是拿 TreeSet 存一个已排好序的巨大数据流白交一堆比较的学费。面试里还有一个高频追问TreeSet 里放自定义对象怎么办答案是实现Comparable或者在构造 TreeSet 时传入Comparator。我更推荐构造时传 Comparator因为这把排序规则和业务对象解耦了逻辑更清晰。5. 并发场景下的集合选型从同步容器到并发容器的演进5.1 Collections.synchronizedList 和 CopyOnWriteArrayList 是两回事初学并发集合时很多人以为Collections.synchronizedList(new ArrayList())就是线程安全的列表。严格说它确实线程安全但安全的方式是给所有方法加同一把锁读和写全都串行化并发越高性能越难看。CopyOnWriteArrayList 的思路完全不同凡是写操作先复制底层数组的一个副本在副本上修改然后把数组引用指向新数组读操作不加锁永远读到旧数组。这种策略让读完全无锁并发读性能极好但每次写都是一次全量复制非常昂贵。所以选型结论很明显读多写极少选 CopyOnWriteArrayList比如配置信息、白名单、路由表写多读也多老老实实加锁或者考虑synchronizedListCopyOnWriteArrayList 只会在频繁写的场景里成为内存和 CPU 的杀手。5.2 ConcurrentHashMap 的锁粒度从分段锁到 CAS synchronizedJDK7 的 ConcurrentHashMap 用分段锁Segment 数组理论上只有命中同一个 Segment 的写操作才互相阻塞。JDK8 取消了分段锁改为在桶位上用synchronized锁住链表头节点或红黑树根节点同时利用 CAS 在节点为空时直接放入把锁粒度降到了单桶级别。这个变化的高光时刻是并发度不再由固定的 Segment 数量决定而是由数组长度、哈希分布质量共同决定。从实战角度看你要关注的是 ConcurrentHashMap 的两个性格不允许 null 键和值因为无法区分有一个 null 值还是 key 不存在且并发环境下要用 CAS 做占位迭代器是弱一致性的size() 和 isEmpty() 的结果是近似值。我在高并发场景做库存扣减或计数器时有时会考虑用 ConcurrentHashMap 的原子操作来做分段统计效果不错但要注意它并不能帮你完成“先查再改”这种复合操作那需要配合 compute 或 replace 等原子方法。5.3 阻塞队列生产者消费者模型里的万能积木并发集合里还有一个杀手锏是 BlockingQueue 系列最常用的是ArrayBlockingQueue和LinkedBlockingQueue。前者有界需要指定容量后者默认无界也可能导致内存膨胀所以号称用无界队列时我都会多留个心眼。实际项目里线程池的等待队列就是 BlockingQueue 的最佳应用。我记得有个调度系统任务量一高就把 BlockingQueue 默认的无界队列撑爆了直接 OOM。后来规规矩矩配置了 ArrayBlockingQueue 的有界容量和拒绝策略ThreadPoolExecutor executor new ThreadPoolExecutor( 4, 8, 60L, TimeUnit.SECONDS, new ArrayBlockingQueue(200), new ThreadPoolExecutor.CallerRunsPolicy() );这样当队列满了任务会由提交线程自己执行形成天然背压不丢任务也不至于把内存打爆。5.4 不可变集合和空集合并发环境下的隐形盾牌并发集合选型还有一个经常被忽略的细节如果集合在初始化之后就不再变化那它根本需要线程安全——它只需要不可变。Collections.unmodifiableList和 Java 9 之后的List.of()、Map.of()都能快速制造不可变集合。这不仅仅是“保险”的问题更关键的是发布给其他线程时不可变集合天生是线程安全的这是免费的午餐。我在写工具类时有个习惯返回结果集合时如果没有特殊理由一律用不可变集合包一层。这样做可以防止调用方把内部数据改了引发隐蔽 bug也符合很多规约里“返回空集合而不是 null”的约定。Collections.emptyList()、Map.of()这类 API 看着不起眼用到的时候是真省心。6. 实战中避不开的坑fail-fast 机制、迭代器与不可变集合6.1 ConcurrentModificationException 的完整排查链路先看一个经典故障场景某个报表查询的代码里用户反馈偶尔报 ConcurrentModificationException但本地测试死活复现不了。排查链路是这样的异常栈指向ArrayList$Itr.next说明是在迭代过程中抛出的迭代器内部有一个modCount字段每次结构性修改add、remove、clear都会modCount迭代器每次检查modCount ! expectedModCount一旦发现“有人改过结构”立刻抛出异常这个“有人”可能是自己线程的单线程改元素也可能是多线程环境下的操作。实际根因往往不是别人恶意改 list而是业务代码里“迭代时顺手调用 remove”这种隐蔽操作// 错误示范 ListString list new ArrayList(Arrays.asList(a, b, c)); for (String s : list) { if (s.equals(b)) { list.remove(s); // 触发 fail-fast } }正确姿势有两种一是使用迭代器自身的remove()方法它会同步维护 expectedModCount二是先收集要删除的元素循环结束后统一removeAll(collect)。6.2 ArrayList 的 subList 到底是不是视图这个坑我踩得相当惨。list.subList(from, to)返回的是原列表的视图不是副本。你对 subList 做结构修改原列表会跟着变反之如果原列表结构变了subList 再操作时很可能抛出 ConcurrentModificationException。而且 subList 修改后它的 modCount 和原列表一旦不一致后续任何方法都可能随时爆掉。我之前有个需求是“取前 100 条数据做排序”自然而然写了list.subList(0, 100).sort(...)因为 subList 是视图这个方法实际改了原列表的顺序把后续一堆数据的顺序也带偏了。正确做法是先new ArrayList(list.subList(0, 100))把视图快照出来再操作。凡是需要独立处理的子列表记得包一层再动手。6.3 迭代集合时为什么删不掉元素另外要留意for-each 循环本质上是语法糖底层还是 Iterator。所以你在 for-each 里调用list.remove()和直接在迭代器中 remove 不一样前者破坏了迭代器的状态。这个坑在面试里经常被包装成“如何一边遍历一边删除元素”标准答案就两个迭代器的 remove 法或者用List.removeIf(Predicate)。// 推荐 list.removeIf(s - s.equals(b));removeIf 是 JDK8 提供的内部实现也使用了迭代器但它帮你在安全的地方完成了移除操作代码可读性也更好。6.4 LinkedHashMap 实现 LRU 缓存的正确姿势聊到实战避坑不得不提 LRU 缓存这是我在实际开发里用过很多次的一招。LinkedHashMap 有一个钩子方法removeEldestEntry默认返回 false永远不会删除最老元素。你只要在超过容量时返回 true它就会在插入新元素后自动删除头部最久未访问的节点class LRUCacheK, V extends LinkedHashMapK, V { private final int capacity; public LRUCache(int capacity) { super(capacity, 0.75f, true); // accessOrdertrue按访问顺序 this.capacity capacity; } Override protected boolean removeEldestEntry(Map.EntryK, V eldest) { return size() capacity; } }注意这里的构造参数accessOrder为 true 才表示“访问过的节点移到尾部”LRU 才能生效。很多人直接在 for-each 或者 Stream 里对 entrySet 手动排序实现 LRU复杂度高且性能差不如一行构造参数来得优雅。7. 面试与工作双场景下的集合选型决策清单7.1 一个需求进来怎么快速定集合类型我给自己总结了一套决策流程分享出来可以直接抄作业如果是键值对场景一律先想 Map然后再问排序吗保持插入顺序吗线程安全吗不排序、不保序、单线程HashMap。要插入顺序LinkedHashMap。要自然排序或规则排序TreeMap。要并发访问ConcurrentHashMap。如果是元素列表场景先问需要按下标随机访问吗需要频繁在头部插删吗默选 ArrayList只有在明确头尾插删时才选 LinkedList。需要去重HashSet要保插入顺序去重LinkedHashSet。如果需要线程安全的 List读多写少用 CopyOnWriteArrayList写频繁用同步包装器或自行加锁。如果只是临时做数据处理优先考虑 Stream API而不是再建一个中间集合。7.2 性能调优时我优先检查集合初始容量很多人做 JVM 调优喜欢盯着堆内存和 GC其实有些性能问题就是裸的集合容量不够导致的。线上故障排查的过程我建议按这个顺序来先看日志里有没有 ConcurrentModificationException再查集合是否存在反复扩容最后用jmap或 dump 文件看看集合对象的实际大小。我看到过太多ArrayList明明可以一次性分配却因为偷懒没有指定初始容量在循环里膨胀了几十次造成大量内存碎片和 GC 压力。一个实用的建模经验是凡是解析文件、批处理返回、数据库分页查询结果集数量级都是可预估的这些地方必须给集合指定容量。像CollectionUtils这类工具类的新建集合方法也尽量带上预估参数。7.3 关于八股文和实际工作我的一点个人体会面试题里特别喜欢考 HashMap 源码、fail-fast、ArrayList 和 LinkedList 区别这类问题本质上是因为这些题能考察一个人“是否理解数据结构对程序行为的影响”。但实际工作和八股文之间有一道鸿沟八股文背得熟不代表你在评审别人代码时能一眼看出 ArrayList 的扩容风暴也不代表你在设计缓存时知道用 LinkedHashMap 实现 LRU。我的感受是集合框架选型这个能力靠背是背不出来的要靠“数据结构复杂度 实际场景约束 性能测试数据”三方面叠加。每写一个集合脑子里过一遍底层是什么结构增删改查什么复杂度是否会并发访问容量是否可预估这样写出来的代码才谈不上完美但一定不会坍成事故现场。最后再分享一个小技巧我平时做技术方案设计会专门在文档里留一个小节把所有用到的集合标注“数据结构 选型理由 预估容量”例如“MapLong, List HashMap外层预估 10 万内层 ArrayList 预分配 20”。出问题的时候回溯特别快面试官问细节也完全不打怵。这个习惯是踩过几次线上坑之后养成的现在推荐给每一个写 Java 的同学。
Java集合框架实战指南：底层原理、选型避坑与高并发安全
说起来有点不好意思我在团队里被问得最多的问题不是微服务怎么做熔断也不是高并发怎么扛流量反而是“这个场景到底该用 ArrayList 还是 LinkedList”“HashMap 的容量为什么要搞成 2 的幂”——这些集合框架里的基础问题恰恰是线上代码里最容易埋雷、又最容易被忽视的地方。我之前改过一个性能问题二话不说就定位到某段代码用了高频头插的 LinkedList还有一次 OOM 的根因是一个 HashMap 忘了设初始容量在超大循环体里反复扩容了几十次。集合框架就这么点东西但选对了是润物细无声选错了就是事故现场。这篇文章不是贴 API 文档也不是把 Java 代码抄一遍给你看而是基于我这些年实际开发、排查线上故障、刷面试题和带新人的真实经验把 Java 集合框架的总览、数据结构本质、源码关键点、并发场景选型和避坑经验一次性讲透。无论你是刚入门 Java 基础的小白还是已经被八股文折磨过的中高级开发这篇都能当工具书翻尤其适合面试前临时抱佛脚或者做技术评审时快速对照选型依据。1. 集合框架全景图先把容器按“数据组织方式”分清楚1.1 Collection 与 Map 两条主线的本质差异很多人一上来就背“Collection 是单列集合Map 是双列集合”但这么记有一个坏处你记住了分类却理解不了设计者的意图。更务实的理解方式是Collection 系列解决的是“一堆元素的组织和访问”问题而 Map 系列解决的是“通过一个键快速定位一个值”的问题——这两种东西的数据结构底座完全不同前者主要依赖数组、链表和树后者在哈希表、红黑树和跳表之间做选择。这两条主线里Collection 又细分出 List、Set、Queue 三个分支。List 强调有序、可重复、可通过下标访问Set 强调唯一性常用来去重Queue 则是为生产者-消费者模型准备的讲究先进先出或按优先级出队。很多人问“Set 是不是就是去重的 List”这个理解方向对了但不精确因为 Set 在底层玩的是哈希和比较而 List 底层玩的是索引两者对元素的约束和处理机制完全不同。1.2 先分清“接口、实现和算法”三个层次看集合框架总览最容易乱的地方是把接口和实现混在一起。比如你写代码时用的是List但真正干活的可能是ArrayList也可能是LinkedList。接口层次看的是“能干什么”实现层次看的是“怎么干的”。接口里有List、Set、Map、Queue这些抽象约束实现里有ArrayList、LinkedList、HashSet、TreeSet、HashMap、TreeMap、ConcurrentHashMap、PriorityQueue这些具体数据结构。另外算法层次很容易被忽略——比如Collections.sort()、Collections.binarySearch()、Collections.shuffle()这些工具方法把排序、查找、洗牌这类通用算法从集合里抽离出来。你不用自己手写快排和二分查找但不代表可以不懂它们的复杂度因为选型的时候你要判断的就是“我这个数据规模下哪种数据结构的增删改查最划算”。1.3 Map 家族四兄弟的分工一张表说清楚很多面试题爱问 HashMap 和 Hashtable 的区别、HashMap 和 TreeMap 的区别。我先给一张宏观对照表后面再详细展开各家的底层机制实现类底层结构是否允许 null键/值线程安全性核心适用场景HashMap数组 链表 红黑树键和值都允许非线程安全90% 的键值对存储需求读多写少的单线程场景LinkedHashMap哈希表 双向链表键和值都允许非线程安全需要保持插入顺序或 LRU 顺序的缓存场景TreeMap红黑树键不允许 null非线程安全需要按 key 排序、范围查询ConcurrentHashMap数组 链表 红黑树 CAS synchronized键和值都不允许 null线程安全并发环境下的全局键值存储我见过很多项目不管三七二十一所有 Map 一律new HashMap()结果遇到需要排序的需求又自己在外面套一层 Comparator 对 entrySet 排序代码绕了一大圈。这种问题的根源不是不会用 TreeMap而是脑子没有先形成选型意识——选 Map 实现之前先问自己三个问题要不要排序要不要保持插入顺序要不要线程安全三个问题一旦回答完用哪个实现基本就定死了。2. ArrayList 与 LinkedList 的选择逻辑从底层数据结构推导真实性能差异2.1 数组和链表的本质差别连着索引一起讲ArrayList 的底层是Object[]它在内存里是连续的一块空间所以访问第 i 个元素只需要一次“数组首地址 偏移量”计算时间复杂度是 O(1)。LinkedList 的底层是双向链表每个节点上挂着前后指针你要找第 i 个节点就得从头一个一个往后跳虽然它有 first 和 last 两头但平均还是要走一半时间复杂度是 O(n)。别小看这个差别。我见过有人用 LinkedList 存了一个五万元素的列表然后天天按 index 遍历功能是没跑错但每次 get 都在从头到尾游走肉眼可见的卡顿。反过来用 ArrayList 做频繁的头部插入每次插入都要把后面所有元素平移一位五万元素的数组插一次就是五万次数组复制CPU 直接烧穿。2.2 实测下来什么场景 LinkedList 才真正胜出很多人只知道 LinkedList 的优势在“插入删除快”但这个结论误导了太多人。链表在插入删除时快的是“已经拿到节点引用”的那一次 O(1) 操作比如你知道要删的是第 index 个节点且你已经有该节点的引用。但更多时候你是先要找到这个位置——抱歉这个查找本身就是 O(n)提前就把优点抵消了。我在实际项目里测过对 10 万条数据做“在头部反复插入 1 万次”ArrayList 耗时要到几十毫秒量级LinkedList 只要几毫秒。但换一个场景随机位置插入 1 万次两者差距就急剧缩小甚至 ArrayList 因为 CPU 缓存的友好性反而更快。所以我的选型经验是只有“已知节点的头尾插入删除 不需要按下标访问”这种明确场景才选 LinkedList否则一律 ArrayList。LinkedList 被 JDK 官方都标注为“通常应优先考虑 ArrayList”你还纠结什么2.3 ArrayList 初始容量是我做性能调优时最先检查的点ArrayList 的扩容机制是当元素个数超过当前数组长度时新数组长度约等于旧长度的 1.5 倍然后把旧数组复制到新数组。如果你在循环里向 ArrayList 分批添加数据它就会在这期间反复扩容、反复复制。我建议所有确定数据规模的场景都直接指定初始容量。// 反例反复扩容 ListString list new ArrayList(); for (int i 0; i 100000; i) { list.add(item- i); } // 正例指定初始容量提前分配 ListString list new ArrayList(100000); for (int i 0; i 100000; i) { list.add(item- i); }第一个例子表面上没问题但底层数组可能扩容了十几次每一次扩容都触发一次Arrays.copyOf这可不是几纳秒完事的事。经验数据是5 万条数据指定初始容量之后添加耗时能下降一个数量级。这个优化的性价比高到不值得你忽略。当然容量也非越大越好初始容量过大会浪费内存所以“可预估就指定不可预估也别设一个无厘头的几十万”。3. HashMap 源码级拆解哈希、扩容、红黑树和并发死循环3.1 为什么 HashMap 要把 hash 值右移 16 位再异或面试题的经典起手式。HashMap 的hash()方法不是直接拿 key 的hashCode()来用而是把高 16 位和低 16 位异或目的是让高位信息也参与低位计算。因为哈希桶的下标是用(n - 1) hash算出来的n 是数组长度所以当 n 较小时只有低几位生效高位信息会被丢弃。如果 key 的 hashCode 只在高位有差异就容易形成哈希碰撞。这个异或有个高大上的名字叫“扰动函数”。你可以不必背名词但要理解意图尽量让每个 key 对应的桶位分布均匀减少堆链表。我自己做映射表时也会刻意选择字段组合来保证 hash 分布不然一个糟糕的 hashCode 会让 HashMap 退化成一个长链表查询从 O(1) 变成 O(n)。3.2 负载因子 0.75时间和空间的折中值HashMap 默认容量是 16默认负载因子是 0.75意思是当元素个数达到 16 × 0.75 12 个时触发扩容数组变两倍32然后所有元素重新散列。负载因子越大比如 1.0意味着数组越填越满才扩容空间利用率高但碰撞概率上涨查询效率下降负载因子越小比如 0.5空间浪费严重但 hash 冲突少查询效率高。0.75 这个数字是 JDK 作者从时间和空间两个维度折中的结果。实操上我要说一个坑不要以为调大负载因子就能省内存大量碰撞导致的链表查询效率下降才是更严重的后果。反过来如果你对某张 HashMap 的读性能有极致要求且内存不敏感可以把负载因子设成 0.5~0.6。我在本地缓存里这么干过读性能有明显改善。3.3 链表转红黑树的阈值为什么是 8HashMap 的源码里有两个经典阈值链表长度达到 8 时转红黑树树大小为 6 时退化为链表。为什么不直接一刀切因为红黑树的节点是链表节点的两倍大如果频繁地插入删除导致链表长度在 6~8 之间波动反复树化和退化会造成不必要的开销所以设计了两个阈值制造缓冲。至于为什么选 8源码注释里写得很清楚基于泊松分布在随机哈希码且负载因子 0.75 的情况下链表长度达到 8 的概率已经低到千万分之一。也就是说转树是防极端情况不是常态。这里顺带纠正一个面试高频误区HashMap 的默认容量 16 并不是因为 16 好看而是因为它正好是 2 的 4 次方。HashMap 要求容量必须是 2 的幂所以当你传入一个非 2 的幂的初始容量时它会被转成大于等于该值的最近 2 的幂比如传 17实际容量为 32。用位运算代替取模唯一目的就是快。3.4 高并发下的 HashMap 死循环JDK7 的老事故JDK8 也没完全平息JDK7 的 HashMap 在多线程扩容时因为采用头插法可能把链表倒置形成循环引用get 时进入死循环。这在当时是线上事故的经典教材。JDK8 改成尾插法之后扩容时的死循环问题基本消失但并发下丢数据、数据覆盖的问题依旧存在。这里我想说一句可能被喷的话面试题让你背 JDK7 死循环但实际工作中真没人会在多线程场景下用裸 HashMap。真正要记住的是即使在 JDK8 下HashMap 的 put 也没有原子性两个线程同时触发扩容时可能丢失部分元素。解决办法从来不是“小心点用”而是直接换 ConcurrentHashMap。这也是为什么阿里规约会强制你在高并发场景禁用 HashMap 的深层原因。4. Set 去重的底层契约hashCode 与 equals 缺一不可4.1 为什么两个“内容相同”的对象HashSet 依然存了两个HashSet 去重的本质是依赖 HashMap 的 key 不可重复。当你往 HashSet 里 add 一个对象时它先计算对象的 hashCode 定位桶再在桶里用 equals 判断是否存在相同对象。问题来了如果两个对象的 hashCode 不同HashSet 认为它不是同一个对象equals 根本不会被调用于是内容相同的对象被存进了两个桶。我的经验是自定义对象要放进 Set 或者作为 Map 的 key 时hashCode 和 equals 必须同时重写且满足一致性——两个对象 equals 为 truehashCode 必须相同反过来不要求。我见过一个真实案例团队里只重写了 equals没重写 hashCode结果用户 ID 作为 key 存储时同一个用户被当成不同 key数据全乱套。Lombok 的Data注解默认会生成 hashCode 和 equals能省不少事但前提是你理解它生成的逻辑是否符合业务语义。4.2 去重的正确姿势HashSet vs Stream distinct说到去重很多人以为只有 Set 一条路。其实 Java 8 的 Stream 也提供了distinct()。两者的适用边界完全不同Set 是“全量去重保留集合”适合需要后续继续用这个集合做判断、遍历、存储的场景Stream distinct 是“管道内去重数据可能很大”适合流式处理中顺手去重不影响原数据源。// Set 去重结果可复用 SetInteger uniqueIds new HashSet(idList); // Stream 去重流式处理 ListInteger uniqueIds idList.stream().distinct().collect(Collectors.toList());这里要提醒一个性能陷阱如果 idList 是几十万条new HashSet(idList)的构造过程没有指定初始容量HashSet 内部同样会经历扩容。先对这个 list 预估规模new HashSet(list.size())可能不够精确因为 HashSet 自带负载因子会放大容量但至少比默认值靠谱得多。4.3 TreeSet 和 LinkedHashSet同一件事不同的有序性HashSet 不保证顺序LinkedHashSet 保证插入顺序TreeSet 保证自然顺序或自定义排序。三个都去重但耗的底层功夫完全不同。LinkedHashSet 额外维护了一条双向链表来记录插入顺序TreeSet 底层是红黑树每次插入都要做 O(logn) 的比较和旋转。所以“有序去重”从来不是白来的你要是拿 TreeSet 存一个已排好序的巨大数据流白交一堆比较的学费。面试里还有一个高频追问TreeSet 里放自定义对象怎么办答案是实现Comparable或者在构造 TreeSet 时传入Comparator。我更推荐构造时传 Comparator因为这把排序规则和业务对象解耦了逻辑更清晰。5. 并发场景下的集合选型从同步容器到并发容器的演进5.1 Collections.synchronizedList 和 CopyOnWriteArrayList 是两回事初学并发集合时很多人以为Collections.synchronizedList(new ArrayList())就是线程安全的列表。严格说它确实线程安全但安全的方式是给所有方法加同一把锁读和写全都串行化并发越高性能越难看。CopyOnWriteArrayList 的思路完全不同凡是写操作先复制底层数组的一个副本在副本上修改然后把数组引用指向新数组读操作不加锁永远读到旧数组。这种策略让读完全无锁并发读性能极好但每次写都是一次全量复制非常昂贵。所以选型结论很明显读多写极少选 CopyOnWriteArrayList比如配置信息、白名单、路由表写多读也多老老实实加锁或者考虑synchronizedListCopyOnWriteArrayList 只会在频繁写的场景里成为内存和 CPU 的杀手。5.2 ConcurrentHashMap 的锁粒度从分段锁到 CAS synchronizedJDK7 的 ConcurrentHashMap 用分段锁Segment 数组理论上只有命中同一个 Segment 的写操作才互相阻塞。JDK8 取消了分段锁改为在桶位上用synchronized锁住链表头节点或红黑树根节点同时利用 CAS 在节点为空时直接放入把锁粒度降到了单桶级别。这个变化的高光时刻是并发度不再由固定的 Segment 数量决定而是由数组长度、哈希分布质量共同决定。从实战角度看你要关注的是 ConcurrentHashMap 的两个性格不允许 null 键和值因为无法区分有一个 null 值还是 key 不存在且并发环境下要用 CAS 做占位迭代器是弱一致性的size() 和 isEmpty() 的结果是近似值。我在高并发场景做库存扣减或计数器时有时会考虑用 ConcurrentHashMap 的原子操作来做分段统计效果不错但要注意它并不能帮你完成“先查再改”这种复合操作那需要配合 compute 或 replace 等原子方法。5.3 阻塞队列生产者消费者模型里的万能积木并发集合里还有一个杀手锏是 BlockingQueue 系列最常用的是ArrayBlockingQueue和LinkedBlockingQueue。前者有界需要指定容量后者默认无界也可能导致内存膨胀所以号称用无界队列时我都会多留个心眼。实际项目里线程池的等待队列就是 BlockingQueue 的最佳应用。我记得有个调度系统任务量一高就把 BlockingQueue 默认的无界队列撑爆了直接 OOM。后来规规矩矩配置了 ArrayBlockingQueue 的有界容量和拒绝策略ThreadPoolExecutor executor new ThreadPoolExecutor( 4, 8, 60L, TimeUnit.SECONDS, new ArrayBlockingQueue(200), new ThreadPoolExecutor.CallerRunsPolicy() );这样当队列满了任务会由提交线程自己执行形成天然背压不丢任务也不至于把内存打爆。5.4 不可变集合和空集合并发环境下的隐形盾牌并发集合选型还有一个经常被忽略的细节如果集合在初始化之后就不再变化那它根本需要线程安全——它只需要不可变。Collections.unmodifiableList和 Java 9 之后的List.of()、Map.of()都能快速制造不可变集合。这不仅仅是“保险”的问题更关键的是发布给其他线程时不可变集合天生是线程安全的这是免费的午餐。我在写工具类时有个习惯返回结果集合时如果没有特殊理由一律用不可变集合包一层。这样做可以防止调用方把内部数据改了引发隐蔽 bug也符合很多规约里“返回空集合而不是 null”的约定。Collections.emptyList()、Map.of()这类 API 看着不起眼用到的时候是真省心。6. 实战中避不开的坑fail-fast 机制、迭代器与不可变集合6.1 ConcurrentModificationException 的完整排查链路先看一个经典故障场景某个报表查询的代码里用户反馈偶尔报 ConcurrentModificationException但本地测试死活复现不了。排查链路是这样的异常栈指向ArrayList$Itr.next说明是在迭代过程中抛出的迭代器内部有一个modCount字段每次结构性修改add、remove、clear都会modCount迭代器每次检查modCount ! expectedModCount一旦发现“有人改过结构”立刻抛出异常这个“有人”可能是自己线程的单线程改元素也可能是多线程环境下的操作。实际根因往往不是别人恶意改 list而是业务代码里“迭代时顺手调用 remove”这种隐蔽操作// 错误示范 ListString list new ArrayList(Arrays.asList(a, b, c)); for (String s : list) { if (s.equals(b)) { list.remove(s); // 触发 fail-fast } }正确姿势有两种一是使用迭代器自身的remove()方法它会同步维护 expectedModCount二是先收集要删除的元素循环结束后统一removeAll(collect)。6.2 ArrayList 的 subList 到底是不是视图这个坑我踩得相当惨。list.subList(from, to)返回的是原列表的视图不是副本。你对 subList 做结构修改原列表会跟着变反之如果原列表结构变了subList 再操作时很可能抛出 ConcurrentModificationException。而且 subList 修改后它的 modCount 和原列表一旦不一致后续任何方法都可能随时爆掉。我之前有个需求是“取前 100 条数据做排序”自然而然写了list.subList(0, 100).sort(...)因为 subList 是视图这个方法实际改了原列表的顺序把后续一堆数据的顺序也带偏了。正确做法是先new ArrayList(list.subList(0, 100))把视图快照出来再操作。凡是需要独立处理的子列表记得包一层再动手。6.3 迭代集合时为什么删不掉元素另外要留意for-each 循环本质上是语法糖底层还是 Iterator。所以你在 for-each 里调用list.remove()和直接在迭代器中 remove 不一样前者破坏了迭代器的状态。这个坑在面试里经常被包装成“如何一边遍历一边删除元素”标准答案就两个迭代器的 remove 法或者用List.removeIf(Predicate)。// 推荐 list.removeIf(s - s.equals(b));removeIf 是 JDK8 提供的内部实现也使用了迭代器但它帮你在安全的地方完成了移除操作代码可读性也更好。6.4 LinkedHashMap 实现 LRU 缓存的正确姿势聊到实战避坑不得不提 LRU 缓存这是我在实际开发里用过很多次的一招。LinkedHashMap 有一个钩子方法removeEldestEntry默认返回 false永远不会删除最老元素。你只要在超过容量时返回 true它就会在插入新元素后自动删除头部最久未访问的节点class LRUCacheK, V extends LinkedHashMapK, V { private final int capacity; public LRUCache(int capacity) { super(capacity, 0.75f, true); // accessOrdertrue按访问顺序 this.capacity capacity; } Override protected boolean removeEldestEntry(Map.EntryK, V eldest) { return size() capacity; } }注意这里的构造参数accessOrder为 true 才表示“访问过的节点移到尾部”LRU 才能生效。很多人直接在 for-each 或者 Stream 里对 entrySet 手动排序实现 LRU复杂度高且性能差不如一行构造参数来得优雅。7. 面试与工作双场景下的集合选型决策清单7.1 一个需求进来怎么快速定集合类型我给自己总结了一套决策流程分享出来可以直接抄作业如果是键值对场景一律先想 Map然后再问排序吗保持插入顺序吗线程安全吗不排序、不保序、单线程HashMap。要插入顺序LinkedHashMap。要自然排序或规则排序TreeMap。要并发访问ConcurrentHashMap。如果是元素列表场景先问需要按下标随机访问吗需要频繁在头部插删吗默选 ArrayList只有在明确头尾插删时才选 LinkedList。需要去重HashSet要保插入顺序去重LinkedHashSet。如果需要线程安全的 List读多写少用 CopyOnWriteArrayList写频繁用同步包装器或自行加锁。如果只是临时做数据处理优先考虑 Stream API而不是再建一个中间集合。7.2 性能调优时我优先检查集合初始容量很多人做 JVM 调优喜欢盯着堆内存和 GC其实有些性能问题就是裸的集合容量不够导致的。线上故障排查的过程我建议按这个顺序来先看日志里有没有 ConcurrentModificationException再查集合是否存在反复扩容最后用jmap或 dump 文件看看集合对象的实际大小。我看到过太多ArrayList明明可以一次性分配却因为偷懒没有指定初始容量在循环里膨胀了几十次造成大量内存碎片和 GC 压力。一个实用的建模经验是凡是解析文件、批处理返回、数据库分页查询结果集数量级都是可预估的这些地方必须给集合指定容量。像CollectionUtils这类工具类的新建集合方法也尽量带上预估参数。7.3 关于八股文和实际工作我的一点个人体会面试题里特别喜欢考 HashMap 源码、fail-fast、ArrayList 和 LinkedList 区别这类问题本质上是因为这些题能考察一个人“是否理解数据结构对程序行为的影响”。但实际工作和八股文之间有一道鸿沟八股文背得熟不代表你在评审别人代码时能一眼看出 ArrayList 的扩容风暴也不代表你在设计缓存时知道用 LinkedHashMap 实现 LRU。我的感受是集合框架选型这个能力靠背是背不出来的要靠“数据结构复杂度 实际场景约束 性能测试数据”三方面叠加。每写一个集合脑子里过一遍底层是什么结构增删改查什么复杂度是否会并发访问容量是否可预估这样写出来的代码才谈不上完美但一定不会坍成事故现场。最后再分享一个小技巧我平时做技术方案设计会专门在文档里留一个小节把所有用到的集合标注“数据结构 选型理由 预估容量”例如“MapLong, List HashMap外层预估 10 万内层 ArrayList 预分配 20”。出问题的时候回溯特别快面试官问细节也完全不打怵。这个习惯是踩过几次线上坑之后养成的现在推荐给每一个写 Java 的同学。
