Java TreeMap

Java TreeMap

TreeMap 是 Java 集合框架（Java Collections Framework）中的一个重要类，它实现了 SortedMap 接口，基于红黑树（Red-Black Tree）数据结构存储键值对。TreeMap 的主要特点是能够按照键的自然顺序或自定义顺序进行排序，并提供高效的查找、插入和删除操作。

概述

TreeMap 是一个有序的键值对集合，其中：

• 键（Key）必须是可比较的（实现 Comparable 接口），或者在构造 TreeMap 时提供 Comparator。
• 值（Value）可以是任意对象。
• 默认情况下，键按照自然顺序（升序）排序，但也可以自定义排序规则。

TreeMap 的时间复杂度：

• 查找（get）、插入（put）、删除（remove）操作的平均时间复杂度为 $O(\log n)$。

基本用法

创建 TreeMap

以下示例展示如何创建一个 TreeMap 并添加元素：

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", 20);
        treeMap.put("Cherry", 30);

        System.out.println(treeMap); // 输出：{Apple=10, Banana=20, Cherry=30}
    }
}

输出：

{Apple=10, Banana=20, Cherry=30}

自定义排序

可以通过传递 Comparator 来自定义排序逻辑：

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

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

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

        System.out.println(treeMap); // 输出：{Kiwi=5, Apple=10, Banana=20, Cherry=30}
    }
}

输出：

{Kiwi=5, Apple=10, Banana=20, Cherry=30}

核心方法

TreeMap 提供了一系列方法来操作和查询数据：

常用方法

• put(K key, V value)：插入键值对。
• get(K key)：获取键对应的值。
• remove(K key)：删除键值对。
• containsKey(K key)：检查是否包含某个键。
• firstKey()：返回最小的键。
• lastKey()：返回最大的键。
• subMap(K fromKey, K toKey)：返回子映射（范围查询）。

示例：范围查询

import java.util.TreeMap;

public class RangeQueryExample {
    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, 4)); // 输出：{2=Two, 3=Three}
    }
}

输出：

{2=Two, 3=Three}

内部实现：红黑树

TreeMap 基于红黑树（一种自平衡二叉查找树）实现，确保操作的时间复杂度为 $O(\log n)$。

红黑树的特性： 1. 每个节点是红色或黑色。 2. 根节点是黑色。 3. 红色节点的子节点必须是黑色。 4. 从任一节点到其叶子节点的路径包含相同数量的黑色节点。

实际应用案例

案例 1：统计单词频率

TreeMap 可用于统计文本中单词的出现频率，并按字母顺序排序：

import java.util.TreeMap;

public class WordFrequencyCounter {
    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}
    }
}

输出：

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

案例 2：事件调度系统

TreeMap 可用于存储按时间排序的事件：

import java.util.TreeMap;

public class EventScheduler {
    public static void main(String[] args) {
        TreeMap<Long, String> events = new TreeMap<>();
        events.put(System.currentTimeMillis() + 5000, "Send email");
        events.put(System.currentTimeMillis() + 2000, "Backup database");
        events.put(System.currentTimeMillis() + 1000, "Check updates");

        // 获取最近的事件
        System.out.println("Next event: " + events.firstEntry());
    }
}

总结

• TreeMap 是一个基于红黑树的有序键值对集合。
• 默认按自然顺序排序，也可自定义 Comparator。
• 提供高效的查找、插入、删除操作（$O(\log n)$）。
• 适用于需要排序或范围查询的场景。

参见

• HashMap：基于哈希表的无序键值对集合。
• LinkedHashMap：保持插入顺序的哈希表。