java - TreeSet 集合的 higher() 方法在降序模式下的行为？

Question

任何人都可以描述 TreeSet 集合的 higher() 方法在按降序排序时的这种行为:

代码:

NavigableSet<Integer> set = new TreeSet<>();

set.add(10);
set.add(22);
set.add(34);
set.add(40);
set.add(45);
set.add(56);
set.add(77);
set.add(79);
set.add(84);
set.add(99);

set = set.descendingSet();

System.out.printf("%n Higher than 40 : %s", set.higher(40));

它返回以下结果即。

Higher than 40 : 34

现在，尽管集合按降序排序，higher(40) 方法是否应该返回大于 40(当然是 45)的值？

Answer 1

• set.higher(T) : 函数返回此集合中严格大于给定元素的最小元素，如果没有这样的元素，则返回 null。

• set.descendingSet() : 返回此 set 中包含的元素的反向顺序 view。

到底发生了什么？

TreeSet 本质上使用 TreeMap 来实现其功能。对 descendingSet() 的调用最终会调用 TreeMap 实例上的 descendingMap() 函数，从以下源代码可以明显看出:

public NavigableSet<E> descendingSet() {
        return new TreeSet<>(m.descendingMap());
    }

每个 TreeMap 通常维护两个 View :

• 普通排序 View :使用通用比较器对其元素进行排序
• 后代 map View :使用比较器，它对升序比较器进行反向排序。它使用 Collections.reverseOrder(m.comparator()) 返回这个降序比较器。

我称这些 view 是因为 TreeMap 实际上并没有用它的 entries(key, value) 创建另一个后代 Map，而是它维护两个比较器，相互施加相反的顺序。当 descendantMap() 被调用时，后代 View 第一次被创建。对该函数的任何后续调用都将返回相同的后代 map View 。

注意: set.descendingSet().descendingSet() 返回 set 的 View ，本质上等同于 set。因为第一次调用的结果比较器被 descendingSet() 的第二次调用再次反转(实际上是在内部执行 map.descendingMap() ).

继续您的示例:

System.out.printf("%n Higher than 40 : %s", set.higher(40)); // prints 45
set = set.descendingSet(); // create a reverse ordering 
                           //comparator as described above 
System.out.printf("%n Higher than 40 : %s", set.higher(40)); // prints 34
set = set.descendingSet(); // again trying to get descending set!
System.out.printf("%n Higher than 40 : %s", set.higher(40))  // prints 45