Временная сложность операций TreeMap — subMap, headMap, tailMap

Для этих вопросов очень полезно иметь под рукой исходный код, так как при достаточной поддержке IDE вы можете просто просмотреть реализацию. При просмотре исходного кода TreeMap видно, что все три метода создают новую карту, используя конструктор AscendingSubMap:

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. выбора.

Мне удалось просмотреть исходный код TreeMap, чтобы получить подробную реализацию.

Если вы подробно расскажете об исходном коде о том, как они на самом деле получают подкарту, это что-то вроде этого...

Если вы видите метод размера NavigableSubMap

  public int size() {
        return (fromStart && toEnd) ? m.size() : entrySet().size();
    }

Реализация entrySet() при множественных вызовах final вызывает функцию getCeilingEntry()

final Entry<K,V> getCeilingEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp < 0) {
            if (p.left != null)
                p = p.left;
            else
                return p;
        } else if (cmp > 0) {
            if (p.right != null) {
                p = p.right;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } else
            return p;
    }
    return null;
}

ТАК я думаю, чтобы получить реальную карту из созданной подкарты; временная сложность больше O(1).