java - Java 中 ContainsAll 的成本是多少？

Question

我在今天的一些编码过程中发现了 containsAll()(一个 List 接口(interface)方法)，它看起来很漂亮。有谁知道这在性能/迭代方面的成本是多少？

documentation在这方面并没有提供太多。

Answer 1

使用来源，卢克 :)

编辑:正如 Bozho 指出的那样，您询问的是覆盖 Collection.containsAll() 的 List.containsAll()。下面的漫谈主要与后者有关:

大多数 Collection 类将使用 implementation of containsAll from AbstractCollection ，它是这样的:

public boolean containsAll(Collection<?> c) {
    for (Object e : c)
        if (!contains(e))
            return false;
    return true;
}

但不能保证某些实现会完全不同 - 这可能会导致更好或更差的运行时行为。

containsAll 的上述实现将至少为 O(n)，其中 n 是您传递的 Collection 参数 中的项目数in, plus 无论 contains 花费多少时间:

• 对于 HashSet/HashMap 这可能是 O(1)(最好的情况，没有冲突)，所以 containsAll 的整体运行时间仍然是 O(n)
• 对于 ArrayList，contains 将占用 O(m)，其中 m 是列表中的项目数(不是参数)，因此 的总时间>containsAll 将是 O(n*m)