Java集合中元素比较的性能表现

Question

问题：

给定两个Collection<?>，检查它们是否包含相同的元素。

• 假设集合的实际实现是未知的
• 假设元素不按相同顺序出现
• 假设同一集合中没有元素出现两次

解决方案1：

boolean equals = c1.containsAll(c2) && c2.containsAll(c1);

解决方案 2：

boolean equals = new HashSet<?>(c1).equals(new HashSet<?>(c2));

我认为解决方案2比解决方案1更有效率（O(n) vs O(n^2)）。

我对吗？还是我漏掉了什么？

- Stefan Winkler

Answer 1

这些的 Big O 复杂度是正确的，解决方案 1 每次迭代另一个列表时都需要迭代一个列表（O（n）），这样是 O（n^2）。 解决方案 2 需要两个 O（n） 复制操作，并迭代其中一个集合（O（n）），在另一个集合上做 O（1）的.contains() 检查。 总起来说，那只是 O（n）。

但根据限制条件，您可以做得更好（不是渐近式地更好，而是更好的实现）。

- 因为我们假设没有重复元素，所以没有必要进行第二个 .containsAll() 检查。 只需检查它们是否具有相同的大小（可能是 O(n)，但仍然比复制 O(n^2) 的检查好），然后执行 .containsAll()。 - 没有必要将 c2 转换为 Set，因为它将被迭代; 只需转换 c1 并使用 .containsAll()。 - 您可以使用 instanceof Set 来测试 c1 或 c2 是否已经是 Set，并使用该对象的 .containsAll() 方法; 即使另一个对象不是 set，这将在 O(n) 时间内运行，并避免了解决方案 2 中的复制开销。

- dimo414

---

谢谢！我没有考虑到大小比较。好答案。 - Stefan Winkler

事实上，Truth并没有针对这种情况进行优化，而且实际上可能表现得更差。Truth是一个测试库，不应该在性能关键的代码中使用。（这是来自与Truth维护者同处一室的发言。） - Louis Wasserman

@LouisWasserman 感谢您的见解，我已删除了Truth插件。 我曾认为Truth流利的设计会使这些优化变得容易，但显然我不应该做出这样的假设。 由于Truth不能假定任意集合不包含重复元素，因此它无法安全地将它们整合到集合中。 - dimo414

@user902383，我不明白你的观点。即使它们包含相同的元素，一个List并不等于一个Set。如果你想比较两个Collection的内容，你必须使用.containsAll()或者在使用.equals()之前确保它们是相同的集合类型。 - dimo414

Answer 2

正如dimo414所说，一般来说是可以的。但你总是可以做得更好（不是渐进式地更好，只是更快）。这变得更加复杂：

if (c1.size() != c2.size()) {
    return false;
} else if (c1 instanceof Set) {
    return c1.containsAll(c2);
} else if (c2 instanceof Set) {
    return c2.containsAll(c1);
} else {
    return new HashSet<>(c1).containsAll(c2);
}

有一些集合的size方法执行速度较慢，您可能需要特殊处理...

- maaartinus