在Java中使用HashSets时,方法retainAll的时间和空间复杂度是多少？

Question

例如,在下面的代码中:

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

Answer 1

让我们仔细阅读代码.该方法retainAll继承自AbstractCollection(至少在OpenJDK中)如下所示:

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().

重要的是该contains方法在另一方面 被调用Collection,因此复杂性取决于另一方的复杂性Collection contains.

所以,同时:

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

将是O(a.length),既然HashSet.contains又HashSet.remove是O(1)(摊销).

如果你打电话

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

然后,由于O(n) contains在Arrays.ArrayList此将成为O(a.length * b.length)-通过花费即O(n)数组复制到HashSet您实际拨打电话来retainAll要快得多.

就空间复杂性而言,不需要额外的空间(超出Iterator)retainAll,但是当你分配两个HashSet实际完全成熟的新实现时,你的调用实际上是非常昂贵的空间HashMap.

还可以注意到另外两件事:

1. 没有理由HashSet从元素中分配一个a- 一个更便宜的集合,也O(1)可以从中间删除,如LinkedList可以使用.(内存更便宜,也可以构建时间 - 不构建哈希表)
2. 在创建新的集合实例并且仅返回时,您的修改将丢失b.size().