# 问题
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)，比HashMapO(1) 查询更慢。
# 相关面试题
TreeMap如何支持并发访问？HashMap和TreeMap的本质区别是什么？- 如何用
TreeMap实现一个 LRU 缓存？
