TreeMap 源码解析
简介
TreeMap 是 Map 接口的有序实现，底层为一棵红黑树（Red-Black Tree），因此它能保证键（key）按「自然顺序」或「定制 Comparator」保持有序。
- 实现
NavigableMap（间接实现SortedMap），支持firstKey/lastKey/lowerKey/higherKey/subMap等区间查询。 - 不是线程安全的；多线程可用
Collections.synchronizedSortedMap包装，或改用ConcurrentSkipListMap。 - 不允许「无法比较」的 key：使用自然排序（无
Comparator）时传入null键会抛NullPointerException；使用允许null的Comparator时则可。 - 与
HashMap（无序、O(1)）、LinkedHashMap（插/访问顺序）相比，TreeMap的核心价值是有序 + 范围查询，时间复杂度稳定在 O(log n)。
注意：
TreeMap的相等性比较的是「key 的有序内容」，只要两个 TreeMap 的 key 集合与映射一致即相等，与其内部树结构无关。
底层数据结构分析
红黑树是一种自平衡二叉查找树，每个节点多一个 color（红 / 黑）字段，通过旋转和重新着色维持以下性质，从而保证最长路径不超过最短路径的 2 倍：
- 节点非红即黑；根节点为黑。
- 红色节点的子节点必为黑（不能有连续红节点）。
- 从任一节点到其所有叶子（null 叶子）的黑色节点数相同（黑高一致）。
TreeMap 的节点（Entry）就是红黑树节点，同时保存父、左、右指针和颜色。
java
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK; // 默认黑色
}核心成员变量
java
// 排序用的比较器；为 null 表示使用 key 的自然顺序（key 必须实现 Comparable）
private final Comparator<? super K> comparator;
// 红黑树的根节点，未初始化时为 null
private transient Entry<K,V> root;
// 键值对数量
private transient int size = 0;源码分析
比较：compare / comparator 选择
所有查找、插入、删除都依赖比较结果。TreeMap 优先使用外部 Comparator，否则要求 key 实现 Comparable：
java
final int compare(Object k1, Object k2) {
return comparator == null
? ((Comparable<? super K>)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
}写入：put
put 先沿树根据比较结果向下查找目标位置：找到相等 key 就替换 value；否则作为叶子插入新节点，最后调用 fixAfterInsertion 重新平衡（旋转 + 变色）。
java
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) { // 空树，直接作为根（黑色）
compare(key, key); // 检查 key 是否可比较（不可比较会抛异常）
root = new Entry<>(key, value, null);
size = 1;
return null;
}
int cmp;
Entry<K,V> parent;
Comparator<? super K> cpr = comparator;
// 1. 根据比较结果下钻，找到插入点（或命中已有 key）
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); // 命中，替换 value
} while (t != null);
} else { /* 使用 Comparable 版本，逻辑相同 */ }
// 2. 作为红色叶子挂到 parent 之下
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0) parent.left = e; else parent.right = e;
// 3. 重新平衡红黑树（旋转 + 变色）
fixAfterInsertion(e);
size++;
return null;
}读取：get / getEntry
get 本质是二叉查找：从根开始，按比较结果向左 / 右走，直到命中或走到空。
java
final Entry<K,V> getEntry(Object key) {
if (comparator != null) return getEntryUsingComparator(key);
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) { // 标准 BST 查找
int cmp = k.compareTo(p.key);
if (cmp < 0) p = p.left;
else if (cmp > 0) p = p.right;
else return p;
}
return null;
}删除：remove
remove 先 getEntry 找到节点，再 deleteEntry：
- 若节点有 0 或 1 个子节点：直接用其子节点（或 null）替换它。
- 若有两个子节点：用「右子树的最小节点（后继）」替换它，再删除后继节点。
- 删除黑色节点会破坏黑高，最后
fixAfterDeletion重新平衡。
java
private void deleteEntry(Entry<K,V> p) {
size--;
// 两个子节点：用后继替换 p，问题转化为删除后继（至多一个子节点）
if (p.left != null && p.right != null) {
Entry<K,V> s = successor(p);
p.key = s.key; p.value = s.value;
p = s;
}
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
replacement.parent = p.parent; // 用 replacement 顶替 p
/* ... 接好父节点的 left/right 指针 ... */
}
else if (p.color == BLACK)
fixAfterDeletion(p); // 删黑节点，重新平衡
/* ... */
}与 HashMap / LinkedHashMap 的对比
| 维度 | HashMap | LinkedHashMap | TreeMap |
|---|---|---|---|
| 底层结构 | 数组+链表/红黑树 | HashMap + 双向链表 | 红黑树 |
| 顺序 | 无序 | 插入/访问顺序 | key 有序 |
| 时间复杂度 | 平均 O(1) | 平均 O(1) | 稳定 O(log n) |
| 范围查询 | 不支持 | 不支持 | 支持 |
| 线程安全 | 否 | 否 | 否 |
| 允许 null 键 | 允许 | 允许 | 否（自然排序下） |
经典 Demo
java
import java.util.*;
public class TreeMapDemo {
public static void main(String[] args) {
TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "c"); map.put(1, "a"); map.put(2, "b");
System.out.println(map); // {1=a, 2=b, 3=c} 自动按 key 升序
System.out.println(map.firstKey()); // 1
System.out.println(map.lastKey()); // 3
System.out.println(map.subMap(1, 3)); // {1=a, 2=b} 区间 [1,3)
System.out.println(map.descendingMap()); // {3=c, 2=b, 1=a} 降序视图
}
}