TreeMap 是基于红黑树实现的有序 Map。它按照 key 的自然顺序或自定义 Comparator 排序，支持有序遍历、范围查询、找第一个/最后一个 key 等能力。

如果说 HashMap 追求平均 O(1) 查找，那么 TreeMap 追求“始终有序”和稳定的 O(log n) 操作。

1. 核心特点

特点	说明
key 有序	按自然顺序或比较器排序
底层红黑树	自平衡二叉搜索树
操作复杂度	put/get/remove 是 O(log n)
不允许随意 null key	自然排序下不允许 null key
value 可为 null	value 没有排序要求
非线程安全	并发访问需要额外同步

示例：

Map<Integer, String> map = new TreeMap<>();
map.put(3, "C");
map.put(1, "A");
map.put(2, "B");

System.out.println(map.keySet()); // [1, 2, 3]

2. 红黑树结构

红黑树是近似平衡的二叉搜索树。

        4(B)
       /    \
    2(R)    6(R)
   /  \     /  \
 1(B) 3(B) 5(B) 7(B)

二叉搜索树规则：

左子树 key < 当前 key < 右子树 key

红黑树通过颜色和旋转控制树高度，避免退化成链表。

TreeMap 节点大致包含：

Entry
├─ key
├─ value
├─ left
├─ right
├─ parent
└─ color

3. 排序规则

TreeMap 有两种排序方式：

方式	说明
自然排序	key 实现 Comparable
比较器排序	构造 TreeMap 时传入 Comparator

自然排序：

Map<String, Integer> map = new TreeMap<>();
map.put("b", 2);
map.put("a", 1);

自定义排序：

Map<String, Integer> map = new TreeMap<>(Comparator.reverseOrder());
map.put("a", 1);
map.put("b", 2);

System.out.println(map.keySet()); // [b, a]

如果 key 没有实现 Comparable，又没有提供 Comparator，插入时会抛 ClassCastException。

4. put 流程

put(key, value)
  │
  ▼
从 root 开始比较
  │
  ├─ key 更小：进入左子树
  ├─ key 更大：进入右子树
  └─ 比较结果为 0：覆盖 value
  │
  ▼
插入新节点
  │
  ▼
通过变色和旋转修复红黑树

注意：TreeMap 判断 key 是否“相同”，主要看比较结果是否为 0，而不是 equals。

Comparator<User> comparator = Comparator.comparing(User::getAge);
Map<User, String> map = new TreeMap<>(comparator);

如果两个用户年龄相同，比较结果为 0，后放入的会覆盖前一个，即使它们不是同一个用户。

5. get 流程

get(key)
  │
  ▼
从 root 开始比较
  │
  ├─ key 更小：找左子树
  ├─ key 更大：找右子树
  └─ 比较结果为 0：返回 value

树高约为 O(log n)，所以查找是 O(log n)。

与 HashMap 的区别：

对比项	HashMap	TreeMap
定位方式	hash 定位桶	比较 key 大小
平均复杂度	O(1)	O(log n)
是否有序	不保证	有序
是否要求 key 可比较	不要求	要求

6. 范围查询

TreeMap 实现了 NavigableMap，支持范围视图。

TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "A");
map.put(2, "B");
map.put(3, "C");
map.put(4, "D");

SortedMap<Integer, String> sub = map.subMap(2, 4);
System.out.println(sub.keySet()); // [2, 3]

常用范围方法：

方法	作用
subMap(from, to)	获取 [from, to) 范围
headMap(to)	获取小于 to 的部分
tailMap(from)	获取大于等于 from 的部分
ceilingKey(key)	大于等于 key 的最小 key
floorKey(key)	小于等于 key 的最大 key
higherKey(key)	大于 key 的最小 key
lowerKey(key)	小于 key 的最大 key

范围查询是 TreeMap 相比 HashMap 的核心优势。

7. 视图是联动的

范围方法返回的是视图，不是独立副本。

TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "A");
map.put(2, "B");
map.put(3, "C");

SortedMap<Integer, String> sub = map.subMap(1, 3);
sub.put(2, "BB");

System.out.println(map.get(2)); // BB

向范围视图放入超出范围的 key 会抛异常：

sub.put(5, "E"); // IllegalArgumentException

如果需要独立数据：

Map<Integer, String> copy = new TreeMap<>(sub);

8. null key

自然排序下，TreeMap 不允许 null key：

Map<String, Integer> map = new TreeMap<>();
map.put(null, 1); // NullPointerException

如果自定义比较器能处理 null，可以支持：

Map<String, Integer> map = new TreeMap<>(Comparator.nullsFirst(String::compareTo));
map.put(null, 0);
map.put("A", 1);

但业务上要慎重，null key 通常会让语义变模糊。

9. TreeSet 与 TreeMap

TreeSet 底层基于 TreeMap。

TreeSet
  │
  ▼
TreeMap<E, Object>
key = Set 元素
value = 占位对象

所以 TreeSet 的排序和去重也依赖比较结果。

Set<User> users = new TreeSet<>(Comparator.comparing(User::getAge));

如果两个用户年龄一样，会被认为重复。

10. Comparator 设计

比较器必须满足基本约定：

• 自反：compare(a, a) == 0
• 反对称：compare(a, b) 与 compare(b, a) 符号相反
• 传递：a > b 且 b > c，则 a > c
• 与相等语义尽量一致

错误比较器会导致 TreeMap 行为异常，例如元素丢失、顺序错乱。

推荐写法：

Comparator<User> comparator = Comparator
        .comparing(User::getAge)
        .thenComparing(User::getId);

不要简单相减：

(a, b) -> a.getAge() - b.getAge()

可能整数溢出。使用：

Comparator.comparingInt(User::getAge)

11. 适用场景

适合：

• 需要按 key 排序输出。
• 需要范围查询。
• 需要找最近大于/小于某个 key 的条目。
• 需要有序字典结构。

不适合：

• 只需要普通 key-value 快速查找。
• key 不具备稳定比较规则。
• 高并发写入。

普通映射优先 HashMap，需要排序和范围能力时再选 TreeMap。

Tips 快问快答

Q：TreeMap 底层是什么？ A：红黑树。

Q：TreeMap 为什么有序？ A：每次插入和查找都按照 key 的比较规则维护二叉搜索树顺序。

Q：TreeMap 操作复杂度是多少？ A：put/get/remove 通常是 O(log n)。

Q：TreeMap 判断 key 重复看 equals 吗？ A：主要看比较器或 compareTo 的结果是否为 0。

Q：为什么比较器只按 age 可能丢数据？ A：age 相同的两个对象比较结果为 0，会被当作同一个 key。

Q：自然排序下能放 null key 吗？ A：不能，通常会抛 NullPointerException。

Q：范围查询返回新 Map 吗？ A：不是独立副本，是原 Map 的范围视图。

Q：按插入顺序遍历应该用 TreeMap 吗？ A：不应该，用 LinkedHashMap。

Q：普通查询选 HashMap 还是 TreeMap？ A：不需要排序或范围查询时优先 HashMap。

Q：比较器为什么不要用减法？ A：可能整数溢出，推荐使用 Integer.compare 或 Comparator.comparingInt。