集合Java类树集合中的Java方法headSet和tailSet在日志（N）时间内工作吗？

Question

JavaDoc中写到，树集上的基本操作在log（N）时间内工作，其中N是集合的大小。在我看来，如果集合足够大，headSet和tailSet方法应该通过类似二进制搜索的方式找到正在计算的视图的开始，但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.

（我强调的是查看）。而视图确实是最重要的部分。在最坏的情况下，创建视图总是一个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属性的实际含义。因此，上面的操作将委托给TreeMap.headMap(E toElement, boolean inclusive)方法，然后创建一个新的TreeSet实例，该实例由TreeMap.headMap(E toElement, boolean inclusive)返回的NavigableMap实例支持

首先，让我们看看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);
}

这只是委托给超类的构造函数（AscendingSubMap的超类是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也可以不是。如果不是，则在构造TreeMap实例时必须提供Comparator，这就是上面代码中的comparator属性）

这就是调用headSet方法时所做的一切tailSet遵循相同的模式（只是最终子贴图的边界不同）

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

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

---

编辑：

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

迭代tailSet返回的集合视图具有相同的时间复杂性：O(logN)。这是因为实现需要对其值更接近所提供的下限的节点执行搜索，并且此搜索也是O(logN)