TreeMap 的底层原理是什么？和 HashMap 有什么区别？

简化版

TreeMap 底层是一棵红黑树（自平衡二叉搜索树），按 key 的排序规则组织元素，所以它是有序 Map——遍历时 key 天然从小到大。代价是 put/get/remove 都是 O(log n)（要沿树查找），比 HashMap 平均 O(1) 慢。选它的唯一理由是「需要有序」：范围查询、找最接近某值的 key、按序遍历。key 必须可比较（实现 Comparable 或构造时传 Comparator）。

详细版

TreeMap 实现了 NavigableMap（继承 SortedMap），核心是一棵红黑树：

有序：每次 put 都按 key 的比较结果找到正确位置插入，中序遍历即为升序。默认用 key 的自然顺序（Comparable.compareTo），也可在构造时传 Comparator 自定义。
O(log n)：查找/插入/删除都要从根节点沿树下行，路径长度约 log n；红黑树保证树高不退化，最坏也是 O(log n)。
不允许 null key：因为要拿 key 做比较，null 无法 compareTo（除非 Comparator 特殊处理），会抛 NullPointerException；value 可为 null。

它比 HashMap 多出一批「有序才能提供」的导航方法：

TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "a"); map.put(3, "c"); map.put(5, "e");

map.firstKey();          // 1   最小 key
map.lastKey();           // 5   最大 key
map.floorKey(4);         // 3   ≤4 的最大 key
map.ceilingKey(4);       // 5   ≥4 的最小 key
map.headMap(3);          // {1=a}      小于 3 的部分
map.subMap(1, 5);        // {1=a, 3=c} 区间 [1,5)

⚠️ TreeMap 的「相等」由比较结果为 0 决定，不看 equals。若 Comparator 认为两个 key 相等（compare 返回 0），第二次 put 会覆盖第一个——即使它们 equals 为 false。

完整版教学

一、TreeMap 和 HashMap：本质是两种数据结构

这俩都是 Map，但底层结构完全不同，性能和能力也就此分野：

维度	HashMap	TreeMap
底层结构	数组 + 链表/红黑树（哈希表）	红黑树
顺序	无序（扩容还会变）	按 key 排序（升序）
get/put/remove	平均 O(1)	O(log n)
key 要求	重写 hashCode/equals	可比较（Comparable/Comparator）
null key	允许一个	不允许
额外能力	无	范围查询、floor/ceiling、首尾 key

一句话选型：只要 key、不要序 → HashMap；要按 key 有序或范围查询 → TreeMap。如果只要「插入顺序」而非「排序顺序」，那是 LinkedHashMap，别用 TreeMap。

二、为什么用红黑树：有序 + 不退化

要实现「有序」，二叉搜索树（BST）是最自然的选择——左小右大，中序遍历即升序。但普通 BST 有个致命问题：如果按已排序的数据依次插入（1,2,3,4,5…），它会退化成一条链表，树高变 O(n)，查询也退化成 O(n)。

红黑树是「自平衡 BST」，靠 5 条规则（根黑、红节点的孩子必黑、任意路径黑节点数相同等）+ 旋转/变色，保证最长路径不超过最短路径的 2 倍，树高始终维持在 O(log n)。所以哪怕你顺序插入 100 万个递增 key，TreeMap 也不会退化，稳定 O(log n)。

普通 BST 顺序插入 1,2,3,4,5：      红黑树自动平衡：
1                                        3
 \                                      / \
  2                                    2   4
   \                                  /     \
    3        树高 O(n)，退化成链      1       5   树高 O(log n)
     \
      4
       \
        5

三、有序带来的「导航方法」：TreeMap 的杀手锏

TreeMap 值钱的地方不是普通 get/put（那还比 HashMap 慢），而是只有有序结构才能高效提供的导航查询。用一组数字看清每个方法：

TreeMap 里的 key: [10, 20, 30, 40, 50]

floorKey(35)   → 30   （≤35 的最大 key）
ceilingKey(35) → 40   （≥35 的最小 key）
lowerKey(30)   → 20   （严格 <30 的最大 key）
higherKey(30)  → 40   （严格 >30 的最小 key）
firstKey()     → 10
lastKey()      → 50
subMap(20,40)  → {20,30}   （区间 [20,40)）

这些操作都是沿树下行 O(log n)。用 HashMap 实现同样功能，只能全表扫描 O(n)。典型应用：按分数段找档位、按时间戳找最接近的记录、限流的滑动窗口边界查找——都是「找最接近某值」或「取某区间」的场景。

四、Comparable vs Comparator：key 怎么排

TreeMap 必须知道「谁比谁大」，两种途径：

// ① key 自身实现 Comparable（自然顺序）
TreeMap<String, Integer> m1 = new TreeMap<>();   // String 已实现 Comparable，按字典序
m1.put("banana", 1); m1.put("apple", 2);
// 遍历顺序: apple, banana

// ② 构造时传 Comparator（自定义顺序），优先级高于 Comparable
TreeMap<String, Integer> m2 = new TreeMap<>(Comparator.reverseOrder());
m2.put("banana", 1); m2.put("apple", 2);
// 遍历顺序: banana, apple（降序）

如果 key 没实现 Comparable，又没传 Comparator，put 时会抛 ClassCastException。这跟 HashMap 完全不同——HashMap 只要 key 能算 hashCode 就行，不要求可比较。

五、致命陷阱：判等靠 compare，不靠 equals

这是 TreeMap 最容易踩的坑。HashMap 判断两个 key 是否「同一个」用的是 hashCode + equals；而 TreeMap 完全不看 equals，只看 compare/compareTo 是否返回 0。

// Comparator 只比较字符串长度
TreeMap<String, Integer> map = new TreeMap<>(Comparator.comparingInt(String::length));
map.put("cat", 1);   // 长度 3
map.put("dog", 2);   // 长度 3 → compare 返回 0 → 被当作"同一个 key"，覆盖！
System.out.println(map.size());     // 1  ！不是 2
System.out.println(map.get("cat")); // 2  取 cat 也返回 dog 的值

"cat".equals("dog") 明明是 false，但 Comparator 认为它们相等，TreeMap 就把它们当同一个 key。所以给 TreeMap 写 Comparator 时，必须保证「compare 返回 0」当且仅当「业务上真的是同一个 key」，否则会莫名其妙丢数据。这就是 SortedMap 文档说的「排序应与 equals 一致」。

六、复杂度与选型总结

操作	HashMap	TreeMap	LinkedHashMap
get/put	O(1)	O(log n)	O(1)
按 key 排序遍历	不支持（需另排序）	O(n)，天然有序	不支持
范围/最接近查询	O(n)	O(log n)	O(n)
保持插入顺序	不支持	不支持	支持

选型口诀：默认 HashMap；要排序/范围查询用 TreeMap；要插入顺序或 LRU 用 LinkedHashMap。别为了「顺便有序」在高频读写场景用 TreeMap，log n 的常数在大数据量下会明显拖慢。

记忆钩子：TreeMap = 红黑树 = 有序 + O(log n) + 导航方法；它的判等看 compare 不看 equals，这是最大的坑。

七、常见误区与追问

误区：TreeMap 比 HashMap 快。 恰恰相反，TreeMap 是 O(log n)，HashMap 平均 O(1)；TreeMap 的价值是「有序」，不是「快」。
误区：TreeMap 判断 key 相等用 equals。 用的是 compare/compareTo 返回 0，与 equals 无关；Comparator 写不好会误判两个不同 key 为同一个而覆盖。
误区：TreeMap 可以存 null key。 不行，比较 null 会抛 NPE（除非 Comparator 特殊处理）；value 可以为 null。
误区：TreeMap 的顺序是插入顺序。 是 key 的排序顺序；要插入顺序请用 LinkedHashMap。
追问：TreeMap 的 key 没实现 Comparable 会怎样？ 若也没传 Comparator，put 时抛 ClassCastException；要么让 key 实现 Comparable，要么构造时传 Comparator。
追问：为什么 TreeMap 不用 AVL 树？ 红黑树增删旋转更少、维护成本低，而 Map 增删也频繁；红黑树是查询与增删的综合折中，Java 里 TreeMap、HashMap 树化桶都用它。
追问：如何按 value 排序？ TreeMap 只能按 key 排；按 value 排要把 entrySet 拿出来用 List.sort(Map.Entry.comparingByValue())，结果是 List 不再是 Map。

八、加强记忆

把 TreeMap 记成「一棵永远排好序的红黑树」：它牺牲了 HashMap 的 O(1)，换来两样 HashMap 给不了的东西——天然有序遍历和一批 O(log n) 的导航查询（floor/ceiling/first/last/subMap，专治「找最接近某值」和「取某区间」）。红黑树的自平衡保证了哪怕顺序插入递增数据也不退化成链表，树高稳定 O(log n)。用它有三条铁律：key 必须可比较（Comparable 或 Comparator），不能存 null key，以及最容易翻车的一条——判等看 compare 返回 0，不看 equals，Comparator 写松了会把不同 key 当成同一个而覆盖丢数据。选型上记住「默认 HashMap、要序用 TreeMap、要插入顺序用 LinkedHashMap」，这题就通透了。

简化版

详细版