- 正确答案：排行榜（如游戏积分榜、直播打赏榜）在服务器内存中的典型高效数据结构设计是「有序集合（Sorted Set）」，底层通常采用跳表（Skip List）或平衡二叉搜索树（如红黑树），配合哈希表（Hash Table）实现 O(1) 查询与 O(log n) 插入/更新/排名查询；实际生产中，Redis 的 ZSET 是工业级标杆实现，其内存结构为「跳表 + 哈希表」双索引结构。 - 解答思路：排行榜核心操作包括：① 用户分数更新（插入或覆盖）；② 查询某用户当前排名（Rank）；③ 查询 Top-K 用户（按分降序）；④ 查询指定排名区间（如第100~110名）；⑤ 删除用户（如封禁后剔除）。这些操作需兼顾高频写入（如每秒万级打赏更新）和低延迟读取（毫秒级响应）。若仅用数组+排序，每次更新需 O(n log n)；若仅用哈希表，无法支持按分排序；因此必须引入支持动态有序性的数据结构。跳表因其实现简单、并发友好、平均性能稳定（O(log n) 查找/插入/删除）、且天然支持「按排名范围遍历」（即 ZRANGE BYRANK）而成为首选；哈希表则用于 O(1) 定位用户当前分数，避免跳表中重复遍历查找节点。 - 深度知识讲解： 1. 跳表（Skip List）原理：跳表是概率性多层链表，底层为有序单链表（Level 0），上层为稀疏索引链表（Level 1, 2, …），每层节点以概率 p（通常为 0.5）晋升到上一层。查找时从最高层头结点开始，沿当前层向右滑动至「下一个节点值 > target」，然后下降一层继续，直至 Level 0 找到目标或确定不存在。插入时先随机生成层数（基于几何分布），再逐层定位插入位置并更新前驱指针。跳表的期望高度为 O(log n)，每层平均节点数减半，故平均时间复杂度为 O(log n)，空间复杂度 O(n)（期望总节点数 ≈ 2n）。相比红黑树，跳表无复杂旋转逻辑，更易实现无锁并发（如通过 CAS 更新指针），适合高并发排行榜场景。 2. 双索引设计必要性： - 跳表按 score + member 字典序组织，支持按分排序和范围查询（ZRANGEBYSCORE），但不支持 O(1) 查找某 member 的当前节点（需遍历）； - 因此需额外维护一个哈希表（如 unordered_map），key 为用户ID，value 指向跳表中该用户的节点指针；当用户分数更新时，先查哈希表得原节点，O(1) 删除（需跳表支持反向指针或标记删除+惰性清理），再以新分插入跳表并更新哈希表。这样「更新」整体为 O(log n）（删除+插入各 O(log n)，哈希操作 O(1)）；「查排名」即跳表中统计小于该 score 的节点数（可优化为每个节点存「跨度」span 字段，记录本节点到下一层同位置节点间跨越的 Level-0 节点数，从而 O(log n) 计算 rank）；「查 Top-K」直接从跳表头开始遍历 K 个节点。 3. 内存布局与缓存友好性：实际实现中，跳表节点常设计为紧凑结构： struct SkipListNode { double score; // 分数（主排序键） string member; // 用户ID（唯一标识，次排序键防重复） SkipListNode** forward; // 各层后继指针数组（动态分配） int* span; // 各层跨度数组（用于 O(log n) rank 计算） SkipListNode* backward; // 仅 Level 0 需要前驱（支持 ZREVRANGE） }; 哈希表使用开放寻址（如 Robin Hood Hashing）可减少指针跳转，提升 CPU cache 命中率。对于超大规模排行榜（如千万级用户），可引入分片（Sharding）：按用户ID哈希分桶，每个分片独立维护跳表+哈希表，Top-K 查询需合并各分片结果（归并K路有序链表）。 4. 对比其他结构： - 红黑树：理论上支持 O(log n) 所有操作，但 STL map/set 不支持按排名（rank）直接访问（需 order statistic tree 扩展，glibc 不提供）；且迭代器不稳定，删除后失效；并发需全局锁，扩展性差。 - 堆（Heap）：仅支持 Top-K 查询快，但无法高效支持「查某用户排名」或「删除任意用户」（堆不支持按值删除，需 O(n) 查找）。 - B+树：磁盘友好，但内存中指针开销大、cache 不友好，且无天然 rank 支持。 - 数组+二分：静态场景可用，但插入/删除为 O(n)，不可接受。 - 伪代码（核心操作示意）： ``` class Leaderboard { private: struct Node { double score; string member; vector forward; // forward[i] = next node at level i vector span; // span[i] = # nodes between this and forward[i] at level 0 }; Node* head; int max_level; unordered_map member_table; // member -> node ptr mt19937 rng; int random_level() { int lvl = 1; while (rng() & 1 && lvl < max_level) lvl++; return lvl; } public: void update(string member, double score) { // Step 1: if exists, remove old node auto it = member_table.find(member); if (it != member_table.end()) { remove_node(it->second); member_table.erase(it); } // Step 2: insert new node Node* newNode = create_node(member, score, random_level()); insert_node(newNode); member_table[member] = newNode; } int get_rank(string member) { // 1-indexed rank, higher score first auto it = member_table.find(member); if (it == member_table.end()) return -1; Node* node = it->second; int rank = 0; Node* x = head; for (int i = max_level-1; i >= 0; i--) { while (x->forward[i] && (x->forward[i]->score > node->score || (x->forward[i]->score == node->score && x->forward[i]->member < node->member))) { rank += x->span[i]; x = x->forward[i]; } } return rank + 1; // because rank is 0-indexed in calc } vector> top_k(int k) { vector> res; Node* x = head->forward[0]; // first node at level 0 while (x && k-- > 0) { res.push_back({x->member, x->score}); x = x->forward[0]; } return res; } }; ```

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

全站热榜

创作者周榜