编辑“︁Java TreeMap”︁

= Java TreeMap =

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

== 概述 ==
TreeMap 是一个有序的键值对集合，其中：
* 键（Key）必须是可比较的（实现 [[Comparable]] 接口），或者在构造 TreeMap 时提供 [[Comparator]]。
* 值（Value）可以是任意对象。
* 默认情况下，键按照自然顺序（升序）排序，但也可以自定义排序规则。

TreeMap 的时间复杂度：
* 查找（get）、插入（put）、删除（remove）操作的平均时间复杂度为 <math>O(\log n)</math>。

== 基本用法 ==

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

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

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

'''输出：'''
<pre>
{Apple=10, Banana=20, Cherry=30}
</pre>

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

<syntaxhighlight lang="java">
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}
    }
}
</syntaxhighlight>

'''输出：'''
<pre>
{Kiwi=5, Apple=10, Banana=20, Cherry=30}
</pre>

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

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

=== 示例：范围查询 ===
<syntaxhighlight lang="java">
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}
    }
}
</syntaxhighlight>

'''输出：'''
<pre>
{2=Two, 3=Three}
</pre>

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

<mermaid>
graph TD
    A((5)) --> B((3))
    A --> C((8))
    B --> D((2))
    B --> E((4))
    C --> F((7))
    C --> G((9))
</mermaid>

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

== 实际应用案例 ==

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

<syntaxhighlight lang="java">
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}
    }
}
</syntaxhighlight>

'''输出：'''
<pre>
{apple=3, banana=2, cherry=1}
</pre>

=== 案例 2：事件调度系统 ===
TreeMap 可用于存储按时间排序的事件：

<syntaxhighlight lang="java">
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());
    }
}
</syntaxhighlight>

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

== 参见 ==
* [[HashMap]]：基于哈希表的无序键值对集合。
* [[LinkedHashMap]]：保持插入顺序的哈希表。

[[Category:编程语言]]
[[Category:Java]]
[[Category:Java集合框架]]