JTechVault

Appearance

TreeMap：红黑树上的排序 Map ​

TreeMap 是什么 ​

TreeMap 是基于红黑树的 Map 实现，核心能力是：按键排序存储，按 key 快速查找。

java
// HashMap：key 无序
Map<String, Integer> hash = new HashMap<>();
hash.put("z", 1); hash.put("a", 2); hash.put("m", 3);
System.out.println(hash); // 无序，如 {z=1, a=2, m=3}

// TreeMap：key 有序（字典序）
Map<String, Integer> tree = new TreeMap<>();
tree.put("z", 1); tree.put("a", 2); tree.put("m", 3);
System.out.println(tree); // {a=2, m=3, z=1}

红黑树：TreeMap 的底座 ​

为什么不用普通 BST ​

普通二叉搜索树（BST）在极端情况下会退化成链表：

已排序数据插入 BST：
  1
   \
    2
     \
      3
       \
        4       ← 退化成链表，查找 O(n)

红黑树（自动平衡）：
      2（黑）
     / \
   1(红) 3(红)    ← 自动旋转，查找 O(log n)

红黑树的五大规则 ​

  1. 节点非红即黑
  2. 根节点是黑色
  3. 红节点的子节点必须是黑色（不能连续两个红节点）
  4. 每条路径的黑色节点数相同
  5. 叶子节点（NIL）都是黑色

这五条规则保证了：树高 ≤ 2 × log₂(n)，即查找始终是 O(log n)。

TreeMap 的独有能力 ​

导航操作：TreeMap 最有价值的功能 ​

java
NavigableMap<Integer, String> map = new TreeMap<>();
map.put(10, "十");
map.put(30, "三十");
map.put(20, "二十");
map.put(50, "五十");
map.put(40, "四十");

// 最值
map.firstKey();   // 10
map.lastKey();    // 50

// 邻居查询
map.lowerKey(30);   // 20（小于 30 的最大）
map.higherKey(30); // 40（大于 30 的最小）
map.floorKey(35);  // 30（≤ 35 的最大）
map.ceilingKey(35);// 40（≥ 35 的最小）

// 范围视图
map.subMap(20, 50);   // [20, 30, 40]  20 ≤ key < 50
map.headMap(30);       // [10, 20]      key < 30
map.tailMap(40);       // [40, 50]      key ≥ 40

HashMap 完全没有这些能力。

反向遍历 ​

java
NavigableMap<Integer, String> desc = map.descendingMap();
// {50=五十, 40=四十, 30=三十, 20=二十, 10=十}

两种排序方式 ​

自然排序：元素实现 Comparable ​

java
// String 按字典序，Integer 按数值大小
TreeMap<String, Integer> natural = new TreeMap<>();
natural.put("cherry", 3);
natural.put("apple", 1);
natural.put("banana", 2);
System.out.println(natural); // {apple=1, banana=2, cherry=3}

自定义排序：传入 Comparator ​

java
// 按字符串长度排序
TreeMap<String, Integer> byLen = new TreeMap<>(
    Comparator.comparingInt(String::length)
);
byLen.put("hi", 1);
byLen.put("banana", 2);
byLen.put("apple", 3);
System.out.println(byLen); // {hi=1, apple=3, banana=2}

// 降序排列
TreeMap<Integer, String> desc = new TreeMap<>(Comparator.reverseOrder());
desc.put(1, "one"); desc.put(3, "three"); desc.put(2, "two");
System.out.println(desc); // {3=three, 2=two, 1=one}

两者谁优先 ​

Comparator 优先。如果创建 TreeMap 时传了 Comparator，元素的 Comparable 实现就被忽略：

java
class User implements Comparable<User> {
    String name;
    int score;

    @Override
    public int compareTo(User other) {
        return this.score - other.score; // 按分数升序
    }
}

// ❌ Comparator 优先，compareTo 被忽略
TreeMap<User, String> map = new TreeMap<>(
    Comparator.comparing(u -> u.name) // 按姓名排序
);

null 的处理 ​

key 不能为 null ​

java
TreeMap<String, Integer> map = new TreeMap<>();
map.put(null, 1); // NullPointerException！

因为红黑树需要比较 key 来决定位置，null 无法参与比较。

value 可以为 null ​

java
TreeMap<String, Integer> map = new TreeMap<>();
map.put("a", null); // ✅ OK
map.put("b", null); // ✅ OK

如果非要 key 为 null ​

java
// 使用接受 null 的 Comparator
TreeMap<String, Integer> nullable = new TreeMap<>(
    Comparator.nullsLast(Comparator.naturalOrder())
);
nullable.put(null, 1); // ✅ null 排在最后

典型应用场景 ​

场景 1：排行榜 ​

java
TreeMap<Integer, String> leaderboard = new TreeMap<>(Comparator.reverseOrder());
leaderboard.put(1500, "张三");
leaderboard.put(2000, "李四");
leaderboard.put(1800, "王五");

// 获取前 3 名
leaderboard.descendingMap().entrySet().stream()
    .limit(3)
    .forEach(e -> System.out.println(e.getValue() + ": " + e.getKey()));
// 输出：李四: 2000, 王五: 1800, 张三: 1500

场景 2：时间区间查找 ​

java
TreeMap<LocalTime, String> schedule = new TreeMap<>();
schedule.put(LocalTime.of(9, 0), "会议");
schedule.put(LocalTime.of(14, 0), "演示");
schedule.put(LocalTime.of(18, 0), "下班");

// 当前时间是 10:00，找最近的下一个事件
LocalTime now = LocalTime.of(10, 0);
Map.Entry<LocalTime, String> next = schedule.higherEntry(now);
System.out.println("接下来: " + next.getValue()); // 演示

场景 3：分层统计 ​

java
// 按年龄段分组
TreeMap<Integer, List<String>> byAge = new TreeMap<>();
List.of("张三(25)", "李四(30)", "王五(25)", "赵六(35)")
    .forEach(name -> {
        int age = Integer.parseInt(name.replaceAll("\\D+", ""));
        byAge.computeIfAbsent(age, k -> new ArrayList<>()).add(name);
    });
System.out.println(byAge);
// {25=[张三(25), 王五(25)], 30=[李四(30)], 35=[赵六(35)]}

性能特点 ​

操作时间复杂度说明
putO(log n)插入 + 可能触发再平衡
getO(log n)二叉搜索
removeO(log n)删除 + 可能触发再平衡
first/lastO(log n)最值查询
lower/higherO(log n)邻居查询
subMapO(log n + k)k = 返回元素数

TreeMap vs HashMap ​

维度TreeMapHashMap
排序✅ 按 key 排序❌ 无序
查找速度O(log n)O(1) 均摊
导航操作✅ 丰富❌ 不支持
key 为 null❌ 不允许✅ 允许一个
内存占用较高（树节点）较低
适用场景需要排序/导航纯粹映射

总结 ​

要点说明
底层结构红黑树（自平衡 BST）
核心能力按 key 排序 + 导航操作
时间复杂度O(log n)，稳定
key 要求必须可比较（或提供 Comparator）
独有功能first/last/lower/higher/subMap
线程安全非安全，多线程用 ConcurrentSkipListMap

一句话：HashMap 管「找不找得到」，TreeMap 管「排第几」。

相关链接 ​

基于 VitePress 构建

Copyright © 2025-2026 JTechVault