跳表的原理及 Redis ZSet 的实现
哪些公司问过
答案要点
- 跳表:多层有序链表,L0 包含全部元素,上层是下层的子集,作为索引
- 节点层数由随机晋升决定(每层概率 p,Redis 为 0.25);查找、插入、删除平均 O(log n)
- 查找:从最高层向右走到最后一个小于目标的节点,再下降一层,重复直到 L0
- Redis 有序集合(ZSet)元素多时用跳表 + 哈希表:跳表按 score 排序,哈希表按成员 O(1) 查找
- 优点:实现简单、范围查询方便(沿底层链表遍历)、内存占用可调;缺点是概率性,不保证最坏复杂度
易错点
- 说跳表是红黑树的变种
- 查找时说不清为什么要下降一层
- 说跳表最坏复杂度是 O(log n)
- 把 Redis 选跳表的原因归为并发友好:Redis 命令是单线程执行的
面试官常见追问
- 为什么 Redis 用跳表而不用红黑树?
- ZSet 小数据量时用什么编码?为什么不用 B+ 树?
- 跳表和平衡树相比,最坏情况怎么样?
- ZSet 为什么还要配合哈希表?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。