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

Question

在JavaDoc中编写的是,TreeSet上的基本操作在log(N)时间内工作,其中N是集合的大小.在我看来,如果集合足够大,headSet和tailSet方法应该通过二进制搜索等方式找到他们正在计算的视图的开头,但JavaDoc对此保持沉默.

Answer 1

文档没有提及headSetandtailSet的时间复杂度。他们只说：

返回此集合中元素严格小于 toElement 的部分的视图。返回的集合由该集合支持，因此返回集合中的更改会反映在该集合中，反之亦然。返回的集合支持该集合支持的所有可选集合操作。

（我强调的是观点）。而视图确实是最重要的部分。创建视图总是一个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由NavigableMap返回的实例支持的新实例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);
}

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

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

所以，作为一个结论，headSet并且tailSet实际上是O(1)最坏的情况。

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

编辑：

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

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