HashSet<T>.removeAll 方法出奇地慢

performance collections java hashset

2022-08-31 10:20:13

Jon Skeet最近在他的博客上提出了一个有趣的编程主题：“亲爱的Liza，亲爱的Liza，我的抽象中有一个漏洞”（着重号是后加的）：

我有一套 —— 事实上是一套。我想从中删除一些项目...许多项目很可能不存在。实际上，在我们的测试用例中，“删除”集合中的任何项都不会位于原始集合中。这听起来 - 确实如此 - 非常容易编码。毕竟，我们有Set<T>.removeAll来帮助我们，对吧？HashSet

我们在命令行上指定“源”集的大小和“删除”集合的大小，并构建它们。源集仅包含非负整数;删除集仅包含负整数。我们使用来衡量删除所有元素所需的时间，这不是世界上最准确的秒表，但在这种情况下已经绰绰有余，如您所见。代码如下：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
好吧，所以我们没想到它会很慢...显然，我们可以把事情提高一点。要删除的 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
对不起？将近三分钟？哎呀！当然，从较小的集合中删除项目应该比我们在38ms内管理的集合更容易吗？

有人能解释为什么会发生这种情况吗？为什么这种方法这么慢？HashSet<T>.removeAll

答案 1

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

此实现通过调用每个集合的 size 方法来确定此集合和指定集合中哪个较小。如果此集合具有较少的元素，则实现将循环访问此集合，依次检查迭代器返回的每个元素，以查看它是否包含在指定的集合中。如果它被如此包含，则使用迭代器的 remove 方法将其从此集中删除。如果指定的集合具有较少的元素，则实现将循环访问指定的集合，并使用此集合的 remove 方法从此集合中删除迭代器返回的每个元素。

这在实践中意味着什么，当您调用：source.removeAll(removals);

如果集合的大小小于，则调用的方法，这是快速的。removalssourceremoveHashSet
如果集合的大小等于或大于，则调用，这对于 ArrayList 来说很慢。removalssourceremovals.contains

快速修复：

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

请注意，有一个与您描述的非常相似的开放错误。底线似乎是它可能是一个糟糕的选择，但无法更改，因为它记录在javadoc中。

作为参考，这是（在Java 8中 - 尚未检查其他版本的代码）：removeAll

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;
}

答案 2