哈希集.removeAll方法出奇的慢

Question

乔恩·斯凯特（Jon
Skeet）最近在他的博客上提出了一个有趣的编程主题：“我的抽象中有一个漏洞，亲爱的Liza，亲爱的Liza”（强调）：

我有一套- HashSet实际上。我想从中删除一些项目……许多项目可能不存在。实际上，在我们的测试案例中，“删除”集合中的所有项目 都不
在原始集中。这听起来（确实 是
）非常容易编写。毕竟，我们Set<T>.removeAll需要帮助我们，对吧？

我们在命令行上指定“源”集的大小和“删除”集合的大小，然后构建它们两者。源集仅包含非负整数；清除集仅包含负整数。我们将使用来测量删除所有元素所需的时间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

好的，所以我们没想到它会变慢……很明显，我们可以将事情加速进行。一百万个项目和30万个要删除的项目的来源怎么样？

c:UsersJonTest>java Test 1000000 300000
Time taken: 38ms

嗯 看起来还是很快的。现在，我觉得自己有点残酷，要求它执行所有删除操作。让我们简化一下– 300,000个源项目和300,000个清除项目：

c:UsersJonTest>java Test 300000 300000
Time taken: 178131ms

对不起？近三 分钟 ？kes！当然，从一个 较小的 集合中删除项目应该比我们在38毫秒内管理的项目更容易吗？

有人可以解释为什么会这样吗？为什么HashSet<T>.removeAll方法这么慢？

Answer 1

该行为（某种程度上）记录在javadoc中：

此实现通过在每个集合上调用size方法来确定该集合和指定集合中的较小者。 如果此集合具有较少的元素
，则实现将对此集合进行迭代，依次检查迭代器返回的每个元素，以查看 其是否包含在指定的collection中
。如果包含此类内容，则使用迭代器的remove方法将其从此集合中删除。如果指定的集合具有较少的元素，则实现将迭代指定的集合，并使用此集合的remove方法从此集合中删除迭代器返回的每个元素。

实际上，当您致电时意味着什么source.removeAll(removals);：

• 如果removals集合的大小小于source，则调用的remove方法HashSet，这是快速的。

• 如果removals集合的大小等于或大于source，则将removals.contains调用，这对于ArrayList来说很慢。

快速解决：

Collection<Integer> removals = new HashSet<Integer>();

请注意，存在一个与您所描述的非常相似的公开错误。底线似乎是它可能是一个较差的选择，但不能更改，因为它已在javadoc中进行了说明。

作为参考，这是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;
}