TreeMap 详解（附源码）
字数: 0 字 时长: 0 分钟
之前在 LinkedHashMap 中提到过：
HashMap
↓
不保证遍历顺序
LinkedHashMap
↓
通过双向链表
维护插入顺序或访问顺序那 TreeMap 呢？
TreeMap 底层由：
红黑树实现，可以按照 Key 的：
自然顺序
或者
Comparator 指定的自定义顺序进行排列。
红黑树（Red-Black Tree）是一种自平衡的二叉查找树（Binary Search Tree），结构比较复杂，但拥有良好的性能，查找、插入和删除操作的时间复杂度通常为
O(log n)。
二叉查找树是一种常见的树形结构。
每个节点都包含一个键值对，并且：
左子树节点
↓
小于当前节点
右子树节点
↓
大于当前节点这个特点使二叉查找树非常适合进行：
查找
排序下面是一个简单的二叉查找树：
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13在这棵二叉查找树中：
根节点
↓
8
左子树
↓
3、1、6、4、7
右子树
↓
10、14、13满足：
3 < 8 < 10
1 < 3 < 6
4 < 6 < 7
10 < 14
13 < 14这是一棵典型的二叉查找树：
- 左子树上的节点值小于或等于根节点的值。
- 右子树上的节点值大于或等于根节点的值。
- 左、右子树本身也分别是二叉查找树。
二叉查找树进行查找时：
从根节点开始
↓
与当前节点比较如果：
目标值 == 当前节点
↓
查找成功
目标值 < 当前节点
↓
继续查找左子树
目标值 > 当前节点
↓
继续查找右子树如果一直遍历到叶子节点仍然没有找到：
查找失败插入操作也类似。
从根节点开始比较：
新 Key < 当前 Key
↓
进入左子树
新 Key > 当前 Key
↓
进入右子树
Key 已经存在
↓
更新对应的 Value删除操作稍微复杂一些，需要考虑：
删除叶子节点
删除只有一个子节点的节点
删除拥有两个子节点的节点总的来说，二叉查找树非常适合：
查找
排序
删除但普通二叉查找树有一个明显的问题：
可能变得不平衡。
例如：
6
/ \
4 8
/ / \
3 7 9
/
1这棵树中：
根节点
↓
6
左子树
↓
4、3、1
右子树
↓
8、7、9左子树明显比右子树更高。
树一旦越来越不平衡：
查找
插入
删除的效率都会下降。
再看一个更加极端的情况：
1
\
2
\
3
\
4
\
5
\
6这棵树中，所有节点都只有右子节点。
此时虽然结构上还是一棵树，但实际上已经越来越像：
链表查找效率也会从理想状态下的：
O(log n)逐渐退化到：
O(n)所以必须想办法让树保持平衡。
于是就有了：
平衡二叉树典型的平衡二叉树会尽量保证左右子树高度接近。
例如：
8
/ \
4 12
/ \ / \
2 6 10 14
/ \ / \
5 7 13 15根节点：
8左子树：
4、2、6、5、7右子树：
12、10、14、13、15左右两边保持得比较平衡。
当插入或者删除节点以后，平衡树会通过一定的调整方式，让树重新保持平衡。
常见的平衡二叉树包括：
AVL 树
红黑树它们都会通过：
旋转等方式调整树的结构。
AVL 树示意图：
8
/ \
4 12
/ \ / \
2 6 10 14
/ \
5 7AVL 树是一种高度平衡的二叉查找树，它要求左右子树的高度差不超过 1。
由于 AVL 树的平衡程度比较高，因此插入和删除时可能需要更多的旋转操作来维持平衡，但查找效率较高。
AVL 树比较适合：
读操作较多的场景例如需要频繁查找或者保证数据有序性的场景。
AVL 树最初由两位苏联计算机科学家：
Adelson-Velskii
Landis在 1962 年提出。
因此：
AVL就是两人名字首字母的组合。
红黑树示意图：
8B
/ \
4R 12R
/ \ / \
2B 6B 10B 14B
/ \
5R 7R其中：
R
↓
Red
红色
B
↓
Black
黑色红黑树是一种通过：
红色节点
黑色节点以及一系列规则维持相对平衡的二叉查找树。
主要规则：
- 每个节点只能是红色或者黑色。
- 根节点是黑色。
- 每个叶节点，也就是
NIL空节点，是黑色。 - 如果一个节点是红色，那么它的两个子节点都是黑色，也就是说一条路径上不能出现连续的两个红色节点。
- 从任意一个节点到其所有叶节点的路径，都包含相同数量的黑色节点。
红黑树的平衡程度没有 AVL 树那么严格，因此：
插入
删除时需要进行的旋转调整通常更少。
同时它仍然可以保持较好的查找效率，因此比较适合：
读写操作比较均衡的场景1. 自然顺序
默认情况下，TreeMap 会根据：
Key 的自然顺序进行排列。
例如整数：
1
2
3
4
5默认按照升序排列。
public static void main(
String[] args) {
TreeMap<Integer, String> mapInt =
new TreeMap<>();
mapInt.put(
3,
"灭绝师太"
);
mapInt.put(
2,
"灭绝师太"
);
mapInt.put(
1,
"灭绝师太"
);
mapInt.put(
5,
"灭绝师太"
);
mapInt.put(
4,
"灭绝师太"
);
System.out.println(
mapInt
);
}输出：
{1=灭绝师太, 2=灭绝师太, 3=灭绝师太, 4=灭绝师太, 5=灭绝师太}TreeMap 是怎么做到的？
来看 put() 方法的源码：
public V put(
K key,
V value) {
// 根节点
Entry<K, V> t =
root;
// TreeMap 为空
if (t == null) {
// 检查 Key 类型是否合法
compare(
key,
key
);
// 创建根节点
root =
new Entry<>(
key,
value,
null
);
size =
1;
return null;
}
int cmp;
Entry<K, V> parent;
// 获取 Comparator
Comparator<? super K> comparator =
this.comparator;
// 使用 Comparator
if (comparator != null) {
do {
parent =
t;
cmp =
comparator.compare(
key,
t.key
);
if (cmp < 0) {
// 进入左子树
t =
t.left;
} else if (cmp > 0) {
// 进入右子树
t =
t.right;
} else {
// Key 相同，更新 Value
return t.setValue(
value
);
}
} while (t != null);
} else {
if (key == null) {
throw new NullPointerException();
}
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 {
// Key 相同，更新 Value
return t.setValue(
value
);
}
} while (t != null);
}
// 没找到相同 Key，创建新节点
Entry<K, V> entry =
new Entry<>(
key,
value,
parent
);
if (cmp < 0) {
parent.left =
entry;
} else {
parent.right =
entry;
}
// 插入后重新调整红黑树
fixAfterInsertion(
entry
);
size++;
return null;
}整体过程：
获取 root
↓
TreeMap 是否为空如果为空：
创建根节点
↓
size = 1如果不为空：
判断是否存在 Comparator存在 Comparator：
Comparator.compare()
↓
比较 Key不存在 Comparator：
Comparable.compareTo()
↓
比较 Key比较结果：
cmp < 0
↓
进入左子树
cmp > 0
↓
进入右子树
cmp == 0
↓
Key 已存在
↓
更新 Value如果一直没有找到相同 Key：
创建新的 Entry
↓
挂到 parent 左侧或右侧
↓
fixAfterInsertion()
↓
重新调整树的平衡最后：
size++如果更新的是已有 Key：
返回原来的 Value其中非常重要的一句：
cmp =
k.compareTo(
t.key
);就是使用：
Comparable进行 Key 的自然顺序比较。
如果 Key 是 String，就会调用 String 的：
compareTo()例如源码中的比较逻辑：
public int compareTo(
String anotherString) {
// 两个字符串长度
int len1 =
value.length;
int len2 =
anotherString.value.length;
// 取较短的长度
int lim =
Math.min(
len1,
len2
);
char[] v1 =
value;
char[] v2 =
anotherString.value;
int k =
0;
while (k < lim) {
char c1 =
v1[k];
char c2 =
v2[k];
if (c1 != c2) {
return c1 - c2;
}
k++;
}
return len1 - len2;
}例如最终得到：
{a=灭绝师太, b=灭绝师太, c=灭绝师太, d=灭绝师太, e=灭绝师太}可以看到：
a
b
c
d
e按照字母自然顺序排列。
2. 自定义排序
如果：
自然顺序不能满足需求，就可以在创建 TreeMap 时指定：
Comparator自定义排序规则。
例如逆序：
TreeMap<Integer, String> mapIntReverse =
new TreeMap<>(
Comparator.reverseOrder()
);
mapIntReverse.put(
3,
"灭绝师太"
);
mapIntReverse.put(
2,
"灭绝师太"
);
mapIntReverse.put(
1,
"灭绝师太"
);
mapIntReverse.put(
5,
"灭绝师太"
);
mapIntReverse.put(
4,
"灭绝师太"
);
System.out.println(
mapIntReverse
);输出：
{5=灭绝师太, 4=灭绝师太, 3=灭绝师太, 2=灭绝师太, 1=灭绝师太}TreeMap 提供了可以指定排序规则的构造方法：
public TreeMap(
Comparator<? super K> comparator) {
this.comparator =
comparator;
}Comparator.reverseOrder() 返回一个反序比较器，用来将自然顺序反转。
源码：
private static class ReverseComparator
implements Comparator<Comparable<Object>>,
Serializable {
// 逆序比较器单例
static final ReverseComparator REVERSE_ORDER =
new ReverseComparator();
/**
* 进行逆序比较
*/
public int compare(
Comparable<Object> c1,
Comparable<Object> c2) {
return c2.compareTo(
c1
);
}
/**
* 反序列化后仍返回单例对象
*/
private Object readResolve() {
return Collections.reverseOrder();
}
/**
* 再次反转后恢复自然顺序
*/
@Override
public Comparator<Comparable<Object>> reversed() {
return Comparator.naturalOrder();
}
}HashMap 本身不保证遍历顺序。
而 TreeMap 可以始终按照：
自然顺序
或者
自定义顺序排列。
对于需要按照 Key 排序的场景非常有用。
3. 排序的好处
既然 TreeMap 中的 Key 已经是有序的，那么获取：
最大 Key
最小 Key
小于某个值的 Key
大于某个值的 Key就方便很多。
例如：
Integer highestKey =
mapInt.lastKey();
Integer lowestKey =
mapInt.firstKey();
Set<Integer> keysLessThan3 =
mapInt
.headMap(3)
.keySet();
Set<Integer> keysGreaterThanEqTo3 =
mapInt
.tailMap(3)
.keySet();
System.out.println(
highestKey
);
System.out.println(
lowestKey
);
System.out.println(
keysLessThan3
);
System.out.println(
keysGreaterThanEqTo3
);TreeMap 提供了：
lastKey()获取最后一个 Key。
firstKey()获取第一个 Key。
headMap()：
获取指定 Key 之前的数据tailMap()：
获取从指定 Key 开始的数据输出：
5
1
[1, 2]
[3, 4, 5]再来看一个例子：
TreeMap<Integer, String> treeMap =
new TreeMap<>();
treeMap.put(
1,
"value1"
);
treeMap.put(
2,
"value2"
);
treeMap.put(
3,
"value3"
);
treeMap.put(
4,
"value4"
);
treeMap.put(
5,
"value5"
);
// 获取小于 3 的键值对
Map<Integer, String> headMap =
treeMap.headMap(
3
);
System.out.println(
headMap
);
// 获取大于等于 4 的键值对
Map<Integer, String> tailMap =
treeMap.tailMap(
4
);
System.out.println(
tailMap
);
// 获取大于等于 2 且小于 4 的键值对
Map<Integer, String> subMap =
treeMap.subMap(
2,
4
);
System.out.println(
subMap
);输出：
{1=value1, 2=value2}
{4=value4, 5=value5}
{2=value2, 3=value3}所以：
headMap(3)
↓
小于 3
tailMap(4)
↓
大于等于 4
subMap(2, 4)
↓
大于等于 2
并且小于 44. 如何选择 Map
在学习 TreeMap 之前，已经学习了：
HashMap
LinkedHashMap那这三个 Map 应该怎么选择？
主要考虑以下因素：
- 是否需要按照 Key 的自然顺序或者自定义顺序排序。如果需要按照 Key 排序，可以使用
TreeMap；如果不需要排序，可以使用HashMap或LinkedHashMap。 - 是否需要保持插入顺序。如果需要保持插入顺序，可以使用
LinkedHashMap；如果不需要，则可以使用TreeMap或HashMap。 - 是否需要高效查找。
HashMap和LinkedHashMap理想情况下查找时间复杂度为O(1)，TreeMap 的查找时间复杂度为O(log n)。
LinkedHashMap 内部：
哈希表
+
双向链表哈希表负责：
查找键值对双向链表负责：
维护顺序所以其查找仍然主要通过哈希表完成。
简单对比：
| 特性 | TreeMap | HashMap | LinkedHashMap |
|---|---|---|---|
| 排序 | 支持 | 不支持 | 不支持 |
| 插入顺序 | 不保证 | 不保证 | 保证 |
| 查找效率 | O(log n) | 理想情况下 O(1) | 理想情况下 O(1) |
| 空间占用 | 通常较大 | 通常较小 | 通常较大 |
| 适用场景 | 需要排序 | 无需排序 | 需要保持插入顺序 |