TreeMap 是 Java 中的一个基于红黑树的 Map 实现，它保证了键值对按照键的自然顺序或自定义的比较器进行排序。在 TreeMap 中，键必须是唯一的，并且元素以有序的方式存储，这使得它适合于需要按键排序的数据集。由于是基于树的结构，TreeMap 提供了对数时间复杂度的搜索、插入和删除操作。它通常用于需要有序遍历键值对的场景，如字典序排序、范围查询和有序映射。

肖哥弹架构 跟大家“弹弹” 高并发锁， 关注公号回复 'mvcc' 获得手写数据库事务代码

欢迎 点赞，关注，评论。

关注公号 Solomon 肖哥弹架构获取更多精彩内容

历史热点文章

• 解锁大语言模型参数：零基础掌握大型语言模型参数奥秘与实践指南
  

• 高性能连接池之HikariCP框架分析：高性能逐条分解(架构师篇)
  

• 缓存雪崩/穿透/击穿/失效原理图/14种缓存数据特征+10种数据一致性方案
  

• Java 8函数式编程全攻略：43种函数式业务代码实战案例解析(收藏版)
  

• 一个项目代码讲清楚DO/PO/BO/AO/E/DTO/DAO/ POJO/VO
  

• 17个Mybatis Plugs注解：Mybatis Plugs插件架构设计与注解案例(必须收藏)
  

2.3 TreeMap

设计思考：

1. 需求场景：

2. 在许多应用中，需要根据键的自然顺序或自定义顺序来存储和检索键值对。例如，需要实现有序的查找表、索引表或执行范围查询等。

3. 适用于需要有序遍历键值对的场景，如字典、词典、电话簿等。

4. 现有技术局限性：

5. HashMap 和 Hashtable 提供了快速的查找性能，但它们不维护键的任何顺序。

6. 其他线性数据结构，如 ArrayList 或 LinkedList，虽然可以保持元素顺序，但查找性能为 O(n)。

7. 技术融合：

8. TreeMap 结合了哈希表的快速查找特性和二叉搜索树的有序性，使用红黑树（一种自平衡的二叉搜索树）来维护键的排序。

9. 设计理念：

10. TreeMap 提供了一个能够根据键的自然顺序或指定的 Comparator 来维护键的顺序的映射结构，同时保持了快速的查找性能。

11. 实现方式：

12. TreeMap 内部使用一个红黑树来存储键值对，每个节点包含键、值以及指向父节点、左子节点、右子节点的引用。

13. 插入、删除和查找操作都通过维护红黑树的平衡来保证 O(log n) 的时间复杂度。

2.3.1 数据结构

图说明：

• TreeMap：

• 表示 TreeMap 类的实例，是一个基于红黑树的有序键值对集合。

• RedBlackTree：

• TreeMap 内部使用一个红黑树来存储键值对，确保元素处于排序状态。

• Root：

• 根节点，是红黑树的入口点，树中所有节点的父节点都是根节点。

• Node：

• 红黑树中的节点，包含键值对和指向左右子节点以及父节点的引用。

• Key：

• 节点中存储的键。

• Value：

• 节点中存储的值。

• Left Child & Right Child：

• 节点的左子节点和右子节点，用于维护树的结构和顺序。

• Parent：

• 节点的父节点，用于维护树的父子关系。

• Color：

• 节点的颜色，红黑树中的节点颜色可以是红色或黑色，用于维护树的平衡。

2.3.2 执行流程

图说明：

• 创建 TreeMap 实例：初始化 TreeMap 对象。

• 插入元素(put) ：执行将键值对插入到 TreeMap 的操作。

• 计算键的哈希码：计算插入键的哈希码以确定其在树中的位置。

• 确定节点位置：根据哈希码确定节点在树中的大致位置。

• 处理哈希冲突：如果存在哈希冲突，将节点插入到相应的链表中。

• 插入节点：将节点插入到树中，并维护红黑树的性质。

• 查找元素(get) ：执行根据键查找值的操作。

• 遍历树节点：从根节点开始遍历树，直到找到对应的键。

• 找到节点：找到包含指定键的节点。

• 返回值：返回找到节点的值。

• 删除元素(remove) ：执行根据键删除键值对的操作。

• 找到节点：找到包含指定键的节点。

• 删除节点：从树中删除节点，并维护红黑树的性质。

• 重新平衡树：删除节点后，可能需要对树进行重新平衡。

优点

1. 有序性：

2. 元素会根据键的自然顺序或构造时提供的 Comparator 进行排序。

3. 快速查找：

4. 提供了对数时间复杂度的查找性能。

5. 元素唯一性：

6. 自动处理元素的唯一性，避免了重复键的问题。

7. 范围查询：

8. 可以方便地进行范围查询和获取子集。

缺点

1. 性能开销：

2. 相比于 HashMap，TreeMap 在添加、删除和查找操作上有更高的性能开销。

3. 内存消耗：

4. 相比于 HashMap，TreeMap 可能需要更多的内存来存储红黑树结构。

5. 数据实时性：

6. 由于排序操作的开销，TreeMap 在数据更新时可能不如 HashMap 快。

使用场景

• 需要保持元素排序顺序的场景：

• 适用于排序的配置列表、按顺序执行的任务调度等。

• 需要进行范围查询的场景：

• 适用于需要执行范围查找或有序遍历的应用程序。

7、类设计

8、应用案例

TreeMap 通常用于需要根据键的自然顺序或自定义顺序存储和检索数据的情况。这是一个学生成绩管理系统，其中学生的成绩按照学生 ID 或姓名进行排序：

import java.util.Comparator;import java.util.Map;import java.util.TreeMap;
// 学生类，包含学生姓名和分数class Student {    private String name;    private int score;
    public Student(String name, int score) {        this.name = name;        this.score = score;    }
    public String getName() {        return name;    }
    public int getScore() {        return score;    }
    @Override    public String toString() {        return "Student{" +               "name='" + name + ''' +               ", score=" + score +               '}';    }}
public class StudentGrades {    public static void main(String[] args) {        // 创建一个 TreeMap 来存储学生的成绩，按照学生姓名排序        TreeMap<String, Integer> studentGrades = new TreeMap<>();
        // 添加学生及其成绩        studentGrades.put("Alice", 90);        studentGrades.put("Bob", 80);        studentGrades.put("Charlie", 70);        studentGrades.put("David", 85);        studentGrades.put("Eve", 95);
        // 遍历 TreeMap 并打印每个学生的成绩        for (Map.Entry<String, Integer> entry : studentGrades.entrySet()) {            System.out.println(entry.getKey() + ": " + entry.getValue());        }
        // 查找特定学生的成绩        String studentName = "Charlie";        if (studentGrades.containsKey(studentName)) {            System.out.println("Grade for " + studentName + " is " + studentGrades.get(studentName));        } else {            System.out.println("Student not found.");        }
        // 获取成绩最高的学生        String topStudent = studentGrades.lastKey();        System.out.println("Top student is " + topStudent + " with a grade of " + studentGrades.get(topStudent));    }}