实现游戏排行榜

实现一个游戏排行榜要求有：

• 1.支持添加/更新玩家分数
• 2.支持查询玩家排名
• 3.支持获取前N名玩家
• 4.需要考虑并发安全

代码实现：

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentSkipListMap;
import java.util.concurrent.ConcurrentSkipListSet;public class GameRankSystem {private final ConcurrentHashMap<String, Long> hash = new ConcurrentHashMap<>();// 分数排名存储（分数 -> 玩家ID集合），使用线程安全的跳表实现，分数按降序排列private final ConcurrentSkipListMap<Long, Set<String>> rankList =new ConcurrentSkipListMap<>(Comparator.reverseOrder());public void addScore(String playerId,long score) {hash.compute(playerId, (id, oldScore) -> {if (oldScore != null) {// 如果已有分数，先从排名中移除旧分数removePlayerFromRankings(id, oldScore);}// 更新分数并添加到新排名addPlayerToRankings(id, score);return score;});}private void addPlayerToRankings(String playerId, long score) {rankList.compute(score,(oldScore,players)->{if(players==null) {players=ConcurrentHashMap.newKeySet();}players.add(playerId);return players;});}private void removePlayerFromRankings(String playerId, long score) {rankList.computeIfPresent(score,(s,players)->{hash.remove(playerId);return players.isEmpty()? null:players;});}public int getPlayerRank(String playerId) {Long score = hash.get(playerId);if(score==null) {return -1;}int rank=1;for(Map.Entry<Long, Set<String>> entry : rankList.headMap(score).entrySet()) {rank+=entry.getValue().size();}Set<String> sameScorePlayers = rankList.get(score);if (sameScorePlayers!=null) {for(String players:sameScorePlayers) {if(playerId.equals(players)) {break;}rank++;}}return rank;}public List<String> getTopN(int n ) {List<String> topN = new ArrayList<>();int count=0;for(Map.Entry<Long, Set<String>> entry : rankList.entrySet()) {for (String player : entry.getValue()) {if(count>=n) {break;}topN.add(player);count++;}//双层break跳出循环。if(count>=n) {break;}}return topN;}}

1.为什么选用这样的数据结构呢

在设计并发游戏排名系统时，我们需要考虑：

• 1.高效的插入，更新，查询O（1）或0（log n）
• 2.线程安全
• 3.支持高效的范围查询（如获取前N名）
• 4.处理同分玩家（多个玩家可能有相同分数）

1.ConcurrentHashMap存储玩家分数

作用：存储playerId -> score的映射

为什么选择它：

线程安全：ConcurrentHashMap是线程安全的哈希表，支持高并发读写。

O（1）查询：可以快速获取某个玩家的分数。

原子性更新：使用compute()方法可以保证get+update操作的原子性

2.ConcurrentSkipListMap存储分数排名

作用：存储score -> Set<playerId> 的映射，并按分数降序排列。

为什么选择它？

线程安全：ConcurrentSkipListMap是并发版本的跳表（SkipList），支持高并发访问。

有序性：自动按分数进行排序（使用Comparator.reverseOrder()使分数降序排列）。

高效的范围查询：headMap可以快速获取所有比score高的分数（用于计算排名）

遍历时直接按分数从高到低获取前N名（getTopN只需O（N）时间）。

支持同分玩家：使用Set<String>存储相同的分数玩家，避免重复。

对比其他可能的数据结构：

方案1：TreeMap+HashMap（非线程安全）

问题：

TreeMap不是线程安全的，高并发环境下需要额外加锁，性能下降

HashMap也需要同步，否则可能导致数据不一致

方案2：PriorityQueue（堆结构）

问题：

标准PriorityQueue不是线程安全的

更新某个玩家的分数时，需要先删除再插入O（N)时间，效率低

无法高效的计算某个玩家的排名（堆结构不支持O（1）或O（log n）排名查询

方案3：数据库（如Redis ZSET)

优点：

Redis的ZSET天然支持排名，范围查询，分数更新

缺点：

需要引入外部存储，增加系统复杂度

如果仅需内存计算，ConcurrentSkipListMap是更轻量级的替代方案

总结：

当前方案的优缺点：

优点：

线程安全：ConcurrentHashMap+ConcurrentSkipListMap都是并发优化的数据结构，无需额外同步

高效查询：

获取玩家分数：O（1）（ConcurrentHashMap）

计算玩家排名：O（log n）跳表的查询范围。

获取前N名：O（n）（直接遍历跳表)

支持同分玩家：使用Set<String>存储相同的分数的玩家，避免冲突。

缺点：

内存占用较高：

ConcurrentSkipListMap相比TreeMap占用更多的内存（因为跳表的多层索引结构）。

同分玩家的排名顺序不固定：

如果多个玩家同分，getPlayerRank返回的排名可能因为并发插入顺序而变化（如需严格顺序，可改用List并加锁，但会影响性能）。

分析一段代码：

 public void addScore(String playerId,long score) {hash.compute(playerId, (id, oldScore) -> {if (oldScore != null) {// 如果已有分数，先从排名中移除旧分数removePlayerFromRankings(id, oldScore);}// 更新分数并添加到新排名addPlayerToRankings(id, score);return score;});}

在调用这一段代码过程中参数对应关系：

1.方法定义原型

V compute(K key, BiFunction<K,V,V> remappingFunction)

• 1.读取旧值（oldScore）
• 2.执行Lambda逻辑
• 3.写入新值（score）
• 整个过程对当前键playerId是原子的。

对比其他方法：