【JavaSE专栏54】Java集合类TreeMap解析，基于红黑树的键值对存储结构

Designer 小郑

发布于 2023-08-02 08:15:08

4030

发布于 2023-08-02 08:15:08

文章被收录于专栏：跟着小郑学JAVA

作者主页：Designer 小郑 作者简介：3年JAVA全栈开发经验，专注JAVA技术、系统定制、远程指导，致力于企业数字化转型，CSDN学院、蓝桥云课认证讲师。 主打方向：Vue、SpringBoot、微信小程序

本文讲解了 Java 中集合类 TreeMap 的语法、使用说明和应用场景，并给出了样例代码。

一、什么是TreeMap

TreeMap 是 Java 中的一个有序映射类，实现了 SortedMap 接口，它是基于红黑树数据结构实现的，用于存储键值对，并根据键的自然顺序或指定的比较器进行排序，与 HashMap 不同，TreeMap 中的元素是按照键的顺序进行排列的。

TreeMap 的主要特点如下。

排序：TreeMap 中的键值对按照键的顺序进行排序，默认情况下按键的自然顺序排序，或者可以通过指定的 Comparator 来进行排序。
有序性：TreeMap 中的键值对是有序的，因此在遍历时可以按照排序顺序获取或操作元素。
动态更新：TreeMap 支持动态插入、删除和修改键值对操作，而且这些操作会保持元素的有序性。
支持范围查询：TreeMap 提供了一系列的方法来支持范围查询，例如 headMap、tailMap 和 subMap 等，这些方法可以根据指定的范围获取子映射。

TreeMap 的应用场景包括以下

点。

排序需求：当需要按照键的顺序访问和处理数据时，可以使用 TreeMap 来存储键值对，并利用排序特性方便地进行相关操作。
范围查询：当需要根据键的范围来查询和操作数据时，可以利用 TreeMap 提供的范围查询方法来快速定位所需的子映射。

提示：由于 TreeMap 是基于红黑树实现的，其插入、删除和查找的时间复杂度为 O(logN)，相对于 HashMap 的 O(1) 复杂度较高，因此在一些对性能要求较高的场景下可能需要权衡使用。

二、TreeMap类的使用

下面是使用 TreeMap 类的示例代码，请同学们复制到本地执行。

import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        // 创建一个TreeMap对象
        TreeMap<Integer, String> treeMap = new TreeMap<>();

        // 向TreeMap中添加键值对
        treeMap.put(3, "Apple");
        treeMap.put(1, "Banana");
        treeMap.put(2, "Orange");
        treeMap.put(4, "Mango");

        // 遍历TreeMap并输出键值对
        for (Integer key : treeMap.keySet()) {
            System.out.println("Key: " + key + ", Value: " + treeMap.get(key));
        }

        // 获取键最小的键值对
        System.out.println("First Entry: " + treeMap.firstEntry());

        // 获取键最大的键值对
        System.out.println("Last Entry: " + treeMap.lastEntry());

        // 获取小于等于给定键的最大键值对
        System.out.println("Floor Entry: " + treeMap.floorEntry(2));

        // 获取大于等于给定键的最小键值对
        System.out.println("Ceiling Entry: " + treeMap.ceilingEntry(3));

        // 删除指定键的键值对
        treeMap.remove(2);

        // 判断TreeMap是否包含指定键
        System.out.println("Contains Key 2: " + treeMap.containsKey(2));
    }
}

这个示例代码展示了使用 TreeMap 类的基本操作。首先创建了一个 TreeMap 对象，并使用 put() 方法向其中添加键值对。然后使用 keySet() 方法遍历 TreeMap 并输出键值对，使用 firstEntry() 和 lastEntry() 方法获取最小和最大的键值对，使用 floorEntry() 和 ceilingEntry() 方法获取小于等于给定键和大于等于给定键的键值对。最后使用 remove() 方法删除指定键的键值对，并使用 containsKey() 方法判断 TreeMap 是否包含指定键。

提示：TreeMap 中的键默认按照自然顺序排序，如果需要使用自定义的比较器来排序，可以在创建 TreeMap 对象时传入比较器。另外，TreeMap 同样是线程不安全的，如果需要在多线程环境下使用，可以考虑使用 ConcurrentSkipListMap 类。

三、TreeMap类的应用场景

TreeMap 类的应用场景包括以下

点，请同学们认真学习。

排序需求：当需要按照键的顺序访问和处理数据时，可以使用 TreeMap 来存储键值对，并利用排序特性方便地进行相关操作。例如，根据学生的分数进行排名、按照日期对事件进行排序等。
范围查询：TreeMap 提供了一系列的方法来支持范围查询，例如 headMap、tailMap 和 subMap 等。这些方法可以根据指定的范围获取子映射。例如，根据日期范围查询某段时间内的事件。
时间轴数据存储：TreeMap 结构适合存储时间轴数据，因为时间是有序的。可以将时间作为键，事件或数据作为值，便于按照时间顺序进行检索和分析。
缓存实现：TreeMap 可以用于实现基于 LRU 算法的缓存。通过在 TreeMap 中存储键值对，并使用访问顺序作为键的比较器，实现缓存中最近访问的元素始终位于 Map 的最后。
数据统计和分析：由于 TreeMap 中的元素是有序的，可以根据键的顺序进行数据统计和分析。例如，可以统计某段时间内的数据变化趋势，找出数据的最大值和最小值等。