TreeMap 是 Java 集合框架中一个非常重要的 Map 实现，它的核心特点就是能够自动对其中的键进行排序,这种排序功能使得它在需要维护键值对有序性的场景下非常有用。

核心原理：红黑树

TreeMap 的底层实现是红黑树,这是一种自平衡的二叉查找树。

• 自动排序：当元素被插入到 TreeMap 中时，红黑树会根据键的比较结果，将元素放置在正确的位置,以保证整个树的中序遍历结果就是键的有序序列。
• 高效操作：由于是树结构，TreeMap 的 get(), put(), remove() 等操作的时间复杂度都是 O(log n)，这比 HashMap 的平均 O(1) 要慢,但在需要有序性时是值得的。

TreeMap 的两种排序方式

TreeMap 提供了两种主要的排序方式：

1. 自然排序
2. 自定义排序

自然排序

这是 TreeMap 默认的排序方式，当你在创建 TreeMap 时没有指定比较器，它会要求键对象必须实现 java.lang.Comparable 接口，并调用其 compareTo() 方法来进行比较和排序。

规则：

• 如果键是数字类型（如 Integer, Double）,则按数值大小从小到大排序。
• 如果键是字符类型（如 Character），则按 Unicode 码值从小到大排序。
• 如果键是字符串，则按字典序（字母顺序）从小到大排序。
• 如果键是自定义对象，则该对象必须实现 Comparable 接口。

示例代码：

a) 使用基本类型和字符串作为键

import java.util.TreeMap;
public class NaturalOrderExample {
    public static void main(String[] args) {
        // 1. 使用 Integer 作为键，自动按数值排序
        TreeMap<Integer, String> integerMap = new TreeMap<>();
        integerMap.put(30, "Thirty");
        integerMap.put(10, "Ten");
        integerMap.put(20, "Twenty");
        integerMap.put(5, "Five");
        System.out.println("Integer TreeMap (Natural Order): " + integerMap);
        // 输出: {5=Five, 10=Ten, 20=Twenty, 30=Thirty}
        System.out.println("-----------------------------------");
        // 2. 使用 String 作为键，自动按字典序排序
        TreeMap<String, Integer> stringMap = new TreeMap<>();
        stringMap.put("Charlie", 3);
        stringMap.put("Alice", 1);
        stringMap.put("Bob", 2);
        stringMap.put("David", 4);
        System.out.println("String TreeMap (Natural Order): " + stringMap);
        // 输出: {Alice=1, Bob=2, Charlie=3, David=4}
    }
}

b) 使用自定义对象作为键（必须实现 Comparable）

假设我们有一个 Student 类,我们希望按学生的年龄进行排序。

import java.util.TreeMap;
// 1. 自定义 Student 类，实现 Comparable 接口
class Student implements Comparable<Student> {
    private String name;
    private int age;
    public Student(String name, int age) {
        this.name = name;
        this.age = age;
    }
    public String getName() {
        return name;
    }
    public int getAge() {
        return age;
    }
    @Override
    public String toString() {
        return "Student{name='" + name + "', age=" + age + "}";
    }
    // 2. 实现 compareTo 方法，定义排序规则（这里按年龄排序）
    @Override
    public int compareTo(Student other) {
        // this < other  -> 返回负数
        // this == other -> 返回 0
        // this > other  -> 返回正数
        return this.age - other.age;
    }
}
public class CustomObjectNaturalOrderExample {
    public static void main(String[] args) {
        TreeMap<Student, String> studentMap = new TreeMap<>();
        studentMap.put(new Student("David", 22), "CS101");
        studentMap.put(new Student("Alice", 20), "MATH101");
        studentMap.put(new Student("Charlie", 21), "PHYS101");
        studentMap.put(new Student("Bob", 20), "ENG101"); // 年龄与 Alice 相同
        System.out.println("Student TreeMap (sorted by age): " + studentMap);
        // 输出:
        // Student TreeMap (sorted by age): [
        //   Student{name='Alice', age=20}=MATH101,
        //   Student{name='Bob', age=20}=ENG101,
        //   Student{name='Charlie', age=21}=PHYS101,
        //   Student{name='David', age=22}=CS101
        // ]
        // 注意：当年龄相同时，compareTo 返回 0，TreeMap 会认为它们是同一个键（后 put 的会覆盖先前的）。
        // 这里的结果是 Alice 被覆盖了，或者 Bob 被覆盖了，取决于 JVM 的具体实现和插入顺序。
        // 要解决这个问题，可以在 compareTo 中增加对 name 的二次比较。
    }
}

自定义排序

如果你无法修改键类的源代码（使用 String 作为键但你希望按长度排序），或者你希望有多种不同的排序规则,可以使用自定义排序。

实现方式： 在创建 TreeMap 时，传入一个 java.util.Comparator 对象。Comparator 是一个“外部”的比较器,它定义了如何比较两个对象。

如何创建 Comparator：

• 匿名内部类 (Java 7 及之前)
• Lambda 表达式 (Java 8 及之后,推荐)

示例代码：

假设我们希望 String 键按长度排序,而不是默认的字典序。

import java.util.TreeMap;
import java.util.Comparator;
public class CustomComparatorExample {
    public static void main(String[] args) {
        // 1. 使用 Lambda 表达式创建 Comparator
        // 比较规则：按字符串长度升序排序
        Comparator<String> lengthComparator = (s1, s2) -> Integer.compare(s1.length(), s2.length());
        // 2. 在创建 TreeMap 时传入这个 Comparator
        TreeMap<String, Integer> mapByLength = new TreeMap<>(lengthComparator);
        mapByLength.put("Apple", 1);
        mapByLength.put("Banana", 2);
        mapByLength.put("Kiwi", 3);
        mapByLength.put("Mango", 4);
        mapByLength.put("Grape", 5);
        System.out.println("String TreeMap (sorted by length): " + mapByLength);
        // 输出: {Kiwi=3, Apple=1, Mango=4, Grape=5, Banana=2}
        // 注意：当长度相同时（如 "Apple" 和 "Mango"），TreeMap 会保持它们插入时的相对顺序（稳定排序）。
        // 这是 Java 8 中对 `Comparable` 和 `Comparator` 的一个改进。
        System.out.println("-----------------------------------");
        // 3. 另一个例子：按字符串长度降序排序
        TreeMap<String, Integer> mapByLengthDesc = new TreeMap<>((s1, s2) -> {
            // s2.length > s1.length, 返回正数，表示 s1 应该在 s2 后面
            return s2.length() - s1.length();
        });
        mapByLengthDesc.put("Apple", 1);
        mapByLengthDesc.put("Banana", 2);
        mapByLengthDesc.put("Kiwi", 3);
        mapByLengthDesc.put("Mango", 4);
        mapByLengthDesc.put("Grape", 5);
        System.out.println("String TreeMap (sorted by length descending): " + mapByLengthDesc);
        // 输出: {Banana=2, Grape=5, Apple=1, Mango=4, Kiwi=3}
    }
}

总结与最佳实践

关键点回顾：

1. TreeMap 总是有序的，这是它区别于 HashMap 和 LinkedHashMap 的核心特征。
2. 排序只针对键,值是无序的。
3. 两种排序方式是互斥的：如果你在创建 TreeMap 时传入了 Comparator，TreeMap 就会使用自定义排序，而忽略键类可能实现的 Comparable 接口。
4. 排序规则必须与 equals 方法一致（这虽然不是强制要求，但强烈推荐），如果两个对象根据 compareTo 或 compare 方法被认为是相等的（返回 0），那么它们在 TreeMap 中会被视为同一个键，后插入的会覆盖先前的，这可能会导致违反 Map 接口的一般约定（即两个不相等的 key 不能对应同一个 value），如果需要避免覆盖，可以在 Comparator 中增加更细致的比较逻辑（先按年龄，年龄相同再按姓名）。

希望这个详细的解释能帮助你完全理解 Java TreeMap 的排序机制！