【Java】TreeMap 详解：从红黑树原理到实战应用
大家好，我是云扬～ 今天来和大家深入聊聊 Java 集合框架中的 TreeMap，这个基于红黑树实现的有序映射容器，在实际开发中经常被用于需要排序的场景。本文会从底层数据结构讲起，结合代码示例，帮大家彻底搞懂 TreeMap 的用法和原理。
一、TreeMap 概述
TreeMap 是 Java 中唯一的有序 Map 实现，它基于红黑树（Red-Black Tree） 数据结构，能够自动保持键（Key）的有序性 —— 要么遵循自然顺序，要么通过自定义比较器指定顺序。这一点和 HashMap（无序）、LinkedHashMap（保持插入顺序）有本质区别。
二、底层核心：红黑树基础
要理解 TreeMap 的性能优势，首先得搞懂红黑树的特性。红黑树是一种自平衡二叉查找树，它解决了普通二叉查找树容易失衡的问题，保证了查找、插入、删除操作的时间复杂度均为 O(log n)。
2.1 二叉查找树的不足
普通二叉查找树的特性是：左子树键值 父节点键值 右子树键值。但如果插入的元素是有序的（比如 1、2、3、4），会退化成链表结构，此时操作复杂度变成 O (n)，性能极差。
2.2 红黑树的 5 大特性
红黑树通过以下规则保证自平衡：
- 每个节点要么是红色，要么是黑色；
- 根节点必须是黑色；
- 所有叶子节点（NIL 节点）都是黑色；
- 红色节点的两个子节点必须是黑色（避免连续红节点）；
- 从任一节点到其所有叶子节点的路径，黑色节点数量相同（保证树的高度平衡）。
当插入或删除元素破坏这些规则时，红黑树会通过旋转（左旋 / 右旋） 和颜色翻转来恢复平衡，这也是 TreeMap 能保持高效的核心原因。
三、TreeMap 的核心特性与用法
3.1 自然顺序（默认排序）
TreeMap 对实现了 Comparable 接口的键（如 Integer、String、Date 等），会自动使用其 compareTo() 方法进行排序。
代码示例：自然顺序排序
import java.util.TreeMap;
public class TreeMapNaturalOrderDemo {
public static void main(String[] args) {
// 键为 Integer 类型（实现了 Comparable 接口）
TreeMap<Integer,String> treeMap = new TreeMap<>();
// 无序插入数据
treeMap.put(3, "张三");
treeMap.put(1, "李四");
treeMap.put(2, "王五");
treeMap.put(5, "赵六");
treeMap.put(4, "孙七");
// 遍历输出：自动按键升序排列
System.out.println("自然顺序（升序）：");
for (Integer key : treeMap.keySet()) {
System.out.println(key + " -> " + treeMap.get(key));
}
// 输出结果：
// 自然顺序（升序）：
// 1 -> 李四
// 2 -> 王五
// 3 -> 张三
// 4 -> 孙七
// 5 -> 赵六
}
}
源码解读：TreeMap 的 put() 方法会调用 compareTo() 进行键的比较，核心逻辑如下（简化版）：
public V put(K key, V value) {
Entry t = root;
if (t == null) {
compare(key, key); // 检查键是否为 null（TreeMap 不允许 null 键）
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
Comparator<? super K> cpr = comparator;
if (cpr != null) {
// 自定义比较器逻辑
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value); // 键相同则更新值
} while (t != null);
} else {
// 自然顺序逻辑（依赖 Comparable 接口）
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key); // 调用键的 compareTo 方法
if (cmpcmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e); // 插入后修复红黑树平衡
size++;
modCount++;
return null;
}
3.2 自定义排序（Comparator）
如果键没有实现 Comparable 接口，或者想改变默认排序规则（比如降序），可以通过 TreeMap(Comparator> comparator) 构造方法指定排序逻辑。
代码示例：自定义降序排序
import java.util.TreeMap;
import java.util.Comparator;
public class TreeMapCustomComparatorDemo {
public static void main(String[] args) {
// 自定义比较器：按 Integer 键降序排列
TreeMap<Integer, String> treeMap = new TreeMap<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// o1 - o2 是升序，o2 - o1 是降序
return o2 - o1;
}
});
// 简化写法（Lambda 表达式，Java 8+）
// TreeMap<Integer, String> treeMap = new TreeMap<>((o1, o2) -> o2 - o1);
treeMap.put(3, "张三");
treeMap.put(1, "李四");
treeMap.put(2, "王五");
treeMap.put(5, "赵六");
treeMap.put(4, "孙七");
// 遍历输出：按键降序排列
System.out.println("自定义顺序（降序）：");
for (Integer key : treeMap.keySet()) {
System.out.println(key + " -> " + treeMap.get(key));
}
// 输出结果：
// 5 -> 赵六
// 4 -> 孙七
// 3 -> 张三
// 2 -> 王五
// 1 -> 李四
}
}
代码解读：通过 Comparator 接口的 compare(o1, o2) 方法定义排序规则：
- 返回负数：o1 排在 o2 前面；
- 返回正数：o1 排在 o2 后面；
- 返回 0：o1 和 o2 视为相同键，后面的会覆盖前面的值。
3.3 有序性带来的实用方法
TreeMap 的有序性提供了很多便捷方法，这是 HashMap 不具备的：
// 1. 获取最小键
Integer firstKey = treeMap.firstKey(); // 结果：1（自然顺序）
// 2. 获取最大键
Integer lastKey = treeMap.lastKey(); // 结果：5（自然顺序）
// 3. 获取小于等于指定键的最大键
Integer floorKey = treeMap.floorKey(3); // 结果：3
// 4. 获取大于等于指定键的最小键
Integer ceilingKey = treeMap.ceilingKey(3); // 结果：3
// 5. 获取小于指定键的最大键
Integer lowerKey = treeMap.lowerKey(3); // 结果：2
// 6. 获取大于指定键的最小键
Integer higherKey = treeMap.higherKey(3); // 结果：4
// 7. 截取子Map（左闭右开）
SortedMap<Integer, String> subMap = treeMap.subMap(2, 5);// 键：2、3、4
subMap.forEach((key, value) -> System.out.println(key + " -> " + value));
四、TreeMap vs HashMap vs LinkedHashMap
实际开发中如何选择 Map 实现？关键看需求：
| 特性 | TreeMap | HashMap | LinkedHashMap |
|---|---|---|---|
| 底层结构 | 红黑树 | 数组 + 链表 / 红黑树（JDK8+） | 数组 + 链表 / 红黑树 + 双向链表 |
| 排序性 | 自然顺序 / 自定义顺序 | 无序 | 保持插入顺序 |
| 查找效率 | O(log n) | O (1)（理想情况） | O (1)（理想情况） |
| 插入 / 删除效率 | O(log n) | O (1)（理想情况） | O (1)（理想情况） |
| 允许 null 键 | 不允许 | 允许（仅一个） | 允许（仅一个） |
| 适用场景 | 需要排序的场景 | 无需排序，追求高效 | 需要保持插入顺序的场景 |
五、实战场景示例：排行榜功能
TreeMap 的有序性非常适合实现排行榜、优先级队列等功能。比如，实现一个学生成绩排行榜（按成绩降序）：
import java.util.Comparator;
import java.util.TreeMap;
// 学生类
class Student {
private String name;
private int score;
public Student(String name, int score) {
this.name = name;
this.score = score;
}
// getter/setter
public String getName() { return name; }
public int getScore() { return score; }
@Override
public String toString() {
return "{" + name + ": " + score + "}";
}
}
public class ScoreRankingDemo {
public static void main(String[] args) {
// 自定义比较器：按成绩降序，成绩相同按姓名升序
TreeMap<Student, Integer> rankingMap = new TreeMap<>(new Comparator<Student>() {
@Override
public int compare(Student s1, Student s2) {
// 成绩降序
if (s1.getScore() != s2.getScore()) {
return s2.getScore() - s1.getScore();
}
// 姓名升序（String 实现了 Comparable）
return s1.getName().compareTo(s2.getName());
}
});
// 添加学生成绩
rankingMap.put(new Student("张三", 95), 95);
rankingMap.put(new Student("李四", 98), 98);
rankingMap.put(new Student("王五", 95), 95);
rankingMap.put(new Student("赵六", 92), 92);
// 输出排行榜（自动排序）
System.out.println("学生成绩排行榜：");
int rank = 1;
for (Student student : rankingMap.keySet()) {
System.out.println("第" + rank + "名：" + student);
rank++;
}
// 输出结果：
// 学生成绩排行榜：
// 第1名：{李四: 98}
// 第2名：{张三: 95}
// 第3名：{王五: 95}
// 第4名：{赵六: 92}
}
}
六、总结
TreeMap 是 Java 中极具特色的 Map 实现，其核心优势在于有序性，底层通过红黑树保证了高效的操作性能。总结一下：
- TreeMap 基于红黑树，查找、插入、删除复杂度 O (log n)；
- 支持自然顺序（需实现 Comparable）和自定义顺序（需指定 Comparator）；
- 不允许 null 键，有序性带来了丰富的便捷方法；
- 适用于需要排序的场景（如排行榜、区间查询），无需排序时优先选择 HashMap。
希望本文能帮助大家彻底搞懂 TreeMap，如果有疑问或补充，欢迎在评论区交流～
