详解数据结构之跳表

跳表的定义

跳表是由 William Pugh(音译为威廉·普) 发明的，最早出现于他在 1990 年发表的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。跳表全称为跳跃列表，它允许快速查询、插入和删除一个有序连续元素的数据链表。

跳表的演化过程

对于单链表来说，即使数据是已经排好序的，想要查询其中的一个数据，只能从头开始遍历链表，这样效率很低，时间复杂度很高，是 O(n)。

为了提高查询的效率，我们可以为链表建立一个'索引'。在原始链表的基础上，每两个结点提取一个结点建立索引，我们把抽取出来的结点叫作索引层或者索引，down 表示指向原始链表节点的指针。

例如查找 15，首先在索引层遍历，当遍历到值为 14 的结点时，发现下一个结点的值为 17，则目标值在这两个结点之间。通过 14 结点的 down 指针回到原始链表继续遍历，只需再遍历两个结点即可找到数据。整个过程比原始链表少遍历了节点。

如果给索引层再加一层索引，效率会更高。这种通过对链表加多级索引的结构，就是跳表。

跳表的优化思路

按照上述生成链表的方式，每一层链表的节点个数是下面一层的节点个数的一半，查找过程类似二分查找，时间复杂度可降低到 O(log n)。但在插入或删除数据时，会打乱上下相邻两层链表上节点个数的严格对应关系。如果要维持这种关系，必须重新调整后续所有节点，导致时间复杂度蜕化成 O(n)。

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

跳表如何保证效率

Skiplist 插入节点时随机出层数，一般跳表会设计一个最大层数 maxLevel 的限制，其次会设置多增加一层的概率 p。计算随机层数的逻辑如下：

在 Redis 的 skiplist 实现中，这两个参数的取值为：

产生越高的节点层数，概率越低。定量分析如下：

节点层数至少为 1。而大于 1 的节点层数，满足一个概率分布。

节点层数恰好等于 1 的概率为 1-p。

节点层数大于等于 2 的概率为 p，而节点层数恰好等于 2 的概率为 p(1-p)。

节点层数大于等于 3 的概率为 p^2，而节点层数恰好等于 3 的概率为 p^2*(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+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. 哈希表在极端场景下哈希冲突高，效率下降厉害，需要红黑树补足接力。