数据结构：跳表讲解

1.什么是跳表-skiplist

1.1简介

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

skiplist是由William Pugh发明的，最早出现于他在1990年发表的论文《Skip Lists: A
Probabilistic Alternative to Balanced Trees》。

skiplist，顾名思义，首先它是一个list。实际上，它是在有序链表的基础上发展起来的。如果是一个有序的链表，查找数据的时间复杂度是O(N)。

1.2设计思路

（1）假如我们每相邻两个节点升高一层，增加一个指针，让指针指向下下个节点，如下图所示。这样所有新增加的指针连成了一个新的链表，但它包含的节点个数只有原来的一半。由于新增加的指针，我们不再需要与链表中每个节点逐个进行比较了，需要比较的节点数大概只有原来的一半（后面讲为什么）。

这样设计利于查找，查找规则为：

1. cur表示当前节点，nextV为节点指针数组，j表示下标，key为要查找的值。 其中cur一开始为哨兵节点，j为顶部下标。
2. 从cur位置向右看，如果key大于右边，就直接向右走，即更新cur为右节点
   (即cur = cur->nextV[j])。
3. 如果key小于右边或者右边为空，直接向下走，即让j减一。
4. 右边等于key找到。
5. 不存在的情况，j最后会走到-1（看后面图解）。

查找存在的情况：

查找不存在的情况：

（2）以此类推，我们可以在第二层新产生的链表上，继续为每相邻的两个节点升高一层，增加一个指针，从而产生第三层链表。如下图，这样搜索效率就进一步提高了。

（3）skiplist正是受这种多层链表的想法的启发而设计出来的。实际上，按照上面生成链表的方式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似二分查找，使得查找的时间复杂度可以降低到O(log n)。但是这个结构在插入删除数据的时候有很大的问题，插入或者删除一个节点之后，就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度重新退化成O(n)。


（4）skiplist的设计为了避免这种问题，做了一个大胆的处理，不再严格要求对应比例关系，而是插入一个节点的时候随机出一个层数。这样每次插入和删除都不需要考虑其他节点的层数，这样就好处理多了。细节过程入下图（插入和删除过程后面详细讲，现在只需知道随机层数一样可行）：

2.跳表的效率分析

上面我们说到，skiplist插入一个节点时随机出一个层数，听起来怎么这么随意，如何保证搜索时的效率呢？

这里首先要细节分析的是这个随机层数是怎么来的。一般跳表会设计一个最大层数maxLevel的限制，其次会设置一个多增加一层的概率p。那么计算这个随机层数的代码如下：

int RandomLevel()
{
     int level = 1;
     //RAND_MAX为rand函数可生成的最大值
     //即rand()落到[0, RAND_MAX * _p]的概率为_p
     while(rand() < RAND_MAX * _p)
     {
         level++;
     }
     return level;
 }
1
2
3
4
5
6
7
8
9
10
11

根据前面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。
• p越大，平均层数越多，时间效率就越快，但太大可能导致空间浪费，故一般都会限制最大层数。

跳表的平均时间复杂度为O(logN)，我会用图解来帮助大家理解大概，但完整推导的过程较为复杂，需要有一定的数学功底，有兴趣的同学，可以参考以下文章中的讲解：

铁蕾大佬的博客：Redis内部数据结构详解(6)——skiplist

3.跳表实现

本文跳表实现以本题为准：设计跳表

3.1类成员设计

//跳表节点
struct SkiplistNode
{
    SkiplistNode(int val, int level)
    {
        _val = val;
       _nextV.resize(level, nullptr); 
    }
    int _val;  //节点值
    vector<SkiplistNode*> _nextV;  //指针数组
};

//跳表
class Skiplist {
public:
    typedef SkiplistNode Node;
    Skiplist() {
        srand(time(0));  //设置随机数种子
        _head = new Node(-1, 1);
    }
    
    double _p = 0.25;  //增加层数的概率
    int _maxLevel = 32;  //限制最大层数
    Node* _head;  //哨兵头节点，存储的是无效数据
    //头节点从一层开始，后面生成了更高层数节点在扩容，减少不必要的查询工作
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

3.2查找

参照设计思路里面讲的即可

bool search(int target) 
{
    int level = _head->_nextV.size() - 1;  //下标从顶部开始
    Node* cur = _head;  //从哨兵位开始
    while(level >= 0)
    {
        //大于，跳到下个节点
        //小于或者空，向下走
        if(cur->_nextV[level] && cur->_nextV[level]->_val < target)  
        {
            cur = cur->_nextV[level];
        }
        else if(!cur->_nextV[level] || cur->_nextV[level]->_val > target)  
        {
            level--;
        }
        else  //找到了
        {
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3.3插入

思路很简单，假设当前插入节点有x层，只需要找到这x层每一层对应的前置节点，然后做简单的链接工作即可。

//找前置节点
vector<SkiplistNode*> GetPrev(int num)
{
    //核心是找到每一层的前置节点
    //本题允许冗余
    int level = _head->_nextV.size() - 1;
    vector<SkiplistNode*> prevV(level + 1, nullptr);
    Node* cur = _head;
    while(level >= 0)
    {
        //大于，跳到下个节点
        //小于或者空，向下走
        if(cur->_nextV[level] && cur->_nextV[level]->_val < num)  
        {
            cur = cur->_nextV[level];
        }
        else  
        {
            prevV[level] = cur;
            level--;
        }
    }
    return prevV;
}

//插入节点
void add(int num) {
    vector<SkiplistNode*> prevV = GetPrev(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(int i = 0; i < n; i++)
    {
        newnode->_nextV[i] = prevV[i]->_nextV[i];
        prevV[i]->_nextV[i] = newnode;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

3.4删除

删除大体分两种情况：

1. 存在该节点，思路与插入类似，假设当前删除节点有x层，只需要找到这x层每一层对应的前置节点，然后做简单的链接工作即可。
2. 不存在该节点，那找前置节点的时候第0层的右边要么是空，要么就不是目标值。

删除还有个可优化的点，不做也不影响正确性：

bool erase(int num) {
  vector<SkiplistNode*> prevV = GetPrev(num);
    //随机生成至少有一层节点
    if(prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num)  //不存在
    {
        return false;
    }
    else 
    {
        //记录待删除的节点
        SkiplistNode* del = prevV[0]->_nextV[0];
        for(int i = 0; i < del->_nextV.size(); i++)
        {
            prevV[i]->_nextV[i] = del->_nextV[i];
        }
        delete del;
        //这里不影响正确性，对头节点的多余空间做处理
        int j = _head->_nextV.size() - 1;
        while(j >= 0)
        {
            if(_head->_nextV[j] == nullptr)
            {
                j--;
            }
            else
            {
                break;
            }
        }
        _head->_nextV.resize(j + 1);
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

3.5完整代码

struct SkiplistNode
{
    SkiplistNode(int val, int level)
    {
        _val = val;
       _nextV.resize(level, nullptr); 
    }
    int _val;
    vector<SkiplistNode*> _nextV;
};

class Skiplist {
public:
    typedef SkiplistNode Node;
    Skiplist() {
        srand(time(0));
        _head = new Node(-1, 1);
    }
    
    bool search(int target) {
        int level = _head->_nextV.size() - 1;
        Node* cur = _head;
        while(level >= 0)
        {
            //大于，跳到下个节点
            //小于或者空，向下走
            if(cur->_nextV[level] && cur->_nextV[level]->_val < target)  
            {
                cur = cur->_nextV[level];
            }
            else if(!cur->_nextV[level] || cur->_nextV[level]->_val > target)  
            {
                level--;
            }
            else  //找到了
            {
                return true;
            }
        }
        return false;
    }

    vector<SkiplistNode*> GetPrev(int num)
    {
        //核心是找到每一层的前置节点
        //本题允许冗余
        int level = _head->_nextV.size() - 1;
        vector<SkiplistNode*> prevV(level + 1, nullptr);
        Node* cur = _head;
        while(level >= 0)
        {
            //大于，跳到下个节点
            //小于或者空，向下走
            if(cur->_nextV[level] && cur->_nextV[level]->_val < num)  
            {
                cur = cur->_nextV[level];
            }
            else  
            {
                prevV[level] = cur;
                level--;
            }
        }
        return prevV;
    }
    
    void add(int num) {
        vector<SkiplistNode*> prevV = GetPrev(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(int i = 0; i < n; i++)
        {
            newnode->_nextV[i] = prevV[i]->_nextV[i];
            prevV[i]->_nextV[i] = newnode;
        }
    }
    
    bool erase(int num) {
        vector<SkiplistNode*> prevV = GetPrev(num);
        //随机生成至少有一层节点
        if(prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num)  //不存在
        {
            return false;
        }
        else 
        {
            //记录待删除的节点
            SkiplistNode* del = prevV[0]->_nextV[0];
            for(int i = 0; i < del->_nextV.size(); i++)
            {
                prevV[i]->_nextV[i] = del->_nextV[i];
            }
            delete del;
            //这里不影响正确性，对头节点的多余空间做处理
            int j = _head->_nextV.size() - 1;
            while(j >= 0)
            {
                if(_head->_nextV[j] == nullptr)
                {
                    j--;
                }
                else
                {
                    break;
                }
            }
            _head->_nextV.resize(j + 1);
            return true;
        }
    }

    int RandomLevel()
    {
        int level = 1;
        while(rand() < RAND_MAX * _p)
        {
            level++;
        }
        return level;
    }
    double _p = 0.25;
    int _maxLevel = 32;
    Node* _head;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

4.skiplist跟平衡搜索树和哈希表的对比

1. skiplist相比平衡搜索树(AVL树和红黑树)对比，都可以做到遍历数据有序，时间复杂度也差不多。
   skiplist的优势是：
   a、skiplist实现简单，容易控制。平衡树增删查改遍历都更复杂。
   b、skiplist的额外空间消耗更低。平衡树节点存储每个值有三叉链，平衡因子/颜色等消耗。skiplist中p=1/2时，每个节点所包含的平均指针数目为2；skiplist中p=1/4时，每个节点所包含的平均指针数目为1.33；
2. skiplist相比哈希表而言，就没有那么大的优势了哈希表平均时间复杂度是O(1)，比skiplist快。。
   skiplist优势如下：
   a、遍历数据有序b、skiplist空间消耗略小一点，哈希表存在链接指针和表空间消耗。
   b、哈希表扩容有性能损耗。
   c、哈希表再极端场景下哈希冲突高，效率下降厉害，需要红黑树补足接力，实现复杂。