小编mar*_*rio的帖子

最近,我对一些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实现的(非常简短的)分析是对还是错,我想知道是否有关于许多此类操作的性能的详细而完整的文档,尤其是那些完全出乎意料的操作？