1. 集合框架全貌从数据结构看懂设计者的意图很多Java开发者用了几年集合ArrayList、HashMap写得飞起但真被问到为什么HashMap的默认负载因子是0.75ArrayList扩容到底怎么扩的就哑火了。这不怪大家因为日常CRUD确实用不到这些底层细节。但一旦你开始处理几万、几百万条数据或者你的接口被频繁调用到性能瓶颈这些用不到的知识就成了分水岭。集合框架本身不是一个需要背的东西它是一套围绕数据结构设计出来的接口体系。搞清楚这套体系是怎么组织的比记住某个类的API重要得多。1.1 Collection与Map两条完全不同的家族线Java集合框架最顶层只有两大接口体系Collection和Map。注意这两个接口在设计逻辑上是并列的不存在谁继承谁的问题。Collection下面又拆成三个子接口List有序可重复、Set不可重复、Queue队列通常FIFO。这三大子接口各自有对应的典型实现类ArrayList/LinkedList、HashSet/TreeSet、ArrayDeque/LinkedList。Map是独立的一条线存的是键值对。典型的实现有HashMap、TreeMap、LinkedHashMap、ConcurrentHashMap。我见过太多人在这上面犯迷糊以为Map继承自Collection。其实不是它们是平级的两大体系。这个设计是合理的因为Map的语义按键查值和Collection的语义元素集合的操作差异很大强行塞进同一棵继承树反而会让API变得别扭。另外一个容易忽略的点是抽象类的作用。JDK里有一批抽象类比如AbstractList、AbstractSet、AbstractMap它们的存在是为了减少实现类的工作量。你自定义一个List实现类时只需要继承AbstractList实现get()和size()两个方法剩下的iterator()、contains()、indexOf()、subList()等一堆方法都帮你搞定了。这算是面向接口编程的教科书级示范。1.2 复杂度模型选错容器是性能问题的第一来源不同实现类的背后对应着不同的数据结构而数据结构直接决定了操作的时间复杂度。这是集合性能优化的第一课。我举几个最基本的对照也是面试问烂了的东西操作ArrayListLinkedListHashSetTreeSetHashMap随机访问 get(i)O(1)O(n)--O(1)平均插入尾部 add均摊O(1)O(1)O(1)平均O(log n)O(1)平均插入中间 add(i,e)O(n)O(n)--O(1)平均查找 containsO(n)O(n)O(1)平均O(log n)O(1)平均删除 remove(e)O(n)O(n)O(1)平均O(log n)O(1)平均排序后遍历O(n log n)O(n log n)无序升序无序这里面有一个最常见的坑LinkedList在中间插入真的是O(1)吗理论上是O(1)——你只需要改前后节点的引用。但实际代码里add(index, element)这个操作在找到index位置的时候就已经花了O(n)了。如果你用迭代器listIterator().add()那确实是O(1)但直接用下标方式插入整体还是O(n)。很多人背了LinkedList插入快就去无脑用它结果性能更差就是这个原因。再比如HashSet查找是O(1)但遍历出来的顺序是不可预测的。如果你需要按插入顺序遍历或者按排序遍历就要考虑LinkedHashSet或TreeSet。这个选择取决于你更看重写入速度还是迭代顺序不存在绝对的更好只有更适合。工程上的建议很简单日常存储和随机访问用ArrayList去重用HashSet不要求顺序或LinkedHashSet要求插入顺序需要按键查值用HashMap并发场景用ConcurrentHashMap有序映射用TreeMap。绝大多数业务代码在这几个选择里就够了不需要用到Vector、Hashtable这些同步容器——它们性能差且没有特别的优势。2. 工具类的微妙之处Collections不只是排序和反转JDK里有两组工具类一组是java.util.Collections专门操作Collection体系另一组是java.util.Arrays专门操作数组。这两兄弟的API看起来简单但里面藏着不少细节用错的话轻则代码难看重则线上事故。2.1 Collections的十大冷门API从反转、洗牌到不可变视图先梳理一下Collections里最常用的几个方法以及它们各自的适用场景sort(ListT)对List排序。注意它只能排List不能直接用Set。如果集合是HashSet得先转成List再排。这个方法的底层在JDK 8之后用了TimSort对部分有序的数据效率非常高。传自定义比较器时可以用lambda简化但要注意比较器的一致性——如果你的compareTo和equals不一致在TreeSet这种按比较器排序的结构里会出现元素看似相同却一直能加进去的神奇现象。reverse(List?)反转List顺序。这个操作对ArrayList和LinkedList都是O(n)没有什么性能悬念。但它直接修改原列表如果你想保留原始顺序记得先new ArrayList(list)拷贝一份再反转。shuffle(List?)洗牌打乱顺序。底层是Random或你传入的Random实例。很多人不知道这个方法是原地修改的而且随机源是可以注入的——测试时传入固定种子的Random就能复现同样的乱序结果这在写测试用例时非常好用。addAll(Collection? super T, T...)批量加元素。它比循环调用add()更快因为内部有优化。注意它返回的是boolean表示集合是否因为调用而变化。这个细节很多人忽略但如果你在一个不允许重复的Set上调用返回值就能告诉你是不是真的加进去了。fill(List? super T, T)用同一个对象填充整个List。生成的列表里所有元素引用同一个对象如果你填充的是可变对象改一个就等于改全部。这是个大坑务必小心。copy(List? super T, List? extends T)列表拷贝。它的语义是把后一个列表的内容覆盖到前一个列表的对应位置前提是目标列表长度不能小于源列表否则抛IndexOutOfBoundsException。这和new ArrayList(source)完全不是一回事。min(Collection)/max(Collection)求极值。底层依赖元素的自然顺序或传入的比较器性能是O(n)。rotate(List?, int distance)旋转列表。这个方法比较冷门但写轮播图、循环队列之类的场景很实用。distance为正数时元素右移负数时左移。indexOfSubList(List?, List?)查找子列表在父列表中第一次出现的位置。相比于手写循环匹配这个方法既简洁又不容易出错。replaceAll(ListT, T oldVal, T newVal)替换所有匹配元素。注意方法是8.0版本其实没有这是Java 8在List接口默认方法里加的replaceAll和Collections.replaceAll是两个入口功能类似。除了这些Collections还提供了一大类视图方法不直接改原集合而是返回一个包装视图。这类方法易踩坑unmodifiableXxx不可变视图、synchronizedXxx同步包装、checkedXxx类型安全检查。不可变视图是运行时抛异常不是编译期就拦住的。你在代码里写Collections.unmodifiableList(list)编译器不会管你运行到.add()那一行才抛UnsupportedOperationException。2.2 不可变视图与同步包装安全性是运行时的事来重点说说视图类的几个经典场景。Collections.unmodifiableList(list)大家喜欢用它做只读保护。但很多人不知道原list改了unmodifiable视图也会跟着变——它只是挡了修改入口并没有做拷贝。网上流传的要用不可变就用List.of()其实也对因为List.of()Java 9返回的是真正不可变、独立快照的列表。两者的核心差别是特性Collections.unmodifiableListList.of()是否拷贝原数据否视图是不可变快照修改原list视图同步变化无影响允许null元素是但后续操作可能异常直接拒收nullJDK版本老版本就有Java 9Collections.synchronizedList(list)则是另外一个方向。它给每个方法加了同步块但要注意它的复合操作比如迭代仍然需要你自己加锁。这是因为迭代需要多个方法调用组合完成单纯锁住单个get()、next()无法保证整个迭代期间集合不被其他线程修改。具体写法是这样ListString syncList Collections.synchronizedList(new ArrayList()); synchronized (syncList) { IteratorString it syncList.iterator(); while (it.hasNext()) { // 安全迭代 } }这里加锁的对象必须是syncList本身不能锁其他对象因为内部方法的同步块锁的都是自己。这条规则在Hashtable、Vector的迭代场景同样适用。但在当今的并发开发中我更推荐直接用CopyOnWriteArrayList读多写少或ConcurrentLinkedQueue它们的设计更贴合并发场景不必背外面要加锁这种心智负担。再说checkedList。它在添加元素时做类型校验用来在泛型擦除后仍能防御烂类型。典型场景老代码里有一个ListString被当作raw type传到别处新代码往里塞了一个Integer运行时到迭代那步才崩。用Collections.checkedList(list, String.class)包装一下加错类型的那一瞬间就抛ClassCastException问题定位快得多。这个API不常用但排查诡异类型错误时非常香。2.3 Collections与Arrays的转换asList和toArray的陷阱数组和集合转换是天坑区我见过好几个线上问题都出在这。Arrays.asList(T... a)返回的List有几个特性定长不能add/remove、基于原数组改list内容会同步反映到数组。很多人以为拿到的是一个独立的新列表实际上不是它只是数组的List视图。如果你需要一个真正的、能add/remove的独立列表正确姿势是ListString realList new ArrayList(Arrays.asList(a, b, c));反向转换也容易出错list.toArray()返回的是Object[]直接强转成String[]会在运行时抛ClassCastException。标准做法是list.toArray(new String[0])。注意这里传new String[0]比传new String[list.size()]更推荐——虽然看起来后者少了一次数组复制但JVM的优化ArraysSupport里对空数组有专门处理让前者的性能和可读性都更好。Java 8之后还有Stream的map/collect路径也可以做数组和集合的转换比如Arrays.stream(arr).collect(Collectors.toList())。但这种写法比new ArrayList(Arrays.asList(arr))重一些且会产生中间对象在性能敏感的循环里要避免。另外Arrays里还有一批值得注意的高阶方法binarySearch二分查找要求数组已排序找不到返回-(插入点)-1、copyOf/copyOfRange数组扩容和截断底层是System.arraycopy原生方法速度极快、equals/deepEquals多维数组比较用deepEquals直接用equals比较的是引用。性能上特别要提的是Arrays.parallelSort()。它在大数组排序时把任务拆给ForkJoinPool并行执行对小数组反而因为线程调度开销更慢。经验值是数组元素少于几千个时不需要parallelSort。我自己在本地测过1万元素时parallelSort大约比普通sort快30%但1000元素时就慢一截。3. 性能优化的实战细节从源码里抠出真实成本集合性能优化不是玄学每一项都有明确的源码依据。这一节我挑几个日常开发最容易踩、优化效果最明显的点逐个拆开讲。3.1 ArrayList扩容机制为什么批量插入前要预估容量ArrayList底层是一个Object数组。当元素装满数组时add()会触发扩容。源码逻辑是int oldCapacity elementData.length; int newCapacity oldCapacity (oldCapacity 1); // 1.5倍 elementData Arrays.copyOf(elementData, newCapacity);等下如果我没记错JDK 8里新容量精确算法是oldCapacity (oldCapacity 1)也就是1.5倍。但如果你addAll传入的集合很大而1.5倍还不够装那就直接按需要的长度扩容。这里每次扩容都要做一次Arrays.copyOf也就是把老数组元素整体搬一次。数据量越大搬迁成本越高而且频繁扩容会浪费大量内存空间——每次扩容之后的空闲区域都是暂时用不上的。实际我测过一个场景往一个空的ArrayList里加100万条数据用默认无参构造器创建扩容大约发生log(1.5)级别次数的搬移如果用new ArrayList(1000000)预分配容量总耗时能节省一半左右。所以规则很简单如果能预估数据规模就尽量传初始容量如果是从另一个集合拷贝直接new ArrayList(otherCollection)不要先建空列表再逐个add。3.2 HashMap的树化与扩容hash扰动、负载因子、红黑树HashMap的源码是集合框架里最值得细读的。它的数据存储由数组链表红黑树组成元素先根据key的hash定位到桶位bucket相同桶位的元素串成链表链表长度超过8且数组长度超过64时转成红黑树。有几个关键细节hash扰动JDK 8的hash(Object key)方法拿到key.hashCode()后做了一次h key.hashCode() ^ (h 16)。高16位和低16位异或是为了让高位的信息也参与定位桶位。因为桶位数数组长度一般远小于hashCode的32位空间如果不扰动分布容易偏向低位导致链表过长。负载因子0.75这是时间与空间的折中。数组元素个数达到capacity * loadFactor时触发扩容。0.75意味着数组用满75%就扩留出25%的空位来减少哈希碰撞。调小了浪费空间、调大了碰撞概率上升。这个值在一般场景不需要动除非你明确知道数据分布很均匀且内存紧张。树化阈值8链表长度超过8且数组长度超过64链表转红黑树。为什么是8源码注释里有一段泊松分布的分析大意是随机hash下链表长度到8的概率已经极低约千万分之六能到8说明hash函数出问题或者数据分布极差此时用红黑树补救。但注意如果数组长度不到64即使链表超8也不树化而是先扩容因为扩容能更快打散数据。实际优化建议是使用自定义对象作为key时hashCode写得好不好直接影响HashMap性能。如果hashCode总是返回同一个常量所有元素都挤到同一个桶位HashMap就退化成链表/O(n)查询。一个合格的hashCode要尽量让每个对象的哈希值分散这块如果面试被问到HashMap为什么查询快答出hashCode把key映射到桶位链表/红黑树解决冲突就够用了。在并发场景HashMap不是线程安全的这个大家都有共识但有没有可能坏数据是另一回事。JDK 7的HashMap在多线程并发扩容时可能产生环链导致后续get进入死循环JDK 8重写了扩容逻辑不再出现环链但并发put/remove仍可能丢数据。要用并发就老老实实换ConcurrentHashMap。3.3 避免自动装箱与临时对象十万级循环里的隐形杀手Java的泛型规定容器只能存对象所以ListInteger在add基本类型int时会自动装箱成Integer对象。每次装箱都要new一个对象除非缓存在-128到127的范围内在十万级循环里就是几万个临时对象堆积GC负担剧增。我踩过的一个场景在for循环里遍历一个大ListInteger做累加第一次跑没注意耗时200ms改用int基本类型数组或IntStream后耗时降到40ms左右。这里面不光是装箱还有Integer.valueOf对缓存的处理和迭代器本身的开销。优化的思路有几种如果是纯数值计算用原始数组int[]而不是ListInteger。如果必须用集合尽量用ArrayListInteger因为它内存连续、迭代最快。循环内不使用Integer的new Integer(x)使用Integer.valueOf(x)缓存范围复用对象或直接依赖自动装箱本质也是valueOf。同理字符串拼接也是个隐藏性能问题。循环里str x每次都会创建新的String对象因为String是不可变的。JDK 8对这样的代码编译期会优化成StringBuilder但循环里每轮都建一个新的StringBuilder性能仍然不好。显式在外层创建一个StringBuilder循环内append结束后toString这一招在拼SQL、拼JSON、拼日志时都有肉眼可见的提升。3.4 Stream与循环的取舍可读性优先但要让数据规模说话Java 8之后StreamAPI写起来确实优雅ListString result list.stream() .filter(s - s.startsWith(a)) .map(String::toUpperCase) .collect(Collectors.toList());但很多人担心Stream性能比循环差。这个问题的准确答案是小数据量下差别可忽略大数据量下Stream的串行模式不一定比循环差但并行流parallelStream要小心。我在本地做的简单基准测试结果大致是100万条数据filtermapcollect普通for循环约60ms串行Stream约75msparallelStream约30ms八核机器。但如果数据量只有几千parallelStream反而更慢因为ForkJoin的拆解合并开销占大头。所以我的建议是数据量不明时先写普通循环简单直接没坑。数据量明确较大几十万以上且处理逻辑无状态、无共享可变变量才考虑parallelStream。永远不要在一个正在被修改的集合上开parallelStream做复合操作后果不可预期。还有一点容易被忽略Stream的collect(Collectors.groupingBy())或toMap()在key冲突时会抛IllegalStateException。比如stream.collect(Collectors.toMap(Function.identity(), x - 1, (a,b) - ab))第三个参数是冲突合并函数不传的话遇到相同key直接抛异常。这个坑特别隐蔽往往上线后在脏数据上炸出来。3.5 并发场景从Hashtable到ConcurrentHashMap的演进在说性能之前先定性Hashtable是全方法synchronized读写都有锁冲突Collections.synchronizedMap和它类似。ConcurrentHashMap在JDK 8里改成了CAS synchronized锁桶位读操作大多无锁并发性能高出好几个量级。ConcurrentHashMap的常见用法putIfAbsent(key, value)原子性的不存在才放用于幂等、防重复。computeIfAbsent(key, mappingFunction)按key取缓存没有就计算并写入。这是最常用的并发缓存模式比先get再put安全。merge(key, value, remappingFunction)原子性的更新或合并用于计数、累加。示例多线程统计关键词出现次数ConcurrentHashMapString, Integer countMap new ConcurrentHashMap(); for (String word : words) { countMap.merge(word, 1, Integer::sum); }这套代码没有锁、并发安全、性能好。如果你用HashMap自己加锁复杂度高还不一定对。能用并发容器解决的事情不要手写synchronized。4. 实战案例从能用到高效的一次集合重构纸上谈兵到此为止我们看一个真实项目里遇到的性能问题。这个案例是某后台管理系统的订单查询接口页面要展示最近30天订单按用户去重并按金额降序分页。原始实现是三层嵌套循环一堆contains调用数据量到了十来万就明显卡顿。4.1 初版实现那个能跑但很慢的代码伪代码如下ListOrder orders orderMapper.queryLast30Days(); ListUserStat result new ArrayList(); for (Order order : orders) { boolean exists false; for (UserStat stat : result) { // O(n) 扫描 if (stat.userId.equals(order.userId)) { stat.amount order.amount; exists true; break; } } if (!exists) { result.add(new UserStat(order.userId, order.amount)); } } result.sort((a, b) - Long.compare(b.amount, a.amount)); // 降序这段代码的逻辑是对的但性能很糟糕。每次处理一个新订单都要在result这个ArrayList上做线性查找。总复杂度是O(n^2)。10万条订单时内层循环平均要扫5万次总操作数50亿跑不动很正常。4.2 第一次优化用HashMap换掉内层线性扫描我把它改成用HashMap维护userId - UserStat的映射MapString, UserStat statMap new HashMap(); for (Order order : orders) { UserStat stat statMap.get(order.userId); if (stat null) { stat new UserStat(order.userId, 0); statMap.put(order.userId, stat); } stat.amount order.amount; } ListUserStat result new ArrayList(statMap.values()); result.sort(Comparator.comparingLong(UserStat::getAmount).reversed());这段代码把每单的查找从O(n)降到了O(1)平均整体复杂度从O(n^2)降到O(n log n)瓶颈只剩最后的排序。10万条数据的处理时间从几百毫秒甚至秒级降到了几十毫秒。差别就是这样来的。这里还有一个小细节new ArrayList(statMap.values())的容量就是statMap.size()刚好避免了ArrayList扩容损耗——把前面讲的预估容量用上了。4.3 第二次优化减少对象创建与按需分页第一次优化后耗时已经可以接受但如果数据量继续涨还有两个方向可以进一步压一是对象创建。new UserStat(...)在每出现一个新用户时都会触发大量小对象会被GC反复回收。可以使用一个可复用的UserStat数组或池化但大多数业务场景没必要——JVM的GC对短生命周期小对象是友好的不要过早优化。二是分页不要全量排序。如果页面只需展示Top 20没必要把所有用户的统计结果都排序。可以维护一个容量为K的最小堆PriorityQueue或者直接用stream().sorted().limit(20)让它短路运算。注意sorted().limit()在实际执行时并不会排完整份数据底层流水线会提前截断但数据量特别大时真正的Top-K算法还是要手写PriorityQueueKQueueUserStat topK new PriorityQueue(Comparator.comparingLong(UserStat::getAmount)); for (UserStat stat : result) { if (topK.size() 20) { topK.offer(stat); } else if (topK.peek().getAmount() stat.getAmount()) { topK.poll(); topK.offer(stat); } }这样内存占用从全量排序降为只在堆里维护20个元素在高并发接口里非常有用。5. 常见问题与排查技巧实录最后一部分我把自己在开发中遇到过的集合相关坑整理成一个速查表每条都是真实踩过或帮别人排查过的。错误/异常根因解决方案ConcurrentModificationException遍历List/Map时直接修改集合使用Iterator.remove()、Collectors或先拷贝再遍历UnsupportedOperationException对Arrays.asList返回的List调用add/remove用new ArrayList(Arrays.asList(...))包一层ClassCastExceptionontoArray()直接强转Object[]为特定类型数组使用list.toArray(new String[0])NullPointerExceptionfromTreeMap使用null key或null valueTreeMap不允许改用HashMap或确保无nullIllegalStateExceptionfromCollectors.toMap有重复key但没传合并函数加第三个参数(v1, v2) - v1或merge并发HashMap数据丢失HashMap在并发下put丢数据换ConcurrentHashMap迭代顺序不稳定使用HashSet/HashMap期望有序输出按需换LinkedHashSet/LinkedHashMap或TreeSet关于并发修改的补充ArrayList在迭代过程中如果有其他线程或同线程的其他代码路径调用了结构性修改add/remove迭代器会快速失败抛出ConcurrentModificationException。这个快速失败机制是通过modCount字段实现的每次结构性修改都会modCount迭代器持有期望的expectedModCount两者不一致就抛异常。理解了原理你就明白不要用list.remove在foreach里删元素改用removeIfJDK 8或显式迭代器。关于equals与hashCode的业务一致性HashMap、HashSet依赖hashCode和equals来判断元素是否相同。你自定义对象放进Set时如果不重写这两个方法同一逻辑值会被当成不同对象导致去重失效。这可能是Set去重没用的最常见原因。IDEA的Generate能帮你生成等价方法的模板但注意业务上相同的定义要和你重写的equals一致。比如订单按订单号相等但日期不同也算不同那equals里就不能写死所有字段比较。关于字符串当key的性能HashMap用String做key是很常见的String的hashCode做了缓存首次计算后存到hash字段所以重复获取hashCode不消耗额外计算。这算是String在集合场景下的一个隐形优势。关于初始化容量的最佳实践HashMap传初始容量时如果实际加载元素数超过capacity * 0.75就会触发扩容所以如果要放1000个元素建议传1000 / 0.75 1 ≈ 1334或者直接写new HashMap(1340)。不过这前提是你明确知道数据量否则一般靠自动扩容也没问题。关于LinkedHashMap做LRU缓存LinkedHashMap的构造方法里有一个accessOrder参数设为true时每次get都会把元素挪到链表尾部配合重写removeEldestEntry(Map.Entry)方法就能实现一个LRU缓存LinkedHashMapString, Integer lru new LinkedHashMap(16, 0.75f, true) { Override protected boolean removeEldestEntry(Map.EntryString, Integer eldest) { return size() 100; } };这个写法在面试中经常被考到在实际项目中做轻量级缓存也够用。它的复杂度是O(1)访问、O(1)淘汰非常经典。把这几年集合框架相关的问题捋了一遍我发现一个普遍规律**绝大多数性能问题不是框架太慢而是用错了结构 没关注规模**。很多人选择容器看心情遍历方法靠直觉从来不估算数据量最后在压测或线上被慢查询教育一顿才回头翻源码。如果你能从现在开始每次写集合代码前问自己三个问题——数据量级是多少核心操作是读还是写要不要顺序和线程安全——那这一章的内容就真正起作用了。