在 Java 中的 HashSet 上使用时，方法 retainAll 的时空复杂度是多少？

java big-o hashset

2022-09-02 21:57:20

例如，在下面的代码中：

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

答案 1

让我们仔细阅读代码。该方法继承自和（至少在 OpenJDK 中）如下所示：retainAllAbstractCollection

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

这里有一个很大的注意事项，我们循环并调用。因此，时间复杂度是调用 where 和最多调用。this.iterator()c.containsnc.containsn = this.size()nit.remove()

重要的是，该方法被调用在另一个方法上，因此复杂性取决于另一个方法的复杂性。containsCollectionCollectioncontains

所以，同时：

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

将是，因为和都是（摊销）。O(a.length)HashSet.containsHashSet.removeO(1)

如果您要致电

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

然后由于 on 这将成为 - 即通过花费花费将数组复制到一个你实际上使调用要快得多。O(n)containsArrays.ArrayListO(a.length * b.length)O(n)HashSetretainAll

就空间复杂性而言，不需要额外的空间（超出），但是您的调用实际上在空间方面非常昂贵，因为您分配了两个实际上已经完全成熟的新实现。IteratorretainAllHashSetHashMap

还有两件事可以注意：

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

答案 2

可以在类中找到该实现。它的实现方式如下所示：java.util.AbstractCollection

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

因此，它将迭代集合中的所有内容，并检查作为参数传递的集合是否包含此元素。common

在你的例子中，两者都是s，因此它将是O（n），因为包含应该是O（1）摊销的，并且对你的集合的迭代是O（n）。HashSetcommon

您可以进行的一项改进就是不要复制到新的，因为它将被迭代，无论如何，您可以保留一个列表。aHashSet