firstKey() 和 lastKey() 均以 O(log n) 时间复杂度直接定位跳表最左/最右有效节点，不遍历全表；前者沿底层链表从头找首个有效键，后者反向追溯尾端有效键，均跳过删除中或未完成节点，支持并发安全但返回弱一致性快照。

ConcurrentSkipListMap 的 firstKey() 和 lastKey() 方法不是遍历查找，而是直接定位到跳表的最左和最右有效节点，时间复杂度为 O(log n)，不依赖元素数量，也不扫描整个结构。

firstKey() 是怎么快速拿到最小键的？

跳表底层维护了一个“头索引层”和指向首尾数据节点的引用。firstKey() 实际沿跳表最底层（即原始有序链表）从头节点出发，跳过所有标记为删除或未完成的节点，找到第一个有效的、非哨兵的数据节点，取其 key。这个过程最多走 O(log n) 层，每层常数步，所以整体对数时间。

• 不等待写操作完成：遇到正在被 remove 或 put 中的节点，会跳过并继续找下一个有效节点
• 不保证强一致性：返回的是某一时刻的快照视图，可能略滞后于最新写入（但符合弱一致性语义）
• 空 map 调用会抛 NoSuchElementException，建议先判空：if (!map.isEmpty()) { ... }

lastKey() 同理，但方向相反

lastKey() 从跳表最底层的尾端反向追溯，利用跳表双向链表结构（每个数据节点含 prev 指针），同样避开无效节点，定位到最后一个有效键。它和 firstKey() 共享同一套节点有效性判断逻辑，只是遍历方向不同。

• 不依赖 size()：即使 map.size() 很大，lastKey() 也不需要遍历全部元素
• 并发安全：整个查找过程无锁，靠 CAS 和 volatile 读保证线程安全
• 注意 null 键限制：ConcurrentSkipListMap 不允许 null 键，所以 firstKey()/lastKey() 返回值绝不会为 null

边界查找的适用场景与注意事项

这两个方法适合做范围控制、分页锚点、监控极值等轻量级元信息获取，但不适合替代业务逻辑中的精确条件判断。

JavaStoryDevelop

你接手一个需求时，是不是经常这样："改一个小字段 → 结果把不相关的代码也改了"、"需求说得很模糊 → 做着做着发现跑偏了"、"数据库加个字段 → 上线才发现漏了数据兼容"、"做了个新功能 → 一个月后自己都忘了当时怎么设计的"、"写到一半被中断 → 再回来不知道从哪继续"；这个 Skill 就是专门解决这些问题的。 它会自动探测你的项目环境（JDK、Spring Boot、ORM、数据库、前端框架），记在

下载

立即学习“Java免费学习笔记（深入）”；

• 不要用于循环中频繁调用：虽然单次 O(log n)，但高并发下仍可能成为瓶颈
• 不能代替 headMap/tailMap：如果需要子视图，直接用 headMap(k, false) 更高效且语义清晰
• key 类型必须实现 Comparable 或提供 Comparator：否则构造时就抛异常，first/last 查找也无从谈起

简单验证示例

可这样验证行为：

ConcurrentSkipListMap<Integer, String> map = new ConcurrentSkipListMap<>();
map.put(5, "a"); map.put(1, "b"); map.put(9, "c");
System.out.println(map.firstKey()); // 输出 1
System.out.println(map.lastKey());  // 输出 9
map.remove(1);
System.out.println(map.firstKey()); // 输出 5（自动跳过已删节点）

输出结果稳定，且无论插入顺序如何，始终按 key 自然序返回边界值。