TreeMap 深度解析（基于 JDK 8）
TreeMap 是 Java 集合框架中基于红黑树实现的 Map 接口实现类，其核心特性是键的有序性—— 通过键的自然排序或定制排序维持键值对的顺序。与 HashMap 相比，TreeMap 不依赖哈希值，而是通过比较键的大小来组织数据，适用于需要有序键值对的场景。本文将从底层结构、排序机制、核心方法及红黑树平衡操作等方面，全面解析 TreeMap 的实现原理。
TreeMap 核心特性与继承关系
核心特性
- 有序性：键值对按键的顺序（自然排序或定制排序）存储，遍历顺序为键的升序（或定制排序顺序）。
- 无哈希冲突：基于红黑树实现，不依赖哈希值，因此不存在哈希冲突问题。
- 键不可为 null：自然排序时，键需实现
Comparable 接口，compareTo 方法无法处理 null；定制排序时，若 Comparator 不支持 null，则键也不能为 null（否则抛出 NullPointerException）。
- 非线程安全：多线程并发修改需手动同步（如使用
Collections.synchronizedSortedMap）。
- 导航方法：实现
NavigableMap 接口，提供丰富的导航方法（如 ceilingKey、floorKey、subMap 等），方便范围查询。
继承关系
![TreeMap]()
1
2
| public class TreeMap<K,V> extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
|
- 继承
AbstractMap：复用 Map 接口的基础实现（如 entrySet、size 等）。
- 实现
NavigableMap：扩展 SortedMap 接口，支持导航操作（如获取大于 / 小于某键的最值）。
- 实现
Cloneable：支持浅拷贝（复制红黑树结构，键值对对象本身不复制）。
- 实现
Serializable：支持序列化，通过自定义 writeObject 和 readObject 保存 / 恢复红黑树结构。
底层结构：红黑树
TreeMap 的底层是红黑树—— 一种自平衡二叉搜索树（BST），通过维护节点颜色和旋转操作，确保树的高度始终为 O(log n)，从而保证增删改查的时间复杂度为 O(log n)。
红黑树的基本性质
红黑树通过以下性质维持平衡：
- 每个节点要么是红色，要么是黑色；
- 根节点是黑色；
- 所有叶子节点（NIL 节点，空节点）是黑色；
- 若一个节点是红色，则其两个子节点必为黑色（红色节点的子节点不能是红色）；
- 从任一节点到其所有叶子节点的路径中，黑色节点的数量相同（“黑高” 相等）。
节点结构（Entry 内部类）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| 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;
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}
|
- 每个节点包含键、值、左右子节点、父节点及颜色，构成红黑树的基本单元。
关键变量
1
2
3
4
| private final Comparator<? super K> comparator;
private transient Entry<K,V> root;
private transient int size = 0;
private transient int modCount = 0;
|
排序机制：自然排序与定制排序
TreeMap 的有序性依赖于键的比较逻辑，分为两种方式：
自然排序（comparator == null）
当未指定比较器时，TreeMap 采用自然排序，要求键必须实现 Comparable 接口，通过 compareTo 方法比较大小：
1
2
3
|
Comparable<? super K> k = (Comparable<? super K>) key;
int cmp = k.compareTo(p.key);
|
- 例如：
Integer、String 等类已实现 Comparable，可直接作为 TreeMap 的键，按默认顺序（数字升序、字符串字典序）排列。
定制排序（comparator != null）
当传入 Comparator 时，TreeMap 按比较器的 compare 方法排序，无需键实现 Comparable：
1
2
3
|
Comparator<? super K> cpr = comparator;
int cmp = cpr.compare(key, t.key);
|
示例：创建按字符串长度排序的 TreeMap：
1
| Map<String, Integer> map = new TreeMap<>((s1, s2) -> Integer.compare(s1.length(), s2.length()));
|
构造函数：初始化排序方式
TreeMap 提供 4 种构造函数，核心是初始化比较器（决定排序方式）。
无参构造器（自然排序）
1
2
3
| public TreeMap() {
comparator = null;
}
|
带比较器的构造器（定制排序）
1
2
3
| public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
|
基于已有 Map 初始化
1
2
3
4
| public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
|
基于 SortedMap 初始化
1
2
3
4
| public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
}
|
核心方法解析
1. get(Object key)：查询键对应的值
通过比较键的大小遍历红黑树，找到匹配的节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p == null) ? null : p.value;
}
final Entry<K,V> getEntry(Object key) {
if (comparator != null) {
return getEntryUsingComparator(key);
}
if (key == null) {
throw new NullPointerException();
}
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0) {
p = p.left;
} else if (cmp > 0) {
p = p.right;
} else {
return p;
}
}
return null;
}
|
- 查询过程：从根节点开始，通过比较键的大小决定遍历左子树（键更小）或右子树（键更大），直到找到匹配节点或遍历至叶子节点（返回 null）。
2. put(K key, V value)：插入键值对
插入节点后，需通过红黑树的平衡操作（变色、旋转）维持红黑树性质。
步骤 1：定位插入位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null) {
compare(key, key);
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 {
if (key == null) throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 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;
}
|
步骤 2：插入后平衡（fixAfterInsertion）
新节点默认为红色，可能破坏红黑树性质（如红色节点的父节点为红色），需通过变色和旋转修复。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
|
- 旋转操作：左旋（
rotateLeft）和右旋（rotateRight）用于调整树的结构，避免倾斜过度。例如，左旋将右子节点提升为父节点，原父节点变为其左子节点，维持二叉搜索树的性质。
3. remove(Object key)：删除键值对
删除节点后，需通过平衡操作维持红黑树性质，过程比插入更复杂（需处理多种子节点情况）。
步骤 1：找到要删除的节点
1
2
3
4
5
6
7
| public V remove(Object key) {
Entry<K,V> p = getEntry(key);
if (p == null) return null;
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
|
步骤 2：删除节点并平衡（deleteEntry）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
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;
if (p.parent == null) {
root = replacement;
} else if (p == p.parent.left) {
p.parent.left = replacement;
} else {
p.parent.right = replacement;
}
p.left = p.right = p.parent = null;
if (p.color == BLACK) {
fixAfterDeletion(replacement);
}
} else if (p.parent == null) {
root = null;
} else {
if (p.color == BLACK) {
fixAfterDeletion(p);
}
if (p.parent != null) {
if (p == p.parent.left) {
p.parent.left = null;
} else {
p.parent.right = null;
}
p.parent = null;
}
}
}
|
- 后继节点（successor）：当节点有两个子节点时，后继节点是右子树中最小的节点（最左节点），其最多有一个右子节点，简化删除操作。
步骤 3：删除后平衡（fixAfterDeletion）
删除黑色节点可能破坏红黑树的黑高性质，需通过变色和旋转修复（过程类似插入后的平衡，但更复杂，涉及兄弟节点的处理）。
TreeMap 与其他 Map 的对比
| 特性 |
TreeMap |
HashMap |
Hashtable |
LinkedHashMap |
| 底层结构 |
红黑树 |
数组 + 链表 / 红黑树 |
数组 + 链表 |
数组 + 链表 / 红黑树 + 双向链表 |
| 有序性 |
按键排序 |
无序 |
无序 |
插入 / 访问顺序 |
| 时间复杂度 |
O(log n) |
O (1)（平均） |
O (1)（平均） |
O (1)（平均） |
| 键是否可为 null |
否（自然排序） |
是（最多 1 个） |
否 |
是（最多 1 个） |
| 线程安全 |
否 |
否 |
是（synchronized） |
否 |
| 适用场景 |
有序键值对、范围查询 |
高效存取 |
旧系统兼容 |
需保留插入 / 访问顺序 |
