在Java中比较两个集合最快的方法是什么?

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) 返回布尔值,而不是集合。要使用removeAll(),必须先复制集合,然后再使用它。

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)

equals 方法 AbstractSet 大致如下:

    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);
    }

请注意它是如何优化常见情况的:

• 这两个物体是一样的
• 两套的尺寸不同。

之后, containsAll(...) 会回来的 false 一旦它在另一个集合中找到一个不在这个集合中的元素。但是如果两个集合中都存在所有元素,则需要测试所有元素。

因此,当两个集合相等但不是相同的对象时,就会出现最差的性能。这种成本通常是 O(N) 或 O(NlogN) this.containsAll(c) .

更新

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

其思想是,您需要预先计算并缓存整个集合的哈希,这样就可以获得集合的当前哈希代码值 O(1) . 然后您可以比较两个集合的hashcode作为加速。

• 空集合为零,并且

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

O(N)

你可以把这个想法再进一步。。。至少在理论上。

警告

假设您的set element类有一个方法来返回元素的加密校验和。现在,通过对元素返回的校验和进行异或运算来实现集合的校验和。

这给我们买了什么?

好吧,如果我们假设没有秘密发生,任何两个不相等的集合元素有相同的N位校验和的概率是2 ^-N . 两个不等集具有相同N位校验和的概率也是2 ^-N 等于

    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);
    }

^-N 时间。如果N足够大(例如512位),错误答案的概率就可以忽略不计(例如大约10 ).

缺点是计算元素的加密校验和非常昂贵,特别是随着比特数的增加。所以你真的需要一个有效的机制来记忆校验和。这可能会有问题。

可能是 不管可能性有多小都是不可接受的。(但如果是这样的话。。。如何处理宇宙射线翻转临界点的情况?或者如果它在冗余系统的两个实例中同时翻转相同的位?)

番石榴有一种方法 Sets 这有助于:

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

您可以从 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);
}

有一个O(N)解决方案,适用于非常具体的情况:

• 这两个集合都是排序的

    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;
        }
    }

如果你正在使用 Guava 图书馆可以:

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

并在此基础上得出结论。

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
    }
}

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;
    }

我认为可以使用equals方法引用方法。我们假设没有疑问的对象类型有自己的比较方法。这里有一个简单明了的例子,

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