Java 集合框架中的 Map 主要用于存储键值对，但不同实现对顺序的保证差异很大。HashMap 的遍历顺序与哈希桶分布有关，几乎不可预测；而 TreeMap 则能在任意时刻按照键的大小顺序输出数据。TreeMap 实现了 SortedMap 和 NavigableMap 接口，其内部并不依赖 hashCode，而是通过红黑树来组织键值对。这种设计让 TreeMap 在插入、删除和查找操作上都能保持 O(log n) 的时间复杂度，同时天然支持范围查询和有序遍历。理解 TreeMap 的排序机制，对处理排行榜、区间过滤、按序聚合等需求非常有帮助。

一、红黑树如何让TreeMap保持有序

TreeMap 的底层数据结构是一棵红黑树。红黑树是一种自平衡的二叉搜索树，每个节点除了存储键、值和左右子节点引用外，还携带一个颜色状态，即红色或黑色。红黑树需要满足四条核心性质：节点不是红色就是黑色；根节点必须是黑色；红色节点的两个子节点必须是黑色；从任一节点到其每个叶子节点的路径上，黑色节点数量相同。这些约束保证了树的高度始终维持在 log n 级别，从而避免普通二叉搜索树在极端插入顺序下退化成链表的问题。

当新的键值对插入 TreeMap 时，TreeMap 会先将新节点按二叉搜索树规则放到合适位置，然后根据红黑树性质进行颜色调整和旋转操作。旋转分为左旋和右旋，目的是重新平衡子树结构。经过这些修复后，红黑树仍然保持有序性，其中序遍历结果就是键的升序排列。TreeMap 判断键顺序时依靠比较器或键自身的 compareTo 方法，因此键不能为 null，否则比较时会抛出 NullPointerException。值可以为 null，除非 TreeMap 所在的 JDK 版本或后续操作明确禁止。

下面是一个自然排序的简单示例，将一些无序的单词放入 TreeMap，遍历时输出会自动按照字典序排列：

import java.util.Map;
import java.util.TreeMap;
public class TreeMapOrderDemo {
    public static void main(String[] args) {
        Map<String, Integer> map = new TreeMap<>();
        map.put("orange", 10);
        map.put("apple", 5);
        map.put("banana", 8);
        map.put("pear", 3);
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }
    }
}

运行这段代码，输出顺序将是 apple、banana、orange、pear。这个顺序与插入顺序无关，完全由 String 类实现的 Comparable 接口决定。TreeMap 会在每次插入时比较键与已有节点的大小，最终形成一棵符合红黑树规范的有序树。

二、自然排序与Comparator自定义排序

TreeMap 支持两种排序方式：自然排序和比较器排序。自然排序要求键的类必须实现 Comparable 接口，比如 String、Integer、LocalDate 等 JDK 内置类型都实现了该接口。调用 put 方法时，TreeMap 会使用键的 compareTo 方法与树节点比较。如果键类没有实现 Comparable，而构造 TreeMap 时又没有传入 Comparator，那么在第一次插入时就会抛出 ClassCastException。

自定义排序通过向 TreeMap 构造方法传入 Comparator 实现来完成。Comparator 可以定义任意比较逻辑，例如降序排列、按字符串长度排列、先按某个字段再按另一个字段排列。Java 8 之后可以用 lambda 表达式简化 Comparator 的创建。比较器与 Comparable 同时存在时，TreeMap 优先使用 Comparator，这给开发者提供了完全掌控顺序的能力。需要注意的是，Comparator 的 compare 结果最好与 equals 保持一致，否则在 SortedMap 的语义中可能出现键唯一性不一致的奇怪问题，例如两个 compare 返回 0 的对象被视为同一个键，但 equals 却认为它们不相等。

下面的示例演示了先按字符串长度排序、长度相同时再按字典序排序的规则：

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;
public class CustomOrderDemo {
    public static void main(String[] args) {
        Comparator<String> lengthThenAlpha = (a, b) -> {
            int lenCompare = Integer.compare(a.length(), b.length());
            return lenCompare != 0 ? lenCompare : a.compareTo(b);
        };
        Map<String, Integer> map = new TreeMap<>(lengthThenAlpha);
        map.put("banana", 1);
        map.put("kiwi", 2);
        map.put("apple", 3);
        map.put("fig", 4);
        map.put("grape", 5);
        for (String key : map.keySet()) {
            System.out.println(key);
        }
    }
}

输出结果为 fig、kiwi、apple、grape、banana。长度分别为 3、4、5、5、6，其中 apple 和 grape 长度相同，因此按字典序 apple 排在 grape 前面。这种组合排序在处理复杂业务键时非常实用，比如先按部门编号排序，再按员工工号排序。

三、TreeMap的核心操作与范围查询

TreeMap 除了继承 Map 接口的 put、get、remove、containsKey 等方法外，还提供了一组 NavigableMap 接口定义的导航方法。firstKey 和 lastKey 分别返回最小键和最大键；ceilingKey 返回大于等于给定键的最小键；floorKey 返回小于等于给定键的最大键；higherKey 返回严格大于给定键的最小键；lowerKey 返回严格小于给定键的最大键。这些操作都受益于红黑树的结构，平均时间复杂度为 O(log n)，远快于在无序 Map 上手工遍历筛选。

范围查询是 TreeMap 的另一项核心能力。headMap(toKey) 返回键小于 toKey 的子映射视图，tailMap(fromKey) 返回键大于等于 fromKey 的子映射视图，subMap(fromKey, toKey) 返回键在指定区间内的子映射。这些方法返回的是原 TreeMap 的视图，而非副本，因此对子映射的修改会直接影响原映射。从 Java 6 开始，还可以使用重载版本 subMap(fromKey, boolean fromInclusive, toKey, boolean toInclusive) 明确控制区间边界是否包含。

以下示例展示如何利用 TreeMap 快速获取分数在某个区间内的记录：

import java.util.NavigableMap;
import java.util.TreeMap;
public class RangeQueryDemo {
    public static void main(String[] args) {
        TreeMap<Integer, String> scoreMap = new TreeMap<>();
        scoreMap.put(55, "不及格");
        scoreMap.put(70, "及格");
        scoreMap.put(85, "良好");
        scoreMap.put(95, "优秀");
        NavigableMap<Integer, String> passRange = scoreMap.subMap(60, true, 100, true);
        System.out.println(passRange);
        System.out.println("第一个键：" + scoreMap.firstKey());
        System.out.println("最后一个键：" + scoreMap.lastKey());
        System.out.println("大于等于80的最小键：" + scoreMap.ceilingKey(80));
        System.out.println("大于90的最小键：" + scoreMap.higherKey(90));
    }
}

该代码输出 passRange 子映射包含 70=及格、85=良好、95=优秀，因为区间设置为左闭右闭，60 到 100 之间只包含这三个键。firstKey 输出 55，lastKey 输出 95，ceilingKey(80) 输出 85，higherKey(90) 输出 95。这些方法为区间统计和分页查询提供了非常直接的支持。

四、TreeMap与HashMap、LinkedHashMap的对比

HashMap、LinkedHashMap 和 TreeMap 是 Java 中最常用的三种 Map 实现，它们在顺序保证和性能上有显著差异。HashMap 以哈希表为基础，插入和查找的平均时间复杂度为 O(1)，但遍历顺序完全由哈希桶分布决定，不具备稳定性。LinkedHashMap 在 HashMap 的基础上维护了双向链表，可以保证遍历顺序与插入顺序一致，或者在 accessOrder 为 true 时与访问顺序一致，但同样不具备按键排序的能力。TreeMap 则通过红黑树保证按键自然顺序或比较器顺序遍历。

从性能角度看，TreeMap 的插入、删除、查找都需要沿树路径比较，时间复杂度稳定为 O(log n)。当 n 较小时，红黑树的常数因子会导致实际速度可能慢于 HashMap；当 n 很大时，HashMap 在哈希冲突严重的情况下可能退化为 O(n)，但通常扩容和良好的散列函数能保持 O(1)。内存占用方面，TreeMap 的每个节点除了键值外还要存储父节点、左右子节点引用和颜色标志，因此比 HashMap 的数组加链表节点更重。LinkedHashMap 因为额外维护链表指针，内存也略高于 HashMap。

选型建议可以总结为：需要按键排序或执行范围查询时选择 TreeMap；追求最高随机访问性能且不关心顺序时选择 HashMap；需要保持插入顺序或实现 LRU 缓存时选择 LinkedHashMap。将 TreeMap 用于大规模高并发随机读取场景并不合适，因为它的所有操作都涉及比较和树结构调整，而 HashMap 在只读场景下可以接近 O(1)。反过来，如果业务中频繁需要获取最小值、最大值或某个区间的数据，TreeMap 可以省去大量排序和筛选代码。

五、使用TreeMap时容易忽略的细节

第一个容易被忽略的问题是键不能为 null。很多人习惯在 HashMap 中使用 null 作为键，但 TreeMap 在插入 null 键时会调用 compareTo 或 Comparator.compare，而 null 无法参与比较，会直接抛出 NullPointerException。因此如果业务数据中可能包含 null 键，需要在使用 TreeMap 前做非空校验，或者换用允许 null 键的其他实现。值是否允许为 null 取决于 JDK 版本和具体实现，通常 TreeMap 允许值为 null，但某些受检方法或序列化场景会拒绝。

第二个问题是比较器的稳定性。如果 Comparator 在映射的生命周期内返回的结果发生变化，例如比较规则依赖外部可变状态，那么红黑树的结构可能会被破坏，导致后续操作出现无法预期的结果。比较器应当保持稳定，至少在键对象生命周期内比较逻辑不能随意改变。如果键对象是可变的，并且会影响比较结果，那么在存入 TreeMap 后绝不能修改这些参与比较的字段，否则树的有序性会被打乱，查找和删除都可能失败。

第三个问题是 subMap、headMap 和 tailMap 返回的是视图，不是独立副本。对子映射执行 clear、remove 或 put 操作都会反映到原 TreeMap 中。此外，视图会限制键的范围，如果尝试往子映射中 put 超出范围的键，会抛出 IllegalArgumentException。如果需要独立的子集，可以构造一个新的 TreeMap 并将子映射传入构造方法，这样后续对副本的修改不会影响原映射。TreeMap 也不是线程安全的，多线程并发读写时需要外部同步或使用 ConcurrentSkipListMap 作为替代，后者同样支持排序并具备更好的并发性能。

综合来看，TreeMap 提供了一个稳定的有序映射实现，理解它的红黑树原理、排序规则、导航 API 以及与 HashMap 的差异，能够帮助开发者在合适的场景中做出正确选择。当键几乎不会变化、业务依赖于顺序输出或范围统计时，TreeMap 会比手动排序映射条目更简洁也更可靠。