TreeMap 与 TreeSet
TreeMap 是按键的大小顺序保存映射的 Map,底层是红黑树;TreeSet 是把元素当作 TreeMap 的键来保存的 Set,所以它的元素同样有序且唯一。和 HashMap 相比,它们用 O(log n) 的操作成本,换来了排序遍历、邻近键查询和范围视图这些 HashMap 给不了的能力。要用好它们,关键是理解比较规则的作用:它不仅决定顺序,还决定两个键算不算重复。下文以 Java 21 为准。
1. 面试核心
先记住这几条,再读正文- TreeMap 用红黑树按键排序,查找、插入和删除都是 O(log n)。卡 · 排序规则
floor和ceiling查询包含与目标相等的键,lower和higher只找严格小于或大于目标的键。卡 · 范围删除与导航边界- TreeMap 与 TreeSet 以比较结果为 0 判断键重复,不再调用
equals,所以 TreeSet 只会保留其中一个。卡 · 比较结果与键相等 - 比较顺序与
equals一致时,TreeMap 和 TreeSet 才满足 Map、Set 的通用契约。卡 · 比较结果与键相等 subMap返回与原 Map 共享数据的范围视图,向视图插入越界的键会抛出IllegalArgumentException。卡 · 范围删除与导航边界
2. 排序规则
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 输出,因为 TreeMap 只按键的大小排列,不记录插入顺序。
需要别的顺序时,可以在构造时传入一个 Comparator,也就是比较两个对象大小的规则:
NavigableSet<User> users = new TreeSet<>(
Comparator.comparing(User::score)
.reversed()
.thenComparing(User::id)
);
这个比较器先按分数降序排,分数相同再按 id 排。加上 id 这一层很重要:如果只比较分数,同分的两个用户比较结果为 0,会被当成同一个元素,只能留下一个(第 6 节会细讲)。
比较器必须给出一个稳定的全序,即任意两个元素都能分出确定的大小。具体要满足三项约束:
- 反对称性:交换两个比较对象,结果的正负号应该相反。
- 传递性: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(键为 10、20、30):
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)找严格大于 20 的最小键,排除了 20 本身,返回键为 30 的条目。ceilingEntry(20)找不小于 20 的最小键,包含 20 本身,返回键为 20 的条目。
只需要键的话,对应有下面四种边界查询:
| 方法 | 含义 |
|---|---|
lowerKey(k) | 严格小于 k 的最大键 |
floorKey(k) | 小于等于 k 的最大键 |
ceilingKey(k) | 大于等于 k 的最小键 |
higherKey(k) | 严格大于 k 的最小键 |
这类操作适合版本生效点、价格区间、时间调度和阈值规则。比如用生效时间作键,floorEntry(now) 就能找到当前时刻已经生效的最近一个版本。找不到符合条件的键或条目时,这些方法返回 null。
5. 范围视图
范围视图是原 Map 中一段连续键的「窗口」,它不复制数据,而是和原 Map 共享条目。处理一段连续的键时,可以用 subMap 取得:
NavigableMap<Integer, String> middle =
levels.subMap(10, true, 30, false);
两个布尔参数分别表示是否包含起点和终点,所以 middle 覆盖的是 [10, 30)。通过视图修改条目会影响原 Map,原 Map 在这个范围内的变化也会反映到视图上。视图有自己的边界,向它插入范围外的键会抛出 IllegalArgumentException。
需要一份互不影响的独立数据时,要显式复制:
NavigableMap<Integer, String> snapshot = new TreeMap<>(middle);
复制后,两个 Map 各自增删条目互不影响,但条目里的键和值对象仍然是同一批对象。
headMap、tailMap 和 descendingMap 返回的也是共享视图:前两个分别取某个端点之前或之后的范围,descendingMap 按相反顺序查看整个 Map。调用范围方法时,最好用带 inclusive 参数的重载,把是否包含端点写清楚,避免选错重载。
5.1 范围删除与导航边界
因为视图和原 Map 共享数据,对视图执行 clear() 就能批量删除原 Map 里一个区间的条目,范围外的条目不受影响:
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,所以删除后只剩键 30。这时 floorKey(30) 返回 30,lowerKey(30) 找严格小于 30 的键,找不到,返回 null。
另外要分清导航方法返回的条目和范围视图。floorEntry 这类方法返回的是查询那一刻的条目快照,不连着原 Map,对它调用 setValue 会抛出 UnsupportedOperationException。要修改映射,应该调用 Map 自己的 put 等方法。
6. 比较结果与键相等
排序规则同时决定了 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 约定按 equals 判断重复。树本身仍然按比较器正常工作,但调用方如果按普通 Set 的规则去理解它,就会得到意外的结果,比如把它和一个 HashSet 比较内容时结论对不上。
元素放进集合之后,参与排序的字段不能再改。修改这些字段并不会让节点在树里移动位置,之后的查找会按新的值沿错误的路径走,可能找不到它,遍历顺序也不再正确。
7. 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
lower 和 higher 都是严格比较,排除了 20 本身,所以分别返回前驱 10 和后继 30。
既然 TreeSet 按比较结果去重,需要保留同分的不同对象时就有两种办法:在比较分数之后再比较唯一的 id,或者改用 TreeMap<SortKey, List<Value>>,把同一个排序键的对象放进一个列表里。
8. 常见问题
8.1 TreeMap 的空键与空值
使用自然顺序时,null 无法参与比较,插入 null 键会抛出 NullPointerException。自定义比较器可以用 Comparator.nullsFirst 给 null 规定一个位置;如果接口允许 null 键,还应该说明它在业务里代表什么。null 值没有问题,因为值不参与排序。
8.2 HashMap 与 TreeMap
只需要精确查找时,用平均 O(1) 的 HashMap。需要范围查询、排序遍历或前驱后继时,用基本操作 O(log n) 的 TreeMap。选定之后,键还要分别满足对应的契约:HashMap 依赖 hashCode 和 equals,TreeMap 依赖比较器。
8.3 PriorityQueue 与 TreeSet
PriorityQueue 适合反复取出优先级最高的元素,允许重复元素。它只保证队首是按比较规则最小的那个,遍历时并不是全局有序的;判断任意元素是否存在要线性查找,也没有前驱后继查询。需要有序、唯一的元素集合,或者需要邻近元素查询时,用 TreeSet。
8.4 比较器的稳定性与开销
比较器应该快速、确定、没有副作用,因为一次树操作要调用它 O(log n) 次。如果在比较器里访问数据库或远程服务,每次比较都会带上远程延迟;远程数据一变,同样两个对象的比较结果也可能变,传递性和排序稳定性就被破坏了。正确的做法是先取好比较需要的数据,放进不可变的键里,再交给 TreeMap。
9. 面试题卡片
10. 参考资料
来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明