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

Question

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

虽然我了解到集合的并发实现作为并发增益(在ConcurrentLinkedQueue,ConcurrentSkipListSet,LinkedTransferQueue等中的大小为O(n))的权衡取得了一些妥协,但好消息是这在API文档中有适当的记录.

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

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

例如，TreeSet.tailSet返回元素大于或等于 的支持集部分的视图fromElement。让我很惊讶的是，调用size返回SortedSet在时间上是线性的，即O(n)。

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

“返回的集合由该集合支持，因此返回集合中的更改会反映在该集合中，反之亦然。”

由于尾部集是支持集的动态视图，因此在实践中必须动态计算其大小。另一种选择是，当对支持集进行更改时，必须调整所有现有尾部（和耳机）视图的大小。这将使支持集的更新更加昂贵，并且会带来存储管理问题。（为了更新视图大小，支持集需要引用所有现有视图集……这是潜在的隐藏内存泄漏。）

现在您确实对文档有了一定的了解。但事实上，javadoc 没有提及视图集合的复杂性。事实上，它甚至没有记录这TreeSet.size()一点O(1)！事实上，它仅记录了add,remove和contains操作的复杂性。

我想知道是否有关于许多此类操作（尤其是完全意想不到的操作）性能的详细且完整的文档？

AFAIK，不。当然，不是来自 Sun / Oracle ...