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

Question

有谁知道像 subMap、headMap 这样的 TreeMap 操作的时间复杂度。尾图。

get、put等操作的时间复杂度是O(logn)。 但是 javadoc 并没有说明上述操作的复杂性。

我能想到的最坏情况复杂度为 O(n)，因为如果集合包含最后一个元素，它将遍历整个列表。 我们可以确认吗？

Answer 1

对于那些手头有源代码的问题非常有用，因为有足够的 IDE 支持，您可以简单地浏览实现。查看TreeMap的源代码时可以看出，这三种方法都是通过使用constructor of 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);
}

什么都不做，然后将参数与 super 构造函数一起传递给类 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)。

你总是可以browse the source code online ，但我真的建议获取源文件并将它们链接到您选择的 IDE。