相关疑难解决方法(0)

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

有没有人知道TreeMap操作的时间复杂度 - 例如 - subMap,headMap.的tailMap.

像get,put这样的操作的时间复杂度是O(logn).但javadoc并没有说明上述操作的复杂性.

最糟糕的情况复杂性我可以想到O(n),因为如果集合包含最后一个元素,它将遍历整个列表.我们可以证实吗？

我想知道size()TreeSet的部分视图的时间复杂度是多少.

假设我正在添加随机数来设置(我不关心重复):

    final TreeSet<Integer> tree = new TreeSet<Integer>();
    final Random r = new Random();
    final int N = 1000;
    for ( int i = 0; i < N; i++ ) {
        tree.add( r.nextInt() );
    }

现在我正在考虑size()调用的复杂性:

    final int M = 100;
    for ( int i = 0; i < M; i++ ) {
        final int f = r.nextInt();
        final int t = r.nextInt();
        System.out.println( tree.headSet( t ).size() );
        System.out.println( tree.tailSet( f ).size() );
        if ( f …