TreeMap | JavaSE

TreeMap

一、学习目标

完成本章后，你应该能够：

  1. 能够解释 TreeMap 的核心特点：键不重复、无索引、按照键进行排序。
  2. 能够说明 TreeMap 与 HashMap、LinkedHashMap 在数据结构、顺序特征和应用场景上的区别。
  3. 能够使用键的自然排序（Natural Ordering）和 Comparator 两种方式控制 TreeMap 的排序规则。
  4. 能够解释 TreeMap 为什么根据键的比较结果而不是 value 判断键是否重复。
  5. 能够理解 TreeMap 基于红黑树实现，并解释其 put/get/remove/containsKey 的典型时间复杂度。
  6. 能够使用 TreeMap 完成词频排序、成绩统计、排行榜、区间查询等实际任务。

二、核心知识

2.1 TreeMap 是什么

TreeMap<K, V> 是 Java 集合框架中 Map<K,V> 的一个重要实现类。

它最核心的特点是：

键不重复
+
按照键排序
+
无索引

例如：

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

public class TreeMapDemo {
    public static void main(String[] args) {
        Map<Integer, String> map = new TreeMap<>();

        map.put(30, "Java");
        map.put(10, "C");
        map.put(40, "Python");
        map.put(20, "C++");

        System.out.println(map);
    }
}

虽然添加顺序是：

30
10
40
20

TreeMap 会按照键的自然顺序组织：

10
20
30
40

因此可以建立第一条核心认识：

TreeMap 排序的是 key，不是 value。

2.2 TreeMap 在 Map 体系中的位置

前面已经学习：

Map<K,V>
├── HashMap
├── LinkedHashMap
└── TreeMap

三者共同具有：

key → value

这种键值对数据模型。

但是 key 的组织方式不同。

| Map 实现 | 键顺序 | 主要底层结构 | 典型用途 | | --------------- | -------------------- | ----------------- | ------------------------ | | HashMap | 不保证顺序 | 哈希表 | 高频增删查、普通键值映射 | | LinkedHashMap | 可维护确定的迭代顺序 | 哈希表 + 双向链表 | 既要哈希性能又要顺序 | | TreeMap | 按键排序 | 红黑树 | 需要有序键、范围查询 |

因此选择 TreeMap 的核心条件通常不是：

“我要存键值对。”

因为所有 Map 都可以。

而是：

我要存键值对，并且需要 key 始终保持某种排序关系。

2.3 TreeMap 只按照 key 排序

假设：

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

map.put("Java", 95);
map.put("C", 100);
map.put("Python", 60);

TreeMap 不会因为：

100 > 95 > 60

就按照 value 排列。

它真正比较的是：

"C"
"Java"
"Python"

所以：

TreeMap<K,V>
        ↑
      排序 K

而不是：

TreeMap<K,V>
          ↑
        排序 V

如果业务要求：

“按照 value 排序”

通常需要把 Map 数据转换为其他结构再排序，例如：

entrySet
→ List<Entry<K,V>>
→ Comparator 按 value 排序

或者根据实际业务重新设计数据模型。

2.4 TreeMap 的键为什么不能重复

普通 Map 已经规定：

一个 key
只能对应一个 value

TreeMap 同样如此。

但是 TreeMap 判断两个 key 是否属于同一个排序位置时，核心依赖：

compareTo()

或者：

Comparator.compare()

假设比较结果：

< 0
→ 第一个 key 更小

> 0
→ 第一个 key 更大

== 0
→ TreeMap 认为两个 key 在排序意义上相等

因此：

对 TreeMap 来说，比较结果为 0 非常重要。

例如：

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

map.put(10, "Java");
map.put(10, "Python");

第二次 put 使用相同 key：

10

因此会覆盖原来的 value。

最后相当于：

10 → Python

2.5 TreeMap 的两种排序方式

TreeMap 与之前学习的 TreeSet 很相似。

主要有两套排序方案：

方案一
Comparable
→ key 自己定义自然排序规则

方案二
Comparator
→ 创建 TreeMap 时提供外部排序规则

可以理解为：

Comparable
= 我这个类天生应该怎么排

Comparator
= 这一次我想怎么排

2.6 自然排序

对于 Java 已经实现 Comparable 的类型，例如：

Integer
String
Long
Double
...

可以直接：

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

Integer 已经拥有自然排序规则，因此 TreeMap 可以直接比较 key。

例如：

map.put(30, "A");
map.put(10, "B");
map.put(20, "C");

按照 Integer 的自然顺序：

10
20
30

2.7 自定义对象作为 key

假设：

public class Student {
    private int id;
    private String name;
}

如果直接：

TreeMap<Student, Integer> map = new TreeMap<>();

TreeMap 必须知道：

两个 Student 到底谁大谁小？

如果 Student 没有实现 Comparable<Student>，同时 TreeMap 又没有提供 Comparator，那么就没有排序规则。

一种解决方案是让 Student 自己实现：

Comparable<Student>

例如：

public class Student implements Comparable<Student> {

    private int id;
    private String name;

    public Student(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public int compareTo(Student other) {
        return Integer.compare(this.id, other.id);
    }

    @Override
    public String toString() {
        return "Student{id=%d, name='%s'}".formatted(id, name);
    }
}

现在：

TreeMap<Student, Integer> map = new TreeMap<>();

就可以根据：

student.id

排序。

2.8 使用 Comparator 自定义排序

如果不想修改 Student 类本身，可以：

TreeMap<Student, Integer> map =
        new TreeMap<>(
                (s1, s2) -> Integer.compare(s1.getId(), s2.getId())
        );

如果想倒序：

TreeMap<Student, Integer> map =
        new TreeMap<>(
                (s1, s2) -> Integer.compare(s2.getId(), s1.getId())
        );

注意两个方向：

Integer.compare(s1.getId(), s2.getId())

通常表示：

id 小 → id 大

而：

Integer.compare(s2.getId(), s1.getId())

则将方向反过来：

id 大 → id 小

2.9 多条件排序

实际开发中经常不是只比较一个字段。

例如：

先按工资降序，如果工资相同，再按年龄升序，如果仍相同，再按姓名排序。

可以使用 Comparator 链：

Comparator<Teacher> comparator =
        Comparator.comparingDouble(Teacher::getSalary)
                .reversed()
                .thenComparingInt(Teacher::getAge)
                .thenComparing(Teacher::getName);

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

这个例子非常重要。

因为如果只写：

(o1, o2) ->
        Double.compare(o2.getSalary(), o1.getSalary())

那么：

Teacher A：salary = 10000

Teacher B：salary = 10000

比较结果：

0

TreeMap 就会把二者视为相同排序键。

如果业务上它们实际上是两个不同教师，就可能出现 value 被覆盖。

因此排序规则必须同时回答两个问题：

1. 谁排在谁前面？

2. 什么情况下两个 key 被视为相等？

第二个问题尤其重要。

三、使用方法

3.1 创建 TreeMap

自然排序：

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

如果后面需要 TreeMap 特有 API，可以写：

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

3.2 添加键值对

仍然使用 Map 的：

put(K key, V value)

例如：

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

map.put(3, "Java");
map.put(1, "C");
map.put(4, "Python");
map.put(2, "C++");

TreeMap 会根据 key 自动维护排序关系。

3.3 获取元素

普通 Map API 依然可以使用：

map.get(key);
map.containsKey(key);
map.containsValue(value);
map.remove(key);
map.size();
map.isEmpty();

例如：

System.out.println(map.get(2));
System.out.println(map.containsKey(3));

TreeMap 仍然是 Map。

排序能力是在 Map 基础上的增强，而不是完全另一套集合。

3.4 遍历 TreeMap

可以继续使用 entrySet()：

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

因为 TreeMap 的 key 本身有序，因此遍历结果会按照 TreeMap 的比较规则进行。

也可以：

map.forEach((key, value) ->
        System.out.println(key + "=" + value));

3.5 获取第一个和最后一个 key

TreeMap 还具有排序 Map 特有的能力。

例如：

TreeMap<Integer, String> scores = new TreeMap<>();

scores.put(60, "及格");
scores.put(80, "良好");
scores.put(90, "优秀");

System.out.println(scores.firstKey());
System.out.println(scores.lastKey());

可以直接获得：

最小 key
最大 key

这体现了 TreeMap 与 HashMap 的本质差异：

HashMap
重点：快速映射

TreeMap
重点：有序映射

3.6 floor、ceiling、lower、higher

TreeMap 还支持有序查询。

假设：

10
20
30
40

查询：

map.floorKey(25);

含义：

找到 <= 25 的最大 key。

结果：

20

而：

map.ceilingKey(25);

表示：

找到 >= 25 的最小 key。

结果：

30

对应：

| 方法 | 含义 | | --------------- | --------------------- | | lowerKey(k) | 严格小于 k 的最大 key | | floorKey(k) | 小于等于 k 的最大 key | | ceilingKey(k) | 大于等于 k 的最小 key | | higherKey(k) | 严格大于 k 的最小 key |

这类 API 非常适合：

  • 时间区间
  • 分数区间
  • 价格区间
  • 版本号映射
  • 阶梯规则

3.7 获取一段范围

例如：

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

map.put(10, "A");
map.put(20, "B");
map.put(30, "C");
map.put(40, "D");
map.put(50, "E");

System.out.println(map.subMap(20, true, 40, true));

可以得到指定 key 区间。

还包括：

headMap(...)
tailMap(...)
subMap(...)

因此 TreeMap 不只是：

“一个会自动排序的 HashMap”。

它本质上还是一个：

SortedMap / NavigableMap。

四、原理与进阶

4.1 TreeMap 底层是红黑树

TreeMap 的核心底层数据结构是：

Red-Black Tree
红黑树

它属于一种：

自平衡二叉搜索树

可以抽象理解：

        30
       /  \
     20    50
    / \    / \
   10 25  40 60

因为树节点按照比较规则组织，所以可以进行：

左边较小
当前节点
右边较大

这样的定向查找。

4.2 为什么不用普通二叉搜索树

普通二叉搜索树如果输入：

1
2
3
4
5
6

可能退化成：

1
 \
  2
   \
    3
     \
      4
       \
        5

最终接近链表。

查找性能会变差。

红黑树通过旋转和变色等机制维持近似平衡，使树高保持在合理范围。

因此 TreeMap 的主要操作可以维持：

O(log n)

级别。

4.3 TreeMap 典型时间复杂度

JDK 21 的 TreeMap 对以下操作提供对数级时间保证：

put
get
remove
containsKey

典型复杂度：

O(log n)

与 HashMap 形成鲜明对比：

HashMap
平均情况下：
O(1)

TreeMap：
O(log n)

所以：

如果不需要排序，通常没必要仅仅为了“高级”而使用 TreeMap。

HashMap 通常具有更好的普通键值查找性能。

TreeMap 的价值来自：

排序
+
范围查询
+
有序导航

4.4 TreeMap 如何判断两个 key 相同

这是本章最关键的原理之一。

对于 HashMap：

hashCode
+
equals

非常关键。

对于 TreeMap：

compareTo
或者
Comparator.compare

才是排序和定位 key 的核心。

假设：

Comparator<Student> comparator =
        Comparator.comparingInt(Student::getAge);

然后：

Student("张三", 20)

Student("李四", 20)

比较：

20 vs 20

得到：

0

TreeMap 会从排序结构角度将这两个 key 视为相同。

因此：

TreeMap 中的“不重复”

不能简单理解成：

equals() 不相等就一定能同时存在

更准确的是：

如果 TreeMap 的比较规则认为两个 key 相等，即比较结果为 0，它们就是同一个排序键位置。

4.5 排序规则与 equals 最好保持一致

考虑：

Student a = new Student(1, "张三", 20);
Student b = new Student(2, "李四", 20);

假设：

equals
根据 id 比较

所以：

a.equals(b) == false

但 TreeMap Comparator：

Comparator.comparingInt(Student::getAge)

得到：

20 == 20
→ compare(a,b) == 0

于是出现：

equals 认为：
不是同一个对象

排序规则认为：
是同一个 key

这会让 SortedMap 的行为非常容易令人困惑。

因此通常建议：

TreeMap 的比较规则与对象的 equals 语义保持一致，或者至少明确知道为什么不一致。

4.6 TreeMap 能不能存 null key

默认自然排序：

new TreeMap<>()

通常不能直接使用：

null

作为 key。

因为自然排序需要执行比较，而 null 没有：

compareTo()

如果使用自定义 Comparator，并且 Comparator 明确支持 null，则可以设计允许 null 的排序规则。

例如思想上可以使用：

Comparator.nullsFirst(...)

但普通业务代码中，更重要的是：

不要依赖 TreeMap 的 null key 作为常规设计。

value 则可以为 null。

五、实践应用

5.1 词频统计后按字典序输出

假设统计：

java
python
java
c
python
java

使用 TreeMap：

TreeMap<String, Integer> countMap = new TreeMap<>();

for (String word : words) {
    countMap.put(
            word,
            countMap.getOrDefault(word, 0) + 1
    );
}

最终：

c=1
java=3
python=2

统计结果天然按照 key 顺序输出。

5.2 HashMap 统计 + TreeMap 排序

实际开发中也可以：

第一阶段：
HashMap
负责快速统计

第二阶段：
TreeMap
负责按 key 排序

例如：

Map<String, Integer> counter = new HashMap<>();

// 完成大量统计……

Map<String, Integer> sorted = new TreeMap<>(counter);

这种组合体现了一个重要工程思想：

不同集合负责不同职责。

不是一定只能“从头到尾用一种集合”。

5.3 分数等级匹配

例如规则：

0  → 不及格
60 → 及格
80 → 良好
90 → 优秀

可以：

TreeMap<Integer, String> levels = new TreeMap<>();

levels.put(0, "不及格");
levels.put(60, "及格");
levels.put(80, "良好");
levels.put(90, "优秀");

学生：

score = 87

可以利用：

levels.floorEntry(score)

找到：

80 → 良好

这种“阶梯规则”就是 TreeMap 很典型的应用。

5.4 时间版本映射

例如系统配置：

2026-01-01 → 配置 A
2026-04-01 → 配置 B
2026-08-01 → 配置 C

如果查询：

2026-06-15

可以寻找：

小于等于该时间的最新配置。

本质仍然是：

floorEntry

TreeMap 的有序性能够非常自然地解决这类问题。

六、常见问题

6.1 TreeMap 按 key 还是 value 排序？

只按照：

key

排序。

value 不决定 TreeMap 的结构位置。

6.2 TreeMap 是不是比 HashMap 更高级？

不是。

它们解决不同问题。

HashMap
→ 更关注普通键值映射性能

TreeMap
→ 更关注排序和范围查询

技术选型不存在简单的：

A 高级
B 低级

而应该问：

需求是什么？

6.3 TreeMap 为什么没有索引？

因为 TreeMap 的本质不是：

0
1
2
3

这样的线性位置模型。

它是：

key → value

并且按照 key 的比较关系建立树结构。

6.4 自定义 key 一定要实现 Comparable 吗？

不一定。

两种方式任选其一：

key 实现 Comparable

或者：

创建 TreeMap 时提供 Comparator

6.5 Comparator 和 Comparable 同时存在使用谁？

如果创建 TreeMap 时明确传入：

new TreeMap<>(comparator)

则使用这个 Comparator。

可以理解为：

TreeMap 自己指定的 Comparator
优先于
key 自己的自然排序

6.6 Comparator 返回 0 会发生什么？

TreeMap 会从排序意义上将两个 key 视为相同。

这可能导致：

后 put 的 value
覆盖前一个 value

因此 Comparator 绝不能只考虑“排序好看”，还必须考虑：

哪些对象允许被认为是相同 key？

6.7 为什么比较 double 不建议直接相减再强转 int？

例如不要写：

return (int) (o1.getSalary() - o2.getSalary());

因为可能出现：

  • 小数精度问题
  • 差值不足 1 被截断为 0
  • 极端数值问题

应该使用：

Double.compare(a, b);

七、练习与验收

7.1 知识问答

  1. TreeMap 的三个核心特点是什么？
  2. TreeMap 按 key 还是 value 排序？
  3. TreeMap 的底层主要是什么数据结构？
  4. TreeMap 与 HashMap 的核心区别是什么？
  5. TreeMap 与 LinkedHashMap 的“有序”分别表示什么？
  6. TreeMap 有哪两种指定排序规则的方式？
  7. Comparable 与 Comparator 的职责分别是什么？
  8. Comparator 返回正数、负数和 0 分别表示什么？
  9. 为什么 Comparator 返回 0 会影响 TreeMap 的 key 去重？
  10. TreeMap 的 put/get/remove/containsKey 典型复杂度是多少？
  11. 为什么没有排序需求时通常优先考虑 HashMap？
  12. 什么情况下 TreeMap 的范围查询能力比 HashMap 更适合？
  13. 为什么排序规则最好与 equals 保持一致？

7.2 代码阅读

阅读：

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

map.put(30, "C");
map.put(10, "A");
map.put(20, "B");
map.put(20, "Java");

System.out.println(map);

回答：

  1. TreeMap 最终有几个键值对？
  2. key 的遍历顺序是什么？
  3. 20 最终对应什么 value？
  4. 为什么？

阅读：

TreeMap<Student, String> map =
        new TreeMap<>(
                (s1, s2) ->
                        Integer.compare(s1.getAge(), s2.getAge())
        );

随后加入：

张三，20
李四，20
王五，21

回答：

  1. 三个 Student 是否一定都能作为独立 key 保存？
  2. 哪两个对象的 Comparator 结果可能是 0？
  3. 如何修改比较规则避免非预期覆盖？

7.3 手写代码

  1. 使用 TreeMap<Integer,String> 保存学号和姓名，并按照学号升序输出。
  2. 改为学号降序。
  3. 定义 Teacher，按照 salary 降序排序。
  4. salary 相同时，再按照 age 升序。
  5. age 仍相同时，再按照 name 排序。
  6. 使用 TreeMap 完成字符串词频统计，并按单词字典序输出。
  7. 使用 TreeMap 的范围查询 API 完成分数等级匹配。

7.4 Debug

下面 Comparator 存在业务风险：

TreeMap<Teacher, String> map =
        new TreeMap<>(
                (t1, t2) ->
                        Double.compare(
                                t2.getSalary(),
                                t1.getSalary()
                        )
        );

要求：

  1. 判断当前排序是升序还是降序。
  2. 如果两个 Teacher 的 salary 相同，会发生什么？
  3. 为什么这可能导致数据被覆盖？
  4. 增加第二、第三排序条件修复。

下面代码：

TreeMap<Student, String> map = new TreeMap<>();

map.put(new Student(1, "张三"), "A");

假设 Student 没有实现 Comparable。

要求：

  1. 分析问题产生原因。
  2. 给出 Comparable 解决方案。
  3. 给出 Comparator 解决方案。

7.5 综合训练

设计一个考试成绩等级系统。

要求：

0  → 不及格
60 → 及格
70 → 中等
80 → 良好
90 → 优秀

输入任意：

0~100

的成绩。

要求使用 TreeMap 的有序查询能力，判断该学生对应等级。

禁止通过：

if-else if

硬编码全部等级区间。

并思考：

  1. 为什么 TreeMap 非常适合阶梯配置？
  2. 如果增加一个新的 95 → 卓越，程序主体是否需要修改？

7.6 本章验收

  • [ ] 能闭卷说出 TreeMap 的核心特点。
  • [ ] 能说出 TreeMap、HashMap、LinkedHashMap 的选择区别。
  • [ ] 能解释 TreeMap 为什么基于 key 排序。
  • [ ] 能手写 Comparable 和 Comparator 两种 TreeMap 排序方式。
  • [ ] 能解释 Comparator 返回 0 对 key 唯一性的影响。
  • [ ] 能解释 TreeMap 红黑树与 O(log n) 的关系。
  • [ ] 能使用 firstKey、lastKey、floorKey、ceilingKey。
  • [ ] 能完成一个 TreeMap 范围查询案例。
  • [ ] 能根据业务需求判断是否应该选择 TreeMap。