TreeMap详解

1 TreeMap 概述

TreeMap 是 Java 中的一种有序映射（Map）实现，它基于红黑树（Red-Black Tree）数据结构，可以保持元素的自然顺序或自定义顺序。

2 红黑树（Red-Black Tree）简介

红黑树是一种自平衡的二叉查找树（Binary Search Tree），具有良好的性能，查找、插入和删除操作的时间复杂度均为 O(log n)。以下是对红黑树的详细介绍：

2.1 二叉查找树（Binary Search Tree）

二叉查找树是一种常见的树形结构，具有以下特性：

• 每个节点包含一个键值对。
• 每个节点的左子树节点的键值小于该节点的键值。
• 每个节点的右子树节点的键值大于该节点的键值。
• 左、右子树也分别为二叉查找树。

示例：

        8/   \3     10/ \      \1   6     14/ \    /4   7  13

在这个二叉查找树中：

• 根节点是 8。
• 左子树节点包括 3、1、6、4 和 7。
• 右子树节点包括 10、14 和 13。

2.1.1 二叉查找树的操作

• 查找：从根节点开始遍历，如果当前节点的键值等于要查找的键值，则查找成功；如果要查找的键值小于当前节点的键值，则继续遍历左子树；如果要查找的键值大于当前节点的键值，则继续遍历右子树。如果遍历到叶子节点仍然没有找到，则查找失败。
• 插入：从根节点开始遍历，如果要插入的键值小于当前节点的键值，则将其插入到左子树中；如果要插入的键值大于当前节点的键值，则将其插入到右子树中。如果要插入的键值已经存在于树中，则更新该节点的值。
• 删除：删除操作稍微复杂一些，需要考虑多种情况，包括要删除的节点是叶子节点、要删除的节点只有一个子节点、要删除的节点有两个子节点等等。

2.1.2 二叉查找树的不足

二叉查找树的一个明显不足是容易变得不平衡，即一侧的节点比另一侧多，导致查找、插入和删除操作的效率下降。例如：

        6/   \4     8/     / \3     7   9/1

在这个不平衡的二叉查找树中，左子树比右子树高，导致操作效率下降。

更极端的情况：

    1\2\3\4\5\6

在这个极度不平衡的二叉查找树中，所有节点都只有一个右子节点，导致查找、插入和删除操作的效率急剧下降。

2.2 平衡二叉树

为了解决二叉查找树的不平衡问题，引入了平衡二叉树的概念。平衡二叉树要求左右子树的高度差不超过 1，常见的平衡二叉树包括 AVL 树和红黑树。

示例：

        8/   \4     12/ \    / \2   6  10  14/ \    / \5   7  13  15

在这个平衡二叉查找树中，左子树和右子树的高度差不超过 1。

2.2.1 AVL 树

AVL 树是一种高度平衡的二叉查找树，要求左子树和右子树的高度差不超过 1。由于 AVL 树的平衡度比较高，因此在进行插入和删除操作时需要进行更多的旋转操作来保持平衡，但是在查找操作时效率较高。

示例：

           8/   \4     12/ \   /  \2   6 10  14/ \5   7

AVL 树适用于读操作比较多的场景，如字典树、哈希表等数据结构，以及需要保证数据有序性的场景，如数据库中的索引。

2.2.2 红黑树

红黑树是一种自平衡的二叉查找树，具有以下特性：

• 每个节点要么是红色，要么是黑色。
• 根节点是黑色。
• 每个叶子节点（NIL 节点，空节点）是黑色的。
• 如果一个节点是红色的，则它的两个子节点都是黑色的。
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

红黑树的这些特性保证了树的高度平衡，使得查找、插入和删除操作的时间复杂度均为 O(log n)。

示例：

           8B/   \4R    12R/ \   /  \2B 6B 10B 14B/ \5R 7R

红黑树的平衡度比 AVL 树稍低，因此在进行插入和删除操作时需要进行的旋转操作较少，但是在查找操作时效率仍然较高。红黑树适用于读写操作比较均衡的场景。

2.3 小结

红黑树是一种自平衡的二叉查找树，通过颜色的约束来维持树的平衡，使得查找、插入和删除操作的时间复杂度均为 O(log n)。红黑树适用于需要平衡二叉查找树的场景，特别是在读写操作比较均衡的情况下。通过理解红黑树的特性和操作，可以更好地选择合适的数据结构来满足需求。

3 TreeMap 的特点

• 有序性：TreeMap 中的元素按照键的自然顺序或自定义顺序进行排序。
• 插入顺序：TreeMap 不保证插入顺序，因为它基于红黑树结构。
• 查找效率：查找操作的时间复杂度为 O(log n)。

4 自然顺序

默认情况下，TreeMap 根据键的自然顺序进行排序。例如，整数按升序排列，字符串按字典顺序排列。

4.1 示例代码

/*** 默认情况下，TreeMap 是根据 key 的自然顺序排列的*/
private static void testDefaultOrder() {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=沉默王二}

4.2 源码解读

4.2.1 put方法

public V put(K key, V value) {Entry<K,V> t = root; // 将根节点赋值给变量tif (t == null) { // 如果根节点为null，说明TreeMap为空compare(key, key); // type (and possibly null) check，检查key的类型是否合法root = new Entry<>(key, value, null); // 创建一个新节点作为根节点size = 1; // size设置为1return null; // 返回null，表示插入成功}int cmp;Entry<K,V> parent;// split comparator and comparable paths，根据使用的比较方法进行查找Comparator<? super K> cpr = comparator; // 获取比较器if (cpr != null) { // 如果使用了Comparatordo {parent = t; // 将当前节点赋值给parentcmp = cpr.compare(key, t.key); // 使用Comparator比较key和t的键的大小if (cmp < 0) // 如果key小于t的键t = t.left; // 在t的左子树中查找else if (cmp > 0) // 如果key大于t的键t = t.right; // 在t的右子树中查找else // 如果key等于t的键return t.setValue(value); // 直接更新t的值} while (t != null);}else { // 如果没有使用Comparatorif (key == null) // 如果key为nullthrow new NullPointerException(); // 抛出NullPointerException异常Comparable<? super K> k = (Comparable<? super K>) key; // 将key强制转换为Comparable类型do {parent = t; // 将当前节点赋值给parentcmp = k.compareTo(t.key); // 使用Comparable比较key和t的键的大小if (cmp < 0) // 如果key小于t的键t = t.left; // 在t的左子树中查找else if (cmp > 0) // 如果key大于t的键t = t.right; // 在t的右子树中查找else // 如果key等于t的键return t.setValue(value); // 直接更新t的值} while (t != null);}// 如果没有找到相同的键，需要创建一个新节点插入到TreeMap中Entry<K,V> e = new Entry<>(key, value, parent); // 创建一个新节点if (cmp < 0) // 如果key小于parent的键parent.left = e; // 将e作为parent的左子节点elseparent.right = e; // 将e作为parent的右子节点fixAfterInsertion(e); // 插入节点后需要进行平衡操作size++; // size加1return null; // 返回null，表示插入成功
}

• 首先定义一个Entry类型的变量t，用于表示当前的根节点；
• 如果t为null，说明TreeMap为空，直接创建一个新的节点作为根节点，并将size设置为1；
• 如果t不为null，说明需要在TreeMap中查找键所对应的节点。因为TreeMap中的元素是有序的，所以可以使用二分查找的方式来查找节点；
• 如果TreeMap中使用了Comparator来进行排序，则使用Comparator进行比较，否则使用Comparable进行比较。如果查找到了相同的键，则直接更新键所对应的值；
• 如果没有查找到相同的键，则创建一个新的节点，并将其插入到TreeMap中。然后使用fixAfterInsertion()方法来修正插入节点后的平衡状态；
• 最后将TreeMap的size加1，然后返回null。如果更新了键所对应的值，则返回原先的值。

4.2.2 compareTo方法

注意 cmp = k.compareTo(t.key) 这行代码，就是用来进行 key 比较的，由于此时 key 是 Integer，所以就会调用 Integer 类的 compareTo() 方法进行比较。

public static int compare(int x, int y) {return (x < y) ? -1 : ((x == y) ? 0 : 1);
}

如果此时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;
}

• 来看下面的示例

private static void testTreeMapString() {TreeMap<String,String> mapString = new TreeMap<>();mapString.put("c", "沉默王二");mapString.put("b", "沉默王二");mapString.put("a", "沉默王二");mapString.put("e", "沉默王二");mapString.put("d", "沉默王二");System.out.println(mapString);
}

• 运行结果：

{a=沉默王二, b=沉默王二, c=沉默王二, d=沉默王二, e=沉默王二}

从结果可以看得出，是按照字母的升序进行排序的。

5 自定义排序

可以通过在创建 TreeMap 时指定 Comparator 来实现自定义排序。

5.1 示例代码

/*** 自定义排序：按照整数逆序*/
private static void testTreeMapIntReverse() {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=沉默王二}

5.2 代码解读

TreeMap 提供了可以指定排序规则的构造方法：

public TreeMap(Comparator<? super K> comparator) {this.comparator = comparator;
}

Comparator.reverseOrder() 返回的是 Collections.ReverseComparator 对象，就是用来反转顺序的。

private static class ReverseComparatorimplements Comparator<Comparable<Object>>, Serializable {// 单例模式，用于表示逆序比较器static final ReverseComparator REVERSE_ORDER= new ReverseComparator();// 实现比较方法，对两个实现了Comparable接口的对象进行逆序比较public int compare(Comparable<Object> c1, Comparable<Object> c2) {return c2.compareTo(c1); // 调用c2的compareTo()方法，以c1为参数，实现逆序比较}// 反序列化时，返回Collections.reverseOrder()，保证单例模式private Object readResolve() {return Collections.reverseOrder();}// 返回正序比较器@Overridepublic Comparator<Comparable<Object>> reversed() {return Comparator.naturalOrder();}
}

6 排序的好处

TreeMap 的有序性使得在某些场景下非常方便，例如：

• 获取最大和最小的键。
• 获取小于或大于某个值的所有键。

示例代码：

/*** headMap、tailMap、subMap方法分别获取了小于3、大于等于4、大于等于2且小于4的键值对*/
private static void testTreeMap() {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");// headMap示例，获取小于3的键值对Map<Integer, String> headMap = treeMap.headMap(3);System.out.println(headMap); // 输出 {1=value1, 2=value2}// tailMap示例，获取大于等于4的键值对Map<Integer, String> tailMap = treeMap.tailMap(4);System.out.println(tailMap); // 输出 {4=value4, 5=value5}// subMap示例，获取大于等于2且小于4的键值对Map<Integer, String> subMap = treeMap.subMap(2, 4);System.out.println(subMap); // 输出 {2=value2, 3=value3}
}

运行结果：

{1=value1, 2=value2}
{4=value4, 5=value5}
{2=value2, 3=value3}

7 如何选择 Map

在选择 Map 实现时，需要考虑以下因素：

• 排序需求：如果需要排序，选择 TreeMap；否则选择 HashMap 或 LinkedHashMap。
• 插入顺序：如果需要保持插入顺序，选择 LinkedHashMap；否则选择 TreeMap 或 HashMap。
• 查找效率：如果需要高效的查找，选择 HashMap 或 LinkedHashMap，因为它们的时间复杂度为 O(1)；而 TreeMap 的时间复杂度为 O(log n)。

特性	TreeMap	HashMap	LinkedHashMap
排序	支持	不支持	不支持
插入顺序	不保证	不保证	保证
查找效率	O(log n)	O(1)	O(1)
空间占用	通常较大	通常较小	通常较大
适用场景	需要排序的场景	无需排序的场景	需要保持插入顺序

8 总结

TreeMap 通过红黑树实现，能够保持元素的自然顺序或自定义顺序，适用于需要排序的场景。虽然 TreeMap 的查找效率为 O(log n)，但在需要排序的场景下，它是一个非常有用的工具。通过理解 TreeMap 的特点和使用场景，可以更好地选择合适的 Map 实现来满足需求。

9 思维导图

10 参考链接

Java TreeMap详解：从源码分析到实践应用