【数据结构】跳表

你长大后想成为什么样的人？我难道不能成为我自己吗？

一、跳表是什么？

1. William Pugh在1990年发表了关于skiplist的论文，skiplist本质上也是一种查找结构，用于解决算法中的查找问题，这点几乎是所有数据结构的通性，无论哪个数据结构都离不开增删查改的操作，skiplist同样也是如此，skiplist与红黑树，AVL树的性能相差无几，对于查找的时间复杂度同样是O(logN)，所以skiplist是一个很高效的数据结构，同时他的实现相比AVL和红黑树要简单许多，所以skiplist在很多场景下备受青睐，例如在redis这样出名的nosql中也使用了skiplist，同时在某些大厂的面试笔试中，手写一个跳表也变得频繁起来，所以该数据结构很重要。

2. 跳表其实是从链表转换过来的，在原来的有序链表中，查找某一个关键字的效率是O(N)，因为需要从头结点开始一个一个结点遍历比较，那William Pugh大佬就想到，能否通过更改链表的结构来减少比较的次数呢？大佬决定将部分结点的层数升高，在查找时，先从最高层的结点之间开始比较，拿d图为例，假设我们要查找7，先和dummyHead所指向的下一个结点内的值进行比较，发现7<21，则降低到下一层进行比较，说明我们要查找的值，应该存在于dummyHead和21结点之间，降低到第三层后，发现7<9，则再次降低层数，说明我们要查找的值，应该存在于dummyHead和8结点之间，降低到第二层后，发现7>6，那此时就将cur指针从dummyHead迭代到6结点处，因为我们要查找的值不在6结点的前面，而应该在6结点的后面，所以cur要迭代，在6结点的第二层继续比较，发现7<9，那就说明要查找的结点在6结点和9结点之间，则继续降低层数，降到第一层，发现6的第一层指针指向的刚好就是7，则说明7查找成功。 在上面的查找过程中，通过更高层数之间的比较就可以立马排除掉一半的数，其实原理和二分查找非常的相似，在有序的集合中，通过和中间值的比较，立马就可以排除掉一半的数，在查找的过程中跳跃过了某些值，所以称为跳表，可以看到，如果跳表的层数越高，那么查找的效率也会越高，因为一次比较就跳跃了一半的数(对于最高层来说)。 虽然上面的方法可以让查找的效率变得很高，但是对于插入和删除来说会有问题，如果我们严格按照上层结点个数是下层的一半的话，则当某个结点插入或删除时，就需要重新修改被影响结点后面的一系列结点了，后面的节点需要被升高层数或降低层数，而操作的效率就会退化到O(N)，所以为了解决插入删除时，对上下层节点个数比例的影响，William Pugh大佬决定为跳表中的每个节点设置随机的层数，那在插入或删除时，只会影响每层前后的节点，而不会影响整个跳表，因为上下层节点的1:2比例关系我们干脆就不维护了，直接让层数变为随机的了。

在这里插入图片描述

3. 以下图为例，当插入17时，由17节点的层数是多少，那就会影响每层之前的节点，对于17节点的第二层来说，他只会影响他前面的9节点的第二层存储的内容，对于17节点的第一层来说，他只会影响他前面的12节点的第一层存储的内容。 通过将节点层数设置为随机值，就可以保证在插入或删除时，每一层只影响(被插入或删除节点)前面的一个节点，整体最多只影响被插入或删除节点的层数个数的节点。 （话说的太绕了，大家可以直接看图）

在这里插入图片描述

4. 虽然节点的层数是随机的，但其实他也不是任意给一个随机数就可以，William Pugh大佬给跳表设置了一个概率值，该概率表示每个节点以1层为基础，升高一层的概率，用p来表示，则每层的概率值如下。 可以看到，随着层数的增加，由于不断的累乘p，概率其实在一直减小，有人可能会担心skiplist的空间消耗过大，但其实通过节点层数的平均值，可以看到，当概率为0.5时，每个节点平均包含的指针数目也仅仅才为2，所以跳表的空间消耗并不算大。

在这里插入图片描述

二、跳表的效率如何保证？

1. 跳表的空间复杂度其实就是O(N)，因为每个节点内部平均包含的指针数目仅仅才为常数级，但跳表的时间复杂度其实是比较难计算的，在William Pugh大佬的论文里面，他通过回溯的思想，从底层向左和向上走，推导出了O(logN)的时间复杂度，我自己其实看了三篇文章关于时间复杂度的推导，一个是张铁蕾大佬，一个是leetcode官方题解的推导，还捎带看了一下原论文(借助翻译软件)，不幸的是我还是没看懂，数学很好的小伙伴可以自己试着推导一下。

原论文：Skip Lists: A Probabilistic Alternative to Balanced Trees

张铁蕾大佬的文章

2. 在时间复杂度这里，有一种较粗略的理解方式，既然层数增长是概率性的，那其实我们可以粗略的直接以概率来算出每层节点的个数，最高层节点个数趋近于1，那从最高层开始逐渐向下查找的过程，每次排除非目标的关键字，还是类似于二分查找的，下图的时间复杂度就约等于log以4为底N的对数。所以可以直接将时间复杂度看作为logN （实际上由于层数增长有概率，直接通过该概率来计算每层节点个数的方式在数学上肯定是不严谨的，但本人数学功底太差，只能用二分的查找思想来计算他的时间复杂度了，望见谅）

在这里插入图片描述

三、手写一个跳表

1206. 设计跳表

1. 在实现跳表的时候，一定要对照着图来实现，如果纯靠脑子，很容易把某些特殊情况给遗漏掉，至于图的话，就拿跳表论文里面的这个图就可以，这个图画的是最板正的。 SkipList( )：头结点的层数刚开始暂且设置为1，后面随着add结点，实时更改头结点的层数为跳表内所有结点的最高层数即可，同时别忘了随机数种子的设置，因为生成随机层数需要用到rand函数 search( )：搜索无非就是向下移动或者向右平移，当下一个节点的值小于target时，cur就应该向右平移，当下一个节点为空或者不为空但值大于target时，cur就应该向下减少一层，当下一个节点值等于target时，直接返回false即可。 具体实现时由于要访问下一个节点内部的val值，所以在if else分支语句判断时，一定要保证下一个节点是有效节点而不是nullptr，否则就会出现空指针访问的问题 add( )和erase( )：插入和删除操作的核心操作其实都是一样的，那就是找(被插入位置或被删除结点的)每层的前一个结点，只要找到了每层的前一个结点，那么剩下的插入和删除操作就变为了最基本的普通单向链表的操作了，那就是考察最基本的数据结构知识了。 在add这里，对于findPrev返回的pre数组，我们只需要遍历pre数组中我们所需要的就可以了，我们需要pre数组中多少个元素呢？其实就是newnode的层数，该层数的大小就对应着我们要遍历多少次pre数组。 在erase这里，如果被删除的元素不存在，会有两种情况，拿下图来说，如果删除的元素分别是10和30，那么pre[0]存储的分别就是9结点指针和nullptr，我们如何判断删除元素不存在呢？只要pre[0]指向的结点内的_nextPtrs数组的0索引位置内的值有效，同时该索引位置存储的结点指针指向的val值并不等于target(leetcode给的接口的参数叫num，我这里为了方便叫做target)，这种情况就对应的是删除10的情况，另一种情况就是pre[0]内的_nextPtrs数组的0索引位置内的值无效，也就是nullptr，这种情况就对应的是删除30元素的情况，这两种情况表示的就是删除失败返回false。 如果要删除的元素存在，则我们需要先拿到被删除元素的指针，只有拿到该指针后，我们才能确定被删除结点的层数，确定好该层数之后，就能够确定遍历多少次findPrev返回后的pre数组了（我是倒着遍历的，对应逻辑层面的图的话，其实就是从上向下依次更改每层的指针指向），进而该表指针指向，最后释放被删除元素的空间即可。（erase其实是实现起来最繁琐的，因为要多判断元素不存在的两种情况，实现代码时要多多注意这个地方） findPrev( )：寻找每层的前一个结点，思想其实就是从dummyHead的最高层位置让cur开始向右或向下不断的移动，pre数组中会存储整个跳表中num(被add或erase的结点)之前的，从第一层到最高层的前一个结点指针，这样实现其实是最方便的，add和erase调用完findPrev()之后，拿到满的pre数组后，只需要遍历自己需要的部分即可，但findPrev()填写pre数组时，是将所有层的前一个结点指针填进去了。其实我第一遍实现跳表时，并不是将所有层的前一个结点指针填到pre数组里面，而是按需来确定pre数组大小，例如add的newnode层数是多少，那我就开辟多大的pre数组，理想很美好，但现实很骨感，因为我们在遍历跳表时，一定是要从最高层向右下迭代的，你给pre数组按需分配空间，迭代的过程中，还需要判断到哪一层了，到达pre数组大小的层数之后，在开始填写pre，这样非常的麻烦，最好的实现方式就是直接pre数组开到最大层数，迭代的过程中填写好每一层的前一个结点。 具体实现上，什么时候需要填写pre数组呢？依旧拿下图为例，如果是add 17的话，如果17的层数恰好是最高层数4，那么从头结点开始迭代，17>6，cur跳到6结点的第四层，然后6结点的第四层存储的是nullptr，此时就说明6结点就是第四层，要插入结点17的前一个结点了，那就填写pre数组，填写过后，就要减少层数，跳到6结点的第三层，发现6结点的第三层指针不为空，同时下一个结点的val值25>17，那就说明当前cur结点，也就是6结点依旧是第三层，要插入的17结点的前一个结点，其实第三层和第四层就涵盖了填写pre数组的两种情况了，即当下一个结点指针为空，或者不为空但值大于等于target时(等于时，对于add来说就是相同val值的结点插入在已有结点的前面，对于erase来说就是删除target目标结点)，则当前结点cur即为该层的前一个指针，如果下一个结点指针不为空但值小于target时，那就将cur向右平移一个结点位置即可。 randomLevel( )：这里实现的很巧，借助了RAND_MAX，只要rand()生成的随机数落到了RAND_MAX的前P概率部分，那就将level增1，这就实现了P概率的层数增加。

在这里插入图片描述

在这里插入图片描述

四、跳表与其他数据结构的对比

1. 跳表与AVL树，红黑树相比，在时间复杂度上两者都非常的优秀，同时也都能够做到遍历数据有序，但跳表的空间复杂度更优秀一些，平衡树的每个结点都会存储3个指针，同时还有平衡因子/颜色的空间消耗，拿redis中的跳表为例，在p为0.25的情况下，每个跳表结点内的平均指针数目仅为1.33，所以在空间消耗上，跳表会优秀一些。 站在程序员实现数据结构的角度来讲，平衡树的插入删除和跳表的插入删除来比，平衡树实现的难度还是比较大的，同时也不好控制，而skiplist的增删查改相对来说较容易控制很多。

2. 跳表与哈希表相比，在时间复杂度上来说，哈希表会更优秀，因为他的时间复杂度是O(1)，所以在时间复杂度上跳表的优势并不明显，但跳表可以做到遍历数据有序，而哈希表却做不到这一点。在空间上，skiplist会略优秀一些，因为哈希表会有表空间的消耗，而跳表只需要链接结点即可。同时当哈希冲突较大时，扩容会有性能损耗，因为需要重新对原来存储的数据做一遍哈希映射，如果不扩容，一直哈希冲突的话，哈希表的查找效率就会下降的厉害，需要红黑树来补足接力。 （例如在linux内核中，当哈希表中某一个哈希桶中的链表长度超过阈值时，该哈希桶中的链表就会转换为红黑树，以此来提供更快的查找和插入操作）