Java 集合框架：TreeMap 的介绍、使用、原理与源码解析
大家好，我是栗筝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进行排序。- 两者都非线程安全，如果需要线程安全的操作，需使用其他线程安全的实现。
原文地址：https://blog.csdn.net/weixin_45187434/article/details/140643080
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！