HashSet removeAll方法出奇的慢
我有一个集合 – 一个HashSet我想从中删除一些项目…“清除”集合中的任何项目都不会在原始集合中。
我在命令行中指定“源”集合的大小和“删除”集合的大小，然后构build它们。 源集只包含非负整数; 删除集合只包含负整数。 我测量了使用System.currentTimeMillis（）去除所有元素需要多长时间，这是不是世界上最准确的秒表，但在这种情况下是足够的，正如你将看到的。 代码如下：
import java.util.*; public class Test { public static void main(String[] args) { int sourceSize = Integer.parseInt(args[0]); int removalsSize = Integer.parseInt(args[1]); Set<Integer> source = new HashSet<Integer>(); Collection<Integer> removals = new ArrayList<Integer>(); for (int i = 0; i < sourceSize; i++) { source.add(i); } for (int i = 1; i <= removalsSize; i++) { removals.add(-i); } long start = System.currentTimeMillis(); source.removeAll(removals); long end = System.currentTimeMillis(); System.out.println("Time taken: " + (end – start) + "ms"); } } 让我们开始一个简单的工作： 一个100个项目的源组，100个删除：
c:UsersJonTest>java Test 100 100 Time taken: 1ms
好吧，我想像的那样快
接下来我尝试了一百万件物品和三十万件物品的来源去除？
c:UsersJonTest>java Test 1000000 300000 Time taken: 38ms
这似乎还挺快。 现在让它更容易 – 30万个源项目和30万个清除：
c:UsersJonTest>java Test 300000 300000 Time taken: 178131ms
差不多三分钟？
真的很困惑！ 有人可以解释为什么会发生这种情况。
这个行为（在某种程度上）logging在javadoc中 ：
这个实现通过调用每一个的size方法来确定这个集合和指定的集合中哪一个更小。 如果这个集合有更less的元素 ，那么这个实现迭代这个集合，依次检查迭代器返回的每个元素，看看它是否包含在指定的集合中 。 如果包含它，则使用迭代器的remove方法将其从此集中移除。 如果指定的集合有更less的元素，那么实现迭代指定的集合，从这个集合中删除迭代器返回的每个元素，使用这个集合的remove方法。
这意味着在实践中，当你调用source.removeAll(removals); ：
-
如果
removals集合的大小比source小，则调用HashSet的remove方法，这是快速的。 -
如果
removals集合的大小等于或大于source大小，则调用removals.contains，这对于ArrayList来说是缓慢的。
快速解决：
Collection<Integer> removals = new HashSet<Integer>();
请注意，有一个开放的错误与您描述的非常相似。 底线似乎是，它可能是一个糟糕的select，但不能改变，因为它在javadoc中logging。
作为参考，这是removeAll的代码（在Java 8中 – 没有检查其他版本）：
public boolean removeAll(Collection<?> c) { Objects.requireNonNull(c); boolean modified = false; if (size() > c.size()) { for (Iterator<?> i = c.iterator(); i.hasNext(); ) modified |= remove(i.next()); } else { for (Iterator<?> i = iterator(); i.hasNext(); ) { if (c.contains(i.next())) { i.remove(); modified = true; } } } return modified; }
