TreeMap基于红黑树实现有序性，通过插入/删除时的染色与旋转动态维护平衡，确保中序遍历升序且所有操作稳定在O(log n)；支持自然排序（Comparable）和定制排序（Comparator）。
TreeMap 在 Java 中基于红黑树实现，它在插入、删除、查找时自动维护键的升序（或自定义顺序），核心在于红黑树的自平衡机制——不是简单排序后存数组，而是每插入一个键值对，就通过颜色标记和旋转操作，保证树近似平衡，从而让所有操作稳定在 O(log n) 时间复杂度。
红黑树如何保证有序性和平衡性
TreeMap 的底层是 java.util.TreeMap.Entry 构成的红黑树节点结构。每个节点包含 key、value、left、right、parent 和 color（RED/BLACK）。它满足五条红黑性质：
- 每个节点非红即黑
- 根节点是黑色
- 所有叶子（null）是黑色
- 红色节点的两个子节点必须是黑色（不能连续红）
- 从任一节点到其每个叶子的所有路径包含相同数目的黑节点
这些约束确保了：最长路径（红黑交替）不超过最短路径（全黑）的两倍，因此树高始终在 2log₂(n+1) 内，天然支持有序遍历（中序遍历即按键升序输出）。
插入新键时发生了什么
当你调用 map.put(key, value)，TreeMap 先按比较规则（自然序或 Comparator）找到插入位置（类似二叉搜索树），然后执行三步：
立即学习“Java免费学习笔记（深入）”；
- 把新节点作为红色叶子插入（维持黑高不变）
- 若父节点为红色，触发“重着色”或“旋转”修复红黑性质
- 可能向上递归调整，直到整棵树重新满足红黑规则
例如：插入序列 [5, 3, 7, 2, 4, 6, 8]，TreeMap 不会生成退化链表，而会动态旋转（如左旋/右旋）并翻转颜色，最终形成高度平衡的树结构，中序遍历恒为 2→3→4→5→6→7→8。
Comparator 如何影响排序逻辑
TreeMap 支持两种构造方式：无参构造器（要求 key 实现 Comparable） 或 传入 Comparator。Comparator 的 compare(a, b) 返回负数、0、正数，分别表示 a b。TreeMap 全程依赖该方法做大小判断，包括查找、插入、分裂子树等所有分支跳转。若 comparator 逻辑不满足「自反性、传递性、对称性」，可能导致行为异常（如 containsKey 返回 false 即使 key 存在）。
为什么不用 Arrays.sort + HashMap 模拟
有人误以为“先存 HashMap，定期排序 key”，但这样无法实时响应：每次 get() 都要遍历排序后的 key 列表找匹配，退化为 O(n)；而 TreeMap 的 get() 是标准二叉搜索，O(log n) 完成。更重要的是，TreeMap 提供 headMap()、tailMap()、subMap() 等视图方法，它们复用同一棵红黑树的节点引用，不复制数据，增删仍保持有序——这是纯排序数组无法低成本支持的。
