在Java里TreeMap是如何排序的_TreeMap红黑树解析-java教程-PHP中文网

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

P粉602998670

发布： 2025-12-22 09:18:31

原创

869人浏览过

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

在java里treemap是如何排序的_treemap红黑树解析

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 底层是红黑树，属于自平衡二叉搜索树。它的排序能力来自两个层面：

立即学习“Java免费学习笔记（深入）”；

百度AI开放平台

百度提供的综合性AI技术服务平台，汇集了多种AI能力和解决方案

105

查看详情

二叉搜索树性质：对任意节点，左子树所有 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”。

以上就是在Java里TreeMap是如何排序的_TreeMap红黑树解析的详细内容，更多请关注php中文网其它相关文章！