removeAll性能取决于具体集合类型：ArrayList和LinkedList为O(m×n)，HashSet为O(m)；误用ArrayList作参数会导致O(n²)，应转为HashSet优化至O(n)。
Java中removeAll方法看似简单，但实际性能表现高度依赖集合类型和底层实现。它不是“统一O(n)”的操作，不同子类的复杂度差异极大，稍不注意就会在大数据量场景下引发严重性能问题。
removeAll 的时间复杂度完全由被调用方决定
Collection 接口只定义了 boolean removeAll(Collection> c) 方法签名，不规定实现逻辑。真正执行时，调用的是具体子类（如 ArrayList、HashSet、LinkedList）的重写版本，而非 AbstractCollection 的默认实现。
- ArrayList：平均 O(m×n)，其中 m 是待移除集合大小，n 是原集合大小 —— 因为它内部用
contains判断每个元素是否该删，而 ArrayList 的contains是线性扫描 - HashSet：平均 O(m)，因为
contains是哈希查找，接近 O(1)；整个过程只需遍历待删集合，对每个元素调用一次remove - LinkedList：同样退化为 O(m×n)，因
contains需逐节点遍历
AbstractCollection 提供的是“兜底实现”，但很慢
当某个集合类没重写 removeAll（比如自定义集合仅继承 AbstractCollection 且未覆盖该方法），就会走 AbstractCollection 的默认实现。它的逻辑是：
- 遍历当前集合的迭代器
- 对每个元素，调用参数集合
c.contains(element) - 若返回 true，则调用
iterator.remove()
这个实现隐含两个关键坑点：
- 如果参数集合
c是 ArrayList 或 LinkedList，每次c.contains(...)都是 O(c.size())，整体变成 O(this.size() × c.size()) - 迭代器的
remove()在某些集合中可能低效（如 ArrayList 删除中间元素要移动后续所有元素）
常见误用场景与优化建议
很多开发者以为“只要用了 Set 就快”，却忽略了参数集合的类型选择。
- ❌ 错误写法：
listA.removeAll(listB)，两个都是 ArrayList → 可能 O(n²) - ✅ 正确做法：把 listB 转成 HashSet 再调用，
listA.removeAll(new HashSet(listB))→ 降为 O(n) - ⚠️ 注意：转 HashSet 有额外空间开销和构造成本，小数据量（
- ? 更稳妥方式：对大集合做 removeAll 前，显式确保参数是哈希结构，或改用流式过滤（
listA.removeIf(listB::contains)，但同样要求 listB 支持高效 contains）
retainAll 同理，但语义相反
retainAll(c) 保留当前集合中也在 c 中存在的元素，底层逻辑与 removeAll 对称：也是遍历自身 + 查询参数集合。因此它同样受参数集合 c 的 contains 效率支配。
- 若
c是 HashSet，retainAll可达 O(n) - 若
c是 ArrayList，就又掉进 O(n²) 坑里 - AbstractCollection 的默认
retainAll实现也基于c.contains(...)，逻辑一致
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
