✅ 一、一句话本质（面试金句）

TreeMap 是一个「按键（key）自动排序」的 Map：它不靠哈希函数定位，而是把所有键组织成一棵自平衡二叉搜索树（红黑树），保证 put/get/remove 平均 O(log n)，且 keySet()、entrySet() 等迭代器（升序）。

→ 它解决的是 HashMap 和 LinkedHashMap 根本做不到的事：
❌ HashMap：无序，不能 firstKey() / higherKey(5)；
❌ LinkedHashMap：只能按插入或访问顺序，不能按数值大小排序；
✅ TreeMap：天然支持 floorKey(7)（≤7 的最大键）、subMap(3, true, 8, false)（[3,8) 区间子图）等范围操作。

---

✅ 二、底层结构：不是“链表+数组”，而是「红黑树节点」

TreeMap 没有桶（bucket）、没有 next 字段、没有哈希计算。它的核心是：

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;   // 左子节点（key < 当前）
    Entry<K,V> right;  // 右子节点（key > 当前）
    Entry<K,V> parent; // 父节点
    boolean color = BLACK; // 红黑树颜色标记（用于自平衡）
}

✅ 所以：

• 每个 Entry 是一个树节点，不是链表节点；
• 查找路径：从 root 开始，根据 key.compareTo(x) 大小关系，向左或向右走，直到 null 或匹配；
• 插入/删除后，通过变色 + 旋转（rotateLeft/rotateRight）保持树近似平衡 → 保证最长路径 ≤ 2×最短路径 → height = O(log n)。

🔑 关键前提：K 必须实现 Comparable 接口（如 Integer、String），或构造时传入 Comparator。
❗否则运行时报 ClassCastException —— 这是设计契约，不是 bug。

---

✅ 三、核心能力（HashMap 做不到的，它全能做到）

操作	TreeMap 支持？	说明	HashMap 对比
firstKey() / lastKey()	✅ O(1)	最小/最大键（直接找最左/最右叶子）	❌ 不支持（无序）
floorKey(k) / ceilingKey(k)	✅ O(log n)	≤k 的最大键 / ≥k 的最小键	❌ 不支持
higherKey(k) / lowerKey(k)	✅ O(log n)	>k 的最小键 / <k 的最大键	❌ 不支持
subMap(from, to)	✅ O(log n) 返回子 SortedMap 视图	[from, to) 区间键值对（懒视图，不复制数据）	❌ 不支持
headMap(to) / tailMap(from)	✅ O(log n)	< to 或 ≥ from 的全部映射	❌ 不支持
按自然序遍历 entrySet()	✅ O(n) 全局有序（中序遍历）	for (Entry e : map.entrySet()) 一定从小到大	❌ 无序

💡 示例：

TreeMap<Integer, String> map = new TreeMap<>();
map.put(5, "five"); map.put(1, "one"); map.put(8, "eight");
System.out.println(map.firstKey());     // 1
System.out.println(map.floorKey(6));    // 5 （≤6 的最大键）
System.out.println(map.subMap(2, 7));   // {5="five"} （[2,7) 区间）

---

✅ 四、性能对比（真实数字级）

操作	TreeMap	HashMap	说明
put(K,V)	O(log n)	O(1) 平均	TreeMap 慢约 3~5 倍（小数据）→ 1000 个元素，HashMap ~50ns，TreeMap ~200ns
get(K)	O(log n)	O(1) 平均	同上
remove(K)	O(log n)	O(1) 平均	同上
迭代全部元素	O(n)	O(n + capacity)	TreeMap 更稳定（不受空桶影响）
内存占用	❌ 更高	✅ 更低	TreeMap 每节点多 3 个引用（left/right/parent）+ color 字节

✅ 何时选 TreeMap？

• 需要 key 有序（如时间序列、排名榜、区间查询）；
• 数据量不大（≤ 10⁵），log n ≤ 17，性能可接受；
• 无法用 HashMap + Collections.sort() 代替（因为需要动态增删 + 实时查询）。

---

✅ 五、和 LinkedHashMap 的本质区别（常被混淆）

维度	LinkedHashMap	TreeMap
排序依据	插入顺序 或 访问顺序（时间维度）	键的自然序 或 自定义 Comparator（值大小维度）
底层结构	哈希表 + 双向链表（两个独立结构）	红黑树（单一树结构）
能否 firstKey()？	❌ 不支持（无全局序）	✅ 支持（最左节点）
能否 subMap(1,5)？	❌ 不支持	✅ 支持（原生区间视图）
是否线程安全？	❌ 否	❌ 否（同 HashMap）
key 是否需 Comparable？	❌ 否（任意对象）	✅ 是（必须能比较大小）

🌟 一句话记住：
LinkedHashMap 记住「谁先来」，TreeMap 知道「谁更大」。

---

✅ 六、一句话总结（刻进脑子）

TreeMap 是 Java 中唯一内置的「有序关联容器」：它放弃哈希的极致速度，换来键值的天然全序能力——这不是妥协，而是为金融报价、实时监控、排行榜等场景提供的不可替代的确定性语义。它不存储顺序，它本身就是顺序。