一句话总结
TreeMap 底层是红黑树（自平衡二叉搜索树，O(log n)），key 必须实现 Comparable 或传入 Comparator。红黑树是弱平衡（最长路径 ≤ 最短路径 2 倍），插入删除旋转次数少（最多 3 次），适合写多读少。提供丰富导航方法（firstKey/lastKey/lowerKey/higherKey/subMap）。TreeSet 底层是 TreeMap。
初级理解
TreeMap 底层是红黑树（自平衡二叉搜索树），所有操作 O(log n)。key 必须实现 Comparable 或传入 Comparator，按 key 的自然顺序或自定义顺序排序。
TreeSet 底层是 TreeMap（和 HashSet 底层是 HashMap 一样），元素作为 TreeMap 的 key，value 是固定的 PRESENT。
红黑树的 5 条性质：
1. 节点是红色或黑色
2. 根节点是黑色
3. 叶子节点（NIL）是黑色
4. 红色节点的子节点必须是黑色
5. 从任一节点到其每个叶子节点的路径包含相同数量的黑色节点
// TreeMap 按 key 排序
TreeMap<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]，自动排序
中级深入
两种排序方式：
1. 自然排序：key 实现 Comparable 接口，TreeMap 调用 key.compareTo() 比较
2. 自定义排序：构造 TreeMap 时传入 Comparator，优先使用 Comparator.compare()
// 自定义排序：按字符串长度排序
TreeMap<String, Integer> map = new TreeMap<>((a, b) -> {
int cmp = Integer.compare(a.length(), b.length());
return cmp != 0 ? cmp : a.compareTo(b); // 长度相同按字典序
});
map.put("aaa", 1);
map.put("b", 2);
map.put("cc", 3);
System.out.println(map.keySet()); // [b, cc, aaa]
TreeMap 的 key 不能为 null：因为需要调用 compareTo() 比较，null 会抛 NPE。但 value 可以为 null。
高级拓展
红黑树 vs AVL 树：红黑树是弱平衡（最长路径不超过最短路径的 2 倍），AVL 是严格平衡（高度差 ≤ 1）。红黑树插入删除的旋转次数更少（最多 3 次 vs AVL 的 O(log n) 次），适合写多读少的场景。
TreeMap 的导航方法：利用红黑树的排序特性，TreeMap 提供了丰富的导航方法：
TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "A"); map.put(20, "B"); map.put(30, "C");
map.firstKey(); // 10，最小 key
map.lastKey(); // 30，最大 key
map.lowerKey(20); // 10，小于 20 的最大 key
map.higherKey(20); // 30，大于 20 的最小 key
map.floorKey(15); // 10，≤ 15 的最大 key
map.ceilingKey(15); // 20，≥ 15 的最小 key
map.subMap(10, 30); // {10=A, 20=B}，范围视图
TreeMap 的 fail-fast 机制：和 HashMap 一样，迭代器是 fail-fast 的，迭代过程中结构性修改会抛 ConcurrentModificationException。
面试加分项：能说出红黑树的 5 条性质和导航方法，说明你对 TreeMap 有深入理解。
实战场景
场景：用 TreeMap 实现权重路由
// 按权重范围路由到不同服务
TreeMap<Integer, String> router = new TreeMap<>();
router.put(30, "服务A"); // 0~30 → 服务A
router.put(70, "服务B"); // 31~70 → 服务B
router.put(100, "服务C"); // 71~100 → 服务C
public String route(int hash) {
// ceilingEntry：找到 ≥ hash 的最小 key
return router.ceilingEntry(hash % 100).getValue();
}
// 场景：IP 段查找
TreeMap<Long, String> ipRange = new TreeMap<>();
ipRange.put(ipToLong("10.0.0.0"), "内网");
ipRange.put(ipToLong("172.16.0.0"), "内网");
ipRange.put(ipToLong("192.168.0.0"), "内网");
// floorEntry：找到 ≤ 目标 IP 的最大 key
String region = ipRange.floorEntry(targetIp).getValue();
面试模拟
Q：TreeMap 和 HashMap 怎么选？
A：需要排序用 TreeMap（O(log n)），不需要排序用 HashMap（O(1)）。TreeMap 的优势是 key 有序，支持范围查找（subMap、headMap、tailMap）和导航方法。HashMap 的优势是速度快，大多数场景首选。
Q：红黑树和 AVL 树有什么区别？为什么 TreeMap 用红黑树？
A：AVL 是严格平衡（高度差 ≤ 1），查询更快但插入删除旋转次数多（O(log n)）。红黑树是弱平衡（最长 ≤ 最短 × 2），插入删除最多 3 次旋转，写入性能更好。TreeMap 作为通用容器，读写都需要兼顾，红黑树是更好的折中。