哈希算法题目：设计一个基于哈希的分布式实时排行榜系统（支持分数更新和Top K查询） 题目描述 设计一个分布式实时排行榜系统，支持以下操作： 添加或更新用户分数 （ addScore(userId, score) ）：如果用户已存在，则将新分数累加到原分数上；否则新增用户。 查询Top K用户 （ top(k) ）：返回分数最高的前K个用户（分数相同按用户ID升序排列）。 系统需支持高并发 ，数据分布在不同节点上。 解题思路 核心挑战 分数动态更新 ：需要快速定位用户当前分数并修改。 Top K查询效率 ：传统排序（如全量排序）在数据量大时效率低。 分布式环境 ：数据分片存储，需跨节点聚合结果。 关键技术选择 哈希表 （用户ID → 分数）：实现O(1)时间查询和更新用户分数。 有序结构 （如跳表或平衡树）：维护分数排名，支持高效Top K查询。 分片策略 ：按用户ID分片，分散负载。 逐步实现 步骤1：单机版本设计（先解决核心逻辑） 数据结构 哈希表 user_scores ：记录每个用户的当前分数。 有序集合 ranking （用跳表实现）：以分数为键、用户ID为值，支持相同分数按ID排序。 操作流程 addScore(userId, score) ： 通过 user_scores 获取旧分数 old_score （若不存在则为0）。 计算新分数 new_score = old_score + score 。 更新 user_scores[userId] = new_score 。 若 old_score ≠ 0 ，从 ranking 中删除 (old_score, userId) 。 向 ranking 插入 (new_score, userId) 。 top(k) ： 从 ranking 中反向遍历（分数从高到低），取前K个用户。 时间复杂度 添加/更新：O(log N)（跳表插入删除复杂度）。 Top K查询：O(K)（跳表按排名访问）。 步骤2：分布式扩展 数据分片 对用户ID进行哈希（如一致性哈希），将用户分配到不同节点。 每个节点独立维护其分片内的 user_scores 和 ranking 。 跨节点Top K查询 问题 ：每个节点只能返回本地Top K，需合并所有节点的结果得到全局Top K。 解决方案 ： 向所有节点并发请求本地Top K（假设K=10，则每个节点返回前10名）。 合并结果：将所有返回的候选用户聚合到全局最小堆（容量为K），最终堆中元素即为全局Top K。 优化 ：若某节点的最高分低于当前全局第K名，可提前终止该节点的数据拉取（通过多轮迭代实现）。 分数更新的一致性 由于用户数据只存在于一个节点，更新操作无需跨节点事务，只需保证节点内原子性（如加锁或原子操作）。 步骤3：并发优化 读写锁：支持多线程读（ top(k) ）与单线程写（ addScore ）的并发。 异步合并：分布式查询时，并行请求所有节点，减少延迟。 举例说明 假设系统有2个节点，初始状态如下： 节点1 ：用户A（分数50）、用户C（分数30） 节点2 ：用户B（分数40）、用户D（分数20） 执行 addScore("B", 25) ： 节点2更新用户B分数为65，并调整本地排名。 执行 top(2) ： 向节点1请求Top 2：[ (A,50), (C,30) ] 向节点2请求Top 2：[ (B,65), (D,20) ] 合并结果：全局Top 2为[ (B,65), (A,50) ]。 总结 哈希表 用于快速定位用户， 有序结构 维护排名， 分片策略 解决分布式扩展。 分布式Top K查询通过合并局部结果实现，避免全局排序的开销。 实际应用中可进一步优化（如缓存全局Top K、增量更新排名等）。