- 正确答案：排行榜在服务器内存中通常采用“有序集合（Sorted Set）”作为核心数据结构，典型实现是基于跳表（Skip List）或平衡二叉搜索树（如红黑树），配合哈希表（Hash Table）实现O(1)的成员分数查询与更新。实际生产中（如Redis）采用跳表+哈希表双结构组合：跳表维护按分数排序的双向链式层级索引，支持O(log n)插入、删除、范围查询（如Top-K、排名查询rank、按排名查成员）；哈希表存储成员到分数的映射，支持O(1)分数读取与校验，避免跳表遍历查分。 - 解答思路：设计需同时满足三大高频操作的性能要求——（1）更新某用户分数（含新增/覆盖）；（2）查询某用户当前排名（即比其分数高的人数+1）；（3）获取排名区间数据（如前100名、第50~60名）。单一结构无法兼顾：数组排序后更新O(n)，堆不支持按成员查排名，链表无法高效定位排名。因此必须组合结构——用有序结构承载顺序语义，用哈希结构加速成员级随机访问。进一步考虑工程因素：跳表相比红黑树更易并发实现（节点无严格父子依赖）、层级指针天然支持跳跃式遍历、内存局部性较好、且Redis已验证其高并发下的稳定性，故成为工业界首选。 - 深度知识讲解： 1. 跳表原理：跳表是概率型有序数据结构，由多层链表构成，底层（L0）包含全部元素并有序链接；上层（L1, L2…）为底层的稀疏子集，每个节点以固定概率（通常p=0.5）向上提升一层。查找时从最高层起点开始，向右比较，若下一节点分数过大则下跳一层，最终在L0定位目标。期望层数为O(log n)，查找/插入/删除均摊时间复杂度O(log n)。关键点在于：插入时通过随机数决定新节点层数，保证各层节点数期望为n/2^i，从而维持结构平衡，无需像AVL或红黑树那样频繁旋转/染色。 2. 哈希表协同机制：单独跳表中，若要查“用户A的排名”，需从头遍历计数直到找到A，耗时O(n)；但结合哈希表（如unordered_map score_map），可先O(1)拿到A的分数score_A，再在跳表中执行“小于score_A的元素个数”查询（即rank操作）。跳表需额外在每层节点中维护“跨度（span）”字段：每个前向指针不仅指向下一节点，还记录该指针跨越的底层节点数量。例如L1层某指针从节点X指向Y，则span[X→Y] = L0中X到Y之间（含X不含Y）的节点总数。这样从头开始沿跳表查找score_A时，累加所有经过指针的span值，即可在O(log n)内得到排名（即比score_A小的元素个数），无需遍历。 3. 排名语义与分数冲突处理：当多个用户分数相同时，排名可采用“并列跳位”（如分数[100,100,95] → 排名[1,1,3]）或“并列不跳位”（→ [1,1,2]）。跳表本身只按分数+字典序（如用户名）复合排序，因此需在插入时将分数作为主键、用户名作为次键（tuple），确保相同分数下按名称排序，从而稳定排名。这也意味着：即使分数相同，用户在跳表中仍占据唯一位置，rank查询结果确定。 4. 内存优化细节：真实系统中会限制榜单大小（如仅存前10万），采用LRU或按最后更新时间淘汰；跳表节点常使用内存池（memory pool）预分配+对象复用，避免频繁malloc/free；字符串key使用引用计数或interning减少重复存储；分数类型常用int64_t存储毫秒级时间戳或放大后的定点数，规避浮点精度与比较问题。 - 伪代码（核心操作示意）： ``` // 数据结构定义 struct ScoreNode { string member; double score; vector forward; // 各层前向指针 vector span; // 各层对应前向指针跨越的底层节点数 }; class Leaderboard { private: ScoreNode* head; // 多层头节点 int max_level; unordered_map score_map; // 成员→分数 int length; // 当前总成员数 int random_level() { // 概率提升层数 int lvl = 1; while (rand() % 2 == 0 && lvl < max_level) lvl++; return lvl; } public: void update(string member, double score) { // 1. 更新哈希表 double old_score = score_map.count(member) ? score_map[member] : -INF; score_map[member] = score; // 2. 在跳表中删除旧节点（若存在） if (old_score != -INF) delete_node(member, old_score); // 3. 插入新节点：查找到插入位置，新建节点，更新各层指针和span insert_node(member, score); } int rank_of(string member) { if (!score_map.count(member)) return -1; double target = score_map[member]; ScoreNode* x = head; int rank = 0; // 从最高层向下查找，累加span for (int i = max_level - 1; i >= 0; i--) { while (x->forward[i] && (x->forward[i]->score < target || (x->forward[i]->score == target && x->forward[i]->member < member))) { rank += x->span[i]; x = x->forward[i]; } } return rank + 1; // 排名从1开始 } vector> range_by_rank(int start, int stop) { // 从头开始，先跳过start-1个节点，再取(stop-start+1)个 ScoreNode* x = head; int rank = 0; // 快进到start位置 for (int i = max_level - 1; i >= 0 && rank < start; i--) { while (x->forward[i] && rank + x->span[i] <= start) { rank += x->span[i]; x = x->forward[i]; } } // 收集结果 vector> res; for (int i = 0; i < stop - start + 1 && x->forward[0]; i++) { x = x->forward[0]; res.push_back({x->member, x->score}); } return res; } }; ```

四年工作经验游戏开发社招面经

全站热榜

创作者周榜