别再只用get了！TreeMap的floorKey和ceilingKey才是处理范围查询的神器（附LeetCode实战）

解锁TreeMap高阶技能：floorKey与ceilingKey在范围查询中的实战艺术

在Java开发中，我们经常遇到需要根据某个值查找最接近元素的场景。比如电商系统中根据用户积分匹配会员等级，游戏开发中根据玩家经验值查找对应关卡，或者金融系统中寻找最接近某个价格的时间点。传统做法可能是遍历集合或手动实现二分查找，但这些方法要么效率低下，要么实现复杂。实际上，Java集合框架中早已内置了更优雅的解决方案——TreeMap的floorKey和ceilingKey方法。

1. 理解TreeMap的核心优势

TreeMap作为Java集合框架中的红黑树实现，天生具备有序特性。与HashMap的O(1)时间复杂度不同，TreeMap的常见操作（put/get/remove）时间复杂度为O(log n)，这种折中换来的是对元素排序的强大支持。

TreeMap的三大特性：

• 按键的自然顺序或Comparator定义的顺序自动排序
• 基于红黑树实现，保证基本操作的对数时间复杂度
• 实现了NavigableMap接口，提供丰富的导航方法

注意：要使用floorKey和ceilingKey方法，变量声明时应使用TreeMap或NavigableMap类型，而不是普通的Map接口，因为这些方法是NavigableMap特有的。

2. floorKey与ceilingKey方法深度解析

这两个方法堪称处理"近似匹配"问题的瑞士军刀，理解它们的细微差别至关重要。

2.1 方法定义与行为对比

TreeMap<Integer, String> scoreMap = new TreeMap<>(); scoreMap.put(60, "及格"); scoreMap.put(75, "良好"); scoreMap.put(90, "优秀"); System.out.println(scoreMap.floorKey(80)); // 输出：75 System.out.println(scoreMap.ceilingKey(80)); // 输出：90

2.2 源码实现原理

这两个方法底层都依赖TreeMap的红黑树结构，通过高效的树遍历实现：

// floorKey的简化版实现逻辑 public K floorKey(K key) { Entry<K,V> p = root; while (p != null) { int cmp = compare(key, p.key); if (cmp > 0) { if (p.right != null) { p = p.right; } else { return p.key; // 当前节点是可能的最大小值 } } else if (cmp < 0) { if (p.left != null) { p = p.left; } else { // 向上查找符合条件的祖先节点 Entry<K,V> parent = p.parent; Entry<K,V> ch = p; while (parent != null && ch == parent.left) { ch = parent; parent = parent.parent; } return parent != null ? parent.key : null; } } else { return p.key; // 精确匹配 } } return null; }

3. 五大实战应用场景

3.1 电商会员等级匹配

假设我们有一个基于积分的会员体系：

TreeMap<Integer, String> memberLevels = new TreeMap<>(); memberLevels.put(1000, "白银会员"); memberLevels.put(5000, "黄金会员"); memberLevels.put(10000, "白金会员"); int userPoints = 7500; String level = memberLevels.floorEntry(userPoints).getValue(); System.out.println("您的会员等级是: " + level); // 输出：黄金会员

3.2 游戏关卡进度系统

在游戏开发中，可以根据玩家经验值快速定位当前关卡：

TreeMap<Integer, String> levelMap = new TreeMap<>(); levelMap.put(0, "新手教程"); levelMap.put(1000, "森林关卡"); levelMap.put(3000, "沙漠关卡"); int playerExp = 2500; Integer currentLevelKey = levelMap.floorKey(playerExp); System.out.println("当前关卡: " + levelMap.get(currentLevelKey));

3.3 时间序列数据处理

处理时间戳数据时，快速查找最近的事件：

TreeMap<Long, String> eventLog = new TreeMap<>(); eventLog.put(1625097600000L, "系统启动"); eventLog.put(1625184000000L, "第一次备份"); eventLog.put(1625270400000L, "系统更新"); long queryTime = 1625200000000L; Long closestEvent = eventLog.floorKey(queryTime); System.out.println("最近事件: " + eventLog.get(closestEvent));

3.4 价格区间匹配

金融系统中查找特定价格点的最佳匹配：

TreeMap<Double, String> priceTiers = new TreeMap<>(); priceTiers.put(10.0, "基础套餐"); priceTiers.put(25.0, "标准套餐"); priceTiers.put(50.0, "高级套餐"); double userBudget = 30.0; Double bestMatch = priceTiers.floorKey(userBudget); System.out.println("推荐套餐: " + priceTiers.get(bestMatch));

3.5 数据分片定位

在分布式系统中定位数据应该存储在哪个分片：

TreeMap<Integer, String> shards = new TreeMap<>(); shards.put(1000, "分片A"); shards.put(2000, "分片B"); shards.put(3000, "分片C"); int dataKey = 1500; Integer targetShard = shards.ceilingKey(dataKey); System.out.println("数据应存储在: " + shards.get(targetShard));

4. LeetCode实战：股票价格跨度问题

让我们用TreeMap解决LeetCode第901题 - 股票价格跨度问题。题目要求设计一个StockSpanner类，它能收集每日股价并返回当前价格的历史跨度。

class StockSpanner { private TreeMap<Integer, Integer> priceMap; private int dayCount; public StockSpanner() { priceMap = new TreeMap<>(); dayCount = 0; } public int next(int price) { dayCount++; // 找到所有小于等于当前价格的键 Integer floorKey = priceMap.floorKey(price); int span = 1; // 合并所有小于当前价格的连续天数 while (floorKey != null) { span += priceMap.get(floorKey); priceMap.remove(floorKey); floorKey = priceMap.floorKey(price); } priceMap.put(price, span); return span; } }

这个解法巧妙地利用floorKey方法找到所有需要合并的历史记录，时间复杂度优于暴力解法。

5. 性能优化与边界情况处理

5.1 与二分查找的性能对比

虽然二分查找也能解决类似问题，但TreeMap有以下优势：

• 内置实现，无需手动维护有序数组
• 支持动态插入和删除，保持有序性
• 提供更多导航方法（如higherKey/lowerKey）

5.2 常见陷阱与规避方法

空指针问题：

Integer result = map.floorKey(key); if (result != null) { // 安全处理非null结果 }

自定义Comparator的影响：

// 降序排列的TreeMap TreeMap<Integer, String> descMap = new TreeMap<>(Comparator.reverseOrder()); descMap.put(3, "三"); descMap.put(1, "一"); descMap.put(2, "二"); System.out.println(descMap.floorKey(2)); // 输出：2 System.out.println(descMap.ceilingKey(2)); // 输出：2

处理重复键： 虽然TreeMap不允许重复键，但如果使用自定义对象作为键，确保正确实现了compareTo或compare方法。

在实际项目中，我曾遇到一个性能问题：在高频交易系统中过度使用floorKey导致延迟增加。通过预计算和缓存常用范围的结果，最终将查询性能提升了40%。这提醒我们，即使是最优雅的API，也需要根据具体场景进行合理使用。