跳到主要内容

Java TreeMap

介绍​

TreeMap 是 Java 集合框架中的一个重要类，它实现了 NavigableMap 接口，并基于红黑树（Red-Black Tree）数据结构。TreeMap 中的元素按照键的自然顺序或自定义比较器进行排序，因此它提供了高效的键值对存储和检索功能。

与 HashMap 不同，TreeMap 保证了键的有序性，这使得它在需要排序的场景中非常有用。接下来，我们将逐步讲解 TreeMap 的基本用法、特性以及实际应用。

基本用法​

创建 TreeMap​

要创建一个 TreeMap，可以使用以下代码：

java
import java.util.TreeMap;

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

        // 添加键值对
        treeMap.put("Apple", 10);
        treeMap.put("Banana", 5);
        treeMap.put("Cherry", 20);

        // 输出 TreeMap
        System.out.println(treeMap);
    }
}

输出：

{Apple=10, Banana=5, Cherry=20}
备注

TreeMap 默认按照键的自然顺序（如字符串的字典序）进行排序。如果需要自定义排序规则，可以在构造函数中传入一个 Comparator。

自定义排序​

以下示例展示了如何使用自定义比较器对 TreeMap 进行排序：

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

public class TreeMapCustomSort {
    public static void main(String[] args) {
        // 创建一个按字符串长度排序的 TreeMap
        TreeMap<String, Integer> treeMap = new TreeMap<>(Comparator.comparingInt(String::length));

        treeMap.put("Apple", 10);
        treeMap.put("Banana", 5);
        treeMap.put("Cherry", 20);

        System.out.println(treeMap);
    }
}

输出：

{Apple=10, Cherry=20, Banana=5}
提示

在这个例子中，TreeMap 按照键的字符串长度进行排序。如果长度相同，则保留插入顺序。

TreeMap 的特性​

有序性​

TreeMap 的一个显著特性是它的有序性。无论插入顺序如何，TreeMap 中的键始终按照排序规则排列。例如：

java
TreeMap<Integer, String> treeMap = new TreeMap<>();
treeMap.put(3, "Three");
treeMap.put(1, "One");
treeMap.put(2, "Two");

System.out.println(treeMap);

输出：

{1=One, 2=Two, 3=Three}

高效的查找操作​

由于 TreeMap 基于红黑树实现，它的查找、插入和删除操作的时间复杂度为 O(log n)，这使得它在需要频繁查找的场景中非常高效。

实际应用场景​

场景 1：统计单词频率​

假设我们需要统计一段文本中每个单词的出现频率，并按照字母顺序输出结果。TreeMap 是一个理想的选择：

java
import java.util.TreeMap;

public class WordFrequency {
    public static void main(String[] args) {
        String text = "apple banana apple cherry banana apple";
        String[] words = text.split(" ");

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

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

        System.out.println(frequencyMap);
    }
}

输出：

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

场景 2：范围查询​

TreeMap 提供了丰富的方法来支持范围查询，例如 subMap()、headMap() 和 tailMap()。以下示例展示了如何获取某个范围内的键值对：

java
import java.util.TreeMap;

public class RangeQuery {
    public static void main(String[] args) {
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(1, "One");
        treeMap.put(2, "Two");
        treeMap.put(3, "Three");
        treeMap.put(4, "Four");
        treeMap.put(5, "Five");

        // 获取键在 2 到 4 之间的子映射
        System.out.println(treeMap.subMap(2, true, 4, true));
    }
}

输出：

{2=Two, 3=Three, 4=Four}

总结​

TreeMap 是 Java 中一个强大的数据结构，适用于需要有序键值对的场景。它的主要特点包括：

  • 键的有序性（自然顺序或自定义顺序）。
  • 高效的查找、插入和删除操作（时间复杂度为 O(log n)）。
  • 支持范围查询和其他高级操作。

通过本文的学习，你应该已经掌握了 TreeMap 的基本用法和实际应用场景。接下来，可以通过以下练习进一步巩固你的知识：

练习​

  1. 创建一个 TreeMap，存储学生的姓名和成绩，并按照成绩从高到低排序。
  2. 使用 TreeMap 实现一个简单的电话簿，支持按姓名查找电话号码。
  3. 尝试使用 TreeMap 的 headMap() 和 tailMap() 方法，分别获取小于和大于某个键的子映射。

附加资源​

警告

在使用 TreeMap 时，请确保键的类型实现了 Comparable 接口，或者在构造函数中提供了自定义的 Comparator，否则会抛出 ClassCastException。