跳表

1.跳表的概念

跳表是基于有序链表扩展实现的。对于一个普通的有序链表，我们查找数据的时间复杂度是O(N)。而跳表的出现，让当前结点可能有能力跳过多个结点，以此来减少不必要的查找与比较，从而提高效率，跳表的时间复杂度是O(logN)。

跳表的发展过程:

假设我们让每相邻的两个结点升高一层，增加一个指针，让该指针指向下下个节点，如下图b中所示。这样所有新增加的指针又形成了一个新的链表(不同层级的)，它包含的结点数目是原来的一般。因此在进行数据查找的时候，我们不需要与链表重的每个结点进行比较了，需要比较的结点数目变为了原来的一半(大约)。
我们可以在2层链表的基础上进行进一步的扩展，让每相邻的两个结点(都是2层链表的结点)升高一层，增加一个指针，从而产生三层链表，如下图c中所示。这样搜索效率进一步提高了。

跳表的这个提高链表层级的思路非常类似于二分查找，这使得它的查找时间复杂度可以降低到O(logN)，因为每提高一层，搜索的效率就会提高一些。

但是这个结构在插入或删除数据的时候是存在很大缺陷的，插入或删除数据后，会打乱相邻两层链表上结点个数的严格的比例关系(2:1关系)，因此如果要进行调整的话，也必须要把后面的所有结点都重新调整，这样会使时间复杂度退化为O(N)。

为了避免上述的问题，Skiplist在设计的时候不再要求严格的按照比例关系了。它要求在插入一个结点的时候，随机出一个层数。这样每次插入和删除的时候不需要再考虑其它结点的层数了。下图就是使用随机层数后的插入过程。

2.Skiplist在插入时采用随机层数的方法是如何保证效率的呢?

在此之前，我们先来了解一下Skiplist是如何实现随机层数的方法吧!

实现随机层数的方法:

在Redis的Skiplist的实现中，参数maxLevel和p的取值如下:

maxLevel = 32
p = 0.25

maxLevel表示最大层数，p表示每多一层的概率。

设当前层数level=1
产生层数为1的概率为(1 - p), 产生大于1层的概率为p。
产生层数为2的概率为p * (1 - p)，产生大于2层的概率为p^2。
产生层数为3的概率为p^2 * (1 - p)，产生大于3层的概率为p^3。
产生层数为4的概率为p^3 * (1 - p)，产生大于4层的概率为p^4。
…
产生层数为n的概率为p^(n-1) * (1 - p)，产生大于n层的概率为p^n。

一个结点的平均层数(即，每个结点包含的平均指针数目)，计算如下:

当p = 0.25时,每个结点的平均层数为1.33层。(每个结点包含的平均指针个数为1.33)
当p = 0.5时, 每个节点的平均层数为2层。 (每个节点包含的平均指针个数为2)

3.跳表的模拟实现

struct SkiplistNode{int val;vector<SkiplistNode*> nextV;SkiplistNode(int num, int level):val(num),nextV(level, nullptr){}
};class Skiplist {
public:Skiplist() :head(new SkiplistNode(-1, 1))  //头结点处我们初始化它是1层的(其实也可以直接拉到32层maxLevel,不过性能略有损耗){srand(time(nullptr));   //生成随机数种子}bool search(int target) {SkiplistNode* cur = head;int level = cur->nextV.size() - 1;  //层数的下标//当level小于0时退出循环while(level >= 0){//1. 当前结点的下一个为nullptr 或 下一个的值 > target, 此时向下走if(cur->nextV[level] == nullptr || cur->nextV[level]->val > target){--level;}//2. 当前结点的下一个不为nullptr && 下一个的值 < target, 此时向右走else if(cur->nextV[level]->val < target){cur = cur->nextV[level];}//3. 下一个的值 == targetelse{return true;}}return false;}//找prevV, add和erase均需要用vector<SkiplistNode*> findPrevVector(int target){SkiplistNode* cur = head;int level = cur->nextV.size() - 1;  //下面使用的都是下标, 所以这里作-1处理vector<SkiplistNode*> prevV(level + 1, head); //这里的prevV数组中, "i下标处存储的是第i+1层"的前一个节点//这里prevV默认初始化必须为head, 因为SkipList为空时, 插入的前一个节点一定是headwhile(level >= 0){//1. 当下一个为nullptr 或 下一个的值 >= target, 此时向下走。(这里考虑允许数据冗余了)if(cur->nextV[level] == nullptr || cur->nextV[level]->val >= target){prevV[level] = cur; //prevV[level]存的是cur!!!--level;}else{//2. 当下一个不为nullptr && 下一个的值 < targetcur = cur->nextV[level];}}return prevV;}void add(int num) {int level = randomLevel();  //随机生成层数if(level > head->nextV.size()){ //判断是否需要更新头结点的层数head->nextV.resize(level, nullptr);}vector<SkiplistNode*> prevV = findPrevVector(num);SkiplistNode* newNode = new SkiplistNode(num, level);//更新连接关系for(size_t i = 0; i < level; ++i){newNode->nextV[i] = prevV[i]->nextV[i]; //prevV[i]: i下标就是第i+1层的前一个结点prevV[i]->nextV[i] = newNode;}}bool erase(int num) {vector<SkiplistNode*> prevV = findPrevVector(num);//先判断num值是否存在. 判断prevV[0]的下一个是否为nullptr, 以及下一个值是否为num//这里必须使用0下标, 其它下标的层数可能不存在if(prevV[0]->nextV[0] == nullptr || prevV[0]->nextV[0]->val != num){return false;}else{//删除, 并更新连接关系SkiplistNode* delNode = prevV[0]->nextV[0];for(size_t i = 0; i < delNode->nextV.size(); ++i){prevV[i]->nextV[i] = delNode->nextV[i];}delete delNode;//判断是否需要更新头结点nextV的大小(无关紧要)size_t i = head->nextV.size() - 1;for(; i >= 0; --i){if(head->nextV[i] != nullptr)break;}head->nextV.resize(i + 1);return true;}}int randomLevel(){int level = 1;//rand()的概率是[0, RAND_MAX], 我们这里限定rand() < RAND_MAX * p, 这个概率正好为pwhile(rand() <= RAND_MAX * p && level < maxLevel){++level;}return level;}private:SkiplistNode* head;size_t maxLevel = 32;double p = 0.25;
};

4.跳表VS平衡搜索树和哈希表

跳表本质是一种搜索结构，它根平衡搜索树和哈希表是同一领域的，它同时支持key或key/value的搜索模型。

Skiplist相比平衡搜索树(AVL、红黑树)，遍历数据时都可以做到有序输出，时间复杂度也差不多。
Skiplist的优势:
a. Skiplist的实现更简单，容易控制; 平衡搜索树的增删查改都较为复杂。
b. Skiplist的额外空间消耗更低，Skiplist在p=0.25时，每个结点包含的指针数目为1.33; 而平衡搜索树每个结点都是一个三叉链(存储3个指针)，并且还需要额外存储平衡因子/颜色属性。
Skiplist相比哈希表就没什么优势了。哈希表的时间复杂度为O(1), 要比Skiplist快一些，但是Skiplist的空间消耗要少一些。
Skiplist的优势:
a. 遍历数据有序。
b. Skiplist空间消耗少一些，哈希表存在表空间的消耗以及每个下标处挂的链表的指针消耗。
c. 哈希表扩容时有性能损耗。
d. 哈希表在极端场景下(哈希冲突高)，效率会大幅度下降，此时需要使用红黑树来补救。