Java集合框架中常用方法（size）的意外复杂性？

Question

近期，我惊讶地发现一些Java集合的方法size()并非具有恒定时间操作。

尽管我了解到并发集合实现在获得并发性方面做了一些妥协（如在ConcurrentLinkedQueue、ConcurrentSkipListSet、LinkedTransferQueue等中使size为O(n)），但好消息是这在API文档中得到了充分说明。

令我担忧的是，某些集合方法返回的视图上调用size方法的性能。例如，TreeSet.tailSet 返回一个由其元素大于或等于fromElement的部分组成的视图。令我感到惊讶的是，在返回的SortedSet上调用size方法是线性的，即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实现的（非常简短）分析是否正确，我想知道是否有关于许多此类操作的性能的详细完整文档，特别是那些完全意外的操作？

- mario

---

我认为Javadocs包含了那些信息。 - Thilo

有趣的问题（+1）。我无法在文档方面提供帮助（我没有看到明确记录的复杂性）。然而，我个人认为tailSet()的行为完全符合直觉。我认为期望每个人都为了边缘用例的更好性能而支付内存代价会更令人惊讶。 - NPE

@NPE 你是否同意，我们因为每个Set都被实现为Map的包装器而承受的内存惩罚，只是为了让JDK开发人员不必重复实现相同的功能？ :) 我认为我已经很清楚地表明了我的问题是关于文档而不是性能本身。令我困惑的是，TreeMap.size是O(1)，TreeMap.tailSet是O(log N)，但是对于TreeMap.tailSet().size()，却没有任何信息，我知道它可以是O(log n)或O(n)。 - mario

Answer 1

例如，TreeSet.tailSet返回一个由元素大于或等于fromElement的后备集合构成的视图。 令我惊奇的是，在返回的SortedSet上调用size的时间是线性的，也就是O(n)。

对我而言，这不足为奇。请看以下来自javadoc的句子：

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

由于尾部集是支持集的动态视图，因此实际上必须动态计算其大小。另一种方法需要在对支持集进行更改时调整所有现有的tailset（和headset）视图的大小。这将使得对支持集的更新更加昂贵，并且还会出现存储管理问题。（为了更新视图大小，支持集需要引用所有现有的视图集...这是一个潜在的隐藏内存泄漏。）

现在你对文档确实有点意见。但实际上，javadoc没有关于视图集合复杂度的任何说明。事实上，它甚至没有记录TreeSet.size()的复杂度是O(1)！实际上，它只记录了add、remove和contains操作的复杂度。

我想知道是否有关于许多这样的操作性能的详细完整文档，特别是那些完全意料之外的操作？

据我所知，没有。当然，Sun / Oracle也没有...

- Stephen C

---

我确实理解所有这些，但事实上，有不同的方法，它们都有不同的权衡取舍，并且没有记录哪种方法被选择。 - mario

@mario - 是的，但我不是抱怨的正确对象。（而且，从我的角度来看...你正在抱怨。） - Stephen C