# 问题

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}
1
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 的最小键)
1
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}
1
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
}
1
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)?

  • 因为需要 二叉搜索 找到 fromKeytoKey,然后建立子树视图。

🔹 2. TreeMap 如何与数据库索引(B+ 树)结合?

  • 数据库 B+ 树适用于 磁盘存储,TreeMap 适用于 内存存储,两者在 区间查询、排序、范围查找 上思路一致。

🔹 3. 为什么 TreeMap 不能替代 HashMap

  • TreeMap 有序,但查询 O(log n),比 HashMap O(1) 查询更慢

# 相关面试题

  • TreeMap 如何支持并发访问?
  • HashMapTreeMap 的本质区别是什么?
  • 如何用 TreeMap 实现一个 LRU 缓存?