Java TreeMap用法-马育民老师

# 介绍

`TreeMap` 是 Java 中基于 **红黑树（自平衡二叉查找树）** 实现的 `Map` 接口实现类，其核心特点是**键（key）有序**，支持高效的插入、查询和删除操作（时间复杂度均为 `O(log n)`）。以下是 `TreeMap` 的详细用法：

# 一、基本特性
1. **键的有序性**：默认按键的**自然排序**（实现 `Comparable` 接口），或通过 `Comparator` 自定义排序规则。
2. **无重复键**：键唯一，若插入重复键，新值会覆盖旧值。
3. **非同步**：线程不安全，多线程环境需手动同步（如使用 `Collections.synchronizedMap()`）。
4. **null 键处理**：
   - 自然排序时，键不能为 `null`（会抛出 `NullPointerException`）。
   - 自定义 `Comparator` 时，若支持 `null` 键则可插入（需在比较器中处理 `null`）。

# 二、初始化与基本操作

### 1. 初始化
```java
import java.util.TreeMap;
import java.util.Comparator;

public class TreeMapDemo {
    public static void main(String[] args) {
        // 1. 默认构造：按键的自然排序（键需实现 Comparable）
        TreeMap<Integer, String> treeMap1 = new TreeMap<>();

// 2. 自定义排序：通过 Comparator 实现（例：整数降序）
        TreeMap<Integer, String> treeMap2 = new TreeMap<>(Comparator.reverseOrder());

// 3. 基于已有的 Map 初始化
        TreeMap<Integer, String> treeMap3 = new TreeMap<>(treeMap1);
    }
}
```

### 2. 常用方法（CRUD）
```java
TreeMap<Integer, String> map = new TreeMap<>();

// 添加/修改键值对（key 存在则覆盖值）
map.put(3, "C");
map.put(1, "A");
map.put(2, "B");
map.put(3, "C-Update"); // 覆盖 key=3 的值

// 获取值
String value = map.get(2); // 返回 "B"

// 移除键值对
map.remove(1); // 移除 key=1 的条目

// 判断键是否存在
boolean hasKey = map.containsKey(2); // true

// 判断值是否存在
boolean hasValue = map.containsValue("B"); // true

// 获取键的集合（有序）
System.out.println(map.keySet()); // [2, 3]

// 获取值的集合（无序，因值可重复）
System.out.println(map.values()); // [B, C-Update]

// 获取键值对集合（有序）
System.out.println(map.entrySet()); // [2=B, 3=C-Update]
```

# 三、有序性相关方法（核心特性）
`TreeMap` 提供了一系列基于键有序性的特殊方法，方便范围查询和边界操作：

| 方法                | 说明                                  | 示例（map 键为 2,3,5,7）          |
|---------------------|---------------------------------------|-----------------------------------|
| `firstKey()`        | 返回最小的键                          | `map.firstKey()` → 2              |
| `lastKey()`         | 返回最大的键                          | `map.lastKey()` → 7               |
| `lowerKey(k)`       | 返回小于 `k` 的最大键                 | `map.lowerKey(5)` → 3             |
| `higherKey(k)`      | 返回大于 `k` 的最小键                 | `map.higherKey(5)` → 7            |
| `floorKey(k)`       | 返回小于等于 `k` 的最大键             | `map.floorKey(6)` → 5             |
| `ceilingKey(k)`     | 返回大于等于 `k` 的最小键             | `map.ceilingKey(4)` → 5           |
| `headMap(k)`        | 返回键小于 `k` 的子映射（视图）       | `map.headMap(5)` → {2=B, 3=C}     |
| `tailMap(k)`        | 返回键大于等于 `k` 的子映射（视图）   | `map.tailMap(5)` → {5=E, 7=G}     |
| `subMap(k1, k2)`    | 返回键大于等于 `k1` 且小于 `k2` 的子映射 | `map.subMap(3,7)` → {3=C,5=E}     |

### 示例：范围查询
```java
TreeMap<Integer, String> map = new TreeMap<>();
map.put(2, "B");
map.put(3, "C");
map.put(5, "E");
map.put(7, "G");

// 获取所有键小于 5 的键值对
System.out.println(map.headMap(5)); // {2=B, 3=C}

// 获取键在 [3,7) 之间的键值对
System.out.println(map.subMap(3, 7)); // {3=C, 5=E}

// 获取大于等于 5 的最小键
System.out.println(map.ceilingKey(5)); // 5
```

# 四、自定义排序（`Comparator`）
当键未实现 `Comparable`，或需要自定义排序规则时，可通过 `Comparator` 实现。

### 示例：按字符串长度排序
```java
// 键为 String，按字符串长度升序排序（长度相同则按字典序）
TreeMap<String, Integer> map = new TreeMap<>(
    Comparator.comparingInt(String::length)
        .thenComparing(Comparator.naturalOrder()) // 长度相同则按自然顺序
);

map.put("apple", 5);   // 长度 5
map.put("banana", 6);  // 长度 6
map.put("pear", 4);    // 长度 4
map.put("orange", 6);  // 长度 6（与 banana 长度相同）

// 遍历：按长度升序，长度相同则按字典序
for (var entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}
// 输出：
// pear: 4
// apple: 5
// banana: 6
// orange: 6
```

# 五、遍历方式
`TreeMap` 的遍历结果**按键的排序规则有序输出**，常用遍历方式：

1. **遍历键值对（`entrySet()`）**
```java
for (var entry : map.entrySet()) {
    System.out.println(entry.getKey() + " → " + entry.getValue());
}
```

2. **遍历键（`keySet()`）**
```java
for (String key : map.keySet()) {
    System.out.println(key + " → " + map.get(key));
}
```

3. **迭代器遍历（支持删除）**
```java
var iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    var entry = iterator.next();
    if (entry.getValue() < 5) {
        iterator.remove(); // 安全删除
    }
}
```

# 六、注意事项
1. **排序一致性**：`equals()` 与 `compareTo()`/`compare()` 需保持一致（即若 `a.equals(b)` 为 `true`，则 `compare(a,b)` 必须返回 0），否则可能导致逻辑错误（如 `containsKey()` 结果不符合预期）。
   
2. **性能对比**：
   - 与 `HashMap` 相比，`TreeMap` 插入/查询效率略低（`O(log n)` vs `O(1)`），但支持有序操作。
   - 与 `LinkedHashMap` 相比，`TreeMap` 的有序性是**按键排序**，而 `LinkedHashMap` 是**按插入顺序**。

3. **线程安全**：多线程环境下，可通过 `Collections.synchronizedMap(new TreeMap<>())` 包装为同步集合。

# 总结
`TreeMap` 适合需要**键有序**的场景（如字典排序、范围统计、排行榜等），其核心优势在于基于红黑树的高效有序操作。使用时需注意键的排序规则（自然排序或自定义 `Comparator`），并合理利用范围查询方法提升效率。

原文出处：http://malaoshi.top/show_1GW2AmeyBbJu.html