#TreeMap 与红黑树
面试官问："TreeMap 底层是什么数据结构？"
候选人小习答："红黑树。"
面试官追问："为什么用红黑树而不是平衡二叉树？"
小习说不上来。
【面试官心理】 这道题考查的是候选人对树数据结构的理解。能说出红黑树的平衡特性与 AVL 树对比的候选人，说明对数据结构有基础研究。
#一、红黑树特性 🔴
// 红黑树的 5 个约束条件：
// 1. 节点是红色或黑色
// 2. 根节点是黑色
// 3. 叶节点（NIL）是黑色
// 4. 红色节点的子节点都是黑色（无红色连续）
// 5. 从任一节点到其每个叶子的路径上，黑高相同
// 这些约束保证了：最长路径不超过最短路径的 2 倍
// → 近似平衡，查找/插入/删除都是 O(log n)#1.1 为什么不用 AVL 树
| 维度 | AVL 树 | 红黑树 |
|---|---|---|
| 平衡度 | 严格平衡（高度差 <= 1） | 近似平衡 |
| 查找性能 | 更好（更平衡） | 稍差（但仍是 O(log n)） |
| 插入/删除开销 | 大（更多旋转） | 小 |
| 适用场景 | 查找多（数据库索引） | 插入/删除多 |
#二、TreeMap 基本操作 🔴
#2.1 基本用法
// 自然顺序（key 必须实现 Comparable）
TreeMap<String, Integer> map = new TreeMap<>();
map.put("banana", 2);
map.put("apple", 1);
map.put("cherry", 3);
map.firstKey(); // "apple"（最小）
map.lastKey(); // "cherry"（最大）
map.lowerKey("cherry"); // "banana"（小于 cherry 的最大）
map.higherKey("banana"); // "cherry"（大于 banana 的最小）
map.floorKey("date"); // <= date 的最大
map.ceilingKey("date"); // >= date 的最小#2.2 自定义排序
// 方式一：Comparator
TreeMap<String, Integer> map = new TreeMap<>(Comparator.reverseOrder());
map.put("a", 1);
map.put("b", 2);
// 遍历顺序：b, a（降序）
// 方式二：自定义对象作为 key
class Person {
String name;
int age;
}
TreeMap<Person, Integer> map = new TreeMap<>(new Comparator<Person>() {
@Override
public int compare(Person p1, Person p2) {
return p1.age - p2.age; // 按年龄排序
}
});#三、常用场景 🟡
#3.1 区间查询
TreeMap<Integer, String> map = new TreeMap<>();
map.put(10, "a");
map.put(20, "b");
map.put(30, "c");
map.put(40, "d");
// 获取 [15, 35] 范围内的所有键值对
Map<Integer, String> subMap = map.subMap(15, 35);
// 返回 {20="b", 30="c"}
// 获取小于 25 的所有键值对
Map<Integer, String> headMap = map.headMap(25);
// 返回 {10="a", 20="b"}
// 获取大于等于 25 的所有键值对
Map<Integer, String> tailMap = map.tailMap(25);
// 返回 {30="c", 40="d"}#3.2 LRU 缓存（基于 TreeMap）
// 基于时间过期的缓存
class ExpiringCache<K, V> {
private final TreeMap<Long, K> timeMap = new TreeMap<>();
private final Map<K, V> cache = new HashMap<>();
private final long ttlMillis;
public void put(K key, V value) {
long expireTime = System.currentTimeMillis() + ttlMillis;
timeMap.put(expireTime, key);
cache.put(key, value);
}
public V get(K key) {
// 清理过期数据
Long expireTime = timeMap.ceilingKey(0L);
while (expireTime != null && expireTime < System.currentTimeMillis()) {
K expiredKey = timeMap.remove(expireTime);
cache.remove(expiredKey);
expireTime = timeMap.higherKey(expireTime);
}
return cache.get(key);
}
}#四、与 HashMap 对比 🟡
| 维度 | HashMap | TreeMap |
|---|---|---|
| 底层结构 | 哈希桶 + 链表/红黑树 | 红黑树 |
| 时间复杂度 | O(1) 均摊 | O(log n) |
| 排序 | 无 | 自动排序 |
| 范围查询 | 不支持 | 支持 |
| null 支持 | key/value 都可以为 null | key 不能为 null（可比较性） |
| 适用场景 | 普通 kv 存储，高性能 | 需要排序、区间查询 |
#五、追问升级
面试官："ConcurrentHashMap 不用红黑树做整体结构吗？"
// 不是整体用红黑树
// 而是单个哈希桶超过阈值时，桶内链表转红黑树
// 原因：单个桶内的数据需要快速查找
// 整个 ConcurrentHashMap 还是哈希表结构
// TreeMap：整体是红黑树，所有 key 按序组织
// HashMap/CHM：哈希定位 + 桶内红黑树/链表