java - Java 类 TreeSet 中的 Java 方法 headSet 和 tailSet 是否在 log(N) 时间内工作？

Question

JavaDoc 中写道，TreeSet 的基本操作在 log(N) 时间内完成，其中 N 是集合的大小。在我看来，如果集合足够大，headSet 和 tailSet 方法应该通过二进制搜索之类的方法找到它们正在计算的 View 的开始，但 JavaDoc 对此保持沉默。

Answer 1

文档没有提及headSet 和tailSet 的时间复杂度。他们只说:

Returns a view of the portion of this set whose elements are strictly less than toElement. The returned set is backed by this set, so changes in the returned set are reflected in this set, and vice-versa. The returned set supports all optional set operations that this set supports.

(我强调查看)。而view确实是最重要的部分。创建 View 始终是一个 O(1) 操作，最坏的情况是，因为只创建了包装类。不执行键搜索，只是类型检查，实际上也没有触发其他操作。

这是 TreeSet.headSet(E toElement) 代码:

public SortedSet<E> headSet(E toElement) {
    return headSet(toElement, false);
}

这里是 TreeSet.headSet(E toElement, boolean inclusive) 代码:

public NavigableSet<E> headSet(E toElement, boolean inclusive) {
    return new TreeSet<>(m.headMap(toElement, inclusive));
}

如您所知，TreeSet 由 TreeMap 实例支持。这就是 m 属性的实际含义。所以上面的操作委托(delegate)给 TreeMap.headMap(E toElement, boolean inclusive) 方法，然后创建一个由 NavigableMap 支持的新的 TreeSet 实例TreeMap.headMap(E toElement, boolean inclusive) 返回的实例。

首先，让我们看看TreeSet 构造函数:

TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

如您所见，这只是一项作业。

然后，让我们深入研究TreeMap.headMap(E toElement, boolean inclusive)方法的代码:

public NavigableMap<K,V> headMap(K toKey, boolean inclusive) {
    return new AscendingSubMap<>(this,
                                 true,  null,  true,
                                 false, toKey, inclusive);
}

这只是创建并返回 AscendingSubMap 静态嵌套类的一个实例。这是 AscendingSubMap 构造函数的代码:

AscendingSubMap(TreeMap<K,V> m,
                boolean fromStart, K lo, boolean loInclusive,
                boolean toEnd,     K hi, boolean hiInclusive) {
    super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);
}

这只是委托(delegate)给父类(super class)的构造函数(AscendingSubMap 的父类(super class)是 NavigableSubMap 静态嵌套抽象类)。这是 NavigableSubMap 构造函数的代码:

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;
}

如您所见，这只是检查参数的正确性并将它们分配给属性。

此处 m 是封闭的 TreeMap 实例(请记住 NavigableSubMap 是静态嵌套抽象类)。 TreeMap.compare(Object k1, Object k2)方法如下:

final int compare(Object k1, Object k2) {
    return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}

这个方法只是适本地比较它的参数，这里它只是用来检查子图的边界。 (请记住，TreeMap 键可以是 Comparable 也可以不是。如果不是，则在构造 时必须提供 Comparator TreeMap 实例，这就是上面代码中的 comparator 属性)。

这就是调用 headSet 方法时所做的全部工作。 tailSet 遵循相同的模式(只是最终子图的边界不同)。

因此，作为结论，headSet 和 tailSet 实际上是 O(1) 最坏情况。

注意:我已经检查了 JDK 8 v1.8.0_181 和 openjdk version "11"2018-09-25 版本的代码。我很确定中间版本也没有更改。

---

编辑:

关于访问 headSet 返回的 View 的第一个元素的时间复杂度，即如果要迭代它，实现需要执行 O(logN)到达 TreeSet 最左边的叶子的操作(毕竟，TreeSet 由 TreeMap 支持，后者又实现为红色/黑树)。

迭代 tailSet 返回的 Collection View 具有相同的时间复杂度:O(logN)。这是因为实现需要对值更接近提供的下限的节点执行搜索，并且此搜索也是O(logN)。