HashSetremoveAll方法非常慢

我有一个集合 - 一个HashSet我想从中删除一些项目......"removals"集合中的所有项目都不在原始集合中.

我在命令行中指定"source"集的大小和"removals"集合的大小,并构建它们.源集仅包含非负整数; 删除集仅包含负整数.我测量使用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 source = new HashSet(); 
       Collection removals = new ArrayList(); 

       for (int i = 0; i 

让我们从一个简单的工作开始:一个包含100个项目的源集,以及100个要删除的源:

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


好的,这比我预想的要快. 

接下来我尝试了一百万件物品的来源和300,000件物品去除？

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


这看起来仍然很快.现在让它更容易 -  300,000个源项目和300,000个删除:

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


差不多三分钟？ 

真的很困惑!! 有人可以解释为什么会这样.


1> assylias..：
行为(有些)记录在javadoc中:


  
此实现通过在每个集合上调用size方法来确定哪个是此集合和指定集合中较小的集合.如果此set具有较少的元素,则实现迭代该集合,依次检查迭代器返回的每个元素以查看它是否包含在指定的集合中.如果包含它,则使用迭代器的remove方法从该集合中删除它.如果指定的集合具有较少的元素,则实现迭代指定的集合,使用此set的remove方法从该集合中移除迭代器返回的每个元素.


这在实践中意味着什么,当你打电话source.removeAll(removals);:


如果removals集合的大小小于source,则调用remove方法HashSet,这很快.

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



快速解决:

Collection removals = new HashSet();


请注意,有一个与您描述的非常相似的开放式错误.底线似乎是它可能是一个糟糕的选择,但不能改变,因为它记录在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;
}

        
哇.我今天学到了一些东西 这看起来对我来说是一个糟糕的实现选择.如果其他集合不是Set,则不应该这样做. 
@show_stopper我刚刚运行了一个分析器,发现`ArrayList#contains`是罪魁祸首.看一下`AbstractSet #removeAll`的代码给出了其余的答案. 
@JBNizet是的，很奇怪-有人在您的建议下讨论过[here]（http://mail.openjdk.java.net/pipermail/core-libs-dev/2011-July/007148.html）-不知道为什么这么做不经历...