Java TreeMap 排序原理与实战详解

TreeMap 的本质：它不是“排序工具”，而是“有序映射”

在 Java 集合体系中，TreeMap 是 Map 接口的一个重要实现类。它与 HashMap、LinkedHashMap 最大的区别，不在于是否能存储键值对，而在于键的组织方式。

HashMap 关注的是哈希分布，核心目标是高效定位；LinkedHashMap 关注的是插入顺序或访问顺序；TreeMap 则关注的是键的有序性。只要把数据放进 TreeMap，它就会根据既定排序规则维护键的顺序，因此遍历时得到的结果天然是有序的。

很多人在学习 TreeMap 时，容易把它简单理解为“一个会自动排序的 Map”。这个理解不算错，但不够准确。更严谨的说法是：

• TreeMap 会根据键的自然顺序，或构造时传入的比较器顺序，对键进行组织
• 这种顺序不是遍历时临时计算出来的，而是插入、删除、查找过程中持续维护的
• 因此它的“排序”本质是底层有序结构带来的结果，而不是像 Collections.sort() 那样对已有结果做一次性排序

这一区别非常重要。它直接决定了 TreeMap 的适用场景：当你不仅需要存储键值对，还需要频繁地按顺序访问、区间查询、获取最大最小键、查找前驱后继键时，TreeMap 才真正体现价值。

TreeMap 的底层结构：红黑树

TreeMap 在 JDK 中的底层实现是红黑树。红黑树是一种自平衡二叉搜索树，它通过颜色标记和旋转规则，保证树不会退化成链表，从而使查找、插入、删除操作的时间复杂度保持在 O(log n)。

这意味着：

• put()：平均和最坏时间复杂度为 O(log n)
• get()：平均和最坏时间复杂度为 O(log n)
• remove()：平均和最坏时间复杂度为 O(log n)

与之对比：

• HashMap 的理想查找复杂度通常接近 O(1)
• LinkedHashMap 在哈希定位的基础上维护链表顺序
• TreeMap 用更高的操作成本换取严格有序的键访问能力

因此，TreeMap 并不适合所有场景。它适合的是“既要映射关系，又要顺序能力”的场景，而不是单纯追求极致读写性能的场景。

TreeMap 排序的核心规则

TreeMap 的排序规则只有两类：

1. 自然排序
2. 比较器排序

两者本质上都依赖“比较”来决定键在红黑树中的位置。

自然排序

所谓自然排序，指的是键类型本身实现了 Comparable 接口，并定义了 compareTo() 方法。例如：

• Integer
• Long
• String
• Double
• LocalDate
• 很多 JDK 内置类型

当我们直接创建 TreeMap<K, V>，且没有传入 Comparator 时，TreeMap 就会要求 K 必须具备可比较能力。

Map<Integer, String> map = new TreeMap<>();
map.put(3, "C");
map.put(1, "A");
map.put(2, "B");

System.out.println(map);

输出结果：

{1=A, 2=B, 3=C}

这里的排序规则就是 Integer 的自然升序。

再看字符串：

Map<String, Integer> map = new TreeMap<>();
map.put("banana", 2);
map.put("apple", 1);
map.put("cherry", 3);

System.out.println(map);

输出结果：

{apple=1, banana=2, cherry=3}

这说明 String 默认按照字典序排序。

比较器排序

如果键类型没有实现 Comparable，或者你不想使用默认的自然顺序，就需要在构造 TreeMap 时传入 Comparator。

Map<Integer, String> map = new TreeMap<>((a, b) -> b - a);
map.put(3, "C");
map.put(1, "A");
map.put(2, "B");

System.out.println(map);

输出结果：

{3=C, 2=B, 1=A}

这时就变成了降序排列。

需要注意，一旦传入比较器，TreeMap 后续所有键的组织都以该比较器为准，不会再使用自然排序。

TreeMap 排序的本质不是对 Value 排序，而是对 Key 排序

这是一个非常容易混淆的点。

TreeMap 只能直接对 Key 排序，不能直接对 Value 排序。因为 Map 的本质是“键到值的映射”，而 TreeMap 的底层红黑树节点定位逻辑依赖的是键比较，而不是值比较。

例如：

Map<Integer, String> map = new TreeMap<>();
map.put(3, "Java");
map.put(1, "Spring");
map.put(2, "MySQL");

遍历结果一定按键顺序：

1=Spring
2=MySQL
3=Java

这里和 value 的内容没有关系。

如果业务要求“按 value 排序”，那通常不能单纯依赖 TreeMap，而是需要：

• 先把 entrySet() 转成 List
• 再按 Map.Entry::getValue 排序
• 或借助 Stream API 做排序处理

例如：

Map<Integer, String> map = new HashMap<>();
map.put(3, "Java");
map.put(1, "Spring");
map.put(2, "MySQL");

map.entrySet().stream()
        .sorted(Map.Entry.comparingByValue())
        .forEach(System.out::println);

因此，讨论 TreeMap 排序时，必须明确：它维护的是键的顺序，不是值的顺序。

TreeMap 的常见排序方式

按 Integer 键升序排序

这是最基础的用法。

import java.util.Map;
import java.util.TreeMap;

public class TreeMapDemo1 {
    public static void main(String[] args) {
        Map<Integer, String> scoreMap = new TreeMap<>();
        scoreMap.put(1003, "张三");
        scoreMap.put(1001, "李四");
        scoreMap.put(1002, "王五");

        for (Map.Entry<Integer, String> entry : scoreMap.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

输出：

1001 -> 李四
1002 -> 王五
1003 -> 张三

这里 Integer 默认自然升序，因此遍历结果按学号从小到大排序。

按 Integer 键降序排序

import java.util.Map;
import java.util.TreeMap;

public class TreeMapDemo2 {
    public static void main(String[] args) {
        Map<Integer, String> scoreMap = new TreeMap<>((a, b) -> Integer.compare(b, a));
        scoreMap.put(1003, "张三");
        scoreMap.put(1001, "李四");
        scoreMap.put(1002, "王五");

        for (Map.Entry<Integer, String> entry : scoreMap.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

输出：

1003 -> 张三
1002 -> 王五
1001 -> 李四

这里建议使用 Integer.compare(b, a)，而不是直接写 b - a。原因是数值范围大时，减法有可能发生整数溢出，Integer.compare() 更安全、更规范。

按 String 键排序

import java.util.Map;
import java.util.TreeMap;

public class TreeMapDemo3 {
    public static void main(String[] args) {
        Map<String, Integer> wordCount = new TreeMap<>();
        wordCount.put("orange", 5);
        wordCount.put("apple", 3);
        wordCount.put("banana", 8);

        wordCount.forEach((k, v) -> System.out.println(k + " -> " + v));
    }
}

输出：

apple -> 3
banana -> 8
orange -> 5

这里采用的是字符串字典序。

忽略大小写排序

默认情况下，String 比较区分大小写，这在很多业务场景下未必符合预期。例如 "Apple" 和 "apple" 的顺序会受到字符编码影响。如果希望忽略大小写，可以使用 String.CASE_INSENSITIVE_ORDER。

import java.util.Map;
import java.util.TreeMap;

public class TreeMapDemo4 {
    public static void main(String[] args) {
        Map<String, Integer> map = new TreeMap<>(String.CASE_INSENSITIVE_ORDER);
        map.put("banana", 2);
        map.put("Apple", 1);
        map.put("cherry", 3);
        map.put("apple", 5);

        map.forEach((k, v) -> System.out.println(k + " -> " + v));
    }
}

输出结果中需要特别注意："Apple" 和 "apple" 会被认为比较结果为 0，因此后插入的数据会覆盖前一个键对应的值。最终只会保留一个逻辑上“相等”的键。

这说明 TreeMap 中比较器不仅决定顺序，还决定键是否相同。

自定义对象作为 Key 时如何排序

当 TreeMap 的键是自定义对象时，最常见的做法有两种：

1. 让类实现 Comparable
2. 创建 TreeMap 时传入 Comparator

方式一：实现 Comparable 接口

假设有一个用户类，需要按年龄升序排序：

public class User implements Comparable<User> {
    private Long id;
    private String name;
    private Integer age;

    public User(Long id, String name, Integer age) {
        this.id = id;
        this.name = name;
        this.age = age;
    }

    public Long getId() {
        return id;
    }

    public String getName() {
        return name;
    }

    public Integer getAge() {
        return age;
    }

    @Override
    public int compareTo(User other) {
        int ageCompare = Integer.compare(this.age, other.age);
        if (ageCompare != 0) {
            return ageCompare;
        }
        return Long.compare(this.id, other.id);
    }

    @Override
    public String toString() {
        return "User{id=" + id + ", name='" + name + "', age=" + age + "}";
    }
}

使用方式：

import java.util.Map;
import java.util.TreeMap;

public class TreeMapDemo5 {
    public static void main(String[] args) {
        Map<User, String> map = new TreeMap<>();
        map.put(new User(3L, "张三", 22), "开发");
        map.put(new User(1L, "李四", 20), "测试");
        map.put(new User(2L, "王五", 20), "产品");

        map.forEach((k, v) -> System.out.println(k + " -> " + v));
    }
}

输出逻辑是：

• 先按年龄升序
• 年龄相同再按 id 升序

这里特别关键的一点是：如果只按年龄比较，而年龄相同就返回 0，那么不同用户只要年龄一样，就会被认为是同一个键，后插入的值会覆盖先插入的值。因此，自定义比较规则必须充分体现业务上的“键唯一性”。

方式二：传入 Comparator

如果不想修改实体类本身，或者同一个对象在不同业务里需要不同排序规则，就更适合使用比较器。

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class TreeMapDemo6 {
    public static void main(String[] args) {
        Comparator<User> comparator = Comparator
                .comparing(User::getAge)
                .thenComparing(User::getId);

        Map<User, String> map = new TreeMap<>(comparator);
        map.put(new User(3L, "张三", 22), "开发");
        map.put(new User(1L, "李四", 20), "测试");
        map.put(new User(2L, "王五", 20), "产品");

        map.forEach((k, v) -> System.out.println(k + " -> " + v));
    }
}

这种写法在 Java 8 及以上版本中更常见，可读性也更好。

为什么比较器返回 0 会导致数据覆盖

理解 TreeMap 排序，必须彻底理解一个原则：

在 TreeMap 中，两个键是否被视为同一个键，取决于比较结果是否为 0，而不是 equals() 返回值。

这与很多开发者的直觉不完全一致。

看下面的例子：

import java.util.Map;
import java.util.TreeMap;

public class TreeMapDemo7 {
    public static void main(String[] args) {
        Map<User, String> map = new TreeMap<>((u1, u2) -> Integer.compare(u1.getAge(), u2.getAge()));

        map.put(new User(1L, "张三", 20), "开发");
        map.put(new User(2L, "李四", 20), "测试");

        System.out.println(map.size());
        map.forEach((k, v) -> System.out.println(k + " -> " + v));
    }
}

这里比较器只比较年龄。两个用户虽然 id 不同、name 不同，但因为年龄相同，比较结果是 0，因此第二次 put() 会覆盖第一次的值。

输出结果通常是：

1
User{id=1, name='张三', age=20} -> 测试

或者保留第二个键对象、覆盖第一个值的表现可能因内部逻辑体现为“值被替换”，但本质是：这两个键在 TreeMap 看来是同一个逻辑键。

所以，设计 TreeMap 比较规则时，必须遵循下面的原则：

• 用于区分不同业务对象的关键字段必须纳入比较逻辑
• 只有在业务上确实应视为同一键时，比较器才应返回 0
• 比较规则应保持自反性、对称性、传递性

否则就会出现数据丢失、覆盖、排序异常等问题。

TreeMap 常用导航方法与排序的关系

TreeMap 之所以强大，不只是因为“遍历有序”，更因为它基于有序结构提供了一组非常实用的导航方法。这也是它区别于 HashMap 和 LinkedHashMap 的关键价值。

获取最小键和最大键

TreeMap<Integer, String> map = new TreeMap<>();
map.put(30, "C");
map.put(10, "A");
map.put(20, "B");

System.out.println(map.firstKey()); // 10
System.out.println(map.lastKey());  // 30

获取小于、大于某个键的相邻键

System.out.println(map.lowerKey(20));   // 10
System.out.println(map.floorKey(20));   // 20
System.out.println(map.higherKey(20));  // 30
System.out.println(map.ceilingKey(20)); // 20

含义分别是：

• lowerKey(k)：严格小于 k 的最大键
• floorKey(k)：小于等于 k 的最大键
• higherKey(k)：严格大于 k 的最小键
• ceilingKey(k)：大于等于 k 的最小键

这些操作在以下场景非常常见：

• 成绩区间映射
• 时间段命中
• 价格区间查找
• 排行榜邻位查询
• 路由区间匹配

截取子区间

System.out.println(map.subMap(10, true, 20, true)); // [10,20]
System.out.println(map.headMap(20, false));         // <20
System.out.println(map.tailMap(20, true));          // >=20

这类区间能力正是 TreeMap 在很多业务系统中非常有价值的原因。

一个典型业务案例：按分数区间匹配等级

用 TreeMap 做分数等级匹配，是一个非常经典的示例。

需求如下：

• 90 分及以上：A
• 80 分及以上：B
• 70 分及以上：C
• 60 分及以上：D
• 60 分以下：E

实现代码：

import java.util.TreeMap;

public class ScoreLevelDemo {
    public static void main(String[] args) {
        TreeMap<Integer, String> levelMap = new TreeMap<>();
        levelMap.put(0, "E");
        levelMap.put(60, "D");
        levelMap.put(70, "C");
        levelMap.put(80, "B");
        levelMap.put(90, "A");

        int score = 85;
        Integer key = levelMap.floorKey(score);
        String level = levelMap.get(key);

        System.out.println("score=" + score + ", level=" + level);
    }
}

输出：

score=85, level=B

这里的关键就是 floorKey(score)。它能找到“小于等于当前分数的最大边界值”，从而快速定位对应等级。这种场景若用 HashMap，实现会更复杂；若用数组或大量 if-else，可扩展性和维护性都较差。

TreeMap 与 HashMap、LinkedHashMap 的区别

下面从底层结构、顺序特性、性能和典型场景四个维度进行对比。

集合类型	底层结构	顺序特性	查找性能	典型场景
HashMap	数组 + 链表 + 红黑树（JDK 8）	无序	理想情况下接近 O(1)	高频读写、无需顺序
LinkedHashMap	HashMap + 双向链表	保留插入顺序或访问顺序	理想情况下接近 O(1)	需要顺序遍历、LRU 缓存
TreeMap	红黑树	按键有序	O(log n)	有序遍历、区间查询、导航查找

这张表能帮助我们形成一个非常清晰的判断标准：

• 只关心存取效率，不关心顺序：HashMap
• 关心插入顺序或访问顺序：LinkedHashMap
• 关心键排序、范围、邻接关系：TreeMap

开发中最忌讳的不是不会用 TreeMap，而是在不需要排序能力的场景下误用它，导致无谓的性能损耗。

TreeMap 是否允许 null 键和 null 值

这是一个实践中很容易踩坑的问题。

null 键

TreeMap 通常不允许 null 键。因为排序过程需要比较键，null 无法参与自然排序，也无法可靠地参与大多数比较器逻辑。向 TreeMap 放入 null 键，通常会抛出 NullPointerException。

TreeMap<Integer, String> map = new TreeMap<>();
map.put(null, "A");

null 值

TreeMap 允许 null 值。

TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, null);
System.out.println(map);

这是合法的，因为值不参与排序。

版本说明

在主流 JDK 版本中，TreeMap 对 null 键的限制是一致的：默认排序逻辑下不支持 null 键。即使自定义比较器理论上可以处理空值，也不建议把 null 当作普通业务键使用，因为这会显著增加比较规则复杂度，降低代码可维护性。

Java 8 及以上版本中的推荐写法

在 Java 8 及以上版本，编写 TreeMap 排序逻辑，建议优先采用 Comparator 的链式写法。这种写法比匿名内部类更简洁，也更不容易出错。

例如按年龄升序、id 升序：

Comparator<User> comparator = Comparator
        .comparing(User::getAge)
        .thenComparing(User::getId);

TreeMap<User, String> map = new TreeMap<>(comparator);

按年龄降序、id 升序：

Comparator<User> comparator = Comparator
        .comparing(User::getAge, Comparator.reverseOrder())
        .thenComparing(User::getId);

TreeMap<User, String> map = new TreeMap<>(comparator);

按字符串长度升序，再按字典序升序：

Comparator<String> comparator = Comparator
        .comparingInt(String::length)
        .thenComparing(String::compareTo);

TreeMap<String, Integer> map = new TreeMap<>(comparator);

版本区别说明

• Java 7 及以前：更多采用匿名内部类实现 Comparator
• Java 8 及以后：推荐使用 Lambda、方法引用、Comparator.comparing()、thenComparing() 等函数式写法

这属于语言层面的表达差异，不影响 TreeMap 本身的核心排序机制。

TreeMap 排序中的常见错误

错误一：把 TreeMap 当成 value 排序容器

很多人看到“自动排序”就误以为 TreeMap 能按值排序。实际上它只能直接按键排序。要按值排序，必须先提取条目再处理。

错误二：比较器只比较部分字段，导致键冲突

例如只按年龄排序，却忽略用户 id。结果不同用户只要年龄相同，就会互相覆盖。

错误写法：

new TreeMap<>((u1, u2) -> Integer.compare(u1.getAge(), u2.getAge()))

更合理的写法：

new TreeMap<>(Comparator.comparing(User::getAge).thenComparing(User::getId))

错误三：使用减法比较整数大小

错误写法：

(a, b) -> a - b

或：

(a, b) -> b - a

虽然很多情况下能工作，但在整数接近边界值时有溢出风险。应使用：

Integer.compare(a, b)

或：

Integer.compare(b, a)

错误四：比较器与 equals 语义严重不一致

虽然 TreeMap 判定键相同依赖比较结果是否为 0，但比较逻辑如果与对象实际业务含义严重不一致，会导致集合行为难以理解。最理想的做法是：比较器体现明确、稳定且可解释的业务键定义。

错误五：在不需要有序时盲目使用 TreeMap

如果只是普通缓存、普通统计、普通键值映射，而没有顺序遍历和范围查找需求，HashMap 往往更合适。TreeMap 不是“更高级的 Map”，而是“更适合特定场景的 Map”。

什么时候应该使用 TreeMap

下面这些场景适合选择 TreeMap：

1. 需要按键自动排序输出

例如：

• 按时间戳顺序输出日志片段
• 按编号顺序展示记录
• 按字母顺序展示字典条目

2. 需要区间查询

例如：

• 查找某个时间范围内的数据
• 根据价格区间获取配置
• 根据分值区间匹配策略

3. 需要前驱后继节点

例如：

• 排行榜相邻名次查找
• 最近有效配置查找
• 路由表最接近命中项

4. 需要最大值、最小值能力

例如：

• 获取最早任务
• 获取最新版本号
• 获取最小或最大键对应的配置

如果只是为了“最后遍历时看起来有序”，而过程中几乎不依赖有序能力，也可以考虑：

• 先用 HashMap 存储
• 输出时再对 entrySet 排序

这样在某些场景下反而更高效。

一个完整示例：订单按创建时间排序

下面给出一个更贴近业务的例子。假设需要按订单创建时间排序输出订单信息，若时间相同，再按订单 id 排序，避免键冲突。

import java.time.LocalDateTime;
import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

class Order {
    private Long orderId;
    private LocalDateTime createTime;
    private String userName;

    public Order(Long orderId, LocalDateTime createTime, String userName) {
        this.orderId = orderId;
        this.createTime = createTime;
        this.userName = userName;
    }

    public Long getOrderId() {
        return orderId;
    }

    public LocalDateTime getCreateTime() {
        return createTime;
    }

    public String getUserName() {
        return userName;
    }

    @Override
    public String toString() {
        return "Order{orderId=" + orderId + ", createTime=" + createTime + ", userName='" + userName + "'}";
    }
}

public class TreeMapOrderDemo {
    public static void main(String[] args) {
        Comparator<Order> comparator = Comparator
                .comparing(Order::getCreateTime)
                .thenComparing(Order::getOrderId);

        TreeMap<Order, String> orderMap = new TreeMap<>(comparator);

        orderMap.put(new Order(1003L, LocalDateTime.of(2026, 3, 6, 10, 15), "张三"), "待支付");
        orderMap.put(new Order(1001L, LocalDateTime.of(2026, 3, 6, 9, 30), "李四"), "已支付");
        orderMap.put(new Order(1002L, LocalDateTime.of(2026, 3, 6, 9, 30), "王五"), "已发货");

        for (Map.Entry<Order, String> entry : orderMap.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }
    }
}

这个示例体现了 TreeMap 的几个关键实践原则：

• 自定义对象做键时必须提供稳定排序规则
• 排序字段不足以唯一标识对象时，需要追加次级字段
• 排序规则设计本身就是业务建模的一部分

TreeMap 与数据库排序的区别

在很多后端系统里，排序不只发生在 Java 内存集合中，也发生在数据库层。两者虽然都叫“排序”，但职责完全不同。

数据库排序

数据库排序通常依赖 ORDER BY，适用于：

• 大批量结果集排序
• 基于索引优化的排序
• 分页查询中的顺序控制

例如：

SELECT id, user_name, score
FROM t_user_score
ORDER BY score DESC, id ASC;

TreeMap 排序

TreeMap 排序适用于：

• 已经在内存中的数据结构维护
• 需要反复插入、查询、按顺序访问
• 需要导航方法和区间能力

因此，在工程实践中应避免误区：

• 数据库已经可以高效完成排序的场景，不要先查出无序数据再用 TreeMap 二次维护，除非内存侧确实还要继续做范围操作
• TreeMap 适合内存结构层面的“有序映射建模”，不是数据库排序的替代品

面试中如何准确回答 TreeMap 排序原理

如果在面试中被问到“Java TreeMap 是怎么排序的”，一个准确、完整、专业的回答应该覆盖以下几点：

第一，TreeMap 是基于红黑树实现的有序 Map。 第二，TreeMap 的排序对象是键，不是值。 第三，排序规则来源于两种方式：键的自然排序或构造时传入的比较器。 第四，比较结果不仅影响顺序，还决定两个键是否视为同一键；当比较结果为 0 时，后插入值会覆盖前值。 第五，TreeMap 的查找、插入、删除复杂度通常为 O(log n)。 第六，TreeMap 适用于有序遍历、范围查询、前驱后继查找等场景，而不是普通无序高性能存取场景。

如果能再补充一句“自定义对象作为键时，要确保比较器稳定且能区分业务唯一性”，基本就已经达到了较高质量的回答水平。

总结

TreeMap 排序的核心，从来不是“把数据放进去后帮你排一下序”这么简单。它的本质是：基于红黑树，以键比较规则为基础，持续维护一个有序映射结构。

理解 TreeMap，需要真正掌握四个关键点：

• 它排序的是 key，不是 value
• 它依赖自然排序或比较器排序
• 比较结果为 0 就意味着逻辑上的同一个键
• 它的价值不只是遍历有序，更是区间、导航、前驱后继等能力

在实际开发中，TreeMap 用得好，能让很多区间映射和顺序访问问题变得非常优雅；用不好，则容易出现键覆盖、规则混乱、性能浪费等问题。真正的重点从来不是“会不会用 TreeMap”，而是能否根据业务语义设计出正确、稳定、可解释的排序规则。这才是 TreeMap 排序真正的工程价值所在。