新闻详情

新闻详情

首页 / 资讯中心 / 详情

高频必考!跳表:抛硬币就能O(logn),Redis为什么不用红黑树?

发布时间:2026/11/22 3:43:33来源:尧图网络
高频必考!跳表:抛硬币就能O(logn),Redis为什么不用红黑树?
想要“有序 增删查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)方法你会发现比平衡树好写到难以置信。
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

【外设】之大彩串口显示屏 2026/11/21 14:14:45

【外设】之大彩串口显示屏

大彩串口屏初步使用 1 .官网下载 STM32 屏幕 GUI 设计资料 http://www.gz-dc.com/category/typeid/4112 找到 STM32 Keil 工程,移植相关代码因项目而异进行移植,由于项目简单,本人只对用到的指令接口进行修改。 比如:注意事项&…

阅读更多 →
无法下载Windows系统iso文件 2026/11/21 14:14:26

无法下载Windows系统iso文件

当我遇到这个问题的时候,我打开了一个网站: 登录 然后我打算下载的时候: 突然那个官方的连接就可以下载了:

阅读更多 →
【清华代码熊】DeepSeek V4.1 Flash 后训练详解 2026/11/21 21:08:55

【清华代码熊】DeepSeek V4.1 Flash 后训练详解

📌 上期解析了 DeepSeek V4.1 Flash 模型架构改进,本期解析 DeepSeek V4.1 Flash 预训练/后训练技术: 🌟 预训练:45T 文本 多模态混合语料、直接训练 sparse attention(取消 DeepSeek V4 的 dense 冷启动&…

阅读更多 →
Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ... 2026/11/22 1:51:41

Shuffle-R1: Efficient RL framework for Multimodal Large Language Models via Data-centric Dynamic ...

文章主要内容和创新点 主要内容 本文聚焦于多模态大语言模型(MLLM)强化学习(RL)训练中的效率问题,提出了一个名为Shuffle-R1的框架。研究发现,当前RL训练存在两个关键缺陷: 优势值坍缩(Advantage Collapsing):批次中大多数优势值集中在零附近,导致有效梯度信号被淹…

阅读更多 →
PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction 2026/11/21 19:02:25

PRvL: Quantifying the Capabilities and Risks of Large Language Models for PII Redaction

一、文章主要内容总结 本文聚焦于利用大型语言模型(LLMs)实现个人身份信息(PII)脱敏的研究,旨在解决传统脱敏方法(如基于规则的系统、领域特定命名实体识别(NER)模型)泛化能力差、跨格式/跨语境适应性弱的问题。 研究通过全面评估多种LLM架构(包括密集型LLM(D-LLM…

阅读更多 →
LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model 2026/11/21 14:13:11

LLaVA-RE: Binary Image-Text Relevancy Evaluation with Multimodal Large Language Model

文章主要内容和创新点 主要内容 本文聚焦于二进制图像-文本相关性评估任务(判断图像与文本“相关”或“不相关”),针对该任务中文本格式多样、相关性定义随场景变化等挑战,提出了基于多模态大语言模型(MLLM)的解决方案LLaVA-RE。 模型设计:LLaVA-RE基于LLaVA 1.5架构,…

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞 ✉