红黑树
TreeMap 的底层实现是红黑树（Red-Black Tree），一种自平衡的二叉查找树。
（图片来源网络，侵删）
- 排序发生在哪里？ 排序的逻辑是在插入元素时，通过红黑树的插入和旋转操作来维护的，当你向
TreeMap中添加一个键值对(key, value)时，它会根据key的自然排序（或你指定的Comparator）找到正确的位置插入，并确保整棵树保持平衡。 - 结果：
TreeMap中的键总是处于有序状态，你可以通过keySet(),values(),entrySet()等方法获取到的视图，都是按排序后的顺序遍历的。
如何控制排序？
TreeMap 提供了两种主要的排序方式，你可以根据需求选择：
自然排序
这是最简单的方式,当你创建 TreeMap 时，不提供任何 Comparator，它会要求 Map 的键（Key）对象必须实现 java.lang.Comparable 接口。
Comparable 接口中定义了 compareTo(T o) 方法，用于定义对象之间的“自然”排序规则。
工作原理：
key1.compareTo(key2)返回一个负数，则key1排在key2前面。- 如果返回零，则
key1和key2视为相等。 - 如果返回正数，则
key1排在key2后面。
示例：使用 String 和 Integer 作为键
String 和 Integer 类都已经实现了 Comparable 接口，所以可以直接使用。
import java.util.TreeMap;
public class NaturalOrderExample {
public static void main(String[] args) {
// String 类实现了 Comparable，按字典序排序
TreeMap<String, String> stringMap = new TreeMap<>();
stringMap.put("Charlie", "Charlie's Value");
stringMap.put("Alice", "Alice's Value");
stringMap.put("Bob", "Bob's Value");
stringMap.put("David", "David's Value");
System.out.println("--- String Keys (Natural Order) ---");
// 遍历时会自动按字典序输出
stringMap.forEach((k, v) -> System.out.println(k + " : " + v));
System.out.println("\n--- Integer Keys (Natural Order) ---");
// Integer 类也实现了 Comparable，按数值大小排序
TreeMap<Integer, String> integerMap = new TreeMap<>();
integerMap.put(30, "Thirty");
integerMap.put(10, "Ten");
integerMap.put(20, "Twenty");
integerMap.put(5, "Five");
integerMap.forEach((k, v) -> System.out.println(k + " : " + v));
}
}
输出：
--- String Keys (Natural Order) ---
Alice : Alice's Value
Bob : Bob's Value
Charlie : Charlie's Value
David : David's Value
--- Integer Keys (Natural Order) ---
5 : Five
10 : Ten
20 : Twenty
30 : Thirty自定义排序
Map 的键没有实现 Comparable 接口，或者你不想使用它的自然排序，而是想定义自己的排序规则，那么你可以在创建 TreeMap 时传入一个 Comparator 对象。
Comparator 是一个独立的“比较器”接口，它定义了 compare(T o1, T o2) 方法。
工作原理：
compare(key1, key2)返回一个负数，则key1排在key2前面。- 如果返回零，则
key1和key2视为相等。 - 如果返回正数，则
key1排在key2后面。
示例：使用自定义对象作为键
假设我们有一个 Person 类，我们希望按 age（年龄）来排序。
import java.util.Comparator;
import java.util.TreeMap;
// Person 类，没有实现 Comparable
class Person {
String name;
int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "Person{name='" + name + "', age=" + age + "}";
}
}
public class CustomOrderExample {
public static void main(String[] args) {
// 1. 使用匿名内部类创建 Comparator
Comparator<Person> ageComparator = new Comparator<Person>() {
@Override
public int compare(Person p1, Person p2) {
// 按年龄升序排序
return Integer.compare(p1.age, p2.age);
}
};
TreeMap<Person, String> personMap = new TreeMap<>(ageComparator);
personMap.put(new Person("Alice", 30), "Developer");
personMap.put(new Person("Bob", 25), "Designer");
personMap.put(new Person("Charlie", 35), "Manager");
personMap.put(new Person("David", 22), "Intern");
System.out.println("--- Person Keys (Sorted by Age) ---");
personMap.forEach((k, v) -> System.out.println(k + " : " + v));
// 2. 使用 Java 8+ 的 Lambda 表达式（更简洁）
System.out.println("\n--- Using Lambda Expression ---");
// 假设我们想按名字的长度排序
Comparator<Person> nameLengthComparator = (p1, p2) -> Integer.compare(p1.name.length(), p2.name.length());
TreeMap<Person, String> personMapByNameLength = new TreeMap<>(nameLengthComparator);
personMapByNameLength.put(new Person("Alice", 30), "Developer");
personMapByNameLength.put(new Person("Bob", 25), "Designer");
personMapByNameLength.put(new Person("Charlie", 35), "Manager");
personMapByNameLength.put(new Person("David", 22), "Intern");
personMapByNameLength.forEach((k, v) -> System.out.println(k + " : " + v));
}
}
输出：
--- Person Keys (Sorted by Age) ---
Person{name='David', age=22} : Intern
Person{name='Bob', age=25} : Designer
Person{name='Alice', age=30} : Developer
Person{name='Charlie', age=35} : Manager
--- Using Lambda Expression ---
Person{name='Bob', age=25} : Designer
Person{name='Alice', age=30} : David
Person{name='Charlie', age=35} : Manager
Person{name='Alice', age=30} : Developer(注意：名字长度相同的情况下，TreeMap 会保留插入顺序的相对性，但这不是保证的，因为红黑树的结构会动态调整)
降序排序
无论是自然排序还是自定义排序,要实现降序都非常简单，只需在 compare 或 compareTo 方法中交换两个参数的位置即可。
示例：自然排序降序
import java.util.Collections;
import java.util.TreeMap;
public class ReverseNaturalOrderExample {
public static void main(String[] args) {
// 使用 Collections.reverseOrder() 获取一个自然排序的逆序比较器
TreeMap<String, String> reverseStringMap = new TreeMap<>(Collections.reverseOrder());
reverseStringMap.put("Charlie", "Charlie's Value");
reverseStringMap.put("Alice", "Alice's Value");
reverseStringMap.put("Bob", "Bob's Value");
System.out.println("--- String Keys (Reverse Natural Order) ---");
reverseStringMap.forEach((k, v) -> System.out.println(k + " : " + v));
}
}
输出：
--- String Keys (Reverse Natural Order) ---
Charlie : Charlie's Value
Bob : Bob's Value
Alice : Alice's Value示例：自定义排序降序
import java.util.Comparator;
import java.util.TreeMap;
class Person {
String name;
int age;
// ... (同上)
}
public class ReverseCustomOrderExample {
public static void main(String[] args) {
// 按年龄降序排序
Comparator<Person> reverseAgeComparator = (p1, p2) -> Integer.compare(p2.age, p1.age);
TreeMap<Person, String> reversePersonMap = new TreeMap<>(reverseAgeComparator);
reversePersonMap.put(new Person("Alice", 30), "Developer");
reversePersonMap.put(new Person("Bob", 25), "Designer");
reversePersonMap.put(new Person("Charlie", 35), "Manager");
System.out.println("--- Person Keys (Sorted by Age in Descending Order) ---");
reversePersonMap.forEach((k, v) -> System.out.println(k + " : " + v));
}
}
输出：
--- Person Keys (Sorted by Age in Descending Order) ---
Person{name='Charlie', age=35} : Manager
Person{name='Alice', age=30} : Developer
Person{name='Bob', age=25} : Designer总结与最佳实践
| 排序方式 | 如何实现 | 适用场景 |
|---|---|---|
| 自然排序 | Key 对象实现 Comparable 接口。 |
键对象本身有明确、标准的排序逻辑（如 String, Integer, Date）。 |
| 自定义排序 | 创建 TreeMap 时传入 Comparator 对象。 |
键对象没有实现 Comparable，或者需要多种不同的排序规则，或者不想修改键类的源代码。 |
| 降序排序 | 在 Comparator 或 compareTo 中交换参数，或使用 Collections.reverseOrder()。 |
需要从大到小（或反向）的顺序。 |
重要注意事项：
- 一致性：
TreeMap要汫比较器（无论是Comparable还是Comparator）的规则必须是一致性的。compare(a, b)返回 0，则a.equals(b)必须为true，反之亦然，否则，TreeMap的行为是不可预测的。 - 性能：
TreeMap的基本操作（get,put,remove）的时间复杂度都是O(log n)，这比HashMap的O(1)要慢，但提供了有序性，如果你不需要有序性，只是需要一个高性能的键值对存储，应该优先使用HashMap。 null键：TreeMap不允许null键，因为它无法与任何其他键进行比较（调用compareTo或compare会抛出NullPointerException），而HashMap和LinkedHashMap是允许null键的。TreeMap允许null值。
