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

文档没有提到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实例支持的新实例。NavigableMapTreeMap.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时必须提供a ，这就是上面代码中的属性）。TreeMapcomparator

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

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

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

编辑：

关于访问由. headSet_ O(logN)_实现为红/黑树）。TreeSetTreeSetTreeMap

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

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

问题描述

解决方案

推荐阅读