java 集合中元素比较的性能

Question

问题：

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

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

解决方案一：

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

方案二：

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

我假设 解决方案 2 比 解决方案 1[=] 更有效 (O(n)) 37=] (O(n^2)).

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

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()方法;即使另一个对象不是集合，这也会在 O (n) 时间内运行，并且避免了解决方案 2 的复制开销。

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，您可能需要特别处理...

java 集合中元素比较的性能

Performance of element-compare in java collections

java

collections

performance