首页 › Java论坛 › TreeMap集合--底层原理、源码阅读及它在Java集合框架中扮演什么角色？

罗时庚 發表於 2025-7-21 08:22:00

TreeMap集合--底层原理、源码阅读及它在Java集合框架中扮演什么角色？

<h2 id="1-treemap底层数据结构">1. TreeMap底层数据结构</h2>
<p><strong>TreeMap</strong> 是 Java 集合框架中基于 <strong>红黑树</strong>（Red‑Black Tree）实现的一个 <strong>有序映射</strong>。</p>
<p>它的数据结构非常简单，只使用了<strong>红黑树</strong>一种数据结构，不像<code>HashMap</code>和<code>LinkedHashMap</code> 那么复杂。</p>
<p><strong>Entry内部类字段</strong>：</p>
<pre><code class="language-java">static final class Entry&lt;K,V&gt; implements Map.Entry&lt;K,V&gt; {
        K key;
        V value;
        Entry&lt;K,V&gt; left;       //左子节点
        Entry&lt;K,V&gt; right;      //右子节点
        Entry&lt;K,V&gt; parent;   //父节点
        boolean color = BLACK; //节点颜色：BLACK=true, RED=false
}
</code></pre>
<p>key、value和color为当前对象的值，其它字段为构成红黑树所需的节点对象。数据结构如图：</p>
<img src="https://img2024.cnblogs.com/blog/1209017/202507/1209017-20250720224201170-407435935.jpg" alt="" width="50%">
<p>在Java中所有集合都是保存引用对象的引用，而非对象的值。<code>TreeMap</code>也是如此，在<code>Entry</code>对象中的<code>Entry&lt;K,V&gt; left、Entry&lt;K,V&gt; right、Entry&lt;K,V&gt; parent</code> 都只是保存着对象的引用（可以理解为地址指向），而非具体的值。</p>
<p><code>Map</code>集合的<strong>共性</strong>，只要知道<code>key</code>如何计算，便可知道<code>value</code>所在位置。在<code>TreeMap</code>中也是如此，最需要关注的是<code>key</code>在红黑树中的处理。</p>
<p>例如下图key在TreeMap中的存储：</p>
<img src="https://img2024.cnblogs.com/blog/1209017/202507/1209017-20250720224219586-836423646.jpg" alt="" width="50%">
<h2 id="2-treemap-的特点">2. TreeMap 的特点</h2>
<p><strong>TreeMap</strong> 是 基于 <strong>红黑树</strong>（Red‑Black Tree）实现的一个 <strong>有序映射</strong>，特点是<strong>有序</strong>。这是由底层数据结构所带来的有序特性。</p>
<p>红黑树是一种<strong>自平衡二叉查找树</strong>，是一种有序的二叉树，按照<strong>左中右</strong>从小到大排序。</p>
<p><code>HashMap</code> 同样也使用了红黑树，那是不是<code>HashMap</code>关于红黑树的那部分元素是有序的？没错，在<code>HashMap</code>中红黑树部分的元素是有序的，但是，它的有序性是根据<code>key</code>的<code>hash</code>值进行的排序，并且<code>hash</code>值在计算的过程中进行了扰动，就算没有扰动，<code>hash</code>值的有序<strong>对于使用者</strong>来说也没有意义，这种有序性仅用于维持红黑树。</p>
<p>而<code>TreeMap</code>集合的<strong>有序性</strong>是key值的有序，是<strong>根据key值进行的排序</strong>，这种有序性对于使用者来说才有实际性的价值。</p>
<p>哪么如何根据key值进行的排序呢？</p>
<h3 id="21-treemap如何比较key值大小">2.1. TreeMap如何比较key值大小？</h3>
<p>默认情况的比较，又称为<strong>自然顺序比较</strong>。<code>TreeMap</code>内部假定所有键类型都实现了 <code>Comparable</code> 接口，会直接调用key对象的中比较方法进行比较。</p>
<p>在插入、查找或删除时，会执行强制类型转换并调用：</p>
<pre><code class="language-java">((Comparable&lt;? super K&gt;) key).compareTo(existingKey)
</code></pre>
<p>以确定 <code>key</code> 与树中节点 <code>existingKey</code> 的相对顺序（&lt;0：key 更小；=0：相等；&gt;0：key 更大）。</p>
<p>如果key对象未实现 <code>Comparable</code>，或尝试比较不同类型但不具备可比性的对象，将在运行时抛出 <code>ClassCastException</code>。</p>
<p><strong>重点</strong>：</p>
<blockquote>
<p>默认情况key值对象必须实现 <code>Comparable</code> 接口，并重写比较方法<code>compareTo</code>；</p>
<p>默认情况下 <strong>不允许</strong> <code>null</code> <strong>键</strong>，因为对 <code>null</code> 调用 <code>compareTo</code> 会导致 <code>NullPointerException</code>。</p>
</blockquote>
<p>例如需要使用<code>Person</code>类作为键值<code>key</code>，实现<code>Comparable</code>接口：</p>
<pre><code class="language-java">public class Person implements Comparable&lt;Person&gt;{
    private final String name;
    private final int age;

    public Person(String name, int age) {
      this.name = name;
      this.age = age;
    }
    @Override
    public int compareTo(Person other) {
      int ageCmp = Integer.compare(other.age, this.age); // 降序
      if (ageCmp != 0) return ageCmp;
      return this.name.compareTo(other.name); // 升序
    }
}
</code></pre>
<h3 id="22-如何自定义比较器comparator">2.2. 如何自定义比较器（Comparator）？</h3>
<p>如果key没有实现<code>Comparable</code> 接口，那么需要<strong>自定义比较器</strong>，并通过<code>TreeMap</code>的构造方法传入比较器 <code>Comparator&lt;? super K&gt;</code>，例如：</p>
<pre><code class="language-java">// 组合排序：先按 name 排序，再按 age 排序
Comparator&lt;Person&gt; cmp = Comparator
                .comparing(Person::getName)
                .thenComparingInt(Person::getAge);
Map&lt;Person,Object&gt; treeMap = new TreeMap&lt;&gt;(cmp);
</code></pre>
<p>此时所有键的比较都由指定的自定义比较器方法决定。</p>
<p>比较键值key的大小分为两种：</p>
<ul>
<li>
<p><strong>自然顺序比较</strong>：键实现<code>Comparable</code>接口，调用<code>compareTo</code>。</p>
</li>
<li>
<p><strong>自定义比较器</strong>：通过构造<code>new TreeMap&lt;&gt;(Comparator&lt;? super K&gt; comparator)</code>传入。</p>
</li>
</ul>
<h3 id="23-为何选择红黑树">2.3. 为何选择红黑树？</h3>
<p>在自平衡二叉查找树中，还有一种比较典型的AVL树，它相对于红黑树来说，平衡性的要求更严格，能够保持更高的平衡度。</p>
<p><strong>AVL树</strong>在插入和删除时会进行更多的旋转操作，以确保任意节点左右子树的<strong>高度差不超过1</strong>。而红黑树允许一定程度的不平衡，以减少调整频率，提高插入删除的效率。</p>
<p><strong>对比两者</strong>：</p>
<table>
<thead>
<tr>
<th>特性</th>
<th>AVL（强平衡）</th>
<th>红黑树（弱平衡）</th>
</tr>
</thead>
<tbody>
<tr>
<td>平衡指标</td>
<td>每个节点左右子树高度差 ≤ 1</td>
<td>根到叶子的黑色节点数相同；红节点不能相连</td>
</tr>
<tr>
<td>树高上界</td>
<td>≈ 1.44 log₂ n</td>
<td>≤ 2 log₂ n</td>
</tr>
<tr>
<td>旋转开销</td>
<td>插入/删除可能多次旋转</td>
<td>最多 2 次旋转＋若干颜色翻转</td>
</tr>
<tr>
<td>查询效率</td>
<td>常数更小（更紧凑）</td>
<td>略逊于 AVL，但常数差距不大</td>
</tr>
<tr>
<td>更新开销</td>
<td>较高（为维护严格平衡）</td>
<td>较低（弱平衡条件更松）</td>
</tr>
<tr>
<td>应用场景</td>
<td>读多写少，对查询延迟要求极高</td>
<td>读写均衡，工业生产环境首选（如 Java、C++ STL）</td>
</tr>
</tbody>
</table>
<p><strong>数据结构的选择是一种取舍的抉择。</strong> 一种语言下的数据结构，一般都是以通用情况进行考量，而做出的选择。</p>
<p>红黑树相对于AVL树来说，牺牲了部分平衡性以换取插入和删除操作时少量的旋转操作，整体来说性能要优于AVL树。</p>
<p><strong>关于AVL树和红黑树的选择：</strong></p>
<ul>
<li>
<p>当“查询性能”是唯一且最重要的考量时，AVL 的强平衡更有优势；</p>
</li>
<li>
<p>当需要在“查询”和“更新”之间做折中，且希望实现和维护都更简单时，红黑树的弱平衡更合适。</p>
</li>
</ul>
<h2 id="3-treemap在java集合框架中扮演什么角色">3. TreeMap在Java集合框架中扮演什么角色？</h2>
<p><code>TreeMap</code>与其他 Map 的对比</p>
<table>
<thead>
<tr>
<th>特性</th>
<th>HashMap</th>
<th>LinkedHashMap</th>
<th>TreeMap</th>
</tr>
</thead>
<tbody>
<tr>
<td>底层结构</td>
<td>哈希表 + 链表/红黑树</td>
<td>哈希表 + 链表（维护插入/访问顺序）</td>
<td>红黑树</td>
</tr>
<tr>
<td>键排序</td>
<td>无序</td>
<td>保持插入顺序或访问顺序</td>
<td>按键的自然顺序或 <code>Comparator</code> 排序</td>
</tr>
<tr>
<td>时间复杂度</td>
<td>O(1)O(1) 平均</td>
<td>O(1)O(1) 平均</td>
<td>O(log⁡n)O(\log n)</td>
</tr>
<tr>
<td>允许 <code>null</code> 键</td>
<td>允许一个 <code>null</code></td>
<td>允许一个 <code>null</code></td>
<td><strong>不允许</strong> <code>null</code> 键</td>
</tr>
<tr>
<td>适用场景</td>
<td>追求最快的查找/插入</td>
<td>需要按插入或访问顺序迭代</td>
<td>需要按键排序、范围查询（<code>subMap</code>）等</td>
</tr>
</tbody>
</table>
<blockquote>
<p><code>TreeMap</code> 填补了无序（<code>HashMap</code>）和插入/访问顺序（<code>LinkedHashMap</code>）之外的“键有序”需求。</p>
</blockquote>
<p><strong>应用场景</strong></p>
<ol>
<li>需要<strong>范围查询</strong>：提供了对应的方法<code>subMap、headMap、tailMap</code>，例如 <code>map.subMap(fromKey, toKey)</code> 可以高效获取区间内所有条目。</li>
<li><strong>最小/最大元素快速访问</strong>：<code>firstKey()</code>, <code>lastKey()</code>, <code>ceilingKey()</code>, <code>floorKey()</code> 等导航方法。</li>
<li><strong>按排序顺序敏感的场景</strong>：中序遍历天然保证从小到大。</li>
<li>需要按键排序的<strong>缓存</strong>或<strong>索引</strong>。</li>
</ol>
<h2 id="4-核心api与功能">4. 核心API与功能</h2>
<table>
<thead>
<tr>
<th>方法</th>
<th>描述</th>
<th>时间复杂度</th>
</tr>
</thead>
<tbody>
<tr>
<td><code>put(K key, V v)</code></td>
<td>插入或更新键值对</td>
<td>O(log n)</td>
</tr>
<tr>
<td><code>get(Object key)</code></td>
<td>根据键查找值</td>
<td>O(log n)</td>
</tr>
<tr>
<td><code>remove(Object key)</code></td>
<td>删除节点</td>
<td>O(log n)</td>
</tr>
<tr>
<td><code>subMap(K fromKey, K toKey)</code></td>
<td>获取指定范围的视图</td>
<td>O(log n)</td>
</tr>
<tr>
<td><code>firstKey()</code>, <code>lastKey()</code></td>
<td>获取最小/最大键</td>
<td>O(log n)</td>
</tr>
<tr>
<td><code>ceilingKey(K key)</code></td>
<td>&gt;=key的最小键</td>
<td>O(log n)</td>
</tr>
</tbody>
</table>
<p><code>put</code>, <code>get</code>, <code>remove</code>方法在此不演示，感受下有差异的方法。</p>
<ul>
<li>如何通过<code>subMap</code>, <code>headMap</code>, <code>tailMap</code>等视图方法获取子区间？</li>
<li><code>firstKey</code>, <code>lastKey</code>, <code>ceilingKey</code>等导航方法的使用？</li>
</ul>
<p>通过使用这些方法完成下面的案例。</p>
<h3 id="41-案例--商品订单量统计">4.1. 案例--商品订单量统计</h3>
<p>假设我们要对一款电商商品的每小时下单量进行统计，并且在任意时刻都能快速获取：</p>
<ul>
<li>
<p><strong>过去 N 小时</strong>（如过去 3 小时）的订单总量；</p>
</li>
<li>
<p><strong>某一时间段</strong>（如上午 10 点到下午 2 点）的小时级订单分布；</p>
</li>
<li>
<p><strong>最近一次下单的时间</strong>（最晚的 key）。</p>
</li>
<li>
<p>等等。。。</p>
</li>
</ul>
<p>这时，使用 <code>TreeMap&lt;LocalDateTime, Integer&gt;</code>，键按时间自然排序，就能轻松实现以上功能。</p>
<p>在此<strong>特别说明</strong><code>LocalDateTime</code>为什么可以做键值key：</p>
<blockquote>
<p>该类实现了<code>Comparable</code>接口可以做自然排序；</p>
<p>其次该类是<code>final</code>类不可被继承，同时该类的成员变量被<code>final</code>修饰，为不可变的变量。</p>
</blockquote>
<p>实例源码如下：</p>
<pre><code class="language-java">import java.time.LocalDateTime;
import java.time.format.DateTimeFormatter;
import java.util.NavigableMap;
import java.util.TreeMap;

public class MinuteOrderStats {
    // 按分钟升序存储：key = 每分钟的起始时间（秒、纳秒都为0），value = 该分钟的订单数量
    private final TreeMap&lt;LocalDateTime, Integer&gt; stats = new TreeMap&lt;&gt;();

    private final DateTimeFormatter fmt = DateTimeFormatter.ofPattern("yyyy-MM-dd HH:mm");

    /** 记录一次新订单，orderTime 精确到秒或更高 */
    public void recordOrder(LocalDateTime orderTime) {
      // 截断到分钟（保留年/月/日/时/分，秒和纳秒置零）
      LocalDateTime minute = orderTime.withSecond(0).withNano(0);
      // 累加同一分钟的新订单数，每次加1
      stats.merge(minute, 1, Integer::sum);
    }

    /** 统计从 now 向前 lookbackMinutes 分钟内的总订单量 */
    public int totalInPastMinutes(int lookbackMinutes) {
      LocalDateTime nowMin = LocalDateTime.now()
                .withSecond(0)
                .withNano(0);
      LocalDateTime from   = nowMin.minusMinutes(lookbackMinutes);
      // 包含 from 和 nowMin
      NavigableMap&lt;LocalDateTime, Integer&gt; sub = stats.subMap(from, true, nowMin, true);
      System.out.println("subMap [" + fmt.format(from) + ", " + fmt.format(nowMin) + "):");
      sub.forEach((k, v) -&gt; System.out.println("" + fmt.format(k) + " → " + v));
      return sub.values()
                .stream()
                .mapToInt(Integer::intValue)
                .sum();
    }

    /** 调试时打印所有分钟统计 */
    public void dumpAll() {
      stats.forEach((time, count) -&gt;
                System.out.println(fmt.format(time) + " → " + count));
    }

    public void demo() {
      LocalDateTime now = LocalDateTime.now().withSecond(0).withNano(0);
      LocalDateTime start = now.minusMinutes(8);// 8 分钟前
      LocalDateTime mid   = now.minusMinutes(5);// 5 分钟前
      LocalDateTime end   = now.minusMinutes(2);// 2 分钟前

      // 1. subMap(fromKey, toKey) — [from, to)
      System.out.println("\n—— 过去 5 分钟总订单量 ——");
      System.out.println("总订单量: "+totalInPastMinutes(5));

      System.out.println("\n—— 从8分钟前到2分钟前的分布 ——");
      NavigableMap&lt;LocalDateTime, Integer&gt; sub =stats.subMap(start, true, end, false);
      System.out.println("subMap [" + fmt.format(start) + ", " + fmt.format(end) + "):");
      sub.forEach((k, v) -&gt; System.out.println("" + fmt.format(k) + " → " + v));

      // 2. headMap(toKey) — (&lt; toKey)
      System.out.println("\n—— 从头到5分钟前的分布 ——");
      NavigableMap&lt;LocalDateTime, Integer&gt; head = stats.headMap(mid, false);
      System.out.println("headMap (&lt; " + fmt.format(mid) + "):");
      head.forEach((k, v) -&gt; System.out.println("" + fmt.format(k) + " → " + v));

      // 3. tailMap(fromKey) — [fromKey, ∞)
      System.out.println("\n—— 从5分钟前到末尾的分布 ——");
      NavigableMap&lt;LocalDateTime, Integer&gt; tail = stats.tailMap(mid, true);
      System.out.println("tailMap (≥ " + fmt.format(mid) + "):");
      tail.forEach((k, v) -&gt; System.out.println("" + fmt.format(k) + " → " + v));

      // 4. firstKey() — 最早的键
      System.out.println("\n—— 最早的键分布 ——");
      LocalDateTime first = stats.firstKey();
      System.out.println("firstKey(): " + fmt.format(first) + " → " + stats.get(first));

      // 5. lastKey() — 最晚的键
      System.out.println("\n—— 最晚的键分布 ——");
      LocalDateTime last = stats.lastKey();
      System.out.println("lastKey():" + fmt.format(last) + " → " + stats.get(last));

      // 6. ceilingKey(key) — ≥ key 的最小键
      System.out.println("\n—— ≥ key 的最小键的键分布 ——");
      LocalDateTime query = now.minusMinutes(6).plusSeconds(30);
      LocalDateTime ceil = stats.ceilingKey(query);
      System.out.println("ceilingKey(" + fmt.format(query) + "): "
                + (ceil != null
                ? fmt.format(ceil) + " → " + stats.get(ceil)
                : "null"));
    }

    public static void main(String[] args) throws InterruptedException {
      MinuteOrderStats os = new MinuteOrderStats();
      LocalDateTime now = LocalDateTime.now();
      LocalDateTime hourAgo = now.minusMinutes(10);
      // 模拟插入：跨 3 分钟，每隔几秒记录一次
      for (int i = 0; i &lt; 100; i++) {
            // 让时间分布在 now.minusMinutes(3) ~ now
            os.recordOrder(hourAgo.minusSeconds((3 * 60) - i * 7));
            Thread.sleep(5);
      }

      System.out.println("—— 全部分钟统计 ——");
      os.dumpAll();
      // 常见的集中操作
      os.demo();
    }
}
</code></pre>
<p><strong>案例测试结果</strong></p>
<pre><code>—— 全部分钟统计 ——
2025-06-29 23:16 → 2
2025-06-29 23:17 → 9
2025-06-29 23:18 → 8
2025-06-29 23:19 → 9
2025-06-29 23:20 → 9
2025-06-29 23:21 → 8
2025-06-29 23:22 → 9
2025-06-29 23:23 → 8
2025-06-29 23:24 → 9
2025-06-29 23:25 → 8
2025-06-29 23:26 → 9
2025-06-29 23:27 → 9
2025-06-29 23:28 → 3

—— 过去 5 分钟总订单量 ——
subMap [2025-06-29 23:24, 2025-06-29 23:29):
2025-06-29 23:24 → 9
2025-06-29 23:25 → 8
2025-06-29 23:26 → 9
2025-06-29 23:27 → 9
2025-06-29 23:28 → 3
38

—— 从8分钟前到2分钟前的分布 ——
subMap [2025-06-29 23:21, 2025-06-29 23:27):
2025-06-29 23:21 → 8
2025-06-29 23:22 → 9
2025-06-29 23:23 → 8
2025-06-29 23:24 → 9
2025-06-29 23:25 → 8
2025-06-29 23:26 → 9

—— 从头到5分钟前的分布 ——
headMap (&lt; 2025-06-29 23:24):
2025-06-29 23:16 → 2
2025-06-29 23:17 → 9
2025-06-29 23:18 → 8
2025-06-29 23:19 → 9
2025-06-29 23:20 → 9
2025-06-29 23:21 → 8
2025-06-29 23:22 → 9
2025-06-29 23:23 → 8

—— 从5分钟前到末尾的分布 ——
tailMap (≥ 2025-06-29 23:24):
2025-06-29 23:24 → 9
2025-06-29 23:25 → 8
2025-06-29 23:26 → 9
2025-06-29 23:27 → 9
2025-06-29 23:28 → 3

—— 最早的键分布 ——
firstKey(): 2025-06-29 23:16 → 2

—— 最晚的键分布 ——
lastKey():2025-06-29 23:28 → 3

—— ≥ key 的最小键的键分布 ——
ceilingKey(2025-06-29 23:23): 2025-06-29 23:24 → 9
</code></pre>
<h3 id="42-关于navigablemap接口">4.2. 关于NavigableMap接口</h3>
<p><code>TreeMap</code>实现了<code>NavigableMap</code>接口，<code>NavigableMap</code> 接口是 Java 在 <code>SortedMap</code> 基础上扩展出来的一个接口，代表<strong>可导航的有序映射表</strong>。</p>
<p>它扩展了 <code>SortedMap</code>，支持<strong>更丰富的范围查询与方向遍历操作</strong>。</p>
<p><code>TreeMap</code>实现了<code>NavigableMap</code>接口，使得<code>TreeMap</code> 具有更丰富的查询操作，已将方法汇总如下，可自行尝试。</p>
<h4 id="方法总览">方法总览</h4>
<table>
<thead>
<tr>
<th>方法名</th>
<th>返回值类型</th>
<th>描述</th>
</tr>
</thead>
<tbody>
<tr>
<td><code>lowerKey(K key)</code></td>
<td>K</td>
<td>严格小于给定键的最大键</td>
</tr>
<tr>
<td><code>floorKey(K key)</code></td>
<td>K</td>
<td>小于等于给定键的最大键</td>
</tr>
<tr>
<td><code>ceilingKey(K key)</code></td>
<td>K</td>
<td>大于等于给定键的最小键</td>
</tr>
<tr>
<td><code>higherKey(K key)</code></td>
<td>K</td>
<td>严格大于给定键的最小键</td>
</tr>
<tr>
<td><code>lowerEntry(K key)</code></td>
<td>Map.Entry&lt;K,V&gt;</td>
<td>严格小于给定键的最大条目</td>
</tr>
<tr>
<td><code>floorEntry(K key)</code></td>
<td>Map.Entry&lt;K,V&gt;</td>
<td>小于等于给定键的最大条目</td>
</tr>
<tr>
<td><code>ceilingEntry(K key)</code></td>
<td>Map.Entry&lt;K,V&gt;</td>
<td>大于等于给定键的最小条目</td>
</tr>
<tr>
<td><code>higherEntry(K key)</code></td>
<td>Map.Entry&lt;K,V&gt;</td>
<td>严格大于给定键的最小条目</td>
</tr>
<tr>
<td><code>subMap(fromKey, incl, toKey, incl)</code></td>
<td>NavigableMap</td>
<td>返回子视图，支持边界包含/排除控制</td>
</tr>
<tr>
<td><code>headMap(toKey, inclusive)</code></td>
<td>NavigableMap</td>
<td>返回 &lt;= toKey 的子视图</td>
</tr>
<tr>
<td><code>tailMap(fromKey, inclusive)</code></td>
<td>NavigableMap</td>
<td>返回 &gt;= fromKey 的子视图</td>
</tr>
<tr>
<td><code>descendingMap()</code></td>
<td>NavigableMap</td>
<td>返回一个键降序排列的视图</td>
</tr>
<tr>
<td><code>descendingKeySet()</code></td>
<td>NavigableSet</td>
<td>返回键集合的降序视图</td>
</tr>
<tr>
<td><code>pollFirstEntry()</code></td>
<td>Map.Entry&lt;K,V&gt;</td>
<td>弹出并移除最小键对应的条目</td>
</tr>
<tr>
<td><code>pollLastEntry()</code></td>
<td>Map.Entry&lt;K,V&gt;</td>
<td>弹出并移除最大键对应的条目</td>
</tr>
</tbody>
</table>
<h2 id="5-源码阅读">5. 源码阅读</h2>
<p><code>TreeMap</code> 源码的学习本质是<strong>红黑树数据结构</strong>的学习，关键源码为红黑树插入、删除和调平衡（染色和旋转），重点关注<code>TreeMap.put</code>, <code>TreeMap.remove</code>, <code>rotateLeft</code>, <code>rotateRight</code>和<code>fixAfterInsertion</code>, <code>fixAfterDeletion</code>方法。</p>
<p>这些方法中最为主要的是：<code>fixAfterInsertion</code> 和 <code>fixAfterDeletion</code>方法。</p>
<h3 id="51-插入平衡fixafterinsertion">5.1. 插入平衡：<code>fixAfterInsertion</code></h3>
<p>当你往红黑树里插入一个新节点时，通常分为两大步：</p>
<p>1.<strong>新节点染成红色</strong>（保证不破坏从根到叶子的黑色节点数一致性）。</p>
<p>2.如果它的父节点也是红色，就会违反“红色节点不能有红色子节点”这一性质，需进行修复：</p>
<blockquote>
<ul>
<li>
<p><strong>Case 1（叔叔节点也红）</strong><br>
父、叔都染黑，祖父染红，指针上移到祖父，继续检查上层。</p>
</li>
<li>
<p><strong>Case 2（叔黑，且当前节点与父节点在同一侧）</strong><br>
对父节点做一次旋转（左旋或右旋），把自己变成父的位置，再归为 Case 3。</p>
</li>
<li>
<p><strong>Case 3（叔黑，且当前节点与父节点在“外侧”）</strong><br>
将父染黑、祖父染红，然后对祖父做一次与父同方向的旋转。</p>
</li>
</ul>
</blockquote>
<p><code>fixAfterInsertion(Entry&lt;K,V&gt; x)</code> 就是把这三个 Case 全部编码在一个while循环里，最终把根节点染黑，恢复所有红黑树性质。</p>
<p>可视化过程：</p>
<p><img src="https://img2024.cnblogs.com/blog/1209017/202507/1209017-20250720224145695-1836458362.gif" alt="image" loading="lazy"></p>
<h3 id="52-删除平衡fixafterdeletion">5.2. 删除平衡：<code>fixAfterDeletion</code></h3>
<p>删除节点更复杂，因为可能产生“双重黑”（double-black）问题。大致流程：</p>
<p>1.如果被删节点或被删替换节点是红色，则简单染黑，完事。</p>
<p>2.否则，当前“替代”节点（可能为 <code>null</code> 代表叶子）就相当于带了一个额外的黑色，需要通过一系列 Case：</p>
<blockquote>
<ul>
<li>
<p><strong>Case 1（兄弟节点是红色）</strong><br>
将兄弟染黑、父染红，然后对父做一次旋转，使兄弟变成新的兄弟（变为黑色兄弟的场景）。</p>
</li>
<li>
<p><strong>Case 2（兄弟黑，且兄弟的两个子节点都黑）</strong><br>
将兄弟染红，上移到父，继续在父节点处做平衡。</p>
</li>
<li>
<p><strong>Case 3（兄弟黑，兄弟的外侧子节点黑，内侧子节点红）</strong><br>
将兄弟内侧子节点染黑、兄弟染红，然后对兄弟做一次旋转，转为 Case 4。</p>
</li>
<li>
<p><strong>Case 4（兄弟黑，兄弟的外侧子节点红）</strong><br>
将兄弟染成父颜色、父染黑、兄弟外侧节点染黑，对父做一次旋转，结束。</p>
</li>
</ul>
</blockquote>
<p><code>fixAfterDeletion(Entry&lt;K,V&gt; x)</code> 同样也是把以上 Case 都写一个while循环里，最终把根节点染黑。</p>
<p>删除根节点的可视化过程：</p>
<p><img src="https://img2024.cnblogs.com/blog/1209017/202507/1209017-20250720224127126-766363003.gif" alt="image" loading="lazy"></p>
<h2 id="5-总结">5. 总结</h2>
<p><code>TreeMap</code>底层数据结构、特点、与其他Map集合的差异，并提供一个简单案例感受TreeMap带来的高效处理。如果只关心 <strong>快速存取</strong>，且对顺序无要求，首选 <code>HashMap</code>； 如果需要按 <strong>插入或访问顺序</strong> 遍历，用 <code>LinkedHashMap</code>； 若需 <strong>按键排序</strong>、<strong>范围查询</strong> 或访问 <strong>最小/最大值</strong>，则应使用 <code>TreeMap</code>。</p>
<h2 id="往期推荐">往期推荐</h2>
<table>
<thead>
<tr>
<th>分类</th>
<th>往期文章</th>
</tr>
</thead>
<tbody>
<tr>
<td>Java集合底层原理可视化</td>
<td>LinkedHashMap集合--原理可视化<br>HashMap集合--基本操作流程的源码可视化<br>Java集合--HashMap底层原理可视化，秒懂扩容、链化、树化<br>Java集合--从本质出发理解HashMap<br>Java集合--LinkedList源码可视化<br>Java集合源码--ArrayList的可视化操作过程</td>
</tr>
<tr>
<td>设计模式秘籍<br>（已全部开源）</td>
<td>掌握设计模式的两个秘籍<br>往期设计模式文章的：设计模式</td>
</tr>
<tr>
<td>软件设计师</td>
<td>软考中级--软件设计师毫无保留的备考分享<br>通过软考后却领取不到实体证书？<br>2023年下半年软考考试重磅消息</td>
</tr>
<tr>
<td>Java学习路线<br>和相应资源</td>
<td>Java全栈学习路线、学习资源和面试题一条龙</td>
</tr>
</tbody>
</table>
<p>原创不易，觉得还不错的，三连支持：点赞、分享、推荐↓</p><br><br>
来源：https://www.cnblogs.com/dennyLee2025/p/18994785

查看完整版本: TreeMap集合--底层原理、源码阅读及它在Java集合框架中扮演什么角色？