Java Collections Framework中常用方法（大小）的意外复杂性？

data-structures collections java size complexity-theory

2022-09-04 04:43:32

最近，我对一些Java集合没有方法size（）的恒定时间操作这一事实感到惊讶。

虽然我了解到集合的并发实现做出了一些妥协，作为并发收益的权衡（在ConcurrentLinkedQueue，ConcurrentSkipListSet，LinkedTransferQueue等中，大小为O（n），但好消息是这在API文档中得到了适当的记录。

我关心的是某些集合的方法返回的视图上方法大小的性能。例如，TreeSet.tailSet 返回其元素大于或等于 fromElement 的支持集部分的视图。令我非常惊讶的是，返回的 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;
    }

    ....
}

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

不考虑我对TreeSet的OpenJDK实现的（非常简短）分析的正确或错误，我想知道是否有关于许多此类操作性能的详细而完整的文档，特别是那些完全出乎意料的操作？

答案 1

例如，返回元素大于或等于的支持集部分的视图。令我非常惊讶的是，对返回的调用在时间上是线性的，也就是说。TreeSet.tailSetfromElementsizeSortedSetO(n)

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

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

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

现在，您确实有关于文档的观点。但实际上，javadocs并没有说明视图集合的复杂性。而且，事实上，它甚至没有记录这是！实际上，它只记录了和操作的复杂性。TreeSet.size()O(1)addremovecontains

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

阿法伊克，没有。当然，不是来自太阳/甲骨文...

答案 2