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详解:从源码分析到实践应用