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

Jon Skeet最近在他的博客上提出了一个有趣的编程主题:"There's a hole in my abstraction, dear Liza, dear Liza"(添加了重点):

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

最佳答案

该行为(某种程度上)记录在javadoc中:



实际上，当您调用source.removeAll(removals);时意味着什么:

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

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

快速解决:

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

请注意，有一个an open bug与您描述的非常相似。底线似乎是它可能是一个较差的选择，但不能更改，因为它已在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;
}