NavigableSet/NavigableMap

1. 引言

在 Java 标准库中有许多集合，但当涉及到 范围、查找“最近”元素、优先级处理以及时间槽时，NavigableSet 和 NavigableMap 就派上用场了。

NavigableSet 扩展了 SortedSet，新增了按给定值进行相对查找（更小、更大、最近等）以及处理范围的方法。
NavigableMap 扩展了 SortedMap，提供了类似的按键查找与范围操作。

最常用的实现：TreeSet 和 TreeMap。

何时需要 NavigableSet/NavigableMap？

• 当不仅需要按排序顺序保存唯一的元素/键，还要快速找到“邻居”（例如最近的空闲时间、最高优先级的任务、数值范围）时。
• 当需要处理范围时：“X 与 Y 之间的所有元素”、“所有键大于/小于给定值”、“找到最近的键”。

2. 范围：subSet、headSet、tailSet

用于处理范围的方法

NavigableSet 和 NavigableMap 允许获取集合子集的“活的”表示（view）：

• subSet(fromElement, fromInclusive, toElement, toInclusive) —— 范围 [fromElement; toElement] 内的元素，可选择端点是否包含。
• headSet(toElement, inclusive) —— 所有小于（或小于等于）toElement 的元素。
• tailSet(fromElement, inclusive) —— 所有大于（或大于等于）fromElement 的元素。

示例：

NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30, 40, 50));

// 区间从 15（包含）到 45（不包含）
NavigableSet<Integer> sub = set.subSet(15, true, 45, false); // [20, 30, 40]
System.out.println(sub); // [20, 30, 40]

// 所有元素 <= 30
NavigableSet<Integer> head = set.headSet(30, true); // [10, 20, 30]

// 所有元素 > 20
NavigableSet<Integer> tail = set.tailSet(20, false); // [30, 40, 50]

端点是否包含：

• true —— 包含（端点计入范围）
• false —— 不包含（端点不计入）

对于 NavigableMap，方法同理，只是作用于键。

3. 邻近值操作：floor, ceiling, lower, higher；pollFirst/Last

查找最近的元素

NavigableSet：

• lower(E e) —— 最大的小于 e 的元素（严格小于）
• floor(E e) —— 最大的小于等于 e 的元素（≤）
• ceiling(E e) —— 最小的大于等于 e 的元素（≥）
• higher(E e) —— 最小的大于 e 的元素（严格大于）

示例：

NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30, 40, 50));

System.out.println(set.lower(30));   // 20
System.out.println(set.floor(30));   // 30
System.out.println(set.ceiling(25)); // 30
System.out.println(set.higher(40));  // 50

pollFirst() / pollLast()

• pollFirst() —— 删除并返回最小元素（如果为空则返回 null）
• pollLast() —— 删除并返回最大元素

示例：

System.out.println(set.pollFirst()); // 10
System.out.println(set.pollLast());  // 50
System.out.println(set);             // [20, 30, 40]

NavigableMap：具有键级别的类似方法 —— lowerKey、floorKey、ceilingKey、higherKey，以及 pollFirstEntry、pollLastEntry。

4. 视图：descendingSet/descendingMap；视图 view 及其“活性”

逆序：descendingSet/descendingMap

• descendingSet() —— 返回集合按相反顺序的视图。
• descendingMap() —— 返回 Map 按相反键顺序的视图。

示例：

NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30, 40, 50));
NavigableSet<Integer> desc = set.descendingSet();
System.out.println(desc); // [50, 40, 30, 20, 10]

重要：这不是副本，而是对同一数据集的“活的”表示（view）。一方的更改会反映到另一方。

视图（view）及其“活性”

• 方法 subSet、headSet、tailSet、descendingSet、descendingMap 返回的是 view —— “活的”原集合视图。
• 对 view 的任何更改都会反映到原集合，反之亦然。
• 如果从 subSet 中删除一个元素，它也会从原集合中消失。

示例：

NavigableSet<Integer> set = new TreeSet<>(List.of(10, 20, 30, 40, 50));
NavigableSet<Integer> sub = set.subSet(20, true, 40, true); // [20, 30, 40]
sub.remove(30);
System.out.println(set); // [10, 20, 40, 50]

注意：如果你修改原集合，导致某个元素“掉出” view 的范围，那么下次访问该 view 时会得到 ConcurrentModificationException。

5. 使用场景 NavigableSet/NavigableMap

1. 时间槽/日程安排

目标：查找最近的空闲时间槽。

NavigableSet<LocalTime> slots = new TreeSet<>(List.of(
    LocalTime.of(9, 0),
    LocalTime.of(10, 0),
    LocalTime.of(11, 0),
    LocalTime.of(14, 0)
));

LocalTime requested = LocalTime.of(10, 30);
LocalTime nextSlot = slots.ceiling(requested); // 11:00
System.out.println("最近时间：" + nextSlot);

2. 优先级（优先队列）

目标：始终快速获取优先级最高/最低的元素。

NavigableSet<Task> tasks = new TreeSet<>(Comparator.comparingInt(Task::priority));
tasks.add(new Task("邮件", 2));
tasks.add(new Task("电话", 1));
tasks.add(new Task("报告", 3));

Task next = tasks.pollFirst(); // 优先级最高的任务（1）

3. “最近的键”（例如，在 Map 中查找范围）

目标：根据键查找值范围，或最近的键。

NavigableMap<Integer, String> grades = new TreeMap<>();
grades.put(50, "不及格");
grades.put(65, "及格");
grades.put(75, "良好");
grades.put(85, "优秀");

int score = 78;
int key = grades.floorKey(score); // 75
System.out.println("评分：" + grades.get(key)); // 良好

6. 实践：小示例

示例 1：日期范围

NavigableSet<LocalDate> holidays = new TreeSet<>(List.of(
    LocalDate.of(2024, 1, 1),
    LocalDate.of(2024, 5, 1),
    LocalDate.of(2024, 12, 31)
));
LocalDate from = LocalDate.of(2024, 1, 1);
LocalDate to = LocalDate.of(2024, 6, 1);
NavigableSet<LocalDate> spring = holidays.subSet(from, true, to, false);
System.out.println(spring); // [2024-01-01, 2024-05-01]

示例 2：查找最近值

NavigableSet<Integer> numbers = new TreeSet<>(List.of(10, 20, 30, 40, 50));
int x = 25;
System.out.println("小于：" + numbers.lower(x));              // 20
System.out.println("小于或等于：" + numbers.floor(x));    // 20
System.out.println("大于或等于：" + numbers.ceiling(x));  // 30
System.out.println("大于：" + numbers.higher(x));             // 30

7. 常见错误与注意事项

错误 1：在 subSet/headSet/tailSet 中混淆是否包含端点。
务必留意 inclusive 参数——在旧版本 Java 中范围默认是排除端点的；在 NavigableSet/NavigableMap 中可以显式指定是否包含/排除端点。

错误 2：误以为 view 是副本。
View 是“活的”视图，而不是副本！对 view 的修改会反映到原集合。

错误 3：在 view 之外修改原集合导致 ConcurrentModificationException。
如果你修改原集合，导致元素“掉出” view 的范围，那么下次访问该 view 时会得到该异常。

错误 4：未提供 Comparable 或 Comparator 就使用 NavigableSet/NavigableMap。
这些集合要求元素（或键）可比较（Comparable），或提供一个 Comparator。否则会得到 ClassCastException。

错误 5：以为 pollFirst/pollLast 不会修改集合。
这些方法会删除元素！如果只需要查看，请使用 first()/last()。