java - Java Collections Framework 中常用方法(大小)的意外复杂性？

Question

最近，我对某些 Java 集合没有方法 size() 的常量时间操作感到惊讶。

虽然我了解到集合的并发实现会做出一些妥协，作为并发增益的权衡(ConcurrentLinkedQueue、ConcurrentSkipListSet、LinkedTransferQueue 等中的大小为 O(n))，但好消息是 API 文档中对此进行了适当记录。

我关心的是方法大小对某些集合方法返回的 View 的性能。例如，TreeSet.tailSet返回其元素大于或等于 fromElement 的支持集部分的 View 。令我非常惊讶的是，对返回的 SortedSet 调用大小在时间上是线性的，即 O(n)。至少这是我设法从 OpenJDK 的源代码中挖掘出来的: 在 TreeSet 中实现为 TreeMap 的包装器，在 TreeMap 中，有 EntrySetView 类，其大小方法如下:

abstract class EntrySetView extends AbstractSet<Map.Entry<K,V>> {
    private transient int size = -1, sizeModCount;

    public int size() {
        if (fromStart && toEnd)
            return m.size();
        if (size == -1 || sizeModCount != m.modCount) {
            sizeModCount = m.modCount;
            size = 0;
            Iterator i = iterator();
            while (i.hasNext()) {
                size++;
                i.next();
            }
        }
        return size;
    }

    ....
}

这意味着第一次调用的大小是 O(n)，然后只要不修改后备映射，它就会被缓存。我无法在 API 文档中找到这个事实。更有效的实现是 O(log n)，在子树大小的缓存中进行内存权衡。由于进行此类权衡是为了避免代码重复(TreeSet 作为 TreeMap 的包装器)，我看不出有什么理由不应该出于性能原因做出它们。

不管我对 TreeSet 的 OpenJDK 实现的(非常简短的)分析是对是错，我想知道是否有关于许多此类操作的性能的详细而完整的文档，尤其是那些完全出乎意料的操作？

Answer 1

For example, TreeSet.tailSet returns a view of the portion of backing set whose elements are greater than or equal to fromElement. What surprised me a lot is that calling size on returned SortedSet is linear in time, that is O(n).

对我来说这并不奇怪。考虑 javadoc 中的这句话:

"The returned set is backed by this set, so changes in the returned set are reflected in this set, and vice-versa."

由于尾​​集是支持集的动态 View ，因此在实践中必须动态计算其大小。替代方案要求当对支持集进行更改时，它必须调整所有现存尾部(和耳机) View 的大小。这将使对支持集的更新更加昂贵，并且会带来存储管理问题。 (为了更新 View 大小，后备集需要引用所有现有 View 集……这是潜在的隐藏内存泄漏。)

现在您对文档有了一定的了解。但实际上，javadocs 没有提到 View 集合的复杂性。而且，事实上，它甚至没有记录 TreeSet.size() 是 O(1)!事实上，它只记录了add、remove 和contains 操作的复杂性。

---

I would like to know is there a detailed and complete documentation on performance of many such operations especially ones which are completely unexpected?

据我所知，不。当然，不是来自 Sun/Oracle ...