跳表（SkipList）超详细笔记｜Redis底层实现+代码完整版+面试对比

SkipList 跳表【跳表完整学习笔记面试/备考直接用】详细拆解跳表SkipList核心原理从定义、查询流程到随机层数生成逻辑Redis标准p0.25、maxLevel32附带可直接运行的C完整实现代码无bug。重点对比跳表与红黑树、哈希表的优劣厘清p0.5与p0.25的空间差异解释Redis选择跳表作为ZSet底层的核心原因补充面试高频考点帮你快速吃透跳表搞定面试相关问题。一、What’s SkipListSkipList可以认为是优化过的链表。通过一个数据域搭配多个指针域能够实现类似与二分查找的效果将原来链表的O(N)的时间复杂度优化到logN同时为了避免logN的时间复杂度在插入或者删除的过程中退化各个节点一样高的话就会退化成链表采取随机数的方式来决定每一个节点的高度。当然也并不是随便什么数都可以拿来当作高度我们还引入了一个[0,1]的增长概率p来保证既能防止跳表在插入、删除过程中退化为俩表又能将节点的高度控制在合理的范围内二、跳表查询的过程比如在上面的跳表中我们去查询11。首先从最上面一层开始找到16发现比11大说明11如果存在的话那么一定在头节点到16之间16之后的就都不用查找了接下来找第二层找到8发现比11小说明11存在的话就一定在8和16之间头节点到8之间就不用找了然后找地三层找到13发现比11大说明11存在的话就一定在8和13之间找第四层找到11总结不难发现跳表每次查找都会抛弃掉一部分一定不会存在结果的查找就像二分查找一样每次都会抛弃一半的遍历不过这里并不一定是一半更多更少都有可能三、跳表的效率如何保证前面提到过可能会出现增加、删除节点导致跳表退化为链表的的情况比如上面图中删除所有高度为1、3、4的节点就会造成这种结果而我们增加的话也很难去直接确定某个节点的位置最适合多高。所以我们采取了比较大胆的解法引入一个随机数和一个增长概率p。通过两者结合的方式来决定一个节点的高度。用一份代码来解释的话srand(time(0));doublep0.25;intmax_level32;intlevel1;while(rand()RAND_MAX*plevelmax_level){level;}returnlevel;上面的p为增长概率即一个节点从一层开始有p*(1-p)的概率增长到两层p^2^*(1-p)的概率增长到三层以此类推。不难发现越高的节点产生的概率越低。同时我们还有max_level的限制使得层数不可能无限增加。由此我们也很容易算出当p为0.5时每个节点平均的层数是2当p为0.25是每个节点平均层数是1.33上面的增长概率和最大层数采取的是最新版本的Redis的取值老版本的Redis采取的最大层数是64四、跳表的实现structSkipListNode{intval;vectorSkipListNode*nextV;SkipListNode(intval,intlevel):val(val),nextV(level,nullptr){}};classSkiplist{public:usingNodeSkipListNode;Skiplist(){srand(time(0));_headnewNode(-1,1);}intrandomLevel(){intlevel1;while(rand()RAND_MAX*_plevel_maxLevel){level;}returnlevel;}//遍历的走法其实只有两种一种是往右走说明跳过了一段不会有结果的区间另一种是往下走说明结果有的话就在这次确定的区间不会出现在当前区间后面boolsearch(inttarget){Node*cur_head;intlevel_head-nextV.size()-1;while(level0){if(cur-nextV[level]cur-nextV[level]-valtarget){curcur-nextV[level];}elseif(cur-nextV[level]nullptr||cur-nextV[level]-valtarget){level--;}else{returntrue;}}returnfalse;}//无论插入还是删除除了完成新节点的构建之外还需要完成各层之间连接关系的调整这里所作的就是把新节点所有会链接的节点都跳出来后面直接根据层级去修改连接关系即可vectorNode*findPrev(intnum){intn_head-nextV.size();intleveln-1;vectorNode*prevV(n,_head);Node*cur_head;while(level0){if(cur-nextV[level]cur-nextV[level]-valnum){curcur-nextV[level];}elseif(cur-nextV[level]nullptr||cur-nextV[level]-valnum){prevV[level]cur;level--;}}returnprevV;}voidadd(intnum){vectorNode*prevVfindPrev(num);intlevelrandomLevel();if(_head-nextV.size()level){_head-nextV.resize(level,nullptr);prevV.resize(level,_head);//需要注意的是这里我们只是找出来可能需要改变连接的节点但是我们的新节点的高度并不一定需要改变所有这些节点的连接因为有可能比目前最高的节点要矮}Node*newNodenewNode(num,level);for(inti0;ilevel;i){newNode-nextV[i]prevV[i]-nextV[i];prevV[i]-nextV[i]newNode;}}boolerase(intnum){vectorNode*prevVfindPrev(num);if(prevV[0]-nextV[0]nullptr||prevV[0]-nextV[0]-val!num){returnfalse;}Node*delprevV[0]-nextV[0];for(inti0;idel-nextV.size();i){prevV[i]-nextV[i]del-nextV[i];}deletedel;inti_head-nextV.size()-1;while(i0){if(_head-nextV[i]nullptr){i--;}else{break;}}_head-nextV.resize(i1,nullptr);returntrue;}private:Node*_head;double_p0.25;int_maxLevel32;};五、跳表和平衡搜索树、哈希表的对比1. 与平衡搜索树对比实现更加简单跳表和红黑树、AVL树都能够做到遍历出有序结果但是跳表的实现相比红黑树、AVL树简单很多没有那么多旋转操作暂用的额外空间更少比如红黑树每个节点需要保存两个子节点指针、一个父节点指针、一个颜色而我们的跳表在增长概率为0.5时平均2个指针增长概率为0.25时平均1.33个指针2. 与红黑树相比虽然哈希表在数据冲突比较少时能做到O(1)的时间复杂度但是一旦数据多起来、哈希冲突多起来就需要借助红黑树来存储这就回到了第一种对比哈希表的空间利用率相对低。我们有一个平衡因子一般当占用的节点已经到达70%即平衡因子为0.7时就要扩容。一方面这意味着有30%以上的空间是不会被使用的另一方面扩容也会造成性能损失因为每个元素都需要重新定址哈希表不支持遍历而我们的跳表可以采取全部按照最低层遍历的方式完成全部遍历