Jon Skeet最近在他的博客上提出了一个有趣的编程话题:“我的抽象中有一个洞，亲爱的Liza，亲爱的Liza”(着重部分由作者添加):
我有一个集合 - 事实上是一个HashSet。我想从中删除一些项目...而且许多项目很可能不存在。事实上，在我们的测试用例中，“移除”集合中的任何项目都不会在原始集合中。这听起来 - 而且确实 - 非常容易编码。毕竟，我们已经设定好了
我们在命令行上指定“source”集合的大小和“removals”集合的大小，并构建这两个集合。源集只包含非负整数；移除集只包含负整数。我们使用< code > system . current time millis()来测量移除所有元素需要多长时间，这不是世界上最精确的秒表，但在这种情况下已经足够了，正如您将看到的。代码如下:
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
好吧，所以我们没想到它会很慢...显然，我们可以把事情提高一点。100 万个项目和 300，000 个项目的来源如何？
c:UsersJonTest>java Test 1000000 300000
Time taken: 38ms
嗯。这似乎仍然很快。现在我觉得我有点残忍，要求它做所有这些移除。让我们让它更容易一点 - 300，000 个源项和 300，000 个删除：
c:UsersJonTest>java Test 300000 300000
Time taken: 178131ms
对不起？将近三分钟？哎呀！当然，从较小的集合中删除项目应该比我们在 38 毫秒内管理的项目更容易吗？
有人能解释一下为什么会这样吗？为什么< code >是HashSet
javadoc中(在某种程度上)记录了这种行为:
此实现通过对每个集合调用size方法来确定此集合和指定集合中的较小者。如果此集合的元素较少，那么实现将遍历此集合，依次检查迭代器返回的每个元素，以查看其是否包含在指定集合中。如果包含了它，则使用迭代器的remove方法将其从该集合中删除。如果指定的集合具有更少的元素，那么实现将迭代指定的集合，使用该集合的remove方法从该集合中移除迭代器返回的每个元素。
这在实践中意味着什么，当你调用source.removeAll（removals）;：
>
如果删除集合的大小小于Source，则调用HashSet的删除方法，速度很快。
如果< code>removals集合的大小等于或大于< code>source，则调用< code>removals.contains，这对于ArrayList来说很慢。
快速修复：
Collection<Integer> removals = new HashSet<Integer>();
请注意，有一个打开的bug与您描述的非常相似。底线似乎是，它可能是一个糟糕的选择，但无法更改，因为它在javadoc中有文档记录。
作为参考，这是< code>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;
}
