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

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