01

60 秒回答模板

TreeMap 的底层结构是红黑树，也就是一种近似平衡的二叉搜索树。每个节点保存 key、value、left、right、parent 和颜色信息。插入、查找、删除都要先根据 key 的比较规则从根节点向左或向右走：如果构造 TreeMap 时传了 Comparator，就使用 Comparator；否则要求 key 实现 Comparable。比较结果小于 0 走左子树，大于 0 走右子树，等于 0 时认为是同一个 key，会覆盖旧 value。插入新节点后，红黑树会通过变色和旋转恢复约束，删除黑色节点后也可能触发修复，所以树高能保持在 O(log n) 级别。TreeMap 的价值不只是能存键值，而是天然维护排序能力，提供 firstKey、lastKey、floorKey、ceilingKey、subMap、headMap、tailMap 等 NavigableMap 能力。和 HashMap 相比，它有序但单次操作不是平均 O(1)；和 LinkedHashMap 相比，它不是维护插入顺序，而是维护 key 的排序；和 ConcurrentSkipListMap 相比，它不是线程安全容器，涉及并发读写需要外部同步或改用并发有序 Map。

考点 底层结构
主线 排序规则
易错点 把 TreeMap 说成哈希表实现，忽略红黑树和排序能…
02

深入解析

01

底层结构

TreeMap 底层不是哈希表，而是红黑树。红黑树是一种自平衡二叉搜索树，通过节点颜色、局部旋转和变色来控制树高。它没有 AVL 树那么严格平衡，但插入删除时调整成本更低，工程上适合作为通用有序 Map 的基础结构。

02

排序规则

TreeMap 的顺序完全由比较规则决定。构造时传入 Comparator 就优先使用 Comparator；否则使用 key 自身的 Comparable 自然排序。这里的重复 key 判断依赖 compare 结果是否为 0，而不是单纯依赖 equals，所以比较规则最好和 equals 语义保持一致。

03

写入流程

put 时会从根节点开始比较 key，按小走左、大走右的规则找到插入位置。如果比较结果为 0，就覆盖原节点 value；如果是新 key，就插入一个新节点。新节点通常按红色处理，再通过红黑树的插入修复保证根黑、红节点不相邻、黑高一致等约束。

04

查询与删除

get 查询同样沿着比较路径从根向下走，每次比较都能排除一侧子树，因此复杂度通常是 O(log n)。remove 会先定位节点；如果节点有两个孩子，常用中序后继替换，再删除后继节点。删除黑色节点可能破坏黑高，需要继续做删除修复。

05

有序能力

TreeMap 实现 SortedMap 和 NavigableMap，天然支持按 key 升序遍历，也能得到降序视图。它适合做范围查询、找不大于某个 key 的最大键、找不小于某个 key 的最小键、取头尾区间等需求，这些能力是 HashMap 和普通插入顺序 Map 不擅长的。

06

选型边界

如果只追求按 key 快速查找且不关心顺序，HashMap 通常更合适；如果关心插入顺序或访问顺序，LinkedHashMap 更合适；如果需要并发安全的有序 Map，优先考虑 ConcurrentSkipListMap。TreeMap 适合单线程或外部同步下的有序键值场景。

03

易错点

  • 把 TreeMap 说成哈希表实现，忽略红黑树和排序能力。
  • 认为 TreeMap 查询是平均 O(1)，没有区分它和 HashMap 的复杂度。
  • 以为 TreeMap 按插入顺序遍历，混淆了 LinkedHashMap 的语义。
  • 忽略 compare 结果为 0 会覆盖 value，导致自定义排序规则埋下问题。
  • 默认 TreeMap 线程安全，在并发读写场景下没有额外同步。
04

面试官追问

TreeMap 为什么不用 AVL 树？

AVL 树更严格平衡，查询路径可能略短，但插入删除时旋转更频繁。红黑树在查询和更新之间折中更好，适合通用 Map 的频繁增删改查。

TreeMap 的 key 插入后还能修改吗？

如果修改的是参与排序的字段，就不应该这样做。节点位置已经按旧比较结果确定，字段变化后树不会自动重排，后续查询、删除和范围查询都可能失效。

TreeMap 可以存 null key 吗？

自然排序下通常不允许 null key，因为无法调用 compareTo。若自定义 Comparator 明确能处理 null，才可能支持；null value 通常是允许的。

TreeMap 和 LinkedHashMap 的顺序有什么区别？

TreeMap 按 key 的比较结果排序，LinkedHashMap 维护插入顺序或访问顺序。前者解决排序和范围问题，后者解决按访问轨迹稳定遍历的问题。