大家好，我是栗筝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 介绍
      • 1.2、红黑树回顾
    • 2、TreeMap 底层实现
    • • 2.1、TreeMap 底层结构
      • 2.2、添加元素
      • 2.3、删除元素
      • 2.4、查询元素
    • 3、TreeMap 相关知识点
    • • 3.1、`HashMap` 和 `TreeMap` 的实现
      • 3.2、`HashMap` 和 `TreeMap` 的线程安全性
      • 3.3、`SortedMap` 接口
      • 3.4、自定义比较器实现降序排序

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 的特点：

1. TreeMap 是有序的 key-value 集合，通过红黑树实现。根据键的自然顺序进行排序或根据提供的 Comparator 进行排序。
2. 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     extends AbstractMap     implements NavigableMap, Cloneable, java.io.Serializable {     /**      * 用于维护树映射中顺序的比较器，如果为 null，则使用键的自然顺序。      *      * @serial      */     private final Comparator comparator;      private transient Entry root; // 树的根节点，使用 transient 以防序列化      /**      * 树中的条目数量      */     private transient int size = 0;      /**      * 树的结构性修改次数      */     private transient int modCount = 0;      /**      * 构造一个新的空的树映射，使用键的自然顺序。所有插入到映射中的键必须实现 {@link Comparable} 接口。      * 此外，所有这些键必须是 相互可比较：{@code k1.compareTo(k2)} 对于映射中的任何键 {@code k1} 和 {@code k2}      * 不得抛出 {@code ClassCastException}。如果用户尝试将一个违反此约束的键插入到映射中（例如，用户尝试      * 将字符串键插入到一个键为整数的映射中），{@code put(Object key, Object value)} 调用将抛出 {@code ClassCastException}。      */     public TreeMap() {         comparator = null;     }      /**      * 构造一个新的空的树映射，按照给定的比较器排序。所有插入到映射中的键必须通过给定的比较器进行 相互可比较：      * {@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 comparator) {         this.comparator = comparator;     }      /**      * 构造一个新的树映射，包含与给定映射相同的映射，根据键的 自然顺序 进行排序。      * 所有插入到新映射中的键必须实现 {@link Comparable} 接口。此外，所有这些键必须是 相互可比较：      * {@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 m) {         comparator = null;         putAll(m);     }      /**      * 构造一个新的树映射，包含与指定的排序映射相同的映射，并使用相同的排序。      * 此方法的运行时间为线性时间。      *      * @param  m 要放置在此映射中的排序映射，及其比较器将用于排序此映射      * @throws NullPointerException 如果指定的映射为 null      */     public TreeMap(SortedMap 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 implements Map.Entry {     K key; // 键     V value; // 值     Entry left;   // 左子节点     Entry right;  // 右子节点     Entry parent; // 父节点     boolean color = BLACK; // 节点颜色，红黑树的颜色标记      /**      * 创建一个具有给定键、值和父节点的新的节点，并且子节点链接为 {@code null}，颜色为黑色。      */     Entry(K key, V value, Entry 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 t = root;      // 如果树为空，则插入新的根节点     if (t == null) {         // 检查键的类型（以及可能的 null 值）         compare(key, key);          // 创建一个新的根节点         root = new Entry<>(key, value, null);         size = 1;  // 更新树的大小         modCount++;  // 记录结构修改次数         return null;     }      int cmp;     Entry parent;     // 使用比较器或自然排序路径     Comparator 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 k = (Comparable) 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 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 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 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 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 implements Map.Entry {     public V remove(Object key) {         TreeMap.Entry 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 p) {         modCount++; // 增加修改计数         size--; // 减少元素数量          // 如果节点 p 有两个子节点         if (p.left != null && p.right != null) {             TreeMap.Entry s = successor(p); // 找到 p 的后继节点             p.key = s.key; // 用后继节点的键替换当前节点的键             p.value = s.value; // 用后继节点的值替换当前节点的值             p = s; // 将 p 指向后继节点         } // p 现在只有一个子节点或没有子节点          TreeMap.Entry 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 implements Map.Entry { 	  /**      * 根据指定的键获取对应的值。      * 如果树中存在该键，则返回对应的值；否则返回 null。      *      * @param key 要查找的键      * @return 如果键存在，则返回与键对应的值；否则返回 null      */     public V get(Object key) {         TreeMap.Entry 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 getEntry(Object key) {         // 针对使用比较器的版本进行优化以提高性能         if (comparator != null)             return getEntryUsingComparator(key);         if (key == null)             throw new NullPointerException();         @SuppressWarnings("unchecked")         Comparable k = (Comparable) key;         TreeMap.Entry 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 getEntryUsingComparator(Object key) {         @SuppressWarnings("unchecked")         K k = (K) key;         Comparator cpr = comparator;         if (cpr != null) {             TreeMap.Entry 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 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 iterator = map.keySet().iterator();         while (iterator.hasNext()) {             String key = iterator.next();             System.out.println(map.get(key));         }     }      static class MyComparator implements Comparator {         @Override         public int compare(String o1, String o2) {             // 反向比较实现降序排序             return -o1.compareTo(o2);         }     } } 

总结：

• HashMap 提供快速的查找、插入和删除操作，适用于无序数据；而 TreeMap 提供有序的键值对存储，支持范围查找和排序操作。
• HashMap 需要正确实现 hashCode() 和 equals()，TreeMap 需要实现 Comparable 接口或提供 Comparator 进行排序。
• 两者都非线程安全，如果需要线程安全的操作，需使用其他线程安全的实现。