我们已经习惯了这样一个事实，即JDK中的标准集合做得很好，并且表现直观。但是真的是这样吗？昨天罗曼·伊丽莎罗夫（Roman Elizarov）伊利扎罗夫发布在Twitter上的一个新的有趣的门框的消息。紧紧抓住：Set.removeAll(list)在某些情况下，它可以用于O（N²）。为何如此？
罗曼在调试一段代码时发现了一个问题，由于令人惊讶的原因，该代码工作太慢。他在IntelliJ IDEA的内置事件探查器中启动了它，并立即在火焰图上看到他一直AbstractSet.removeAll在调用方法中浪费所有时间list.contains（链接到代码中的确切位置）。要了解正在发生的事情，请考虑一个稍有不同的示例。早些时候，乔恩·斯凯特（Jon Skeet）发表了一篇文章“我的抽象中有一个洞，亲爱的丽莎，亲爱的丽莎”，他在其中考虑了以下有趣的情况。假设我们有一个HashSet，将从中删除某些内容。假设我们从一个集合A中删除了另一个集合B中的元素。经常会发生这样的情况，即B中的许多元素根本就不存在于A中。当A和B根本不相交时，我们将分析一种特殊情况-也就是说，不需要执行任何操作。我们将编写一个简单的程序，其中从命令行设置集合的大小。为了使这些集合不完全相交，其中的一组将仅填充正数，而另一组将仅填充负数。然后，我们从第一个集合中删除第二个集合的所有元素，并使用System.currentTimeMillis()。这不是计算时间间隔的最佳方法，但是它使得将代码直接从Habr复制粘贴到Idea成为可能，并且使我们不必为JMH设置新的Maven项目。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个元素：$ java Test 100 100
Time taken: 1ms
到目前为止，一切都足够快，但是如果您增加数字会怎样？java Test 1000000 300000
Time taken: 38ms
$java Test 300000 300000
Time taken: 178131ms
您的感觉如何：现在我们等待三分钟。从直觉上看，较小的馆藏（第二种情况下为300,000件物品）的处理时间应该比处理较大馆藏（第一种情况下为一百万件物品）的时间短。事实恰恰相反。生活不是为此做准备的吧？现在是重点的秘密。实际上，它在相应的JavaDoc中以明文形式描述：实现代码确定它是否更少：集合还是集合。这是通过size对每个方法使用的方法来完成的。如果集合中的元素较少，则对集合进行迭代，并在每次迭代时检查当前元素是否在集合中。如果是，则使用removeiterator 方法将元素从集合中移除。如果事实证明集合的元素数量较小，则有必要已经绕过集合，使用removeset中的方法从集合中删除所有此类元素。
实际上，这意味着在调用时source.removeAll(removals)：- 如果集合是
removals小于source，则该方法被调用remove的HashSet，它是相当快; - 如果集合
removals大于或等于集合的大小source，则调用一个方法的removals.contains速度非常慢ArrayList。
在JDK 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;
}
JDK似乎选择了一种较差的方式来完成任务，但是由于JavaDoc已经对其进行了描述，因此没有回头路了。还是在那里？人们急忙转向Roman Yelizarov的推文，Zheka Kozlov发现了与执行者Stuart Marx一起发布在JDK 15上的相应错误。此后，斯图尔特·马克思本人也加入了讨论，并确认他确实在解决这个问题：隧道尽头有光。当然，如果您升级到Java的最新版本。发现
这个故事的结论如下：有一个值得了解的问题。该问题已得到修复，但仅为新Java的满意用户修复，您不应该真正希望它。通常，当您尝试使用Java在集合中存储大量数据时，可能会遇到各种需要准备的不直观的问题。
所以，孩子们，今天我们学到了一些新东西！作为宴会的延续，我建议您查看一些有关Roman Elizarov的报道，他帮助揭露了这个臭虫。当然，这些报告与错误本身无关，但是有很多不同的马口铁：JPoint, , 2020 . , , , .