Java 中 ContainsAll 的成本是多少？

Question

我今天在写代码的时候发现了containsAll()（一个List接口方法），它看起来很流畅。有谁知道这在性能/迭代方面要花多少钱？

该文档在这方面没有提供太多内容。

Answer 1

使用来源，卢克:)

编辑：正如 Bozho 指出的那样，您询问的是List.containsAll()哪些 overrides Collection.containsAll()。以下的闲话主要涉及后者：

大多数Collection类将使用from的实现containsAllAbstractCollection，其作用如下：

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

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

上面的实现containsAll至少是 O(n)，其中 n 是您传入的Collection参数中的项目数，加上所需的时间contains：

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

Answer 2

• 首先，它迭代所提供集合的每个元素
• 然后它迭代列表的所有元素，并使用当前元素与它们进行比较.equals(..)（注意：这是关于列表的，正如您在问题中指定的那样。其他集合的行为不同）

所以它是 O(n*m)，其中 n 和 m 是两个集合的大小。

public boolean containsAll(Collection<?> c) {
    Iterator<?> e = c.iterator();
    while (e.hasNext())
        if (!contains(e.next()))
        return false;
    return true;
}