HashSet的removals()方法注意事项

我有一个集合，实际上是一个HashSet。我想从中删除一些item…其中许多item可能不存在。事实上，在我们的测试用例中，“removals”集合中的所有项都不在原始集合中。这听起来——实际上也是——非常容易编码。毕竟，我们已经准备好了。removeAll来帮助我们，对吗？

让我们把它变成一个小测试。我们在命令行上指定“source”set的大小和“removals”集合的大小，并构建它们。source set合只包含非负整数；删除集仅包含负整数。我们使用系统测量删除所有元素所需的时间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个items的source set，以及要删除的100个items：

c:UsersJonTest>java Test 100 100
Time taken: 1ms

好吧，所以我们没想到会很慢……很明显，我们可以把速度提高一点。一百万件items和300000件items的来源如何？

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

嗯，看起来还是挺快的。现在我觉得我有点残忍，要求它做所有这些移除。让我们让它变得更简单一些–300000个source items和300000个删除：

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

快三分钟了？哎呀！当然，从一个较小的集合中删除items应该比我们在38ms内管理的集合更容易？嗯，最终这一切都是有道理的。HashSet扩展了AbstractSet，它在removeAll方法的文档中包含此代码段：

https://docs.oracle.com/javase/6/docs/api/java/util/AbstractSet.html#removeAll(java.util.Collection)

此实现通过调用每个集合上的size方法来确定此集合和指定集合中的较小者。如果此集合的元素较少，则实现将迭代此集合，依次检查迭代器返回的每个元素，以查看它是否包含在指定的集合中。如果它是这样包含的，则使用迭代器的remove方法将其从该集中移除。如果指定集合的元素较少，那么实现将迭代指定集合，使用该集合的remove方法从该集合中删除迭代器返回的每个元素。

从表面上看，这听起来很合理——遍历较小的集合，检查较大集合中是否存在。然而，这就是抽象存在漏洞的地方。仅仅因为我们可以要求一个item出现在一个大的集合中，并不意味着它会很快出现。在我们的例子中，集合的大小是相同的，但是检查哈希集中是否存在项是O（1），而在ArrayList中检查是O（N）…而每个集合的迭代成本是相同的。基本上，通过选择遍历HashSet并检查ArrayList中是否存在，我们得到了一个O（M*N）解决方案，而不是O（N）解决方案。removeAll方法基于在这种情况下无效的假设进行“优化”。

那么如何解决？

有两种简单的方法可以解决这个问题。首先，只需更改要从中删除的集合的类型。只需将ArrayList<Integer>更改为HashSet<Integer>，我们就可以回到34ms的范围。我们甚至不需要更改声明的删除类型。

第二种方法是更改我们使用的API：如果我们知道要迭代删除并在源代码中执行查找，那么很容易做到：

for (Integer value : removals)
{
    source.remove(value);
}

事实上，在我的机器上，它的性能略优于removeAll–它不需要在每次迭代时检查remove的返回值，removeAll这样做是为了返回是否删除了任何项。以上运行时间约为28ms。（我已经用相当大的数据集对其进行了测试，它确实比双哈希集方法更快。）

然而，这两种方法都需要在源代码中添加注释，以解释为什么我们没有使用最明显的代码（列表和删除）。我不能抱怨这里的文档——它确切地说明了它将做什么。在你遇到这样的问题之前，你根本不需要担心它。

那么，实现应该做什么呢？可以说，它真的需要知道它所处理的每一个集合中什么是便宜的。在决定策略之前探索性能特征的想法对于清理我们喜欢在Java集合之类的框架中考虑的抽象是完全不可取的……但在这种情况下，这可能是一个好主意。