TreeMap简介
一、概述
java.util.TreeMap<K,V> 是 红黑树 （Red‑Black Tree）实现的 有序 Map。
与 HashMap 的无序、O(1) 平均查找不同，TreeMap 保证 键按“大小”单调有序，并提供丰富的 区间/导航 操作。
二、底层实现原理
| 维度 |
说明 |
| 数据结构 |
红黑树（自平衡二叉搜索树），节点类型 TreeMap.Entry<K,V> 持有 key、value、parent、left、right、color。 |
| 排序依据 |
- 若构造时传入 Comparator<? super K>，始终使用它；
- 否则要求 K 实现 Comparable<K> 并使用自然顺序。 |
| 自平衡 |
插入/删除后通过 旋转 + 重新着色 保持红黑树 5 条性质，进而保证最坏情况层高 O(logn)。 |
| 性能 |
查找、插入、删除、导航方法（floorKey、ceilingKey…）全部 O(logn)；中序遍历迭代输出键值对时为升序。 |
三、完整 API 速查表（常用 90%）
| 分类 |
方法 |
备注 |
| 基本增删改查 |
put(K,V) / get(Object) / remove(Object) |
|
|
putIfAbsent / computeIfAbsent |
JDK8+ |
| 最值 & 导航 |
firstKey() / lastKey() |
最小 / 最大键 |
|
floorKey(k) / ceilingKey(k) |
≤k / ≥k |
|
lowerKey(k) / higherKey(k) |
＜k / ＞k |
| 区间视图 |
subMap(fromIncl, toExcl) |
[from, to) |
|
headMap(toKey) / tailMap(fromKey) |
|
| 反序视图 |
descendingMap() |
视图实时联动，不拷贝 |
| 遍历 |
entrySet() / keySet() / values() |
均按递增顺序
迭代器为 fail‑fast |
| 并发安全 |
Collections.synchronizedSortedMap(map) |
外部包装，或用 ConcurrentSkipListMap |
Tip：所有区间视图也是 NavigableMap，对子视图的修改会反映到原表。
四、典型使用场景
| 场景 |
说明 |
| 排名 / 排行榜 |
map.put(score, playerIdSet)，map.descendingMap() 可快速拿到前 N。 |
| 滑动窗口最值 |
统计窗口内元素频次，map.lastKey() / firstKey() 读最大/最小值。 |
| 区间计数 & 离散化 |
floorKey / ceilingKey 找邻接点，做线段合并、日程表… |
| LRU / LFU Cache |
按访问时间或次数排序。 |
| 时间序列检索 |
日志时间戳、股票 K 线等 —— 找最近时间点 (floorKey)。 |
五、注意事项 & 常见坑
null 键限制
自然顺序 TreeMap 禁止 null 键（会 NullPointerException）；若一定要存，必须提供能处理空值的自定义 Comparator。- 可变键问题
键若在映射后被修改其 compareTo/compare 结果，红黑树将被破坏 → 绝对不要用可变对象作键！
- Comparator 一致性
Comparator 必须满足“一致性”：compare(a,b)==0 时视做键相等，否则同一逻辑键可能出现重复。
- 非线程安全
多线程读写需显式同步或改用 ConcurrentSkipListMap（跳表 + 并发分段锁）。
- 遍历 fail‑fast
结构被并发修改（除迭代器自身 remove）抛 ConcurrentModificationException，仅用于 bug 早发现，不保证安全。
六、时间复杂度 & 性能对比
| 操作 |
TreeMap |
HashMap |
ArrayList + 手动排序 |
put / remove / get |
O(logn) |
O(1) 平均 |
O(1) 末尾插入；删除 O(n) |
floorKey / ceilingKey |
O(logn) |
不支持 |
先排序 O(nlogn) 再二分 |
| 顺序遍历 |
O(n)（升序） |
无序 |
需先排序 |
- 如果只需 key→value 快速映射，用
HashMap。
- 需“键排序或范围查询”时，
TreeMap 性价比最高；极端并发场景则考虑 ConcurrentSkipListMap。
- 大数据量且只需 Top‑k，可用
PriorityQueue 代替。
七、微观性能细节
| 侧面 |
说明 |
| 常数因子 |
红黑树节点多 3 指针 + 1 颜色字段，内存占用高于 HashMap |
| 比较器开销 |
若 Comparator 复杂（如字符串局部比较），整体耗时会偏高 |
| 批量遍历 |
迭代顺序 cache‑friendly，但频繁跳转左右孩子，CPU 分支预测利用率一般 |
| JDK 优化 |
JDK 8 之后对红黑树旋转逻辑做了内联及时编译优化，实测百万级数据插入可达 3–5M ops/s |
八、示例代码片段
TreeMap<Integer, String> rank = new TreeMap<>();
// 插入
rank.put(98, "Alice");
rank.put(87, "Bob");
rank.put(91, "Carl");
// 取 top-1（最高分）
System.out.println(rank.lastEntry()); // {98=Alice}
// 找 ≤90 的最高分
Map.Entry<Integer, String> e = rank.floorEntry(90); // {87=Bob}
// 滑动窗口示例：维护长度 k = 3 的窗口最大值
int[] nums = {1, 3, 1, 2, 0, 5};
int k = 3;
TreeMap<Integer, Integer> window = new TreeMap<>();
for (int i = 0; i < nums.length; i++) {
window.merge(nums[i], 1, Integer::sum); if (i >= k) { // 移除窗口左端
int out = nums[i - k]; window.merge(out, -1, (old, n) -> old + n == 0 ? null : old + n); } if (i >= k - 1) { System.out.println(window.lastKey()); // 打印当前窗口最大值
}}
🔚 总结
TreeMap = 有序 + O(logn) 的 Map；- 适合 区间查询、最值检索、排名系统、滑动窗口最值；
- 注意 不可变键、Comparator 一致性、线程安全；
- 当你需要“按键排序”而不仅仅是哈希查找时，
TreeMap 是首选。
