游戏高分映射存储与按值排序的高效实现方案

你当前每次更新得分就全量排序Map再写入LinkedHashMap的实现，性能会随玩家规模上涨快速劣化：

• 单次更新的时间复杂度是O(nlogn)，玩家数到十万级时，单次写入就会出现毫秒级甚至更高的延迟，玩家量再高会直接阻塞业务线程
• LinkedHashMap本身只支持维护插入顺序或访问顺序，不支持动态调整元素顺序，每次排序后全量重新写入的操作会带来额外的*O(n)*内存拷贝开销，完全没有必要
• 更新玩家得分时需要先遍历全量Map找旧值，平白增加了遍历开销

核心是把「每次更新触发全量排序」改成「动态维护有序索引」，把单次更新、查询排名、拉取榜单的时间复杂度都降到*O(logn)*级别，根据你的部署场景和玩家规模选对应方案就行。

方案1：本地内存双索引结构（适合单机、玩家量万级到十万级的场景） #

用两个基础数据结构配合实现，没有额外依赖，性能足够稳定：

• 第一个结构用普通HashMap<UUID, Long>：存储玩家UUID和最新得分的映射，支持*O(1)*复杂度查询玩家当前得分、更新得分时快速拿到旧值，不用全量遍历。
• 第二个结构用自定义排序的TreeMap：因为TreeMap本身是红黑树实现的有序Map，天生支持动态插入、删除时维持顺序，时间复杂度都是O(logn)。注意要解决同分key重复的问题，把Map的key封装成(得分, 玩家UUID)的组合对象，排序规则设为得分倒序，得分相同时按UUID字典序排序，保证每个key唯一。

单次更新得分的流程只有三步：

1. 从HashMap中查询该玩家的旧得分，如果存在旧得分，先从TreeMap中删除旧的(旧得分, UUID)节点
2. 更新HashMap中对应该玩家的得分值为新值
3. 往TreeMap中插入新的(新得分, UUID)节点

核心实现代码示例（Java）：

// 排行组合key类
record ScoreEntry(long score, UUID playerId) {}

// 初始化有序排行Map，按得分倒序、UUID升序排
TreeMap<ScoreEntry, UUID> rankMap = new TreeMap<>((a, b) -> {
    int scoreCompare = Long.compare(b.score(), a.score());
    return scoreCompare != 0 ? scoreCompare : a.playerId().compareTo(b.playerId());
});
HashMap<UUID, Long> playerScoreMap = new HashMap<>();

// 更新得分方法
public void updateScore(UUID playerId, long newScore) {
    Long oldScore = playerScoreMap.get(playerId);
    if (oldScore != null) {
        rankMap.remove(new ScoreEntry(oldScore, playerId));
    }
    playerScoreMap.put(playerId, newScore);
    rankMap.put(new ScoreEntry(newScore, playerId), playerId);
}

需要取前N名榜单时，直接遍历TreeMap的前N个节点即可；需要查询某玩家的排名时，调用rankMap.headMap(new ScoreEntry(currentScore, playerId)).size() + 1就能拿到结果，不用做全量排序。

如果你的场景有高并发读写需求，把TreeMap换成ConcurrentSkipListMap、HashMap换成ConcurrentHashMap就行，并发安全的同时性能损失很小。

方案2：分布式有序结构（适合玩家量十万级以上、多服部署的场景） #

如果你的游戏玩家规模更大、或者是多服共享排行榜的架构，不用自己在内存里维护索引，直接用跳表实现的有序集合结构就行，最常用的是Redis的ZSET数据结构：

• ZSET的member直接存玩家UUID，score存玩家的long类型得分
• 更新得分直接调用ZADD指令，会自动覆盖该玩家的旧得分，单次操作时间复杂度O(logn)
• 取前N名榜单用ZREVRANGE指令，查单个玩家的排名用ZREVRANK指令，查单个玩家得分用ZSCORE指令，所有操作都是对数级复杂度
• 不需要自己处理并发、持久化、多实例共享的问题，成熟稳定，能支撑每秒数万次的得分更新请求。

• 小型单机游戏、玩家量在十万以内，直接用双索引的本地方案，内存占用低，没有外部依赖
• 中大型游戏、多服架构，直接用ZSET实现，省掉自己维护有序结构的潜在bug，性能足够支撑绝大多数游戏的排行需求
• 不要继续用全量排序+LinkedHashMap的方案，这个方案只适合玩家量几百上千的极小场景，规模一上来性能会直接崩掉

内容的提问来源于stack exchange，提问作者user14074829