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

performance java set

2022-08-31 09:00:20

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

例如。

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

请注意，集合中的记录数会很高。

谢谢

谢卡尔

答案 1

firstSet.equals(secondSet)

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

如果需要，可以进行更细粒度的控制：

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

如果您需要获取一个集合中的元素，而不是另一个集合中的元素。
编辑：返回一个布尔值，而不是一个集合。要使用 removeAll（），您必须复制该集，然后使用它。set.removeAll(otherSet)

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

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

您提到记录数量可能很高。如果底层实现是 a，那么每条记录的提取都是及时完成的，所以你真的不能得到比这更好的了。是。HashSetO(1)TreeSetO(log n)

答案 2

如果你只是想知道集合是否相等，那么 on 的方法大致实现如下：equalsAbstractSet

    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)

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

空集为零，并且
非空集的所有元素哈希码的 XOR，

然后，您可以在每次添加或删除元素时便宜地更新集合的缓存哈希码。在这两种情况下，您只需将元素的哈希码与当前设置的哈希码进行异或。

当然，这假设元素哈希码是稳定的，而元素是集合的成员。它还假设元素类哈希码函数给出了良好的传播。这是因为当两个设置的哈希码相同时，您仍然必须回退到所有元素的比较。O(N)

你可以把这个想法更进一步...至少在理论上是这样。

警告 - 这是高度推测性的。如果你愿意，这是一个“思想实验”。

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

这给我们带来了什么？

好吧，如果我们假设没有任何秘密发生，那么任何两个不等集元素具有相同的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）。

缺点是计算元素的加密校验和非常昂贵，特别是随着位数的增加。因此，您确实需要一种有效的机制来记忆校验和。这可能会有问题。

另一个缺点是，无论概率有多小，非零的错误概率都是不可接受的。（但如果是这样的话...你如何处理宇宙射线翻转临界点的情况？或者，如果它同时在冗余系统的两个实例中翻转相同的位？