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

Question

我正在尝试优化一段比较列表元素的代码.

例如.

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

请注意,套装中的记录数量会很高.

谢谢

谢卡尔

Answer 1

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都是空的,那么你知道这两组都是平等的.如果没有,那么你就有了使这些集不相等的元素.

您提到记录数可能很高.如果底层实现是a,HashSet那么每个记录的提取都是O(1)及时完成的,所以你不可能真的比这更好.TreeSet是O(log n).

Answer 2

如果您只是想知道集合是否相等,则equals方法on 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).

如果集合很大并且只有很小一部分元素不同,那么你会得到接近最差的情况.

UPDATE

如果您愿意将时间投入到自定义集实现中,那么有一种方法可以改善"几乎相同"的情况.

这个想法是你需要预先计算和缓存整个集合的哈希值,这样你就可以得到集合的当前哈希码值O(1).然后,您可以将两组的哈希码作为加速度进行比较.

你怎么能实现这样的哈希码？好吧,如果设置的哈希码是:

• 空集合为零,和
• 非空集的所有元素哈希码的XOR,

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

当然,这假设元素哈希码是稳定的,而元素是集合的成员.它还假设元素类hashcode函数给出了良好的扩展.这是因为当两个设置的哈希码相同时,您仍然需要回退到O(N)所有元素的比较.

你可以进一步理解这个想法......至少在理论上如此.

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

这给我们带来了什么？

好吧,如果我们假设没有任何事情发生,那么任何两个不相等的集合元素具有相同的N比特校验和的概率是2- ^N.并且概率2不等集具有相同的N位校验和也是2- ^N.所以我的想法是你可以实现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);
    }

根据上述假设,这只会在2- ^N时间内给出错误答案.如果你使N足够大(例如512位),则错误答案的概率可以忽略不计(例如大约10 ^-150).

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

Answer 3

Guava中有一种方法Sets可以帮助:

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

Answer 4

对于非常特殊的情况，有一个 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;
        }
    }

Answer 5

如果您正在使用Guava库，可以执行以下操作：

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

然后根据这些做出结论。

Answer 6

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