Java ArrayList 怎么实现高效的交集与差集运算-java教程-PHP中文网

arraylist无内置交集差集方法，需用retainall()/removeall()配合hashset将o(n×m)降为o(n+m)；小集合调用、大集合转hashset传入；stream方案可不修改原集合且语义清晰。

java arraylist 怎么实现高效的交集与差集运算

Java 中 ArrayList 本身不提供内置的交集（intersection）或差集（difference）方法，但可以通过结合 HashSet 或 retainAll()/removeAll() 实现高效运算。关键在于：**避免嵌套循环（O(n×m)），优先用哈希结构降为 O(n+m)**。

用 retainAll() 快速求交集（保留共同元素）

retainAll() 是 Collection 接口定义的方法，会修改原集合，只保留与指定集合共有的元素。它内部使用 contains() 判断，因此被调用方（即调用 retainAll 的 ArrayList）越大，性能越差；理想做法是让小集合调用、大集合传入：

先将较大的列表转为 HashSet，提升 contains() 效率为 O(1)
再让较小的 ArrayList 调用 retainAll(hashSet)

示例：

java-enterprise

Java企业开发专家，专注于Spring Boot、微服务架构和JVM优化。适用于：Java语言掌握、

下载

List listA = new ArrayList(Arrays.asList("a", "b", "c", "d"));
List listB = new ArrayList(Arrays.asList("c", "d", "e", "f"));
// 求交集 → ["c", "d"]
HashSet setB = new HashSet(listB); // O(m)
listA.retainAll(setB); // O(n)

用 removeAll() 高效求差集（A - B）

removeAll(Collection> c) 同样基于 contains()，逻辑是“从调用方中移除所有在参数集合中存在的元素”。同样建议：小集合调用，大集合转 HashSet 传入：

若求 A − B（A 中有、B 中没有的元素），把 B 转成 HashSet，再对 A 调用 removeAll(setB)
注意：该操作会修改原 A；如需保留原列表，先 new ArrayList(A) 复制一份

List aCopy = new ArrayList(listA);
HashSet setB = new HashSet(listB);
aCopy.removeAll(setB); // A - B → ["a", "b"]

不修改原集合？用 Stream + HashSet（Java 8+）

如果需要不可变结果或链式处理，Stream 方案更清晰，且自动利用 HashSet 加速：

交集：listA.stream().filter(setB::contains).collect(Collectors.toList())
差集（A−B）：listA.stream().filter(x -> !setB.contains(x)).collect(Collectors.toList())
优势：不改变原集合；语义明确；可轻松去重或映射