在Java里TreeMap是如何排序的_TreeMap红黑树解析

TreeMap 按 key 排序，依赖红黑树结构与 key 的可比较性：自然排序（Comparable）或定制排序（Comparator），插入即有序，遍历、范围查询和极值定位均高效。

TreeMap 的排序不是靠“记住插入顺序”，而是靠底层红黑树在每次插入时，*

*依据 key 的大小关系决定存放位置**，并自动调整结构维持有序性。它不排序“值”，只按 key 排序；且这个排序逻辑，在初始化时就已确定——要么用 key 自带的自然顺序（自然排序），要么用你传入的比较规则（定制排序）。

排序依赖 key 的可比较性

TreeMap 要求 key 必须能比较大小，否则运行时报 ClassCastException 或 NullPointerException。满足方式有两种：

• key 类型实现 Comparable 接口（如 String、Integer、LocalDate），重写 compareTo() 方法
• 创建 TreeMap 时显式传入 Comparator 实例，比如 new TreeMap((a, b) -> a.length() - b.length())

内部通过一个 comparator 字段区分：为 null 表示走自然排序；非 null 则调用其 compare(key1, key2)。

红黑树保证插入即有序

TreeMap 底层是红黑树，属于自平衡二叉搜索树。它的排序能力来自两个层面：

• 二叉搜索树性质：对任意节点，左子树所有 key 小于它，右子树所有 key 大于它 —— 这决定了中序遍历结果天然有序
• 红黑树自平衡机制：插入/删除后自动执行旋转（leftRotate / rightRotate）和变色（recolor），确保最长路径 ≤ 2 倍最短路径，从而维持 O(log n) 时间复杂度

也就是说，你调 put(5, "E") 时，TreeMap 不是先存再排序，而是直接找到“应该放的位置”，再平衡整棵树。

排序结果直接影响遍历与范围操作

因为数据物理上就按 key 有序组织，所以：

• 用 entrySet()、keySet() 或 values() 遍历时，天然按键升序输出
• 支持高效范围查询：subMap(fromKey, toKey)、headMap(toKey)、tailMap(fromKey) 都基于红黑树的结构直接切片，不是过滤后排序
• 快速定位极值：firstKey()、lastKey()、floorKey(k)、ceilingKey(k) 全部是 O(log n)

注意重复 key 的判定逻辑

TreeMap 不允许 key 重复。判断“是否重复”的依据，就是你设定的比较逻辑：

• 若 compare(key1, key2) == 0，就认为是同一个 key，新 value 会覆盖旧 value
• 例如两个 Person("Mike", 17)，如果 compareTo 中只比 age，那它们会被视为相同 key；若还加了 name 比较，则需 age 和 name 都相等才覆盖

这说明：排序规则 = 唯一性规则。设计 compareTo 或 Comparator 时，必须明确“什么才算同一个 key”。