在Java中使用HashSets时，方法retainAll的时间和空间复杂度是多少？ [英] What is the time and space complexity of method retainAll when used on HashSets in Java?

问题描述

例如在下面的代码中：

public int commonTwo(String[] a, String[] b)
{
    Set common = new HashSet<String>(Arrays.asList(a));
    common.retainAll(new HashSet<String>(Arrays.asList(b)));
    return common.size();
} 

推荐答案

让我们来看看< a href =http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7u40-b43/java/util/HashSet.java?av=f>代码。方法 retainAll 继承自 AbstractCollection 并且（至少在OpenJDK中）如下所示：

Lets take a peruse at the code. The method retainAll is inherited from AbstractCollection and (at least in OpenJDK) looks like this:

public boolean retainAll(Collection<?> c) {
    boolean modified = false;
    Iterator<E> it = iterator();
    while (it.hasNext()) {
        if (!c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}

这里有一个值得注意的地方，我们循环超过 this.iterator（）并调用 c.contains 。所以时间复杂度是 n 调用 c.contains 其中 n = this.size（ ）并且最多 n 调用 it.remove（）。

There is one big this to note here, we loop over this.iterator() and call c.contains. So the time complexity is n calls to c.contains where n = this.size() and at most n calls to it.remove().

这个重要的是在其他 上调用包含方法集合因此复杂性取决于其他集合的复杂性 包含。

This important thing is that the contains method is called on the other Collection and so the complexity is dependant upon the complexity of the other Collection contains.

所以，while：

Set<String> common = new HashSet<>(Arrays.asList(a));
common.retainAll(new HashSet<>(Arrays.asList(b)));

O（a.length） ， HashSet.contains 和 HashSet.remove 都是 O（1）（摊销）。

Would be O(a.length), as HashSet.contains and HashSet.remove are both O(1) (amortized).

如果你打电话

common.retainAll(Arrays.asList(b));

然后由于 O（n） 包含 Arrays.ArrayList 这将成为 O（a.length * b.length） - 即花费 O（n）将数组复制到 HashSet 对 retainAll 的调用要快得多。

Then due to the O(n) contains on Arrays.ArrayList this would become O(a.length * b.length) - i.e. by spending O(n) copying the array to a HashSet you actually make the call to retainAll much faster.

就空间复杂性而言，没有额外空间（超出<$ retainAll 需要c $ c> Iterator ，但是当你分配两个新的<$ c $时，你的调用实际上是非常昂贵的。 c> HashSet 实际完全成熟的实现 HashMap 。

As far as space complexity goes, no additional space (beyond the Iterator) is required by retainAll, but your invocation is actually quite expensive space-wise as you allocate two new HashSet implementations which are actually fully fledged HashMap.

还有两件事可以需要注意的是：

Two further things can be noted:

1. 没有理由从元素中分配 HashSet a - 一个更便宜的集合，也有 O（1）从中间删除，例如 LinkedList 可以使用。 （内存更便宜，也有构建时间 - 没有构建哈希表）


2. 当您创建新的集合实例并且只返回 b.size时，您的修改会丢失（）。

1. There is no reason to allocate a HashSet from the elements in a - a cheaper collection that also has O(1) remove from the middle such as an LinkedList can be used. (cheaper in memory and also build time - a hash table is not built)
2. Your modifications are being lost as you create new collection instances and only return b.size().

这篇关于在Java中使用HashSets时，方法retainAll的时间和空间复杂度是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！