---
title: "05-TreeMap"
created: 2025-12-02
tags:
  - Java
---
# TreeMap

> [!note] 定位说明
> Map 系列第 5 篇。红黑树的业务落地：自然排序 vs Comparator 定制、范围查询 API（subMap/headMap/tailMap）。数据结构原理见 07-红黑树。

#### **一、核心特性与设计目的**

**TreeMap** 是 Java 集合框架中基于 **红黑树（Red-Black Tree）** 实现的有序映射（SortedMap），其核心设计目标是：

- **键有序性**：元素按照键的 **自然顺序**（如整数升序、字符串字典序）或 **自定义比较器（Comparator）** 排序。
- **高效操作**：插入、删除、查询操作的时间复杂度均为 **O(log n)**，优于链表结构的
  O (n)。

**与 HashMap/LinkedHashMap 的核心区别**：

| **特性** | **HashMap** | **LinkedHashMap** | **TreeMap** |
| --- | --- | --- | --- |
| **顺序性** | 无序 | 插入 / 访问顺序 | **键有序**（自然 / 定制） |
| **数据结构** | 哈希表 | 哈希表 + 双向链表 | **红黑树** |
| **时间复杂度** | O (1)（平均） | O (1)（平均） | **O(log n)** |
| **适用场景** | 通用快速查找 | 有序遍历、LRU 缓存 | **范围查询、排序需求** |

#### **二、使用方法详解**

##### **1. 基本操作**

```java
// 创建 TreeMap（默认按键的自然顺序排序）
TreeMap<Integer, String> naturalOrderMap = new TreeMap<>();

// 创建 TreeMap（按自定义比较器排序，如降序）
TreeMap<Integer, String> customOrderMap = new TreeMap<>(Comparator.reverseOrder());

// 插入元素
naturalOrderMap.put(3, "C");
naturalOrderMap.put(1, "A");
naturalOrderMap.put(2, "B");

// 遍历（输出顺序：1→2→3，按键的自然顺序）
for (Map.Entry<Integer, String> entry : naturalOrderMap.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}
```

##### **2. 特有 API（基于有序性）**

```java
// 范围查询
TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "A");
map.put(2, "B");
map.put(3, "C");
map.put(4, "D");
map.put(5, "E");

// 获取小于 3 的最大键（返回 2）
Integer lowerKey = map.lowerKey(3);

// 获取大于等于 3 的最小键（返回 3）
Integer ceilingKey = map.ceilingKey(3);

// 获取键在 [2, 4) 范围内的子 Map（返回 {2=B, 3=C}）
SortedMap<Integer, String> subMap = map.subMap(2, 4);

// 获取第一个键和最后一个键
Integer firstKey = map.firstKey(); // 返回 1
Integer lastKey = map.lastKey();   // 返回 5
```

##### **3. 自定义排序规则**

```java
// 按字符串长度排序（需处理 null 和长度相同的情况）
TreeMap<String, Integer> lengthMap = new TreeMap<>(
    Comparator.comparingInt(String::length)
              .thenComparing(Comparator.naturalOrder()));

lengthMap.put("apple", 1);
lengthMap.put("banana", 2);
lengthMap.put("pear", 3);

// 遍历顺序：pear → apple → banana（按长度升序，长度相同按字典序）
lengthMap.forEach((k, v) -> System.out.println(k + ": " + v));
```

#### **三、源码与实现原理**

##### **1. 红黑树结构**

TreeMap 的核心是红黑树，每个节点包含：

```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; // 颜色标记（红/黑）
    // ... 构造方法和红黑树操作
}
```

##### **2. 插入与平衡**

- **插入逻辑**：

  1. 按二叉搜索树规则找到插入位置（小键在左，大键在右）。
  2. 插入新节点（默认红色）。
  3. 通过 **左旋、右旋、变色** 调整树结构，保证红黑树性质（如根节点为黑、红色节点的子节点必为黑）。

```java
  // 简化版插入逻辑（源码）
  Entry<K,V> t = root;
  if (t == null) {
      root = new Entry<>(key, value, null); // 根节点直接插入
      size = 1;
      return null;
  }
  // 查找插入位置
  Entry<K,V> parent;
  Comparator<? super K> cpr = comparator;
  do {
      parent = t;
      int 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);

  // 插入新节点并调整红黑树
  Entry<K,V> e = new Entry<>(key, value, parent);
  if (cmp < 0)
      parent.left = e;
  else
      parent.right = e;
  fixAfterInsertion(e); // 调整树平衡
  ```

##### **3. 范围查询优化**

TreeMap 的红黑树结构天然支持高效的范围查询：

```java
// 获取子 Map（源码）
public SortedMap<K,V> subMap(K fromKey, K toKey) {
    return new AscendingSubMap<>(
        this, false, fromKey, true, toKey, false);
}

// AscendingSubMap 内部通过红黑树遍历实现范围限制
```

[[06-TreeMap源码解析|TreeMap源码解析]]

#### **四、性能分析与注意事项**

1. **时间复杂度**：

   - 插入、删除、查询：**O(log n)**（红黑树高度平衡）。
   - 范围查询（如 `subMap`）：**O(log n + m)**（m 为结果集大小）。
2. **内存开销**：

   - 每个节点需额外存储父节点、左右子节点及颜色标记，空间开销高于 HashMap。
3. **键的约束**：

   - **必须实现** `Comparable` **接口** 或 **显式提供 Comparator**，否则会抛出 `ClassCastException`。
   - 键的比较结果必须与 `equals()` 一致（建议键类同时重写 `equals()` 和 `hashCode()`）。
4. **线程安全**：

   - **非线程安全**，多线程环境需通过 `Collections.synchronizedSortedMap(new TreeMap<>())` 包装，或改用 `ConcurrentSkipListMap`。

#### **五、典型应用场景**

1. **范围统计**：

```java
   // 统计分数在 80-90 之间的学生
   TreeMap<Integer, String> scoreMap = new TreeMap<>();
   SortedMap<Integer, String> range = scoreMap.subMap(80, 91);
   ```
2. **时间序列数据**：

```java
   // 按时间戳排序的事件记录
   TreeMap<LocalDateTime, String> eventLog = new TreeMap<>();
   // 获取最近一小时的事件
   eventLog.tailMap(LocalDateTime.now().minusHours(1));
   ```
3. **优先级队列**：

```java
   // 按任务优先级排序（优先级高的任务在队首）
   TreeMap<Integer, Runnable> taskQueue = new TreeMap<>(Comparator.reverseOrder());
   ```

#### **六、常见面试问题**

1. **TreeMap 如何保证键的有序性？**

   - 通过红黑树结构，每次插入元素后自动调整树的平衡，确保中序遍历结果为有序序列。
2. **TreeMap 与 HashMap 的性能对比？**

   - HashMap 平均 O (1) 时间复杂度，适合快速查找；TreeMap O (log n)，但支持有序操作和范围查询。
3. **红黑树的特点与优势？**

   - **自平衡**：通过颜色标记和旋转操作，保证树的高度始终为 O (log n)。
   - **插入 / 删除效率高**：相比 AVL 树，红黑树允许更宽松的平衡条件，减少旋转次数。
4. **如何自定义 TreeMap 的排序规则？**

   - 方式一：键类实现 `Comparable` 接口，重写 `compareTo()` 方法。
   - 方式二：在 TreeMap 构造函数中传入 `Comparator` 实例。
5. **TreeMap 支持 null 键吗？**

   - **不支持**。因为需要通过比较器确定顺序，null 无法参与比较（`NullPointerException`）。
6. **TreeMap 的遍历顺序是怎样的？**

   - **中序遍历**（左子树 → 根 → 右子树），保证键按升序排列。

#### **总结**

TreeMap 通过红黑树实现了 **键有序的映射**，适用于需要排序或范围查询的场景。其核心优势在于高效的有序操作，但插入、查询性能略低于
HashMap。使用时需注意键的可比性约束和额外的内存开销。在多线程环境中，若需线程安全且有序的映射，可考虑 `ConcurrentSkipListMap`。
---
⬅️ [[04-LinkedHashMap源码剖析|LinkedHashMap源码剖析]] 🏠 [[00-Java|00-Java]] ➡️ [[06-TreeMap源码解析|TreeMap源码解析]]