TreeSet / ConcurrentSkipListSet 排行榜的两个坑改了属性 remove 失效同分的进不来战力榜、积分榜、竞技场排名——排行榜是游戏服里 TreeSet/ConcurrentSkipListSet 的最高频舞台也是两个经典坑的事发地元素改了属性之后 remove 失效以及两个玩家同分时后加入的进不去。这两个坑同根同源都来自有序集合用比较器判等——TreeSet 和 ConcurrentSkipListSet 都一样。这篇把原理、复现、正确姿势一次讲清最后给一个能直接用的排行榜骨架。一、根源TreeSet 的排序和判等是同一套东西先立一个认知后面所有坑都从这里长出来TreeSet 是 TreeMap 的马甲ConcurrentSkipListSet 是 ConcurrentSkipListMap 的马甲底层分别是红黑树和跳表。树/跳表里元素的位置由 compare 结果决定并且compare(a, b) 0就被判定为同一个元素。注意这和 HashSet 完全不同——HashSet 靠hashCodeequals判等你重写的 equals 在 TreeSet 里一个字都用不上。有序集合的世界里比较器就是法律它决定顺序、决定相等、决定 add/remove/contains 的一切行为。二、坑一先改属性再删删不掉排行榜的日常玩家战力变了要更新榜单。元素是可变的参与排序的字段一改事故就来了staticclassPlayer{finallongid;intscore;// 参与排序的字段Player(longid,intscore){this.idid;this.scorescore;}}TreeSetPlayerranknewTreeSet(Comparator.comparingInt(p-p.score));PlayeranewPlayer(1001,60);PlayerpnewPlayer(1002,50);PlayercnewPlayer(1003,70);rank.add(a);// 60 成为根rank.add(p);// 50 60挂到左子树rank.add(c);// 70 60挂到右子树p.score80;// 直接改属性50 → 80rank.remove(p);// 返回 false删不掉System.out.println(rank.size());// 还是 3为什么删不掉remove的定位过程和add一样从根节点开始用比较器决定往左还是往右走。这棵树当初按score50把 p 放在了左子树现在 p 的 score 是 80remove 拿着80从根 a(60) 开始找80 60 往右到 c(70)80 70 继续往右右边为空到头了——p 明明躺在左边 50 的位置上找的人却一路往 80 的方向右边走两条路永远碰不上。找不到返回 false。连带的伤害不止 removecontains(p)同样失效同一个定位逻辑迭代顺序已经乱了p 物理上还挂在旧位置但它的比较值是新分数——中序遍历出来的顺序不再有序之后任何 add/remove 都可能被这棵已经不合法的树带偏错误具有传染性。这个坑还有两处阴险的地方值得点破① 至少要两个元素才会显现——如果树里只有 p 一个节点remove(p)比较的是 p 和它自己compare(p, p)恒为 0反而一定删得掉② 它时灵时不灵——如果被改的元素恰好落在新分数的查找路径上比如它就是根节点remove 又会碰巧成功。正是这种不确定性让它极难排查本地用例偶尔能过上了线才炸。正确姿势先摘下来再改再放回去。下面是完整的正确写法不是接着上文删失败的状态往下写rank.remove(p);// ① 按旧分数定位并移除p.score80;// ② 安全地修改rank.add(p);// ③ 按新分数放回三步的顺序不能乱——本质是保证元素在树里的每一刻比较结果和它的位置都是一致的。ConcurrentSkipListSet 底层是跳表定位同样依赖比较器这个坑一模一样。设计层面的教训参与有序集合排序的字段要么把元素做成不可变的改分 换一个新对象要么用摘下—修改—放回的封装。裸露的可变字段 裸调用 add/remove迟早出事。三、坑二同分的玩家后加入的进不去第二个坑更隐蔽因为它的触发条件是业务数据撞车TreeSetPlayerranknewTreeSet(Comparator.comparingInt(p-p.score));rank.add(newPlayer(1001,100));rank.add(newPlayer(1002,100));// 两人同分System.out.println(rank.size());// 1 —— 1002 没进去原理就是第一节的规则两个玩家 score 相同 →compare 0→ TreeSet 认为是同一个元素 → 第二个 add 直接拒绝返回 false。玩家 1002 凭空从榜上消失而且没有任何报错——榜单人数悄悄少一个直到玩家投诉我打完分怎么没上榜才暴露。正确姿势比较器必须落到一个唯一的字段上同分时用玩家 ID 决胜TreeSetPlayerranknewTreeSet(Comparator.comparingInt((Playerp)-p.score).reversed()// 分数降序.thenComparingLong(p-p.id));// 同分按 ID 决胜这样任何两个玩家的 compare 永远不为 0相等只可能发生在同一个玩家身上——Set 的去重语义从bug变回了防重复添加的本意。两个业务变体同分先到先得tie-break 不用 ID用达到该分数的时间戳或一个自增序号ID 设计篇里的发号器产出的自增序号正好可用——谁先打到这个分谁在前同分并列展示排名计算时把compare 相同分数的相邻元素算同名次1、2、2、4那种这是展示层的逻辑不影响比较器仍然要落到唯一字段。再强调一遍这里重写equals/hashCode毫无作用。TreeSet 不看它们——很多人在坑二里折腾半天 equals方向从第一步就错了。换成 ConcurrentSkipListSet 呢一模一样。它同样用比较器判等同分照样compare 0、照样被判成同一个元素NavigableSetPlayerranknewConcurrentSkipListSet(Comparator.comparingInt(p-p.score));rank.add(newPlayer(1001,100));rank.add(newPlayer(1002,100));// 同分跳表照样进不去System.out.println(rank.size());// 1 —— 和 TreeSet 分毫不差所以别指望换个并发容器就能绕开这两个坑——换容器解决的是线程安全不是比较器语义上面的 tie-break 解法reversed().thenComparingLong(id)原样平移过去即可。四、连带要知道的三件事1比较器违约的下场静默错乱不是报错。JDK 的排序方法TimSort发现比较器不满足反对称/传递性会抛Comparison method violates its general contract!但TreeMap/TreeSet 不做这个检查——违约的树不抛异常只是悄悄地错加得进去删不出来、顺序不对、contains 时灵时不灵。坑一其实就是比较字段在树里变了 比较器违约的一种形式。排查这类问题的第一反应永远是审比较器以及比较器读到的字段稳不稳定。2并发视角。TreeSet 线程不安全换 ConcurrentSkipListSet 解决并发安全弱一致迭代、非阻塞但今天这两个坑一个都不少——它只是跳表版的同一套语义。选型一句话榜单能锁在单逻辑线程里就用 TreeSet确有多线程并发读写才上 ConcurrentSkipListSet但无论哪个比较器都得落到唯一字段。游戏服更常见的做法是釜底抽薪排行榜归属场景逻辑线程单线程访问延时任务篇讲过的单线程模型压根没有并发问题TreeSet 就够。3跨服/全服榜平移到 Redis ZSET。全服百万人的榜不该放单机内存用 Redis ZSET——而 ZSET 底层同样是跳表同分时按 member 的字典序排列和今天讲的tie-break 落到唯一字段完全同构member 天然唯一。内存 TreeSet 的这套经验可以原样平移过去只是先删后改再加变成一条ZADD服务端原子更新 score。五、一个能直接用的排行榜骨架综合两个坑的正确姿势一个单逻辑线程内的迷你排行榜publicclassRankBoard{privatefinalMapLong,PlayerindexnewHashMap();// id → 实体privatefinalTreeSetPlayerboardnewTreeSet(Comparator.comparingInt((Playerp)-p.score).reversed().thenComparingLong(p-p.id));// tie-break唯一 ID/** 更新分数不存在则上榜存在则摘下—改—放回 */publicvoidupdate(longid,intnewScore){Playerpindex.get(id);if(pnull){pnewPlayer(id,newScore);index.put(id,p);board.add(p);return;}board.remove(p);// ① 先按旧分数移除p.scorenewScore;// ② 再修改board.add(p);// ③ 按新分数放回}/** Top N榜单本身有序取前 n 个即可 */publicListPlayertop(intn){ListPlayerresultnewArrayList(n);for(Playerp:board){if(result.size()n)break;result.add(p);}returnresult;}/** 查某玩家名次1-based。注意这步是 O(n)原因见下文 */publicintrankOf(longid){Playerpindex.get(id);if(pnull)return-1;returnboard.headSet(p).size()1;// 排在他前面的人数 1}}设计要点都在注释和前文里了index负责按 ID 找到实体O(1)board只负责序。复杂度更新 O(log n)TopN O(n)查名次的rankOf也是 O(n)。把查名次的代价说清楚。红黑树没有记录每棵子树有多少个节点它不是顺序统计树所以要知道某玩家排第几headSet(p).size()只能把 p 前面那一段线性数一遍——实测 30 万元素的 TreeSet 上一次headSet().size()比一次contains慢几千倍。偶尔查几个无所谓但每个玩家打开榜单都想看自己排第几这种高频需求它就是个性能坑。两条出路平移到 Redis ZSET 用ZRANK/ZREVRANK跳表实现O(log n)或内存版、分数是固定范围内的整数时改用树状数组Fenwick Tree更新和查名次都是 O(log n)。这也呼应上一节——内存 TreeSet 适合中小规模、单逻辑线程、主要拿 TopN的场景一旦要频繁按 id 查名次就该换工具了。六、复盘现象直觉反应真正的原因与解法remove/contains 失效集合有 bug重写 equals排序字段变了元素在树里站错位置——先摘下再改再放回同分玩家上不了榜加锁换容器compare0 被判等——比较器用唯一 ID 做 tie-break顺序偶尔错乱数据问题比较器违约含字段可变TreeMap 静默错乱不报错多线程更新榜单上 ConcurrentSkipListSet并发安全了但坑还在归入单逻辑线程更彻底频繁查某玩家排第几很慢给 TreeSet 加索引红黑树不存子树大小headSet().size()是 O(n)——高频查名次改用 Redis ZRANK 或树状数组三条可复用的经验有序集合的元素参与排序的字段要么不可变要么改前先摘——这条纪律消掉 90% 的坑比较器必须收敛到唯一字段排序业务字段 决胜唯一键compare0 只应意味着同一个元素在 TreeSet 的世界里忘掉 equals/hashCode审问题先审比较器。七、写在最后两个坑一句话总结TreeSet 把排序和判等绑在了同一个比较器上——这个设计让它高效也让它对可变元素和逻辑相等天然苛刻。理解了这一句两个坑就不用背了自己能推出来。