Java Collections Framework中常见方法（大小）的意外复杂性？
最近，我对一些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> { 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实现的（非常简短的）分析是对还是错，我想知道是否有关于许多此类操作的性能的详细而完整的文档，尤其是那些完全出乎意料的操作？
例如，
TreeSet.tailSet返回其元素大于或等于fromElement的支持集部分的视图。 令我惊讶的是，返回的SortedSet上的调用size在时间上是线性的，即O(n)。
对我来说这并不奇怪。 考虑来自javadoc的这句话：
“返回的集由此集支持，因此返回集中的更改将反映在此集中，反之亦然。”
由于尾部集是背景集的动态视图，因此必须在实践中动态计算其大小。 替代方案将要求在对支持集进行更改时，必须调整所有现存的尾部（和耳机）视图的大小。 这会使支持集的更新更加昂贵，并且会出现存储管理问题。 （为了更新视图大小，后台集需要引用所有现有视图集……这可能是隐藏的内存泄漏。）
现在你对文档有一点看法。 但实际上，javadocs没有说明视图集的复杂性。 事实上，它甚至没有记录TreeSet.size()是O(1) ！ 实际上，它只记录了add ， remove和contains操作的复杂性。
我想知道是否有关于许多此类操作的性能的详细而完整的文档，尤其是那些完全出乎意料的操作？
AFAIK，不。当然，不是来自Sun / Oracle ……