跳表简介？

skiplist本质上是一种查找结构，用于解决算法中的查找问题，跟平衡搜索树和哈希表的价值是一样的，可以作为key或者key/value的查找模型。

跳表由来

skiplist是由美国计算机科学家William Pugh于1989年发明，skiplist，顾名思义，首先它是一个list。实际上，它是在有序链表的基础上发展起来的。我们知道在对一个有序链表进行查找，它的时间复杂度为O(N)。

William Pugh开始了他的优化思路:

● 假如我们每相邻两个节点升高一层，增加一个指针，让指针指向下下个节点，如下图所示:

这样新增的一层指针通过连接可以形成新的链表，它包含了整个链表节点的一半，由此需要在这一层进行比较、筛除的个数也就降低了一半。

以此类推，继续增加一层指针，新链表的节点数下降，查找的效率自然而然也就提高了。按照上述每增加一层，节点数就少一半，其查找的过程类似于二分查找，使得查找的时间复杂度可以降低到O(LogN)。

当然上述查找的前提是一个有序的链表。无论你是对其中的链表新增节点，还是删除节点，都可能打乱原有维持的指针连接，从而导致跳表失效。。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度重新蜕化成O(n)。

● 随机层数: 为了避免这种情况，skiplist的设计不再严格要求对应比例关系，而是，插入一个节点的时候随机出一个层数。这样每次插入和删除都不需要考虑其他节点的层数。

skiplist如何保证效率？

那么skiplist在引入随机层数后，如何保证其查找效率呢？首先，这个随机层数会有一个限制，这里把它叫做maxlevel，其次会设置一个多增加一层的概率p。那么计算这个随机层数的伪代码如下图:

我们最终可以得到这样一个数学式，用于计算一个节点的平均层数:

有了这个公式，我们可以很容易计算出:

当 p = 1/2 时: 每个节点所包含的平均指针数目为2。

当 p = 1/4 时: 每个节点所包含的平均指针数目为1.33。

至于跳表的平均时间复杂度为O(logN)，这个推导的过程较为复杂，愚钝的我也就不在此摆弄文墨，下面的两篇中英文章可以给你提供你要的答案:
铁蕾大佬的博客：http://zhangtielei.com/posts/blog-redis-skiplist.html.

William_Pugh大佬的论文: http://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf.

跳表实现:

leetcode上有一道实现跳表的题，你可以在这上面完成跳表的测试： https://leetcode.cn/problems/design-skiplist/
当然讲了这么多，还是没具体说说到底跳表是如何进行查找的，所以我们要实现的第一个函数接口就是跳表元素查找:

skipList初始化:

// 跳表不仅仅是要存储数据 _data
// 还需要有next指针，当然这些next指针也不止一个
// 这取决于 当前节点的层数
typedef struct SkiplistNode
{int _val;                       // 节点值vector<SkiplistNode*> _nextV;   // 节点连接的其他表项SkiplistNode(int val, int level):_val(val), _nextV(level, nullptr){}
}Node;class Skiplist {
public:Skiplist() {// 初始化 _headList// 默认给一层_head = new SkiplistNode(-1, 1);}
private:Node* _head;                // 头节点double _prate = 0.25;       // 新增层概率int _MaxLevel;              // 最大层数
};

Search:

    bool search(int target) {// 1.从头节点查Node* cur = _head;// 记录的层数// 0~n-1的下标int level = _head->_nextV.size() - 1;while (level >= 0){// target 大于 下一个节点的val cur向右移动if (cur->_nextV[level] && target > cur->_nextV[level]->_val){cur = cur->_nextV[level];}                           // 因为支持数据冗余 所以如果出现一样的就把新节点插在它后面即可else if(cur->_nextV[level]==nullptr || target < cur->_nextV[level]->_val){// target 小于 下一个节点的val --level || next节点为空--level;}else{// 找到了return true;}}return false;}

Add:

    vector<Node*> FindPath(int num){// 从头节点查起Node* cur = _head;int level = _head->_nextV.size()-1;// 开和level一样的大小vector<Node*> prevV(level+1,_head);while (level >= 0){if (cur->_nextV[level] && num > cur->_nextV[level]->_val){// 只管移动cur = cur->_nextV[level];} // 因为支持数据冗余 所以如果出现一样的就把新节点插在它后面即可else if (cur->_nextV[level] == nullptr || num <= cur->_nextV[level]->_val){// 记录该层num的前一个节点prevV[level] = cur;// 向下更新--level;}}return prevV;}int RandomLevel(){int level = 1;while (rand() <= _prate * RAND_MAX && level < _MaxLevel){++level;}return level;}void add(int num){// 前驱节点vector<Node*> prevV = FindPath(num);// 创建节点int n = RandomLevel();Node* newnode = new Node(num, n);// 可能创建节点层数 > _headif (n > _head->_nextV.size()){// 进行扩容_head->_nextV.resize(n,nullptr);// prevV也许跟着扩容// 这里的新增前驱节点为什么初始化为 _head?// 新增节点一定是连接在 prevV里的节点之后的prevV.resize(n, _head);}// 前后连接节点for (int i = 0;i < n;++i){// 可以理解为：newnode->next = prev->next->nextnewnode->_nextV[i] = prevV[i]->_nextV[i];prevV[i]->_nextV[i] = newnode; // 连接回来}}

这里的randomLevel()是以一种巧妙的方式完成的:

通过p可以控制最终值产生范围的概率。

不过，C++有专门的随机数生成的库，比这个rand功能更加强大,所以我们可以将那个RandomLevel()改成这样:

    int RandomLevel(){// 随机数种子static static std::default_random_engine generator(std::chrono::system_clock::now().time_since_epoch().count());// 生成随机数范围static std::uniform_real_distribution<double> distribution(0.0,1.0);size_t level = 1;while (distribution(generator) <= _prate && level < _MaxLevel){++level;}return level;}

Erase:

    bool erase(int num){vector<Node*> prevV = FindPath(num);// 这里可能找不到if (prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num) return false;// 我们根据prevV的最底层节点 就可以找到del节点Node* del = prevV[0]->_nextV[0];// 根据该节点的层数 更新prevV 和 nextV// 进行连接for (int i = 0;i < del->_nextV.size();++i){prevV[i]->_nextV[i] = del->_nextV[i];}// 删除节点// 这里记录levelint level = del->_nextV.size();delete del;// 如果删除的节点是 最高层呢？ 并且是唯一呢？// 这种优化可以不做 但你也可以做// 就是重新定义_head的高度// 向下遍历 只要遇到不为空的最高 就breakint i = _head->_nextV.size() - 1; while (i >= 0){if (_head->_nextV[i] == nullptr){--i;}else{break;}}_head->_nextV.resize(i + 1);return true;}