阅读量:0
大家好，我是栗筝i，这篇文章是我的 “栗筝i 的 Java 技术栈” 专栏的第 021 篇文章，在 “栗筝i 的 Java 技术栈” 这个专栏中我会持续为大家更新 Java 技术相关全套技术栈内容。专栏的主要目标是已经有一定 Java 开发经验，并希望进一步完善自己对整个 Java 技术体系来充实自己的技术栈的同学。与此同时，本专栏的所有文章，也都会准备充足的代码示例和完善的知识点梳理，因此也十分适合零基础的小白和要准备工作面试的同学学习。当然，我也会在必要的时候进行相关技术深度的技术解读，相信即使是拥有多年 Java 开发经验的从业者和大佬们也会有所收获并找到乐趣。
–
在 Java 的集合框架中，
TreeMap是一种重要的数据结构，它基于红黑树实现，提供了有序的键值对存储方式。与HashMap不同，TreeMap保证了元素的顺序性，使得我们可以在集合中按自然顺序或自定义顺序进行排序和查找。这使得TreeMap在需要排序的数据操作中表现出色，尤其适合处理有序的数据集合和范围查询。
TreeMap的实现原理涉及红黑树，一种自平衡的二叉搜索树。这种树结构能够在O(log n)时间复杂度内完成插入、删除和查找操作。与之相比，HashMap的操作虽然平均时间复杂度为O(1)，但不保持元素的顺序。因此，TreeMap在需要保持键顺序的场景中显得尤为重要。本文将深入探讨
TreeMap的使用方法、内部原理及其源码实现。我们将从基本概念和常见操作入手，逐步分析TreeMap的实现细节。通过对源码的解析，您将能够深入理解TreeMap的工作机制，从而在实际编程中更好地利用这一强大的数据结构。无论您是 Java 初学者还是有经验的开发者，都能通过本篇文章获得对TreeMap更加深入的认识和实践经验。
文章目录
1、TreeMap 概述
1.1、TreeMap 介绍
Map 在 Java 里面分为两种：HashMap 和 TreeMap，区别就是 TreeMap 有序，HashMap 无序。如果只需要存映射，那么 HashMap 就够了，但是如果需要存有顺序的 key 那么就用 TreeMap。
TreeMap 存储 K-V 键值对，通过红黑树（R-B tree）实现。TreeMap 继承了 NavigableMap 接口，NavigableMap 接口继承了 SortedMap 接口，可支持一系列的导航定位以及导航操作的方法，当然只是提供了接口，需要 TreeMap 自己去实现；TreeMap 实现了 Cloneable 接口，可被克隆，实现了 Serializable 接口，可序列化；TreeMap 因为是通过红黑树实现，红黑树结构天然支持排序，默认情况下通过 Key 值的自然顺序进行排序。
TreeMap 是一个能比较元素大小的 Map 集合，会对传入的 key 进行了大小排序。可以使用元素的自然顺序，也可以使用集合中自定义的比较器来进行排序。
TreeMap 的特点：
- TreeMap 是有序的 key-value 集合，通过红黑树实现。根据键的自然顺序进行排序或根据提供的 Comparator 进行排序。
- TreeMap 继承了 AbstractMap，实现了 NavigableMap 接口，支持一系列的导航方法，给定具体搜索目标，可以返回最接近的匹配项。如
floorEntry()、ceilingEntry()分别返回小于等于、大于等于给定键关联的Map.Entry()对象，不存在则返回 null。lowerKey()、floorKey、ceilingKey、higherKey()只返回关联的key。
1.2、红黑树回顾
红⿊树和 AVL 树 类似，都是在进⾏插⼊和删除时通过旋转保持⾃身平衡，从⽽获得较⾼的查找性能。与 AVL 树 相⽐，红⿊树不追求所有递归⼦树的⾼度差不超过 1，保证从根节点到叶尾的最⻓路径不超过最短路径的 2 倍，所以最差时间复杂度是 O(logn)。
红⿊树通过重新着⾊和左右旋转，更加⾼效地完成了插⼊和删除之后的⾃平衡调整。红⿊树在本质上还是⼆叉查找树，它额外引⼊了 5 个约束条件： ① 节点只能是红⾊或⿊⾊。 ② 根节点必须是⿊⾊。 ③ 所有 NIL 节点都是⿊⾊的。 ④ ⼀条路径上不能出现相邻的两个红⾊节点。 ⑤ 在任何递归⼦树中，根节点到叶⼦节点的所有路径上包含相同数⽬的⿊⾊节点。
这五个约束条件保证了红⿊树的新增、删除、查找的最坏时间复杂度均为 O(logn)。如果⼀个树的左⼦节点或右⼦节点不存在，则均认定为⿊⾊。红⿊树的任何旋转在 3 次之内均可完成。
2、TreeMap 底层实现
2.1、TreeMap 底层结构
TreeMap 类是一个基于红黑树的实现，TreeMap 维护了键的有序性。提供了几种构造函数来初始化映射，包括使用自然顺序、指定比较器、从已有映射构造等。内部的 Entry 类表示树中的节点，每个节点包含了键、值、子节点和父节点的引用，以及节点的颜色标记（红黑树特性）。
public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable { /** * 用于维护树映射中顺序的比较器，如果为 null，则使用键的自然顺序。 * * @serial */ private final Comparator<? super K> comparator; private transient Entry<K,V> root; // 树的根节点，使用 transient 以防序列化 /** * 树中的条目数量 */ private transient int size = 0; /** * 树的结构性修改次数 */ private transient int modCount = 0; /** * 构造一个新的空的树映射，使用键的自然顺序。所有插入到映射中的键必须实现 {@link Comparable} 接口。 * 此外，所有这些键必须是 <em>相互可比较</em>：{@code k1.compareTo(k2)} 对于映射中的任何键 {@code k1} 和 {@code k2} * 不得抛出 {@code ClassCastException}。如果用户尝试将一个违反此约束的键插入到映射中（例如，用户尝试 * 将字符串键插入到一个键为整数的映射中），{@code put(Object key, Object value)} 调用将抛出 {@code ClassCastException}。 */ public TreeMap() { comparator = null; } /** * 构造一个新的空的树映射，按照给定的比较器排序。所有插入到映射中的键必须通过给定的比较器进行 <em>相互可比较</em>： * {@code comparator.compare(k1, k2)} 对于映射中的任何键 {@code k1} 和 {@code k2} 不得抛出 {@code ClassCastException}。 * 如果用户尝试将一个违反此约束的键插入到映射中，{@code put(Object key, Object value)} 调用将抛出 {@code ClassCastException}。 * * @param comparator 用于排序此映射的比较器。如果 {@code null}，则使用 {@linkplain Comparable 自然顺序}。 */ public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; } /** * 构造一个新的树映射，包含与给定映射相同的映射，根据键的 <em>自然顺序</em> 进行排序。 * 所有插入到新映射中的键必须实现 {@link Comparable} 接口。此外，所有这些键必须是 <em>相互可比较</em>： * {@code k1.compareTo(k2)} 对于映射中的任何键 {@code k1} 和 {@code k2} 不得抛出 {@code ClassCastException}。 * 此方法的运行时间为 n*log(n)。 * * @param m 要放置在此映射中的映射 * @throws ClassCastException 如果 m 中的键不是 {@link Comparable}，或不是相互可比较的 * @throws NullPointerException 如果指定的映射为 null */ public TreeMap(Map<? extends K, ? extends V> m) { comparator = null; putAll(m); } /** * 构造一个新的树映射，包含与指定的排序映射相同的映射，并使用相同的排序。 * 此方法的运行时间为线性时间。 * * @param m 要放置在此映射中的排序映射，及其比较器将用于排序此映射 * @throws NullPointerException 如果指定的映射为 null */ public TreeMap(SortedMap<K, ? extends V> m) { comparator = m.comparator(); try { buildFromSorted(m.size(), m.entrySet().iterator(), null, null); } catch (java.io.IOException cannotHappen) { } catch (ClassNotFoundException cannotHappen) { } } } Entry 类:表示树中的一个节点，包含键、值、左右子节点和父节点的引用。提供了基本的 Map.Entry 方法实现，包括获取键值对、设置值以及判断相等和生成哈希码的方法。
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; // 节点颜色，红黑树的颜色标记 /** * 创建一个具有给定键、值和父节点的新的节点，并且子节点链接为 {@code null}，颜色为黑色。 */ Entry(K key, V value, Entry<K,V> parent) { this.key = key; this.value = value; this.parent = parent; } /** * 返回键。 * * @return 键 */ public K getKey() { return key; } /** * 返回与键关联的值。 * * @return 与键关联的值 */ public V getValue() { return value; } /** * 用给定的值替换当前与键关联的值。 * * @return 调用此方法之前与键关联的值 */ public V setValue(V value) { V oldValue = this.value; this.value = value; return oldValue; } public boolean equals(Object o) { if (!(o instanceof Map.Entry)) return false; Map.Entry<?,?> e = (Map.Entry<?,?>)o; return valEquals(key,e.getKey()) && valEquals(value,e.getValue()); } public int hashCode() { int keyHash = (key==null ? 0 : key.hashCode()); int valueHash = (value==null ? 0 : value.hashCode()); return keyHash ^ valueHash; } public String toString() { return key + "=" + value; } } 2.2、添加元素
put 方法在 TreeMap 中用于插入或更新键值对。首先，它检查树是否为空，若为空则创建一个新根节点。如果树非空，它根据提供的比较器或自然排序路径遍历树，找到适合插入的位置。如果键已存在，则更新对应的值。插入新节点后，调用 fixAfterInsertion 方法修复树的结构以维持红黑树的平衡性，并更新树的大小和结构修改次数。
/** * 将指定的值与指定的键关联在此映射中。 * 如果映射中之前包含该键的映射，则替换旧值。 * * @param key 与指定的值关联的键 * @param value 要与指定键关联的值 * * @return 之前与 {@code key} 关联的值，如果 {@code key} 没有映射，则返回 {@code null}。 * （{@code null} 的返回值也可能表示映射中之前与 {@code key} 关联了 {@code null}。） * @throws ClassCastException 如果指定的键无法与当前映射中的键进行比较 * @throws NullPointerException 如果指定的键为 {@code null} 并且此映射使用自然排序，或其比较器 * 不允许 {@code null} 键 */ public V put(K key, V value) { // 获取树的根节点 Entry<K,V> t = root; // 如果树为空，则插入新的根节点 if (t == null) { // 检查键的类型（以及可能的 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(); // 不允许 null 键 @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; } fixAfterInsertion 方法用于在 TreeMap 中插入新节点后修复红黑树的平衡性。它通过调整节点颜色和旋转操作来维护红黑树的性质，确保树的高度平衡。具体来说，当插入节点的父节点为红色时，根据其叔父节点的颜色和位置，进行节点颜色调整和必要的旋转操作，最后确保根节点始终为黑色。
/** * 插入节点后的修复方法，用于保持红黑树的平衡性。 * * @param x 插入的节点 */ private void fixAfterInsertion(Entry<K,V> x) { // 将新插入节点的颜色设为红色 x.color = RED; // 当 x 节点存在且不是根节点，且 x 节点的父节点是红色时 while (x != null && x != root && x.parent.color == RED) { // 如果 x 节点的父节点是祖父节点的左子节点 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { // 获取 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 节点继续修复 x = parentOf(parentOf(x)); } else { // 如果 x 节点是其父节点的右子节点 if (x == rightOf(parentOf(x))) { // 将 x 节点的父节点作为新的 x 节点，进行左旋操作 x = parentOf(x); rotateLeft(x); } // 将父节点设为黑色，祖父节点设为红色，进行右旋操作 setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } else { // 如果 x 节点的父节点是祖父节点的右子节点 // 获取 x 节点的叔父节点（祖父节点的左子节点） 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 节点继续修复 x = parentOf(parentOf(x)); } else { // 如果 x 节点是其父节点的左子节点 if (x == leftOf(parentOf(x))) { // 将 x 节点的父节点作为新的 x 节点，进行右旋操作 x = parentOf(x); rotateRight(x); } // 将父节点设为黑色，祖父节点设为红色，进行左旋操作 setColor(parentOf(x), BLACK); setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); } } } // 将根节点的颜色设为黑色 root.color = BLACK; } 2.3、删除元素
TreeMap 的删除操作包括三个主要步骤：首先，通过 getEntry 方法查找指定键的节点。如果节点存在，调用 deleteEntry 方法删除该节点。在删除过程中，如果节点有两个子节点，将其替换为后继节点；如果只有一个子节点或没有子节点，则直接更新父节点的链接，并处理可能引发的树结构不平衡问题，最终确保红黑树的性质。删除操作完成后，更新树的大小和修改计数器。
static final class Entry<K,V> implements Map.Entry<K,V> { public V remove(Object key) { TreeMap.Entry<K,V> p = getEntry(key); // 查找指定键对应的节点 if (p == null) return null; // 如果找不到节点，返回 null V oldValue = p.value; // 记录旧值 deleteEntry(p); // 删除节点 return oldValue; // 返回被删除节点的值 } /** * 删除 TreeMap 中所有的映射，清空 map。 * 调用此方法后，map 为空。 */ public void clear() { modCount++; // 增加修改计数 size = 0; // 清空大小 root = null; // 设置根节点为 null } /** * 删除节点 p，并重新平衡树。 */ private void deleteEntry(TreeMap.Entry<K,V> p) { modCount++; // 增加修改计数 size--; // 减少元素数量 // 如果节点 p 有两个子节点 if (p.left != null && p.right != null) { TreeMap.Entry<K,V> s = successor(p); // 找到 p 的后继节点 p.key = s.key; // 用后继节点的键替换当前节点的键 p.value = s.value; // 用后继节点的值替换当前节点的值 p = s; // 将 p 指向后继节点 } // p 现在只有一个子节点或没有子节点 TreeMap.Entry<K,V> replacement = (p.left != null ? p.left : p.right); // 确定替换节点 if (replacement != null) { // 将替换节点链接到 p 的父节点 replacement.parent = p.parent; if (p.parent == null) root = replacement; // 如果 p 是根节点，更新根节点 else if (p == p.parent.left) p.parent.left = replacement; // 如果 p 是父节点的左子节点 else p.parent.right = replacement; // 如果 p 是父节点的右子节点 // 清除 p 的链接以便后续修复使用 p.left = p.right = p.parent = null; // 修复替换节点 if (p.color == BLACK) fixAfterDeletion(replacement); } else if (p.parent == null) { // 如果节点 p 是唯一的节点 root = null; // 设置根节点为 null } else { // 节点 p 没有子节点 if (p.color == BLACK) fixAfterDeletion(p); // 修复删除操作后的树结构 if (p.parent != null) { if (p == p.parent.left) p.parent.left = null; // 更新父节点的左子节点 else if (p == p.parent.right) p.parent.right = null; // 更新父节点的右子节点 p.parent = null; // 清除父节点 } } } } 2.4、查询元素
TreeMap 的 get 方法通过调用 getEntry 查找指定键的 Entry 节点。getEntry 根据是否使用比较器来决定使用哪种查找策略：若使用比较器，则调用 getEntryUsingComparator 进行查找；否则，通过比较键的自然顺序在树中遍历。最终，get 返回找到的节点的值，或在键不存在时返回 null。
static final class Entry<K,V> implements Map.Entry<K,V> { /** * 根据指定的键获取对应的值。 * 如果树中存在该键，则返回对应的值；否则返回 null。 * * @param key 要查找的键 * @return 如果键存在，则返回与键对应的值；否则返回 null */ public V get(Object key) { TreeMap.Entry<K,V> p = getEntry(key); return (p == null ? null : p.value); } /** * 返回该映射中给定键的条目，如果该键不存在，则返回 {@code null}。 * * @param key 要查找的键 * @return 该映射中给定键的条目，如果该键不存在，则返回 {@code null} * @throws ClassCastException 如果指定的键无法与当前映射中的键进行比较 * @throws NullPointerException 如果指定的键为 null 并且该映射使用自然排序，或者其比较器不允许 null 键 */ final TreeMap.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; TreeMap.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; } /** * 使用比较器版本的 getEntry 方法。为了性能优化，单独分离出来。 * * @param key 要查找的键 * @return 给定键的条目，如果该键不存在，则返回 {@code null} */ final TreeMap.Entry<K,V> getEntryUsingComparator(Object key) { @SuppressWarnings("unchecked") K k = (K) key; Comparator<? super K> cpr = comparator; if (cpr != null) { TreeMap.Entry<K,V> p = root; while (p != null) { int cmp = cpr.compare(k, p.key); if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p; } } return null; } } 3、TreeMap 相关知识点
3.1、HashMap 和 TreeMap 的实现
HashMap:
- 基于哈希表实现。
- 键需要实现
hashCode()和equals()方法（可以重写）。 - 支持通过调节初始容量和负载因子来优化空间使用。
- 构造方法：
HashMap(): 构建一个空的哈希映射。HashMap(Map m): 构建一个哈希映射，并添加映射m的所有映射。HashMap(int initialCapacity): 构建一个具有特定容量的空哈希映射。HashMap(int initialCapacity, float loadFactor): 构建一个具有特定容量和负载因子的空哈希映射。
TreeMap:
- 基于红黑树实现。
- 自动保持树的平衡状态，无需手动调整。
- 构造方法：
TreeMap(): 构建一个空的映射树。TreeMap(Map m): 构建一个映射树，并添加映射m中的所有元素。TreeMap(Comparator c): 构建一个映射树，并使用特定的比较器对键进行排序。TreeMap(SortedMap s): 构建一个映射树，并添加映射树s中的所有映射，使用与s相同的比较器排序。
3.2、HashMap 和 TreeMap 的线程安全性
两者均为非线程安全。若需线程安全的操作，可以使用 Collections.synchronizedMap 或 ConcurrentHashMap。
3.3、SortedMap 接口
SortedMap 接口保证了键的有序性。它提供了视图（子集）和访问方法，但元素必须实现 Comparable 接口，或提供一个 Comparator 实现。TreeMap 是 SortedMap 的唯一实现。
3.4、自定义比较器实现降序排序
通过实现 Comparator 接口，可以定义自定义比较器来控制 TreeMap 的排序方式。例如，以下代码演示了如何实现降序排序：
import java.util.*; public class MapTest { public static void main(String[] args) { // 初始化自定义比较器 MyComparator comparator = new MyComparator(); // 初始化一个map集合 Map<String, String> map = new TreeMap<>(comparator); // 存入数据 map.put("a", "a"); map.put("b", "b"); map.put("f", "f"); map.put("d", "d"); map.put("c", "c"); map.put("g", "g"); // 遍历输出 Iterator<String> iterator = map.keySet().iterator(); while (iterator.hasNext()) { String key = iterator.next(); System.out.println(map.get(key)); } } static class MyComparator implements Comparator<String> { @Override public int compare(String o1, String o2) { // 反向比较实现降序排序 return -o1.compareTo(o2); } } } 总结：
HashMap提供快速的查找、插入和删除操作，适用于无序数据；而TreeMap提供有序的键值对存储，支持范围查找和排序操作。HashMap需要正确实现hashCode()和equals()，TreeMap需要实现Comparable接口或提供Comparator进行排序。- 两者都非线程安全，如果需要线程安全的操作，需使用其他线程安全的实现。
