TreeMap

一、核心特性与设计目的

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

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

与 HashMap/LinkedHashMap 的核心区别：

二、使用方法详解

1. 基本操作

// 创建 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（基于有序性）

// 范围查询
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. 自定义排序规则

// 按字符串长度排序（需处理 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 的核心是红黑树，每个节点包含：

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. 通过 左旋、右旋、变色 调整树结构，保证红黑树性质（如根节点为黑、红色节点的子节点必为黑）。

  // 简化版插入逻辑（源码）
  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 的红黑树结构天然支持高效的范围查询：

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

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

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. 范围统计：

   // 统计分数在 80-90 之间的学生
   TreeMap<Integer, String> scoreMap = new TreeMap<>();
   SortedMap<Integer, String> range = scoreMap.subMap(80, 91);

2. 时间序列数据：

   // 按时间戳排序的事件记录
   TreeMap<LocalDateTime, String> eventLog = new TreeMap<>();
   // 获取最近一小时的事件
   eventLog.tailMap(LocalDateTime.now().minusHours(1));

3. 优先级队列：

   // 按任务优先级排序（优先级高的任务在队首）
   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。

⬅️ LinkedHashMap源码剖析 🏠 00-Java ➡️ TreeMap源码解析