What is the fastest way to compare two sets in Java?

我试图优化一段比较列表元素的代码。

艾格。

public void compare(Set<Record> firstSet, Set<Record> secondSet){
for(Record firstRecord : firstSet){
for(Record secondRecord : secondSet){
// comparing logic
}
}
}

请考虑到成套记录的数量会很多。

谢谢

Shekhar

251093 次浏览
小开 
firstSet.equals(secondSet)

这实际上取决于你想在比较逻辑中做什么... ... 即如果你在一个集合中发现一个元素而不是在另一个集合中发现一个元素会发生什么？您的方法具有 void返回类型，因此我假设您将在此方法中执行必要的工作。

更细粒度的控制，如果你需要的话:

if (!firstSet.containsAll(secondSet)) {
// do something if needs be
}
if (!secondSet.containsAll(firstSet)) {
// do something if needs be
}

如果你需要得到一个集合中的元素而不是另一个集合中的元素。
编辑: set.removeAll(otherSet)返回一个布尔值，而不是一个集合。

Set one = new HashSet<>(firstSet);
Set two = new HashSet<>(secondSet);
one.removeAll(secondSet);
two.removeAll(firstSet);

如果 one和 two的内容都是空的，那么您就知道这两个集合是相等的。如果不是，那么你就得到了使集合不等的元素。

你提到记录的数量可能很多。如果底层实现是 HashSet，那么每条记录的获取都是在 O(1)时间内完成的，所以实际上不可能比这更好了。TreeSet是 O(log n)。

小开

If you simply want to know if the sets are equal, the equals method on AbstractSet is implemented roughly as below:

    public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Set))
return false;
Collection c = (Collection) o;
if (c.size() != size())
return false;
return containsAll(c);
}

Note how it optimizes the common cases where:

  • 这两个物体是一样的
  • 另一个对象根本不是一个集合
  • 这两套尺寸不同。

After that, containsAll(...) will return false as soon as it finds an element in the other set that is not also in this set. But if all elements are present in both sets, it will need to test all of them.

因此，当两个集合相等但不是相同的对象时，性能最差。该成本通常是 O(N)或 O(NlogN)，具体取决于 this.containsAll(c)的实现。

如果集合很大，并且只有很小的百分比的元素不同，那么您将获得接近最差情况的性能。

更新

如果您愿意在自定义集实现上投入时间，有一种方法可以改进“几乎相同”的情况。

其思想是，您需要预先计算并缓存整个集合的哈希值，以便在 O(1)中获取集合的当前哈希代码值。然后您可以比较两个集合的散列码作为加速度。

如何实现这样的散列码呢:

  • 对于一个空集合为零，并且
  • 一个非空集的所有元素散列码的 XOR,

然后，每次添加或删除一个元素时，都可以廉价地更新集合的缓存哈希代码。在这两种情况下，您只需使用当前 set hashcode 异或元素的 hashcode。

当然，这里假设元素散列码是稳定的，而元素是集合的成员。它还假设元素类散列码函数提供了良好的扩展。这是因为当两个集合的散列码相同时，仍然必须回到所有元素的 O(N)比较。

You could take this idea a bit further ... at least in theory.

警告 -这是高度推测性的。如果你愿意，可以称之为“思维实验”。

假设您的 set 元素类有一个方法来返回元素的加密校验和。现在通过 XORing 为元素返回的校验和来实现集合的校验和。

这能给我们带来什么？

好的，如果我们假设下面没有什么事情发生，那么任意两个不等集合元素具有相同 N 位校验和的概率是2不。并且2个不等集具有相同 N 位校验和的概率也是2不。因此，我的想法是，您可以按以下方式实现 equals:

    public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Set))
return false;
Collection c = (Collection) o;
if (c.size() != size())
return false;
return checksums.equals(c.checksums);
}

Under the assumptions above, this will only give you the wrong answer once in 2不 time. If you make N large enough (e.g. 512 bits) the probability of a wrong answer becomes negligible (e.g. roughly 10-150).

The downside is that computing the crypto checksums for elements is very expensive, especially as the number of bits increases. So you really need an effective mechanism for memoizing the checksums. And that could be problematic.

另一个缺点是，不管错误的概率有多小，也许吧的非零概率都是不可接受的。(但是如果是这样的话，你如何处理宇宙射线发生临界点的情况呢？或者在冗余系统的两个实例中同时翻转相同的位?)

小开 
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Set))
return false;


Set<String> a = this;
Set<String> b = o;
Set<String> thedifference_a_b = new HashSet<String>(a);




thedifference_a_b.removeAll(b);
if(thedifference_a_b.isEmpty() == false) return false;


Set<String> thedifference_b_a = new HashSet<String>(b);
thedifference_b_a.removeAll(a);


if(thedifference_b_a.isEmpty() == false) return false;


return true;
}
小开

番石榴 Sets中有一种方法可以帮助我们:

public static <E>  boolean equals(Set<? extends E> set1, Set<? extends E> set2){
return Sets.symmetricDifference(set1,set2).isEmpty();
}
小开

对于非常特殊的情况，有一个 O (N)解决方案:

  • the sets are both sorted
  • 都按同一顺序排序

下面的代码假设两个集合都基于可比较的记录。类似的方法可以基于比较器。

    public class SortedSetComparitor <Foo extends Comparable<Foo>>
implements Comparator<SortedSet<Foo>> {


@Override
public int compare( SortedSet<Foo> arg0, SortedSet<Foo> arg1 ) {
Iterator<Foo> otherRecords = arg1.iterator();
for (Foo thisRecord : arg0) {
// Shorter sets sort first.
if (!otherRecords.hasNext()) return 1;
int comparison = thisRecord.compareTo(otherRecords.next());
if (comparison != 0) return comparison;
}
// Shorter sets sort first
if (otherRecords.hasNext()) return -1;
else return 0;
}
}
小开

在进行比较之前，我会将第二个 Set 放在 HashMap 中。这样可以将第二个列表的搜索时间减少到 n (1)。像这样:

HashMap<Integer,Record> hm = new HashMap<Integer,Record>(secondSet.size());
int i = 0;
for(Record secondRecord : secondSet){
hm.put(i,secondRecord);
i++;
}
for(Record firstRecord : firstSet){
for(int i=0; i<secondSet.size(); i++){
//use hm for comparison
}
}
小开

If you are using Guava library it's possible to do:

        SetView<Record> added = Sets.difference(secondSet, firstSet);
SetView<Record> removed = Sets.difference(firstSet, secondSet);

And then make a conclusion based on these.

小开

我认为可以使用等于方法的方法引用。我们假设毫无疑问的对象类型有自己的比较方法。简单明了的例子就是,

Set<String> set = new HashSet<>();
set.addAll(Arrays.asList("leo","bale","hanks"));


Set<String> set2 = new HashSet<>();
set2.addAll(Arrays.asList("hanks","leo","bale"));


Predicate<Set> pred = set::equals;
boolean result = pred.test(set2);
System.out.println(result);   // true
小开

您从 https://www.mkyong.com/java/java-how-to-compare-two-sets/得到了以下解决方案

public static boolean equals(Set<?> set1, Set<?> set2){


if(set1 == null || set2 ==null){
return false;
}


if(set1.size() != set2.size()){
return false;
}


return set1.containsAll(set2);
}

或者如果您喜欢使用单个 return 语句:

public static boolean equals(Set<?> set1, Set<?> set2){


return set1 != null
&& set2 != null
&& set1.size() == set2.size()
&& set1.containsAll(set2);
}

提交答案