---
url: https://www.chenlj.top/md/java-base/collections/TreeMap.md
---
# TreeMap 源码解析

## 简介

`TreeMap` 是 `Map` 接口的**有序**实现，底层为一棵**红黑树（Red-Black Tree）**，因此它能保证键（key）按「自然顺序」或「定制 `Comparator`」保持有序。

* 实现 `NavigableMap`（间接实现 `SortedMap`），支持 `firstKey` / `lastKey` / `lowerKey` / `higherKey` / `subMap` 等区间查询。
* **不是线程安全的**；多线程可用 `Collections.synchronizedSortedMap` 包装，或改用 `ConcurrentSkipListMap`。
* 不允许「无法比较」的 key：使用自然排序（无 `Comparator`）时传入 `null` 键会抛 `NullPointerException`；使用允许 `null` 的 `Comparator` 时则可。
* 与 `HashMap`（无序、O(1)）、`LinkedHashMap`（插/访问顺序）相比，`TreeMap` 的核心价值是**有序 + 范围查询**，时间复杂度稳定在 O(log n)。

> 注意：`TreeMap` 的相等性比较的是「key 的有序内容」，只要两个 TreeMap 的 key 集合与映射一致即相等，与其内部树结构无关。

## 底层数据结构分析

红黑树是一种**自平衡二叉查找树**，每个节点多一个 `color`（红 / 黑）字段，通过旋转和重新着色维持以下性质，从而保证最长路径不超过最短路径的 2 倍：

1. 节点非红即黑；根节点为黑。
2. 红色节点的子节点必为黑（不能有连续红节点）。
3. 从任一节点到其所有叶子（null 叶子）的黑色节点数相同（黑高一致）。

`TreeMap` 的节点（`Entry`）就是红黑树节点，同时保存父、左、右指针和颜色。

```java
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; // 默认黑色
}
```

## 核心成员变量

```java
// 排序用的比较器；为 null 表示使用 key 的自然顺序（key 必须实现 Comparable）
private final Comparator<? super K> comparator;

// 红黑树的根节点，未初始化时为 null
private transient Entry<K,V> root;

// 键值对数量
private transient int size = 0;
```

## 源码分析

### 比较：compare / comparator 选择

所有查找、插入、删除都依赖比较结果。`TreeMap` 优先使用外部 `Comparator`，否则要求 key 实现 `Comparable`：

```java
final int compare(Object k1, Object k2) {
    return comparator == null
        ? ((Comparable<? super K>)k1).compareTo((K)k2)
        : comparator.compare((K)k1, (K)k2);
}
```

### 写入：put

`put` 先沿树根据比较结果向下查找目标位置：找到相等 key 就替换 value；否则作为叶子插入新节点，最后调用 `fixAfterInsertion` 重新平衡（旋转 + 变色）。

```java
public V put(K key, V value) {
    Entry<K,V> t = root;
    if (t == null) {            // 空树，直接作为根（黑色）
        compare(key, key);      // 检查 key 是否可比较（不可比较会抛异常）
        root = new Entry<>(key, value, null);
        size = 1;
        return null;
    }
    int cmp;
    Entry<K,V> parent;
    Comparator<? super K> cpr = comparator;
    // 1. 根据比较结果下钻，找到插入点（或命中已有 key）
    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); // 命中，替换 value
        } while (t != null);
    } else { /* 使用 Comparable 版本，逻辑相同 */ }
    // 2. 作为红色叶子挂到 parent 之下
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0) parent.left = e; else parent.right = e;
    // 3. 重新平衡红黑树（旋转 + 变色）
    fixAfterInsertion(e);
    size++;
    return null;
}
```

### 读取：get / getEntry

`get` 本质是二叉查找：从根开始，按比较结果向左 / 右走，直到命中或走到空。

```java
final Entry<K,V> getEntry(Object key) {
    if (comparator != null) return getEntryUsingComparator(key);
    Comparable<? super K> k = (Comparable<? super K>) key;
    Entry<K,V> p = root;
    while (p != null) {                  // 标准 BST 查找
        int cmp = k.compareTo(p.key);
        if (cmp < 0) p = p.left;
        else if (cmp > 0) p = p.right;
        else return p;
    }
    return null;
}
```

### 删除：remove

`remove` 先 `getEntry` 找到节点，再 `deleteEntry`：

* 若节点有 0 或 1 个子节点：直接用其子节点（或 null）替换它。
* 若有两个子节点：用「右子树的最小节点（后继）」替换它，再删除后继节点。
* 删除黑色节点会破坏黑高，最后 `fixAfterDeletion` 重新平衡。

```java
private void deleteEntry(Entry<K,V> p) {
    size--;
    // 两个子节点：用后继替换 p，问题转化为删除后继（至多一个子节点）
    if (p.left != null && p.right != null) {
        Entry<K,V> s = successor(p);
        p.key = s.key; p.value = s.value;
        p = s;
    }
    Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    if (replacement != null) {
        replacement.parent = p.parent; // 用 replacement 顶替 p
        /* ... 接好父节点的 left/right 指针 ... */
    }
    else if (p.color == BLACK)
        fixAfterDeletion(p);            // 删黑节点，重新平衡
    /* ... */
}
```

## 与 HashMap / LinkedHashMap 的对比

| 维度 | HashMap | LinkedHashMap | TreeMap |
| --- | --- | --- | --- |
| 底层结构 | 数组+链表/红黑树 | HashMap + 双向链表 | 红黑树 |
| 顺序 | 无序 | 插入/访问顺序 | **key 有序** |
| 时间复杂度 | 平均 O(1) | 平均 O(1) | 稳定 O(log n) |
| 范围查询 | 不支持 | 不支持 | **支持** |
| 线程安全 | 否 | 否 | 否 |
| 允许 null 键 | 允许 | 允许 | 否（自然排序下） |

## 经典 Demo

```java
import java.util.*;

public class TreeMapDemo {
    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        map.put(3, "c"); map.put(1, "a"); map.put(2, "b");

        System.out.println(map);            // {1=a, 2=b, 3=c} 自动按 key 升序
        System.out.println(map.firstKey()); // 1
        System.out.println(map.lastKey());  // 3
        System.out.println(map.subMap(1, 3));    // {1=a, 2=b} 区间 [1,3)
        System.out.println(map.descendingMap()); // {3=c, 2=b, 1=a} 降序视图
    }
}
```