TreeMap

2401_85239193

369人浏览 · 2026-07-06 06:37:51

2401_85239193 · 2026-07-06 06:37:51 发布

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

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`？	❌ 否（任意对象）	✅ 是（必须能比较大小）