引言

带新同事做订单去重的需求，他写出了这样一段代码：List 里 10 万条订单 ID，要移除一批黑名单 ID，他选择了 list.removeAll(blackList)——然后在压测时发现这个接口要跑 40 多秒。他一脸困惑："ArrayList 的 remove 不就是删个元素吗？"

这是 Java 集合最典型的认知偏差：API 写起来一行代码，底层复杂度却是天壤之别。集合框架的 API 设计得太"平"了——list.remove(i)、list.get(i)、map.put(k,v) 全都长一个样，编译器不会提醒你"这个操作是 O(n)"，JVM 也不会报错，只有当数据量上来后，CPU 和监控才会替它呐喊。

这篇文章梳理 5 个最常见、最容易在生产代码里扎根的集合性能陷阱。每个陷阱给三样东西：触发代码、底层源码原理、修复方案 + 实测量级对比。

一、陷阱一：ArrayList.remove(Object) 是 O(n)——大数据量用 HashSet

1.1 触发代码

// ❌ 典型场景：10 万条订单中剔除黑名单里的 1 万个 ID
List<Long> orderIds = loadOrderIds();          // 100,000 条
List<Long> blacklist = loadBlacklist();        // 10,000 条

for (Long id : blacklist) {
    orderIds.remove(id);                       // 每次 O(n)！
}
// 复杂度：1 万 × 10 万 = 10 亿次比较，数据量再大直接卡死

1.2 源码原理：remove(Object) 干了两件 O(n) 的事

// ArrayList.java（删减）
public boolean remove(Object o) {
    // 第一步：indexOf(o) —— 线性扫描找到下标，O(n)
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) { fastRemove(index); return true; }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) { fastRemove(index); return true; }
    }
    return false;
}

private void fastRemove(int index) {
    // 第二步：System.arraycopy —— 删完把后面所有元素整体前移一位，O(n)
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null;
}

一次 remove = 两次 O(n)（查找 + 数组搬移），而且 removeAll 内部同样依赖这套逐个匹配逻辑，中间状态复杂度更高。remove 越靠前，arraycopy 搬移的元素越多——最坏情况删第 0 个元素要搬移全部 n-1 个。

顺带纠正一个孪生误区：remove(int index)（按下标删）省掉了查找，但 arraycopy 搬移那步 O(n) 依然在——"按下标删就快"是错觉。

1.3 修复：HashSet 承担"成员判断"

// ✅ 黑名单转 HashSet：contains O(1)
Set<Long> blacklistSet = new HashSet<>(blacklist);

// ✅ 方案一：结果集走一遍过滤，O(n)
List<Long> result = orderIds.stream()
        .filter(id -> !blacklistSet.contains(id))
        .collect(Collectors.toList());

// ✅ 方案二：Java 8+ 直接 removeIf（内部遍历一次 + bitset 优化，O(n)）
orderIds.removeIf(blacklistSet::contains);

1.4 实测量级

经验法则：只要代码里出现"在 List 上反复 contains/remove"，就是 HashSet 出场的信号。判断"在不在"用 Set，维护"顺序"才用 List。

二、陷阱二：LinkedList.get(index) 是 O(n)——随机访问用 ArrayList

2.1 触发代码

// ❌ 听信"LinkedList 增删快"，选它存数据，又按下标遍历
List<Order> orders = new LinkedList<>();
// ... add 5 万条

for (int i = 0; i < orders.size(); i++) {      // 每次调用 get(i)
    process(orders.get(i));                    // O(n)！
}
// 复杂度：n × n/2 = 12.5 亿次节点跳转，5 万条就要跑十几秒

2.2 源码原理：get(i) 要从链头/链尾走 i 步

// LinkedList.java（删减）——已算"优化过"的版本
Node<E> node(int index) {
    // 小"聪明"：前半段从头走，后半段从尾走
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++) x = x.next;   // 最多 n/2 步
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--) x = x.prev;
        return x;
    }
}

即使折半优化，单次 get 仍是 O(n/2)；循环里调用就是 O(n²)。链表的物理结构（分散的 Node 节点 + prev/next 指针）决定了它没有"第 i 个"的直达通道。

2.3 "LinkedList 增删快"这句过时结论

老教材说 LinkedList 增删 O(1)、ArrayList 增删 O(n)——这句话有两个时代性的漏洞：

2.4 修复

// ✅ 默认用 ArrayList：99% 的场景它是正确答案
List<Order> orders = new ArrayList<>();

// ✅ 遍历 LinkedList 用迭代器，而不是 get(i)
for (Order order : orders) {           // for-each 编译成 iterator，O(n)
    process(order);
}

// ✅ 真需要频繁头尾操作的队列场景，用 ArrayDeque（比 LinkedList 更快更省）
Deque<Task> queue = new ArrayDeque<>();

2.5 实测量级

经验法则：LinkedList 在现代 JVM 下的适用面极窄（几乎只剩 LRU 手工实现、超长列表频繁头部插入这类边角场景）。看到 LinkedList + get(int) 同时出现，基本可以断定是性能 bug。

三、陷阱三：HashMap 不设初始容量——频繁 resize 的隐形成本

3.1 触发代码

// ❌ 要装 100 万条数据，却用默认容量
Map<Long, Order> orderMap = new HashMap<>();     // 容量 16
for (Order o : orders) {                          // 100 万条
    orderMap.put(o.getId(), o);                   // 中途扩容 ~17 次
}

3.2 源码原理：resize 是"全量 rehash"

// HashMap.java（删减）
final Node<K,V>[] resize() {
    int newThr = 0;                  // 新容量 = 旧容量 × 2
    newCap = oldCap << 1;
    ...
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];   // 分配新数组
    for (int j = 0; j < oldCap; ++j) {                     // 旧数组全量遍历
        ...
        // 每个元素重新计算落位（Java 8 优化为无需重算 hash：
        //   (e.hash & oldCap) == 0 ? 原位置 : 原位置+oldCap）
        // 且**长度 ≥8 的桶会裂成红黑树/退回链表**，树化维护也有成本
        newTab[j] = loHead; ...
    }
    return newTab;
}

默认容量 16、负载因子 0.75，装 100 万元素要经历 17 次 resize：每次都要新建数组、全量搬移、处理红黑树退化——累计 O(n × 次数) 的隐形成本，全部发生在没人注意的 put 循环里。更糟的是业务高峰期，一次扩容可能恰好压在耗时毛刺上。

3.3 修复：预估容量，一步到位

// ✅ 已知规模：初始容量 = 预期元素数 / 0.75，再向上取 2 的幂
Map<Long, Order> orderMap = new HashMap<>((int) (orders.size() / 0.75f) + 1);
// 或者直接用 Guava 的 Maps.newHashMapWithExpectedSize(n)，语义更清晰
Map<Long, Order> orderMap2 = Maps.newHashMapWithExpectedSize(orders.size());

为什么要除以 0.75 而不是直接传 n：threshold = capacity × 0.75，传 n 的话装到 0.75n 时仍会扩容一次。另外注意 HashMap 容量永远是 2 的幂（tableSizeFor 向上取整），预估 10 万会被取整到 131072，是正常行为不是 bug。

3.4 实测量级

经验法则：写代码时问一句"这个 Map/List 最终大概装多少"——能预估就传容量。这也是 Alibaba Java 开发手册明确推荐的规约（initialCapacity = (需要存储的元素个数 / 负载因子) + 1）。

四、陷阱四：parallelStream 滥用——小数据量比串行还慢

4.1 触发代码

// ❌ 听说并行流快，无脑 parallel()
List<Integer> small = load1000Items();          // 1000 条
int sum = small.parallelStream()                 // 反而慢
        .mapToInt(Integer::intValue)
        .sum();

// ❌ 更危险的：并行流里调用 IO/远程接口
orders.parallelStream().forEach(o -> {
    inventoryClient.deduct(o);                   // ❌ 共享 ForkJoinPool 被慢 IO 塞满
});                                              // 整个 JVM 的 parallel 操作一起遭殃

4.2 原理：并行是有固定开销的

parallelStream 底层走 ForkJoinPool.commonPool()（线程数默认 = CPU 核数 - 1），每次并行计算要付三笔固定账：

① 任务切分成本：数据拆分成子任务（Spliterator 分片）
② 线程调度成本：任务入队/窃取/汇总（ForkJoin 的 work-stealing）
③ 结果合并成本：子任务结果的 combine

数据量小时，这些开销远大于计算本身——1 个元素的并行流，切分调度合并的钱一分不少花，计算却只省了"零"。

还有一个隐蔽的工程雷：commonPool 是全 JVM 共享的。一个业务把并行流阻塞在慢 IO 上，整个进程所有 parallel 操作（包括第三方库内部的）都会饿死。线程池隔离原则在这里完全适用。

4.3 修复：三道判断再决定并行

// ✅ 判断一：数据量够大吗？经验阈值 1 万+，且单元素计算别太轻
// ✅ 判断二：单元素计算是 CPU 密集吗？IO 操作禁用 parallelStream
// ✅ 判断三：数据结构可高效分片吗？（ArrayList/数组可分，LinkedList 分片本身就 O(n)）

List<Integer> huge = loadMillionItems();         // 100 万条，纯 CPU 计算
int sum = huge.parallelStream()
        .mapToInt(this::heavyCompute)            // 单元素 ~10μs 的 CPU 计算
        .sum();                                   // ✅ 这才是并行的主场

// ✅ IO 场景：老老实实自己建线程池/异步编排，不要污染 commonPool
ExecutorService pool = Executors.newFixedThreadPool(20);
List<CompletableFuture<Boolean>> futures = orders.stream()
        .map(o -> CompletableFuture.supplyAsync(() -> inventoryClient.deduct(o), pool))
        .collect(Collectors.toList());
CompletableFuture.allOf(futures.toArray(new CompletableFuture[0])).join();

4.4 实测量级

经验法则：parallelStream 不是"免费的加速开关"，它是给"大数据量 × CPU 密集 × 可分片"准备的工具。拿不准就串行——串行的性能是可预期的下限，并行的性能可能是一个意外。

五、陷阱五：for-each 中 remove——ConcurrentModificationException

5.1 触发代码

// ❌ 编译通过、单条数据测试通过、数据量小也许侥幸不炸——上线后炸
List<Order> orders = loadOrders();
for (Order order : orders) {
    if (order.isCancelled()) {
        orders.remove(order);          // 抛 ConcurrentModificationException
    }
}

这个陷阱的特殊性在于：它不是性能问题，是可用性问题——而且有典型的"测试环境测不出来"特性（异常触发依赖"删除后继续遍历"这个时序，删最后一个元素可能侥幸不炸）。

5.2 源码原理：fail-fast 的 modCount 机制

// ArrayList$Itr.next()（增强 for 编译后走这里）
public E next() {
    checkForComodification();          // ← 每次取元素前先"验票"
    ...
}

final void checkForComodification() {
    // modCount：集合结构性修改（add/remove）的次数计数器
    // expectedModCount：迭代器创建时记下的"票根"
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

增强 for 的本质是 iterator：每次 next() 都比对集合的修改次数和迭代器记录的票根。你在循环体里调 list.remove()，modCount +1；下一次 next() 一验票——对不上，当场抛异常。设计意图是"尽早暴露并发修改"，单线程的循环内 remove 同样会被这个机制拦下。

5.3 修复：三种姿势按场景选

// ✅ 方案一（Java 8+，首选）：removeIf——内部用迭代器+bitset，正确且快
orders.removeIf(Order::isCancelled);

// ✅ 方案二：显式 Iterator，用迭代器自己的 remove（会同步 expectedModCount）
Iterator<Order> it = orders.iterator();
while (it.hasNext()) {
    if (it.next().isCancelled()) {
        it.remove();                   // ✅ 注意是 it.remove()，不是 orders.remove()
    }
}

// ✅ 方案三：不删，收集要保留/要删除的，循环外处理
List<Order> toRemove = orders.stream()
        .filter(Order::isCancelled)
        .collect(Collectors.toList());
orders.removeAll(toRemove);            // 配合场景一的 Set 优化

进阶场景——多线程下 Iterator.remove 也不够：fail-fast 机制只保单线程正确。多线程并发读写同一集合，请直接换并发容器：CopyOnWriteArrayList（读多写少）或 ConcurrentLinkedQueue（高并发队列）。fail-fast 是"及时报错"而不是"并发安全"，这个认知差是很多线上事故的源头。

六、常见问题

6.1 怎么快速定位线上代码踩了这些陷阱？

两条路径：① CPU 火焰图（async-profiler）：ArrayList.remove/System.arraycopy/HashMap.resize 在火焰图上占比异常，就是对应陷阱的直接证据；② 代码评审关键词扫描：List 上的 contains/remove、LinkedList、new HashMap<>() 大循环 put、parallelStream、for-each + remove——五个关键词基本覆盖本文全部陷阱。

6.2 数据量多小才算"安全"，多大才必须优化？

给一个可操作的参考线：元素数 < 1000 时，本文陷阱 1/2/3/4 的耗时都在毫秒级以内，可以放过（可读性优先）；达到 1 万~10 万量级，陷阱 1/2/4 开始产生百毫秒到秒级开销，需要处理；百万级以上，5 个陷阱全部按本文方案处理。真正的危险区不是"量大的代码"，而是"不知道会变大多少的代码"——接口签名上是 List 的地方，都默认按"会被塞进几十万条"来写。

6.3 ArrayList 删除大量元素还有别的写法吗？

有，而且 often 最优：不删，重建。orders.removeIf(...) 内部就是对"搬移每个元素"的优化（Java 8 起用 BitSet 标记待删元素、一次搬移压实），如果业务允许，stream().filter().collect() 生成新列表同样是一次 O(n)。它们都优于"循环单删"的 O(n²)。原则：批量删除永远不要写成循环单删。

6.4 ConcurrentHashMap 需要设初始容量吗？

需要，逻辑和 HashMap 一致（threshold 同样是 0.75）。区别在实现：ConcurrentHashMap 扩容是多线程协助搬迁（比单线程 rehash 友好），但扩容期间读写都要走迁移逻辑，仍有性能毛刺。预估容量这个习惯对它同样适用。

6.5 为什么 IDE 不报这些陷阱？

因为它们都是"合法的慢代码"——编译器、IDE 静态检查（除了部分商业工具）都无法从局部语法推断复杂度与数据量。这正是本文存在的意义：性能陷阱的防线在人。建议把第六节的五个关键词写进团队 Code Review checklist，成本最低收益最大。

6.6 有没有工具能自动化兜底？

有方向的：JMH 做微观基准验证、async-profiler 火焰图做线上验证、Alibaba 开发手册对应的 P3C 插件能扫出部分规约违规（如 HashMap 容量建议）。但没有一个工具能完整覆盖这 5 个陷阱——集合复杂度判断依赖"业务数据量"这个只有开发者知道的上下文。工具是网，人是渔。

七、总结

5 陷阱速查卡

┌────┬─────────────────────────┬────────────────────────────────┬──────────────────────────┐
│ #  │ 陷阱                    │ 根因                            │ 修复                      │
├────┼─────────────────────────┼────────────────────────────────┼──────────────────────────┤
│ 1  │ ArrayList.remove(Object)│ 查找 O(n) + arraycopy O(n)      │ Set.contains + removeIf   │
│ 2  │ LinkedList.get(index)   │ 无直达通道，逐节点 O(n)          │ ArrayList / for-each 遍历 │
│ 3  │ HashMap 默认容量         │ resize 全量 rehash × 17 次      │ 预估容量 (n/0.75)+1       │
│ 4  │ parallelStream 滥用      │ 切分/调度/合并固定开销 + IO 污染 │ 三道判断 / 自建线程池      │
│ 5  │ for-each 中 remove       │ modCount fail-fast 验票         │ removeIf / it.remove()    │
└────┴─────────────────────────┴────────────────────────────────┴──────────────────────────┘

关键数据

• ArrayList 循环 remove 1 万黑名单：42 秒 → removeIf 8 毫秒（5000 倍）
• LinkedList 按下标遍历 5 万元素：比 ArrayList 慢 800 倍
• HashMap 百万元素不设容量：17 次 resize，慢 40% 且带 17 次毛刺
• parallelStream 1000 条数据：比串行慢 30 倍

一句话

集合性能陷阱的共同套路是：API 层面一行代码的"小事"，在源码层面是 O(n) 或 O(n²) 的大事，而数据量就是那个把小事放大的乘数。记住三个反直觉和三个直觉——remove 没那么快、LinkedList 没那么好用、parallel 没那么神；Set 判断成员要快、容量要提前给、for-each 里别动手删。看 API 时多想一层"它底层搬了多少数据"，性能直觉自然就长出来了。

给团队的建议

互动话题：这 5 个陷阱你踩过几个？有没有被一个"看起来人畜无害的集合操作"在生产上坑出 P0 的经历？评论区聊聊你的名场面。

参考资料

• OpenJDK ArrayList 源码
• OpenJDK LinkedList 源码
• OpenJDK HashMap 源码（resize/tableSizeFor）
• Oracle 官方教程：Collections 框架性能
• Java 官方文档：Spliterator 与并行流
• ForkJoinPool.commonPool 说明（Java Concurrency 规范）
• Alibaba Java 开发手册（集合处理章节）