约 8 分钟3 张卡

TreeMap 与 TreeSet

TreeMap 按键的顺序保存映射，TreeSet 基于 TreeMap 保存有序且唯一的元素。本文以 Java 21 为准，从排序规则和红黑树入手，再讲邻近键查询与范围视图。最后说明比较器怎样影响元素去重，以及使用时的边界。

1. 面试核心

先记住这几条，再读正文

有序存储。 TreeMap 用红黑树按键排序，查找、插入和删除的时间复杂度都是 O(log n)。卡 · 排序规则
边界查询。 floor 和 ceiling 查询包含与目标相等的键，lower 和 higher 只查找严格小于或大于目标的键。卡 · 范围删除与导航边界
比较判重。 TreeMap 与 TreeSet 都以比较结果为 0 判断键重复，TreeSet 因此只保留一个元素。卡 · 比较结果与键相等
相等契约。 TreeMap 和 TreeSet 的比较顺序与 equals 一致时，才能满足 Map、Set 的通用契约。卡 · 比较结果与键相等
范围视图。 subMap 返回与原 Map 共享数据的范围视图，向视图插入越界键会抛出 IllegalArgumentException。卡 · 范围删除与导航边界

2. 排序规则

必会卡 · TreeMap 的底层结构和适用场景是什么

TreeMap 需要先确定键的大小关系，才能把节点放在正确的位置。自然顺序由键的 Comparable 实现定义，比如整数按数值从小到大排列。

下面先看自然顺序的结果：

NavigableMap<Integer, String> levels = new TreeMap<>();
levels.put(30, "high");
levels.put(10, "low");
levels.put(20, "medium");

System.out.println(levels.keySet()); // [10, 20, 30]

虽然插入顺序是 30、10、20，遍历键时仍按 10、20、30 输出。需要自定义顺序时，可以传入 Comparator，也就是比较两个对象大小的规则：

NavigableSet<User> users = new TreeSet<>(
    Comparator.comparing(User::score)
        .reversed()
        .thenComparing(User::id)
);

上例先按分数降序排列，同分时再按 id 排列。这样，不同用户即使分数相同，也能同时保留。

比较器要给出稳定的全序，也就是任意两个元素都有确定的大小关系。还需要满足以下三项约束：

反对称性：交换两个比较对象后，结果的正负号应相反。
传递性：若 A 小于 B、B 小于 C，那么 A 也应小于 C。
相等组一致性：若 A 与 B 比较为 0，它们各自与 C 比较时，结果的正负号应一致。

3. 红黑树

TreeMap 需要在持续增删后，仍能沿树快速找到键。OpenJDK 21 使用红黑树，这是一种用颜色约束控制树高的二叉搜索树。增删后，它会通过变色和旋转调整局部结构，使树高保持 O(log n)。

因此，常用操作具有以下复杂度：

get、put、remove 是 O(log n)。
最小、最大、前驱、后继是 O(log n) 或沿已知节点取得。
有序遍历是 O(n)。

这里的复杂度把单次比较视为常数成本。前驱和后继指排序中相邻的较小键与较大键，TreeMap 可以直接查询。

如果只需精确查找，HashMap 的平均时间复杂度是 O(1)。需要排序、范围或前驱后继时，再选择 TreeMap。

4. NavigableMap 边界查询

查询价格档位或生效版本时，目标键未必恰好存在。NavigableMap 在有序映射上提供邻近键查询，TreeMap 实现了这个接口。

沿用前面的 levels，可以这样查找：

Map.Entry<Integer, String> atMost = levels.floorEntry(25);   // 20
Map.Entry<Integer, String> above = levels.higherEntry(20);   // 30
Map.Entry<Integer, String> atLeast = levels.ceilingEntry(20); // 20

对照这三次调用，可以看到边界是否包含相等键的区别：

floorEntry(25) 找到不大于 25 的最近条目，所以返回键为 20 的条目。
higherEntry(20) 排除相等键，返回键为 30 的条目。
ceilingEntry(20) 包含相等键，所以返回键为 20 的条目。

只需要键时，可以使用下表中的四种边界查询：

方法	含义
`lowerKey(k)`	严格小于 k 的最大键
`floorKey(k)`	小于等于 k 的最大键
`ceilingKey(k)`	大于等于 k 的最小键
`higherKey(k)`	严格大于 k 的最小键

这类操作适合版本生效点、价格区间、时间调度和阈值规则。比如，用生效时间作键，floorEntry 可以找到指定时刻已生效的最近版本。找不到符合条件的键或条目时，这些方法返回 null。

5. 范围视图

需要处理一段连续键时，可以用 subMap 取得范围视图。视图让调用方操作原 Map 的一部分，并与原 Map 共享数据：

NavigableMap<Integer, String> middle =
    levels.subMap(10, true, 30, false);

这里的两个布尔参数决定是否包含端点，所以视图包含 [10, 30)。通过视图修改条目会影响原 Map，原 Map 在此范围内的更新也会反映到视图。向视图插入范围外的键，会抛出 IllegalArgumentException。

需要独立快照时复制：

NavigableMap<Integer, String> snapshot = new TreeMap<>(middle);

复制后，两个 Map 的条目增删互相独立，条目中的键和值对象仍被复用。

headMap、tailMap 与 descendingMap 也返回共享视图。前两者分别选取某个端点之前或之后的范围，后者按相反顺序查看整个 Map。调用范围方法时，可用 inclusive 参数明确是否包含端点，避免选错重载。

6. 比较结果与键相等

必会卡 · TreeMap 的底层结构和适用场景是什么卡 · TreeSet 中两个不相等对象为什么可能只能保留一个

排序规则也决定了 TreeMap 和 TreeSet 怎样去重。比较结果为 0 时，它们就视为同一个键，不会再用 equals 区分：

Comparator<User> byNameIgnoreCase =
    Comparator.comparing(User::name, String.CASE_INSENSITIVE_ORDER);

Set<User> users = new TreeSet<>(byNameIgnoreCase);

上例忽略姓名的大小写，所以姓名为 Alice 与 alice 的用户比较结果为 0，集合只保留一个。如果两个用户的 equals 返回 false，这种去重就与 Set 的通用契约冲突。树仍会按比较器工作，但调用方按其他 Set 的规则使用它时，容易得到意外结果。

元素加入集合后，用于排序的字段应保持稳定。修改这些字段时，树中的节点仍留在原位置。因此，之后的查找会沿错误的路径进行，遍历结果也会偏离预期顺序。

7. TreeSet

必会卡 · TreeSet 中两个不相等对象为什么可能只能保留一个

只需要保存元素、无需为元素关联值时，可以使用 TreeSet。它把元素作为底层 TreeMap 的键，并通过 NavigableSet 提供范围和邻近元素操作：

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

Integer previous = scores.lower(20); // 10
Integer next = scores.higher(20);    // 30

示例中，20 的前驱是 10，后继是 30，两次查询都排除了 20 本身。

需要保留同分对象时，可以在比较分数后继续比较唯一 id。也可以用 TreeMap<SortKey, List<Value>> 表达分组，把同一个排序键对应的对象放进列表。

8. 范围删除与导航边界

必会卡 · subMap.clear 会修改原 Map 吗，floorKey 与 lowerKey 有什么区别？

共享视图也适合批量删除区间条目。对 subMap(10, true, 30, false) 执行 clear()，会删除原 Map 中 [10, 30) 内的条目。范围外的条目保持原状：

var values = new TreeMap<Integer, String>();
values.put(10, "A");
values.put(20, "B");
values.put(30, "C");
values.subMap(10, true, 30, false).clear();
System.out.println(values.keySet()); // [30]

删除后只剩键 30，所以 floorKey(30) 返回 30，lowerKey(30) 返回 null。

查询导航条目时，还要区分条目与范围视图。TreeMap 的 floorEntry 等方法返回查询时的条目快照。这类条目的 setValue 会抛出 UnsupportedOperationException。需要修改映射时，应调用 Map 的 put 等方法。

9. 常见问题

9.1 TreeMap 的空键与空值

自然顺序无法比较 null，因此插入 null 键会抛出 NullPointerException。自定义比较器可用 Comparator.nullsFirst 定义 null 的顺序。如果接口允许 null 键，还应说明它在业务中代表什么。TreeMap 允许 null 值，因为值并未参与键的排序。