详解数据结构之跳表
目录
跳表的定义
跳表是由William Pugh(音译为威廉·普)发明的，最早出现于他在1990年发表的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》，跳表全称为跳跃列表，它允许快速查询，插入和删除一个有序连续元素的数据链表。
跳表的演化过程
对于单链表来说，即使数据是已经排好序的，想要查询其中的一个数据，只能从头开始遍历链表，这样效率很低，时间复杂度很高，是 O(n)，如下图所示。
那我们有没有什么办法来提高查询的效率呢？我们可以为链表建立一个“索引”，这样查找起来就会更快，如下图所示，我们在原始链表的基础上，每两个结点提取一个结点建立索引，我们把抽取出来的结点叫作索引层或者索引，down 表示指向原始链表节点的指针。
现在如果我们想查找一个数据，比如说 15，我们首先在索引层遍历，当我们遍历到索引层中值为 14 的结点时，我们发现下一个结点的值为 17，所以我们要找的 15 肯定在这两个结点之间。这时我们就通过 14 结点的 down 指针，回到原始链表，然后继续遍历，这个时候我们只需要再遍历两个结点，就能找到我们想要的数据。好我们从头看一下，整个过程我们一共遍历了 7 个结点就找到我们想要的值，如果没有建立索引层，而是用原始链表的话，我们需要遍历 10 个节点。
通过这个例子我们可以看出来，通过建立一个索引层，我们查找一个基点需要遍历的次数变少了，也就是查询的效率提高了。
那么如果我们给索引层再加一层索引呢？遍历的节点会不会更少呢，效率会不会更高呢？我们试试就知道了。
现在我们再来查找 15，我们从第二级索引开始，最后找到 15，一共遍历了 6 个节点，果然效率更高。
当然，因为我们举的这个例子数据量很小，所以效率提升的不是特别明显，如果数据量非常大的时候，我们多建立几层索引，效率提升的将会非常的明显，感兴趣的可以自己试一下，这里我们就不举例子了。
这种通过对链表加多级索引的机构，就是跳表了。
跳表的优化思路
实际上，按照上面生成链表的方式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似二分查找，使得查找的时间复杂度可以降低到O(log n)。但是这个结构在插入删除数据的时候有很大的问题，插入或者删除一个节点之后，就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度重新蜕化成O(n)。
skiplist的设计为了避免这种问题，做了一个大胆的处理，不再严格要求对应比例关系，而是
插入一个节点的时候随机出一个层数。这样每次插入和删除都不需要考虑其他节点的层数，
这样就好处理多了。细节过程如下图所示：
跳表如何保证效率
上面我们说到，skiplist插入一个节点时随机出一个层数，听起来怎么这么随意，如何保证搜索时
的效率呢？
这里首先要细节分析的是这个随机层数是怎么来的。一般跳表会设计一个最大层数maxLevel的限
制，其次会设置一个多增加一层的概率p。那么计算这个随机层数的伪代码如下图：
在Redis的skiplist实现中，这两个参数的取值为：
根据前面randomLevel()的伪码，我们很容易看出，产生越高的节点层数，概率越低。定量的分析
如下：
节点层数至少为1。而大于1的节点层数，满足一个概率分布。
节点层数恰好等于1的概率为1-p。
节点层数大于等于2的概率为p，而节点层数恰好等于2的概率为p(1-p)。
节点层数大于等于3的概率为p^2，而节点层数恰好等于3的概率为p^2*(1-p)。
节点层数大于等于4的概率为p^3，而节点层数恰好等于4的概率为p^3*(1-p)。
……
因此，一个节点的平均层数（也即包含的平均指针数目），计算如下：
现在很容易计算出：
当p=1/2时，每个节点所包含的平均指针数目为2；
当p=1/4时，每个节点所包含的平均指针数目为1.33。
跳表的时间复杂度
通过上边的例子我们知道，跳表的查询效率比链表高，那具体高多少呢？下面我们一起来看一下。
衡量一个算法的效率我们可以用时间复杂度，这里我们也用时间复杂度来比较一下链表和跳表。前面我们已经讲过了，链表的查询的时间复杂度为 O(n)，那跳表的呢？
如果一个链表有 n 个结点，如果每两个结点抽取出一个结点建立索引的话，那么第一级索引的节点数大约就是 n/2，第二级索引的结点数大约为 n/4，以此类推第 m 级索引的节点数大约为 n/(2^m)。
假如一共有 m 级索引，第 m 级的节点数为两个，通过上边我们找到的规律，那么得出 n/(2^m)=2，从而求得 m=log(n)-1。如果加上原始链表，那么整个跳表的高度就是 log(n)。我们在查询跳表的时候，如果每一层都需要遍历 k 个结点，那么最终的时间复杂度就为 O(k*log(n))。
那这个 k 值为多少呢，按照我们每两个结点提取一个基点建立索引的情况，我们每一级最多需要遍历两个个结点，所以 k=2。为什么每一层最多遍历两个节点呢？
因为我们是每两个结点提取一个结点建立索引，最高一级索引只有两个结点，然后下一层索引比上一层索引两个结点之间增加了一个结点，也就是上一层索引两结点的中值，看到这里是不是想起来我们前边讲过的二分查找，每次我们只需要判断要找的值在不在当前结点和下一个节点之间即可。
如上图所示，我们要查询红色结点，我们查询的路线即黄线表示出的路径查询，每一级最多遍历两个节点即可。
所以跳表的查询任意数据的时间复杂度为 O(2*log(n))，前边的常数 2 可以忽略，为 O(log(n))。
跳表的空间复杂度
跳表的效率比链表高了，但是跳表需要额外存储多级索引，所以需要的更多的内存空间。
跳表的空间复杂度分析并不难，如果一个链表有 n 个结点，如果每两个结点抽取出一个结点建立索引的话，那么第一级索引的节点数大约就是 n/2，第二级索引的结点数大约为 n/4，以此类推第 m 级索引的节点数大约为 n/(2^m)，我们可以看出来这是一个等比数列。
这几级索引的结点总和就是 n/2+n/4+n/8…+8+4+2=n-2，所以跳表的空间复杂度为 o(n)。
那么我们有没有办法减少索引所占的内存空间呢？可以的，我们可以每三个结点抽取一个索引，或者没五个结点抽取一个索引。这样索引节点的数量减少了，所占的空间也就少了。
总之，跳表的空间复杂度为 o(n)，跳表之所以比链表快，是因为跳表是以空间换时间。
跳表的查找
查找步骤：
从最高层开始，向右遍历。若当前节点的下一个节点值小于目标值，继续向右。如果当前节点的下一个节点值等于目标值，则返回。否则，向下降一层，重复上述步骤。直到在最底层找到目标或确认不存在。
跳表的插入
插入步骤：
查找插入位置并记录插入位置每一层前面的前驱节点：确定目标值在各层的插入位置并记录插入位置每一层前面的前驱节点。随机生成层数：通过抛硬币（随机算法）决定新节点的层数。插入节点：从底层到生成的最高层，逐层插入新节点并更新指针，若新插入节点的层数高于头节点的层数，则需要提高头结点的层数并更新对应指针。
跳表的删除
删除步骤：
查找目标节点并记录插入位置每一层前面的前驱节点：确定目标值在各层的位置并记录插入位置每一层前面的前驱节点。逐层删除：从要删除节点的最高层到底层，更新前驱节点的指针。释放内存：删除节点并回收空间。更新头结点的层数：若因为删除节点导致整体层数（除头结点外）下降，则需要降低头结点的层数。
跳表的模拟实现
struct SkiplistNode{ int _val; vector<SkiplistNode*> _nextV; SkiplistNode(int val,int level) :_val(val) ,_nextV(level,nullptr) {} }; class Skiplist { typedef SkiplistNode Node; public: Skiplist() { srand(time(0)); _head=new Node(-1,1); } bool search(int target) { Node* cur=_head; int level=_head->_nextV.size()-1; while(level>=0){ if(cur->_nextV[level] && cur->_nextV[level]->_val < target) cur=cur->_nextV[level]; else if(cur->_nextV[level]==nullptr || cur->_nextV[level]->_val > target) --level; else return true; } return false; } void add(int num) { vector<Node*> prevV=FindPrevNode(num); int n=RandomLevel(); Node* newNode=new Node(num,n); if(n>_head->_nextV.size()){ _head->_nextV.resize(n,nullptr); prevV.resize(n,_head); } for(size_t i=0;i<n;i++){ newNode->_nextV[i]=prevV[i]->_nextV[i]; prevV[i]->_nextV[i]=newNode; } } bool erase(int num) { vector<Node*> prevV=FindPrevNode(num); if(prevV[0]->_nextV[0]==nullptr || prevV[0]->_nextV[0]->_val!=num) return false; else{ Node* del=prevV[0]->_nextV[0]; for(size_t i=0;i<del->_nextV.size();i++){ prevV[i]->_nextV[i]=del->_nextV[i]; } delete del; int x=_head->_nextV.size()-1; while(x>=0){ if(_head->_nextV[x]==nullptr) --x; else break; } _head->_nextV.resize(x+1); return true; } } vector<Node*> FindPrevNode(int num){ Node* cur=_head; int level=_head->_nextV.size()-1; vector<Node*> prevV(level+1,_head); while(level>=0){ if(cur->_nextV[level] && cur->_nextV[level]->_val < num) cur=cur->_nextV[level]; else if(cur->_nextV[level]==nullptr || cur->_nextV[level]->_val >= num){ prevV[level]=cur; --level; } } return prevV; } int RandomLevel(){ size_t level=1; while(rand()<=RAND_MAX*_p && level<_maxLevel){ ++level; } return level; } private: Node* _head; int _maxLevel=32; double _p=0.25; };跳表与平衡搜索树及哈希表的对比
1. skiplist相比平衡搜索树(AVL树和红黑树)对比，都可以做到遍历数据有序，时间复杂度也差
不多。skiplist的优势是：a、skiplist实现简单，容易控制。平衡树增删查改遍历都更复杂。
b、skiplist的额外空间消耗更低。平衡树节点存储每个值有三叉链，平衡因子/颜色等消耗。
skiplist中p=1/2时，每个节点所包含的平均指针数目为2；skiplist中p=1/4时，每个节点所包
含的平均指针数目为1.33；
2. skiplist相比哈希表而言，就没有那么大的优势了。相比而言a、哈希表平均时间复杂度是
O(1)，比skiplist快。b、哈希表空间消耗略多一点。skiplist优势如下：a、遍历数据有序
b、skiplist空间消耗略小一点，哈希表存在链接指针和表空间消耗。c、哈希表扩容有性能损
耗。d、哈希表在极端场景下哈希冲突高，效率下降厉害，需要红黑树补足接力。
欢迎大家来访问我的博客主页--》博客主页链接
