想要“有序 增删查O(logn)”第一反应是红黑树或AVL。但它们的白板实现是公认的噩梦旋转、变色、叔叔节点、RR/LL/LR/RL四种情形……30分钟根本写不完。跳表Skip List给出了另一个答案给有序链表加多层“稀疏索引”谁上几层由抛硬币决定。代码不到100行平均O(logn)还天然支持O(logn k)的范围查询。今天我们就手写它并回答那个经典面试题“为什么Redis的有序集合用跳表不用红黑树” 题目速览 LeetCode 120630秒读懂设计一个跳表支持search(target)存在返回trueadd(num)插入元素允许重复erase(num)删除一个值为num的元素成功返回true示例add(1), add(2), add(3) search(0) → false add(4) search(3) → true erase(0) → false约束值 ≤ 2e4调用次数 ≤ 5e4要求平均O(logn)。 核心思路多层稀疏索引 随机化晋升有序链表的致命伤查找只能从头遍历O(n)。二分链表没有随机访问取不到中间节点。灵感给链表加“快速通道”建多条链表第0层包含所有元素完整有序链表数据全在这层第k层是第k-1层的稀疏子集约一半节点晋升搜索时从最高层开始能往右走就往右走不能就下降一层。像地铁先坐快线跳过一堆站再换普通线精确定位——本质是链表的“二分查找”。谁该晋升——抛硬币如果晋升规则固定如每隔一个晋升插入删除后全错位。跳表的做法彻底放弃严格维护改用概率。插入新节点时先在第0层出现然后反复抛硬币——正面晋升一层继续抛反面停。p通常取0.5。每个节点层数服从几何分布50%有1层25%有2层……期望空间开销只有2个指针/节点。妙处插入删除完全不用动其它节点的层数。凭什么平均O(logn)第k层约n·p^k个节点。期望层数 ≈log_{1/p}(n)。搜索路径反向看每上升一层向左一步的期望代价是常数总层数期望O(logn)所以总期望代价O(logn)。注意是期望最坏O(n)但概率指数衰减工程可接受。跳表 vs 红黑树维度跳表红黑树查询/插入/删除O(logn) 平均O(logn) 最坏保证实现难度简单约60行复杂旋转变色范围查询找到起点后沿底层走O(logn k)需中序遍历维护成本高内存平均2指针/节点可调p固定2子指针 颜色并发改造相对容易难旋转涉及大片子树调参灵活性可通过p权衡内存/性能基本不可调️ 图解算法手把手走一遍假设存了1~9按运气晋升后第 3 层 H ─────────────────────────────────▶ 7 ─────────────▶ nil 第 2 层 H ────────────────▶ 3 ─────────────▶ 7 ─────────────▶ nil 第 1 层 H ───────▶ 1 ─────▶ 3 ─────▶ 5 ────▶ 7 ─────▶ 9 ────▶ nil 第 0 层 H ──▶ 1 ──▶ 2 ──▶ 3 ──▶ 4 ──▶ 5 ──▶ 6 ──▶ 7 ──▶ 8 ──▶ 9 ──▶ nil节点7出现在4层是同一个对象只是挂了4根forward指针。走一遍search(7)层当前前方判断动作L3H77 7? ❌下降L2L2H33 7 ✅右移到3L237❌下降L1L135✅右移到5L157❌下降L0L056✅右移到6L0677 7 ✅返回true规律每层往右走到“再走一步就 target”为止然后下降一层降到第0层后检查正前方是否等于target。路径像一条从左上到右下的阶梯。 代码实现Python JavaPython版importrandom MAX_LEVEL32P0.5classNode:__slots__(val,forward)def__init__(self,val,level):self.valval self.forward[None]*levelclassSkiplist:def__init__(self):self.headNode(-1,MAX_LEVEL)# 头哨兵self.level1def_random_level(self):lv1whilerandom.random()PandlvMAX_LEVEL:lv1returnlvdefsearch(self,target:int)-bool:curself.headforiinrange(self.level-1,-1,-1):whilecur.forward[i]andcur.forward[i].valtarget:curcur.forward[i]curcur.forward[0]returncurisnotNoneandcur.valtargetdefadd(self,num:int)-None:update[None]*MAX_LEVEL curself.headforiinrange(self.level-1,-1,-1):whilecur.forward[i]andcur.forward[i].valnum:curcur.forward[i]update[i]cur lvself._random_level()iflvself.level:foriinrange(self.level,lv):update[i]self.head self.levellv nodeNode(num,lv)foriinrange(lv):node.forward[i]update[i].forward[i]update[i].forward[i]nodedeferase(self,num:int)-bool:update[None]*MAX_LEVEL curself.headforiinrange(self.level-1,-1,-1):whilecur.forward[i]andcur.forward[i].valnum:curcur.forward[i]update[i]cur targetcur.forward[0]iftargetisNoneortarget.val!num:returnFalseforiinrange(self.level):ifupdate[i].forward[i]isnottarget:breakupdate[i].forward[i]target.forward[i]whileself.level1andself.head.forward[self.level-1]isNone:self.level-1returnTrueJava 版importjava.util.Random;classSkiplist{privatestaticfinalintMAX_LEVEL32;privatestaticfinaldoubleP0.5;privatefinalRandomrndnewRandom();staticclassNode{intval;Node[]forward;Node(intval,intlevel){this.valval;this.forwardnewNode[level];}}privatefinalNodeheadnewNode(-1,MAX_LEVEL);privateintlevel1;privateintrandomLevel(){intlv1;while(rnd.nextDouble()PlvMAX_LEVEL)lv;returnlv;}publicbooleansearch(inttarget){Nodecurhead;for(intilevel-1;i0;i--){while(cur.forward[i]!nullcur.forward[i].valtarget)curcur.forward[i];}curcur.forward[0];returncur!nullcur.valtarget;}publicvoidadd(intnum){Node[]updatenewNode[MAX_LEVEL];Nodecurhead;for(intilevel-1;i0;i--){while(cur.forward[i]!nullcur.forward[i].valnum)curcur.forward[i];update[i]cur;}intlvrandomLevel();if(lvlevel){for(intilevel;ilv;i)update[i]head;levellv;}NodenodenewNode(num,lv);for(inti0;ilv;i){node.forward[i]update[i].forward[i];update[i].forward[i]node;}}publicbooleanerase(intnum){Node[]updatenewNode[MAX_LEVEL];Nodecurhead;for(intilevel-1;i0;i--){while(cur.forward[i]!nullcur.forward[i].valnum)curcur.forward[i];update[i]cur;}Nodetargetcur.forward[0];if(targetnull||target.val!num)returnfalse;for(inti0;ilevel;i){if(update[i].forward[i]!target)break;update[i].forward[i]target.forward[i];}while(level1head.forward[level-1]null)level--;returntrue;}}⚠️防坑提醒必看update[i]必须在同一趟从高到低遍历中一次性收集不能每层单独遍历。插入时若lv self.level多出来的层前驱是头哨兵。erase里if update[i].forward[i] is not target: break防止越界。允许重复值比较用而非。⏱️ 复杂度分析面试必问操作平均时间空间search / add / eraseO(logn)O(n)范围查询O(logn k)—期望层数1/(1-p) 2个指针/节点。p 调小可省内存但搜索变慢——这是平衡树给不了的旋钮。 举一反三4道高频变体与延伸题目/延伸关键变化思路要点LC.1206今天纯跳表实现多层索引 随机层数Redis zset有序集合dictO(1)定点查 skiplist范围组合LevelDB/RocksDB MemTable内存表跳表插入快、天然有序、支持迭代Java ConcurrentSkipListMap无锁并发有序MapCAS 标记指针JDK唯一无锁有序容器 面试追问模拟提前准备惊艳全场Q1为什么Redis用跳表而不是红黑树四条理由①范围查询天然强ZRANGE一次O(logn)定位起点沿底层走k步红黑树需中序遍历②实现简单跳表60行红黑树删除十几种情形③可通过p调参权衡内存与性能④ 性能同阶无劣势。补充Redis是dict skiplist双结构dict负责ZSCOREO(1)定点查跳表负责ZRANGE/ZRANK。Q2跳表层数上限怎么定MAX_LEVEL log_{1/p}(N)。常见取32Redis就是32p0.5可撑2^32元素Redis p0.2532层撑2^64。Q3什么场景选平衡树而不是跳表① 需要严格最坏保证实时系统② 内存极度敏感跳表每节点指针数可变分配较碎③ 需要树形语义子树聚合、Rank Tree。反过来范围遍历、并发无锁改造、实现速度优先时跳表完胜。Q4删除时为什么用update[]而不能从高层顺序删必须从低层往高层改或先收集所有前驱再统一改。一边找一边改会让高层前驱被跳过留下僵尸节点。 实战小技巧刷题党必备口诀从高往低走能右则右不能则降底层验等。模板跳表 头哨兵 随机层数 update数组 逐层插入/删除。防坑update数组一趟收集删除后收缩level。 实际应用场景不止是刷题Redis 有序集合排行榜、延迟队列、滑动窗口限流LevelDB/RocksDB MemTable内存索引Java ConcurrentSkipListMap并发有序映射Elasticsearch倒排索引部分跳表加速 今日思考题把晋升概率p从0.5调到0.25内存和查询速度分别怎么变提示内存降约1.33指针/节点搜索步数变多。动手题给今天的Skiplist加一个range(start, end)方法你会发现比平衡树好写到难以置信。