java - 如何有效地比较 Sets？

Question

给定两个集合：如何在 Java 中有效地比较它们？

• (a) 将它们保留为Lists，对它们进行排序并比较它们。( Comparable)
• (b) 将它们保持为Sets 并比较hashCodeSet 的？

背景：

需要进行许多比较 集合很小（通常每组 < 5 个元素）。

Answer 1

比较两组的正确方法是使用equals方法。除非您证明这是导致性能问题的代码的一部分（我对此表示怀疑），否则我不会担心性能。考虑到你的集合（5 个元素）的大小，这将非常快（可能是亚毫秒）。

将它们保存为列表，对它们进行排序和比较。（可比）

肯定会更慢，因为您需要复制元素，对它们进行排序并进行比较。

将它们保持为集合并比较集合的哈希码？

如果 2 个集合相等（具有相同的内容），它们将具有相同的哈希码。倒数不正确：具有不同内容的 2 个集合可能具有相同的哈希码。另请注意，HashSet例如，哈希码是通过迭代所有元素来计算的，因此它不是自由操作。

Answer 2

平等有什么问题 ？文档指出，如果两者大小相同，则返回 true，如果containsAll()返回 true，对我来说听起来很有效。

在任何情况下，您都不应该比较哈希码来测试是否相等，两个不同的对象可能具有相同的哈希码。

更新：如评论中所述（以及 assylias 的回答），哈希码可以用作相等测试逻辑的一部分（不同的哈希码意味着不同的对象 - 但不是相反）。我上面的评论意味着单独的哈希码（通常）是不够的。

Answer 3

假设您要比较是否set1 具有完全相同的元素set2。

set1.equals(set2)并set2.equals(set1)确保两者完全相同。

Answer 4

如果你有两个HashSets，比较它们Set.equals将是 O(n)，因为只需要迭代一个集合，而另一个将由 来检查contains，这本身就是 O(1)。

请注意，对于像您这样小的集合，O(n) 和 O(n ² ) 之间的差异可以忽略不计，因此即使是最简单的方法也会产生良好的性能。