TreeMap操作的时间复杂度--subMap,headMap,tailMap

Question

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

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

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

Answer 1

对于那些拥有源代码的问题非常有用,因为有足够的IDE支持,您只需浏览实现即可.在查看TreeMap的源代码时,可以看出,所有三种方法都是使用AscendingSubMap的构造函数构造一个新的map :

public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                                K toKey,   boolean toInclusive) {
    return new AscendingSubMap(this,
                               false, fromKey, fromInclusive,
                               false, toKey,   toInclusive);
}

那么除了将超级构造函数的参数传递给类之外什么都不做NavigableSubMap:

super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);

所以这三种方法都基于以下构造函数:

NavigableSubMap(TreeMap<K,V> m,
                boolean fromStart, K lo, boolean loInclusive,
                boolean toEnd,     K hi, boolean hiInclusive) {
    if (!fromStart && !toEnd) {
        if (m.compare(lo, hi) > 0)
            throw new IllegalArgumentException("fromKey > toKey");
    } else {
        if (!fromStart) // type check
            m.compare(lo, lo);
        if (!toEnd)
            m.compare(hi, hi);
    }

    this.m = m;
    this.fromStart = fromStart;
    this.lo = lo;
    this.loInclusive = loInclusive;
    this.toEnd = toEnd;
    this.hi = hi;
    this.hiInclusive = hiInclusive;
}

我在这里看到的只是compare对类型和断言检查原因的调用.因此,它应该是O(1).

您可以随时在线浏览源代码,但我真的建议您获取源文件并将它们链接到您选择的IDE.