【集合框架TreeMap】

💡 摘要：你是否遇到过这样的需求——希望一个 Map 中的键值对能自动按“键”的大小排序？ 比如，实现一个按价格排序的商品目录、按时间排序的日志记录，或者需要快速找到“最接近的键”（如楼层查找、版本匹配）？ 此时，HashMap 无法满足，LinkedHashMap 只能按插入顺序排序。 而 TreeMap 就是为此而生：它是一个基于红黑树的有序映射，支持按键的自然顺序或自定义比较器排序，并提供高效的范围查询、最值查找等操作。 本文将带你深入理解 TreeMap 的设计思想、底层红黑树原理、核心 API 使用，并对比 HashMap 与 TreeMap 的适用场景，最后附上面试高频问题解析，助你彻底掌握这一“有序王者”。

一、TreeMap 是什么？为什么需要它？

TreeMap 是 Java 集合框架中 SortedMap 和 NavigableMap 接口的核心实现。 它最大的特点是：键值对按照键的顺序存储和遍历。

TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "three");
map.put(1, "one");
map.put(2, "two");

System.out.println(map); // 输出 {1=one, 2=two, 3=three}

这与 HashMap 的无序性形成鲜明对比。

1. 核心特性一句话总结

TreeMap 是一个基于红黑树（Red-Black Tree） 的有序 Map，支持按键的自然顺序或自定义比较器排序，提供 O(log n) 的插入、删除、查找性能。

2. 典型使用场景

✅ 场景一：需要有序遍历的业务数据

// 按学生成绩排名
TreeMap<Integer, String> rank = new TreeMap<>(Comparator.reverseOrder());
rank.put(95, "Alice");
rank.put(87, "Bob");
rank.put(92, "Charlie");

✅ 场景二：范围查询（如时间区间、价格区间）

// 查询价格在 [100, 500] 之间的商品
SortedMap<Double, Product> sub = map.subMap(100.0, 500.0);

✅ 场景三：查找最接近的键（地板键、天花板键）

// 找到小于等于 49 的最大键（地板键）
map.floorKey(49); // 如 45

// 找到大于等于 51 的最小键（天花板键）
map.ceilingKey(51); // 如 55

✅ 场景四：实现优先队列或有序缓存

虽然 PriorityQueue 更适合优先队列，但 TreeMap 提供了更丰富的有序操作。

二、TreeMap vs HashMap：核心差异

✅ 总结：

• 要速度 → 用 HashMap
• 要顺序 → 用 TreeMap

三、底层实现原理：红黑树（Red-Black Tree）

1. 为什么选择红黑树？

• 二叉搜索树（BST）：左子树 < 根 < 右子树，查找 O(log n)（理想情况下）
• 但普通 BST 在有序插入时会退化为链表，性能降为 O(n)
• 红黑树是一种自平衡二叉搜索树，通过以下规则保证树的高度始终为 O(log n)：

🔴 红黑树五大规则：

1. 每个节点是红色或黑色
2. 根节点是黑色
3. 所有叶子（null）是黑色
4. 红色节点的子节点必须是黑色（不能有两个连续的红色节点）
5. 从任一节点到其每个叶子的所有路径包含相同数目的黑色节点

这些规则确保了树的“近似平衡”，最坏情况下高度不超过 2log(n+1)。

2. 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;
    // ...
}

• 每个节点包含左右子节点、父节点指针，以及颜色标记
• 支持高效的中序遍历（得到有序序列）

3. 插入与删除：旋转与变色

插入流程：

1. 按 BST 规则插入新节点（颜色为红色）
2. 如果破坏了红黑规则，通过变色（recolor） 和旋转（rotate） 修复
   • 左旋（left rotate）
   • 右旋（right rotate）

删除流程：

1. 按 BST 规则删除节点
2. 如果破坏了红黑规则，同样通过变色和旋转修复

🔍 这些操作在 TreeMap 源码中由 fixAfterInsertion 和 fixAfterDeletion 方法实现，逻辑复杂但保证了 O(log n) 的性能。

四、核心 API 与使用示例

1. 基本操作

TreeMap<String, Integer> map = new TreeMap<>();
map.put("banana", 2);
map.put("apple", 1);
map.put("cherry", 3);

System.out.println(map); // {apple=1, banana=2, cherry=3}

2. 自定义排序

// 按字符串长度排序
TreeMap<String, Integer> map = new TreeMap<>(
    Comparator.comparing(String::length)
);
map.put("hi", 1);
map.put("hello", 2);
map.put("a", 3);
// 输出 {a=3, hi=1, hello=2}

3. 范围查询（subMap）

SortedMap<String, Integer> sub = map.subMap("b", "d");
// 返回键在 [b, d) 范围内的视图

4. 最值查找

map.firstKey();    // 最小键
map.lastKey();     // 最大键
map.firstEntry();  // 最小键值对
map.lastEntry();   // 最大键值对

5. 邻近查找（NavigableMap 特性）

map.lowerKey("c");     // 小于 c 的最大键
map.floorKey("c");     // 小于等于 c 的最大键
map.ceilingKey("c");   // 大于等于 c 的最小键
map.higherKey("c");    // 大于 c 的最小键

📌 这些方法在实现“模糊匹配”、“版本路由”、“楼层查找”等场景非常有用。

五、线程安全与并发访问

TreeMap 不是线程安全的。多线程并发访问需外部同步：

TreeMap<Object, Object> map = Collections.synchronizedSortedMap(
    new TreeMap<>()
);

或者使用 ConcurrentSkipListMap 作为线程安全的有序 Map 替代方案。

六、性能对比与适用场景总结

⚠️ 注意：TreeMap 的 O(log n) 性能在数据量小时与 HashMap 差距不大，但数据量大时明显慢于 HashMap 的 O(1)。

七、注意事项与最佳实践

❗ 注意事项

自然排序时 key 不能为 null：Comparable 接口不支持 null 比较

自定义 Comparator 可支持 null：

new TreeMap<>((a, b) -> {
    if (a == null) return b == null ? 0 : -1;
    if (b == null) return 1;
    return a.compareTo(b);
});

性能敏感场景慎用：O(log n) 比 O(1) 慢

迭代器是 fail-fast 的：并发修改会抛 ConcurrentModificationException

💡 最佳实践

• 用于需要排序、范围查询、邻近查找的业务
• 避免在高频读写场景使用
• 优先使用 Comparator 而非 Comparable，更灵活

八、面试高频问题解析

❓1. TreeMap 的底层数据结构是什么？

答： TreeMap 基于红黑树（Red-Black Tree） 实现，是一种自平衡二叉搜索树，保证插入、删除、查找的时间复杂度为 O(log n)。

❓2. TreeMap 和 HashMap 的主要区别？

答：

• HashMap 基于哈希表，无序，平均 O(1) 性能；
• TreeMap 基于红黑树，按键有序，O(log n) 性能；
• HashMap 允许一个 null 键，TreeMap 自然排序时不支持 null 键；
• TreeMap 支持范围查询、最值查找等有序操作。

❓3. TreeMap 如何保证有序性？

答： 通过红黑树的结构：左子树 < 根 < 右子树。 中序遍历即可得到有序序列。 插入/删除时通过旋转和变色保持平衡和有序。

❓4. TreeMap 支持 null 键吗？

答：

• 如果使用自然排序（key 实现 Comparable），则不支持 null 键，否则抛 NullPointerException；
• 如果使用自定义 Comparator，则可以在比较器中处理 null，从而支持 null 键。

❓5. 什么是红黑树？它为什么能保持平衡？

答： 红黑树是一种自平衡二叉搜索树，通过五条规则（如红节点子节点为黑、路径黑节点数相同等）确保树的高度近似平衡，最坏情况下查找、插入、删除均为 O(log n)。

❓6. TreeMap 的 subMap 方法返回的是什么？

答： subMap 返回的是原 TreeMap 的一个视图（View），不是副本。 对视图的修改会反映到原 Map 上，反之亦然。 它支持动态范围查询，非常高效。

❓7. 有没有线程安全的 TreeMap？

答： TreeMap 本身不是线程安全的。 可以使用 Collections.synchronizedSortedMap(new TreeMap<>()) 包装， 或使用 ConcurrentSkipListMap，它是 TreeMap 的并发替代品，基于跳表实现，支持高并发有序操作。

九、总结

TreeMap 是 Java 集合中“有序性”的代表。 它牺牲了 HashMap 的极致性能，换来了按键排序、范围查询、邻近查找等强大能力。 理解 TreeMap，不仅是掌握一个集合类，更是理解了 红黑树、自平衡、有序数据结构的设计智慧。

在需要“顺序”的场景中，TreeMap 是你最可靠的伙伴。