在Java的集合框架中，TreeMap是一个非常重要的成员，它实现了SortedMap接口，为键（Key）提供了一个有序的映射。这种有序性是通过红黑树数据结构来实现的，红黑树是一种自平衡的二叉查找树，它能够在最坏的情况下保证基本的动态集合操作（如查找、插入和删除）的时间复杂度仍然是对数的。
1. TreeMap概述
TreeMap存储的键值对默认是按照键的自然顺序进行排序的，也可以根据创建TreeMap时提供的Comparator进行排序。这意味着当你遍历TreeMap时，你会得到一个按键排序的键值对序列。
2. TreeMap的内部结构
红黑树是TreeMap实现有序性的关键。红黑树的特性确保了树的平衡，从而在插入、删除和查找操作时都能保持对数级别的时间复杂度。红黑树的每个节点都有一个颜色属性——红色或黑色，并且满足以下性质：
- 每个节点或是红色，或是黑色。
- 根节点是黑色。
- 每个叶子节点（NIL节点，空节点）是黑色。
- 如果一个节点是红色的，则它的两个子节点都是黑色的。
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
这些性质确保了树的高度相对较低，从而优化了性能。
3. TreeMap的使用场景
- 当你需要一个有序的键值对集合时。
- 当你需要对键进行范围查询时（例如查找所有键在指定范围内的元素）。
- 当你需要一个能够在插入和删除时保持高效性能的数据结构时。
4. 示例代码
下面是一个简单的示例，展示了如何使用TreeMap：
import java.util.TreeMap; public class TreeMapExample { public static void main(String[] args) { // 创建一个TreeMap实例，按照键的自然顺序排序 TreeMap<String, Integer> treeMap = new TreeMap<>(); // 向TreeMap中添加元素 treeMap.put("apple", 1); treeMap.put("orange", 2); treeMap.put("banana", 3); treeMap.put("pear", 4); // 遍历并打印TreeMap中的元素（按键的顺序） for (Map.Entry<String, Integer> entry : treeMap.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); } // 根据键的范围查询元素（包含起始键，不包含结束键） TreeMap<String, Integer> subMap = (TreeMap<String, Integer>) treeMap.subMap("apple", "pear"); System.out.println("Elements between 'apple' and 'pear':"); for (Map.Entry<String, Integer> entry : subMap.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); } } }
输出：
apple: 1 banana: 3 orange: 2 # 注意这里的顺序，因为按照字母顺序排序了键 pear: 4 # 同上，尽管在插入时pear是在orange后面的，但在排序后它的顺序改变了 Elements between 'apple' and 'pear': # 范围查询结果不包括'pear'键对应的元素 apple: 1 banana: 3 # 注意这里只有banana是因为orange不在apple和pear之间（按照字母顺序）
注意：在上面的输出中，你可能会注意到“orange”和“banana”的顺序似乎与插入顺序不同。这是因为TreeMap默认按键的自然顺序（这里是字母顺序）对键进行排序，而不是按照插入顺序。此外，范围查询的结果也是有序的，并且不包括结束键对应的元素。如果你想按照特定的顺序对键进行排序，可以在创建TreeMap时提供一个自定义的Comparator。
5. 自定义排序
为了按照自定义的顺序对TreeMap中的键进行排序，可以在创建时传入一个Comparator对象：
import java.util.Comparator; import java.util.TreeMap; public class CustomSortedTreeMap { public static void main(String[] args) { // 创建一个自定义排序的TreeMap实例（按照字符串长度排序） TreeMap<String, Integer> treeMap = new TreeMap<>(new Comparator<String>() { @Override public int compare(String o1, String o2) { return Integer.compare(o1.length(), o2.length()); } }); // 向TreeMap中添加元素并打印（按键的长度顺序） treeMap.put("apple", 1); // 长度为5的键 treeMap.put("kiwi", 2); // 长度为4的键 treeMap.put("pear", 3); // 长度为4的键 treeMap.put("banana", 4); // 长度为6的键，会被放在最后面即使它是先被插入的 for (Map.Entry<String, Integer> entry : treeMap.entrySet()) { System.out.println(entry.getKey() + ": " + entry.getValue()); } } }
在这个例子中，我们提供了一个自定义的Comparator来按照字符串的长度对键进行排序。因此，“kiwi”和“pear”（长度为4）将出现在“apple”（长度为5）之前，“banana”（长度为6）将出现在最后，即使它是第一个被插入的元素。
