一、什么是跳表

skiplist本质上也是一种查找结构，用于解决算法中的查找问题，跟平衡搜索树和哈希表的价值是
一样的，可以作为key或者key/value的查找模型。那么相比而言它的优势是什么的呢？这么等我
们学习完它的细节实现，我们再来对比。

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

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

William Pugh开始的优化思路：

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

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

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

查找的过程：假如要查找的值是key，那么需要看下一个节点的值是否比key大，如果比key大，就向下走。如果比key小，就向右走。如果没有找到，就会走到第-1层。

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

二、跳表的效率如何保证？

上面我们说到，skiplist插入一个节点时随机出一个层数，听起来怎么这么随意，如何保证搜索时的效率呢？
这里首先要细节分析的是这个随机层数是怎么来的。一般跳表会设计一个最大层数maxLevel的限制，其次会设置一个多增加一层的概率p。那么计算这个随机层数的伪代码如下图：

在 Redis 的 skiplist 实现中，这两个参数的取值为：p = 1/4 和 maxLevel = 32。注：谷歌的开源项目 LevelDB（小型的 KV 型数据库）也采用了 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(logN)，这个推导的过程比较复杂，这里我们稍微提一下。

三、skiplist的实现

结点的设计

struct SkiplistNode
{
   
   
    int _val;
    vector<SkiplistNode*> _nextV;

    SkiplistNode(int val, int level)
        :_val(val)
        , _nextV(level, nullptr)
    {
   
   }
};

因为每个结点的层数是随机的，所以申请一个新节点需要知道其层数和存储的值，通过vector的下标可以表示层数。

整体设计

class Skiplist {
   
   
    typedef SkiplistNode Node;
public:
    Skiplist() {
   
   
        srand(time(0));

        // 头节点，层数是1
        _head = new SkiplistNode(-1, 1);
    }

private:
    Node* _head; // 哨兵位头节点
    size_t _maxLevel = 32; // 最高的层数
    double _p = 0.25; // 增加一层的概率
};

哨兵位头节点的层数是该跳表中最高的，初始时让哨兵位的层数为1.增加一层的概率是0.25，理论而言，概率越大，效率越高。

节点的随机层数

计算这个随机层数的伪代码如下图：

C语言产生随机数

int RandomLevel()
{
   
   
    size_t level = 1;
    // rand() ->[0, RAND_MAX]之间
    // rand() 《= RAND_MAX*_p 可以保证增加一层的概率是_p
    // level <= maxLevel 保证随机层数不超过最高层数maxLevel
    while (rand() <= RAND_MAX*_p && level < _maxLevel)
    {
   
   
        ++level;
    }
    return level;
}

C++产生随机数

int RandomLevel()
{
   
   
    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) <= _p && level < _maxLevel)
    {
   
   
        ++level;
    }

    return level;
}

这里我们需要注意的是：因为C语言产生的随机数范围是0到32767之间的数，范围比较小。不过可以通过加减一些数来扩大随机数的范围。

skiplist的查找

查找的过程:查找是要和下一个节点的值相比，并不是和当前节点的值相比一开始cur在哨兵位头节点的最高层 head，开始进行比较。假如要查找的值为target，如果下一个节点为空或者下一个节点的值比target大，那么cur需要向下一层走;如果下一个节点的值比target下，那么cur向右走。重复上述过程，直至找到或者没找到(没找到的话，cur会去到第-1层，注:层数是从第0层开始的)

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;
}

skiplist的插入

无论是插入值还是删除值，都需要找到该值的前面的节点，这样才能修改指针的指向关系。我们可以将这个保存前一个指针的操作封装成一个函数，提供给插入和删除接口使用。

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)
        {
   
   
            // 更新level层前一个
            prevV[level] = cur;

            // 向下走
            --level;
        }
    }

    return prevV;
}

void add(int num) {
   
   
    vector<Node*> prevV = FindPrevNode(num);

    int n = RandomLevel();
    Node* newnode = new Node(num, n);

    // 如果n超过当前最大的层数，那就升高一下_head的层数
    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);

    // 第一层下一个不是val，val不在表中
    if (prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num)
    {
   
   
        return false;
    }
    else
    {
   
   
        Node* del = prevV[0]->_nextV[0];
        // del节点每一层的前后指针链接起来
        for (size_t i = 0; i < del->_nextV.size(); i++)
        {
   
   
            prevV[i]->_nextV[i] = del->_nextV[i];
        }
        delete del;

        // 如果删除最高层节点，把头节点的层数也降一下
        int i = _head->_nextV.size() - 1;
        while (i >= 0)
        {
   
   
            if (_head->_nextV[i] == nullptr)
                --i;
            else
                break;
        }
        _head->_nextV.resize(i + 1);

        return true;
}

注意：如果删除的节点的层数是最高的，那么可以将哨兵位头结点的层数降一降。如何判断删除的节点层数是不是最高的呢？从哨兵位头结点的最高层其，如果该层的指针指向空，那么就说明删除的节点层数最高。当前层指针指向空，那么就需要看下一层指针是否指向空。以此类推，直至指针不在指向空，那么就可以求出删除最高节点后剩余节点的最高层数了。

打印跳表

void Print()
{
   
   
    Node* cur = _head;
    while (cur)
    {
   
   
        printf("%2d\n", cur->_val);
        // 打印每个每个cur节点
        for (auto e : cur->_nextV)
        {
   
   
            printf("%2s", "↓");
        }    
        printf("\n");

        cur = cur->_nextV[0];
    }
}

打印跳表函数可以让我们更好的观察跳表的样子。

完整代码

#include <iostream>
#include <vector>
#include <time.h>
#include <random>
#include <chrono>
using namespace std;

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));

        // 头节点，层数是1
        _head = new SkiplistNode(-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;
    }

    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)
            {
   
   
                // 更新level层前一个
                prevV[level] = cur;

                // 向下走
                --level;
            }
        }

        return prevV;
    }

    void add(int num) {
   
   
        vector<Node*> prevV = FindPrevNode(num);

        int n = RandomLevel();
        Node* newnode = new Node(num, n);

        // 如果n超过当前最大的层数，那就升高一下_head的层数
        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);

        // 第一层下一个不是val，val不在表中
        if (prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num)
        {
   
   
            return false;
        }
        else
        {
   
   
            Node* del = prevV[0]->_nextV[0];
            // del节点每一层的前后指针链接起来
            for (size_t i = 0; i < del->_nextV.size(); i++)
            {
   
   
                prevV[i]->_nextV[i] = del->_nextV[i];
            }
            delete del;

            // 如果删除最高层节点，把头节点的层数也降一下
            int i = _head->_nextV.size() - 1;
            while (i >= 0)
            {
   
   
                if (_head->_nextV[i] == nullptr)
                    --i;
                else
                    break;
            }
            _head->_nextV.resize(i + 1);

            return true;
        }


    }

    //int RandomLevel()
    //{
   
   
    //    size_t level = 1;
    //    // rand() ->[0, RAND_MAX]之间
    //    while (rand() <= RAND_MAX*_p && level < _maxLevel)
    //    {
   
   
    //        ++level;
    //    }

    //    return level;
    //}

    int RandomLevel()
    {
   
   
        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) <= _p && level < _maxLevel)
        {
   
   
            ++level;
        }

        return level;
    }

    void Print()
    {
   
   
        /*int level = _head->_nextV.size();
        for (int i = level - 1; i >= 0; --i)
        {
            Node* cur = _head;
            while (cur)
            {
                printf("%d->", cur->_val);
                cur = cur->_nextV[i];
            }
            printf("\n");
        }*/

        Node* cur = _head;
        while (cur)
        {
   
   
            printf("%2d\n", cur->_val);
            // 打印每个每个cur节点
            for (auto e : cur->_nextV)
            {
   
   
                printf("%2s", "↓");
            }    
            printf("\n");

            cur = cur->_nextV[0];
        }
    }

private:
    Node* _head;
    size_t _maxLevel = 32;
    double _p = 0.5;
};

四、skiplist跟平衡搜索树和哈希表的对比

skiplist 相比平衡搜索树(AVL 树和红黑树)对比，都可以做到遍历数据有序，时间复杂度也差不多。skiplist 的优势是：a、skiplist 实现简单，容易控制。平衡树增删查改遍历都更复杂。b、skiplist 的额外空间消耗更低。平衡树节点存储每个值有三叉链，平衡因子或者颜色等消耗。skiplist 中 p = 1 / 2 时，每个节点所包含的平均指针数目为 2；skiplist 中 p = 1 / 4 时，每个节点所包含的平均指针数目为 1.33；

skiplist 相比哈希表而言，就没有那么大的优势了。相比而言，a、哈希表平均时间复杂度是 O(1)，比 skiplist快。b、哈希表空间消耗略多一点。skiplist 优势如下：a、遍历数据有序。b、skiplist 空间消耗略小一点，哈希表存在链接指针和表空间消耗。c、哈希表扩容有性能损耗。d、哈希表在极端场景下哈希冲突高，效率下降厉害，需要红黑树补足接力。

【高阶数据结构】跳表

一、什么是跳表

二、跳表的效率如何保证？

三、skiplist的实现

四、skiplist跟平衡搜索树和哈希表的对比

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

【高阶数据结构】跳表

一、什么是跳表

二、跳表的效率如何保证？

三、skiplist的实现

四、skiplist跟平衡搜索树和哈希表的对比

热门文章

最新文章

相关课程

相关电子书