# 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(log n)`。
性能	查找、插入、删除、导航方法（`floorKey`、`ceilingKey`…）全部 `O(log n)`；中序遍历迭代输出键值对时为升序。

# 三、完整 API 速查表（常用 90%）

分类	方法	备注
基本增删改查	`put(K,V)` / `get(Object)` / `remove(Object)`
	`putIfAbsent` / `computeIfAbsent`	JDK 8+
最值 & 导航	`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(log n)	O(1) 平均	O(1) 末尾插入；删除 O(n)
`floorKey / ceilingKey`	O(log n)	不支持	先排序 O(n log n) 再二分
顺序遍历	O(n)（升序）	无序	需先排序

如果只需 key→value 快速映射，用 HashMap。

需“键排序或范围查询”时，TreeMap 性价比最高；极端并发场景则考虑 ConcurrentSkipListMap。

大数据量且只需 Top‑k，可用 PriorityQueue 代替。

# 七、微观性能细节

侧面	说明
常数因子	红黑树节点多 3 指针 + 1 颜色字段，内存占用高于 `HashMap`
比较器开销	若 `Comparator` 复杂（如字符串局部比较），整体耗时会偏高
批量遍历	迭代顺序 cache‑friendly，但频繁跳转左右孩子，CPU 分支预测利用率一般
JDK 优化	JDK 8 之后对红黑树旋转逻辑做了内联及时编译优化，实测百万级数据插入可达 3–5 M 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(log n) 的 Map；
适合 区间查询、最值检索、排名系统、滑动窗口最值；
注意 不可变键、Comparator 一致性、线程安全；
当你需要“按键排序”而不仅仅是哈希查找时，TreeMap 是首选。

← PriorityQueue简介 TreeSet简介 →