# 问题
22. 如何使用 TreeMap 进行区间查询?性能如何优化?
# 标准答案
TreeMap 采用 红黑树 作为底层数据结构,支持 log(n) 复杂度的区间查询。常见的区间查询方法包括:
subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
:返回指定范围内的子 Map。tailMap(K fromKey, boolean inclusive)
:获取大于等于某个键的子集。headMap(K toKey, boolean inclusive)
:获取小于等于某个键的子集。floorEntry(K key)
/ceilingEntry(K key)
:获取小于等于 / 大于等于某个 key 的最近节点。
性能优化方案:
- 避免频繁创建子 Map,改用
floorKey()
/ceilingKey()
直接定位边界值。 - 批量操作时,避免
subMap()
返回 View,尽量手动遍历。 - 使用
NavigableSet
提高查询效率,避免 TreeMap 额外包装 Entry。
# 答案解析
# 1. TreeMap 支持高效区间查询的核心原理
TreeMap 基于 红黑树 实现,保证 O(log n) 的查询复杂度,适用于范围查询、排序查询等需求。
每个操作都基于 二叉搜索树(BST)+ 红黑平衡机制,通过 左/右子树遍历 快速找到区间边界。
# (1)subMap()
查询子区间
TreeMap<Integer, String> map = new TreeMap<>();
map.put(1, "A");
map.put(3, "B");
map.put(5, "C");
map.put(7, "D");
// 查询 (3, 7] 范围内的键值对
NavigableMap<Integer, String> sub = map.subMap(3, false, 7, true);
System.out.println(sub); // 输出:{5=C, 7=D}
2
3
4
5
6
7
8
9
底层执行逻辑:
subMap(3, false, 7, true)
从 root 开始查找 3 和 7,然后向左右子树遍历获取完整区间。- 由于 TreeMap 有序存储,查询复杂度为 O(log n + k)(
log n
查找边界,k
为匹配元素个数)。
# (2)floorKey()
和 ceilingKey()
查找最近边界
System.out.println(map.floorKey(4)); // 输出 3(小于等于 4 的最大键)
System.out.println(map.ceilingKey(4)); // 输出 5(大于等于 4 的最小键)
2
为什么用它们比 subMap()
高效?
subMap()
返回的是 子 Map 视图,需要额外存储引用。floorKey()
和ceilingKey()
直接遍历红黑树,避免创建新对象,查询更高效。
# (3)tailMap()
/ headMap()
进行范围过滤
System.out.println(map.tailMap(3, true)); // 输出 {3=B, 5=C, 7=D}
System.out.println(map.headMap(5, false)); // 输出 {1=A, 3=B}
2
- 适用于滚动窗口查询,例如从某个时间戳开始获取所有数据。
- 避免 subMap 额外的边界检查,更高效。
# 2. TreeMap 区间查询的性能优化
虽然 TreeMap 区间查询比 HashMap 高效,但仍需优化:
✅ 1. 尽量使用 floorKey()
/ ceilingKey()
替代 subMap()
subMap()
返回的子 Map 是视图,不是复制的子树,操作不当可能影响原始 TreeMap。- 直接用
floorKey()
/ceilingKey()
查找边界,减少额外存储,查询更快。
✅ **2. tailMap()
和 headMap()
适用于 范围过滤,避免 subMap()
过度使用
subMap()
在O(log n + k)
复杂度的基础上,可能会影响 TreeMap 迭代器性能,tailMap()
直接访问右子树,性能更优。
✅ 3. 避免 Iterator.remove()
修改子 Map
Iterator<Map.Entry<Integer, String>> it = map.subMap(3, true, 7, true).entrySet().iterator();
while (it.hasNext()) {
it.next();
it.remove(); // ⚠️ 可能影响原始 TreeMap
}
2
3
4
5
问题:subMap()
只是 视图,remove()
可能影响原始 TreeMap,导致 ConcurrentModificationException。
优化方案:
- 遍历子 Map 时,用
new TreeMap<>(subMap).entrySet().iterator()
进行拷贝,避免原始 TreeMap 受到影响。
# 3. TreeMap 的区间查询 VS 其他数据结构
数据结构 | 查询方式 | 时间复杂度 | 适用场景 |
---|---|---|---|
TreeMap | subMap() 、floorKey() | O(log n) + k | 适合范围查询、区间统计 |
ArrayList | Collections.binarySearch() | O(log n) | 适用于 有序数组,但插入/删除较慢 |
HashMap | keySet() 过滤 | O(n) | 适用于 单点查询,但不适合区间查找 |
SkipList(ConcurrentSkipListMap) | subMap() | O(log n) | 并发场景下的有序查询(适合高并发) |
- 如果是并发场景,建议用
ConcurrentSkipListMap
,它是线程安全的TreeMap
替代品。 - 如果是静态数据,可用
ArrayList + binarySearch()
,减少 TreeMap 维护红黑树的开销。
# 常见错误
❌ 误区 1:subMap()
会返回新的 TreeMap
- 事实上,
subMap()
返回的是 视图,修改子 Map 会影响原始数据结构。 - 解决方案:如果需要独立对象,使用
new TreeMap<>(subMap)
。
❌ 误区 2:TreeMap 的 size()
操作是 O(1)
- 实际上
size()
是 O(n),因为subMap()
只是视图,不存储子树大小。 - 优化方案:若频繁计算区间大小,可以用
NavigableSet.size()
或缓存中间结果。
# 最佳实践
1️⃣ 批量区间查询时,优先 floorKey()
/ ceilingKey()
确定边界,减少 subMap()
额外消耗。
2️⃣ 并发场景使用 ConcurrentSkipListMap
,避免 TreeMap
线程不安全问题。
3️⃣ 避免 subMap()
直接迭代修改,先复制 new TreeMap<>(subMap)
进行操作。
# 深入追问
🔹 1. 为什么 subMap()
不是 O(1) 操作,而是 O(log n)?
- 因为需要 二叉搜索 找到
fromKey
和toKey
,然后建立子树视图。
🔹 2. TreeMap
如何与数据库索引(B+ 树)结合?
- 数据库
B+
树适用于 磁盘存储,TreeMap 适用于 内存存储,两者在 区间查询、排序、范围查找 上思路一致。
🔹 3. 为什么 TreeMap
不能替代 HashMap
?
TreeMap
有序,但查询 O(log n),比HashMap
O(1) 查询更慢。
# 相关面试题
TreeMap
如何支持并发访问?HashMap
和TreeMap
的本质区别是什么?- 如何用
TreeMap
实现一个 LRU 缓存?