# TreeMap简介 # 一、概述 java.util.TreeMap 是 红黑树 （Red‑Black Tree）实现的 有序 Map。

与 HashMap 的无序、O(1) 平均查找不同，TreeMap 保证 键按“大小”单调有序，并提供丰富的 区间/导航 操作。

# 二、底层实现原理 维度 说明 数据结构 红黑树（自平衡二叉搜索树），节点类型 TreeMap.Entry 持有 key、value、parent、left、right、color。 排序依据 - 若构造时传入 Comparator，始终使用它；- 否则要求 K 实现 Comparable 并使用自然顺序。 自平衡 插入/删除后通过 旋转 + 重新着色 保持红黑树 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 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 e = rank.floorEntry(90); // {87=Bob}

// 滑动窗口示例：维护长度 k = 3 的窗口最大值

int[] nums = {1, 3, 1, 2, 0, 5};

int k = 3;

TreeMap 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 是首选。