TreeMap与ConcurrentSkipListMap如何选？

本文深入剖析了TreeMap与ConcurrentSkipListMap在不同并发场景下的核心性能差异与选型陷阱：单线程下TreeMap凭借轻量构造、稳定O(log n)操作和O(1)的size()，是绝对首选；而ConcurrentSkipListMap因多层索引、CAS开销及O(log n)的非原子size()等设计代价，在单线程中反而导致GC上升、响应变慢，却被误用于日志聚合、配置加载等典型场景；仅当面临多线程高频写入且强依赖有序语义（如实时风控时间窗口、优先级任务队列）时，其跳表的局部加锁与无锁查找才能释放3–5倍吞吐优势——但需警惕containsValue()全表扫描、弱一致性迭代器及线程安全比较器等隐藏风险，真正决定选型的不是“Concurrent”前缀，而是你代码里真实的线程模型与操作分布。

单线程下别用 ConcurrentSkipListMap，纯属浪费

TreeMap 在单线程场景下性能稳定、内存占用低、GC 压力小；而 ConcurrentSkipListMap 为支持并发额外维护多层索引节点、引入 CAS 和锁字段，导致构造更重、插入慢约 20%～30%，且 size() 是遍历链表的 O(log n) 操作（不是 O(1)），频繁调用会拖慢整体节奏。

常见错误现象：ConcurrentSkipListMap 被误用于日志聚合、配置加载、本地缓存初始化等单线程流程，结果吞吐没提升，反而 GC 次数上升、响应变长。

• 判断依据很简单：整个 Map 生命周期内是否只在一个线程里被创建、填充、读取？是 → 用 TreeMap
• 若后续可能被多线程读，但写只发生一次（如启动时加载），可用 Collections.unmodifiableSortedMap(new TreeMap(...))，安全又轻量
• 不要因为“它带 Concurrent 就觉得更高级”——就像不给自行车装涡轮增压

高并发写+排序需求，ConcurrentSkipListMap 是目前最稳选择

当多个线程持续往有序结构里 put、remove、ceilingKey 或 subMap 时，TreeMap 即使套上 Collections.synchronizedSortedMap，也会因全局锁变成串行瓶颈；而 ConcurrentSkipListMap 的跳表结构天然支持局部加锁：插入只锁前驱/后继节点，查找完全无锁，实测在 8 线程以上写负载下吞吐高出 3～5 倍。

使用场景举例：

• 实时风控系统中按时间戳排序的事件窗口（put(timestamp, event) + headMap(now - 60s, true)）
• 分布式任务调度器里按优先级+提交时间双排序的任务队列
• 高频行情数据按价格档位做并发聚合（键为 price，值为 AtomicLong 订单量）

注意：ConcurrentSkipListMap 的排序依赖 Comparable 或构造时传入的 Comparator，且该比较器必须是线程安全的（不能含可变状态或共享缓存）。

size() 和 containsValue() 是两个隐藏性能陷阱

ConcurrentSkipListMap.size() 不是原子计数，而是从头遍历所有数据节点并累加——它的时间复杂度是 O(log n)，但常数项大，尤其在写入频繁时还可能遇到“懒删除”节点，实际耗时波动明显。同理，containsValue() 必须全表扫描，无法利用排序优势，和 HashMap 完全不是一回事。

• 替代方案：ConcurrentSkipListMap 本身不提供高效 value 查询，真需要查 value，应额外维护一个 ConcurrentHashMap 反向索引
• 如果只是想确认“有没有某个 key”，用 containsKey(key) ——这是 O(log n) 且无锁的
• 避免在循环或高频定时任务里调用 size()；如需监控大小，考虑用 AtomicLong 手动计数（配合自定义 wrapper）

迭代器弱一致性，遍历时删改要格外小心

ConcurrentSkipListMap 的 entrySet().iterator() 是弱一致性的：它不会抛 ConcurrentModificationException，但也不保证看到所有已提交的修改——可能跳过刚插入的项，也可能看到已删除的残留节点（“幽灵节点”）。这和 TreeMap 的 fail-fast 迭代器完全不同。

• 安全做法：遍历中只读，删改操作另起逻辑（比如先收集待删 key，遍历完再批量 removeAll）
• 若必须边遍历边删，用 forEach + computeIfPresent 等原子方法，而不是 iterator.remove()（它不支持）
• 范围视图如 subMap、tailMap 返回的也是弱一致性视图，其迭代行为同样不可预测

跳表不是银弹，它的优势集中在“高并发写+强排序语义”的交叉点上；一旦离开这个象限——比如纯读多写少、或排序要求其实可以妥协（用 ConcurrentHashMap + 外部排序），就该立刻换掉。选型时盯住真实线程模型和操作分布，比背时间复杂度公式管用得多。

以上就是《TreeMap与ConcurrentSkipListMap如何选？》的详细内容，更多关于的资料请关注golang学习网公众号！