跳到主要内容
约 9 分钟3 张卡

TreeMap 与 TreeSet

TreeMap 是按键的大小顺序保存映射的 Map,底层是红黑树;TreeSet 是把元素当作 TreeMap 的键来保存的 Set,所以它的元素同样有序且唯一。和 HashMap 相比,它们用 O(log n) 的操作成本,换来了排序遍历、邻近键查询和范围视图这些 HashMap 给不了的能力。要用好它们,关键是理解比较规则的作用:它不仅决定顺序,还决定两个键算不算重复。下文以 Java 21 为准。

1. 面试核心​

先记住这几条,再读正文

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。

查价格档位、生效版本这类问题时,要找的键往往不存在,真正需要的是离它最近的那个键。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​

8.3 PriorityQueue 与 TreeSet​

8.4 比较器的稳定性与开销​

9. 面试题卡片​

10. 参考资料​

来源:Coding 101 原文 · 免费阅读,引用请保留出处。内容使用说明