java - 在 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

让我们仔细阅读 the code . 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 方法在 other Collection 上调用，因此复杂性取决于另一个的复杂性集合 包含。

所以，同时:

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 on Arrays.ArrayList 这将变成 O(a.length * b .length) - 即通过花费 O(n) 将数组复制到 HashSet 您实际上调用了 retainAll更快。

就空间复杂度而言，retainAll 不需要额外的空间(Iterator 之外)，但是您的调用实际上在空间方面相当昂贵，因为您分配两个新的 HashSet 实现，它们实际上是完全成熟的 HashMap。

还有两件事需要注意:

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