深夜学算法之SkipList：让链表飞

2022-10-03 23:05:58

1. 前言

上次写Python操作LevelDB时提到过，有机会要实现下SkipList。摘录下wiki介绍：

跳跃列表是一种随机化数据结构，基于并联的链表，其效率可比拟二叉查找树。

我们知道对于有序链表，查找的时间复杂度为O(n)，尽管真正的插入与删除操作节点复杂度只有O(1)，但都需要先查找到节点的位置，可以说是查找拉低了有序链表的性能。

简单地讲，SkipList采用“空间换时间”的思想，除了原始链表外还保存一些“跳跃”的链表，达到加速查找的效果。

我的实现：https://github.com/liquidconv/DSAF

2. 感性认识SkipList

bottom-up与top-down，我个人倾向后者。所以在给出SkipList里具体定义与算法前，先从问题出发，研究一下SkipList的设计思路。

来看一个有序链表(这里H表示链表头部，T表示链表尾部，不是有效节点)：

 
深夜学算法之SkipList：让链表飞
1.png

假设我们要查找7，只能老老实实地按照1->2->3->…的顺序走，忍受O(n)的效率；但如果是数组的话，可以使用二分查找达到O(lgn)。

可以在链表中使用二分查找吗？

不可以，因为二分查找需要用到中间位置的节点，而链表不能随机访问。

——那么就把中间位置的节点单独保存吧。

 
深夜学算法之SkipList：让链表飞
2.png

原来的链表写成了三个链表，记从下到上的编号为0、1、2，可以发现0号链表就是原始链表，1号链表是原始链表四等分点，2号链表是原始链表的二等分点。

我们再来查找7，初始搜索范围为(H, T)：

  1. 在2号链表中与4比较，7>4，更新搜索范围为(4, T)
  2. 在1号链表中与6比较，7>6，更新搜索范围为(6, T)
  3. 在0号链表中与7比较，7=7，查找成功。

形象化地说，SkipList就是额外保存了二分查找的中间信息。不过SkipList中含有随机化，生成的结构不会像上面那样完美，来看实际生成的一个SkipList：

 
深夜学算法之SkipList：让链表飞
3.png

之后会详细讨论随机化的问题，现在先承上启下地梳理下信息：

  • SkipList结合了链表和二分查找的思想
  • 将原始链表和一些通过“跳跃”生成的链表组成层
  • 第0层是原始链表，越上层“跳跃”的步距越大，链表元素越少
  • 上层链表是下层链表的子序列
  • 查找时从顶层向下，不断缩小搜索范围

最后，可以利用“链”的性质，减少存储空间：

 
深夜学算法之SkipList：让链表飞
4.png

3. 实现SkipList

这里写的SkipList是非常naive的，有许多可优化之处。

3.1 定义

首先定义SkipList中的节点：

typedef struct SkipListNode {

    int key;

    void *data;

    int level;

    SkipListNode **next_nodes;

} SkipListNode;

key是键，data是值，与标准链表中的节点一样；区别在“链”的部分，level表示节点在第几层中，next_nodes是每层上的后继节点——比如上面那个例子里的节点4，在第2层是T，在第1层是6，在第0层是5。

然后来定义SkipList：

class SkipList {

    public:

        SkipList(int max_level);

        ~SkipList(void);

        void insertNode(int key, void *data);

        void deleteNode(int key);

        void *getData(int key);

        void displayList(void);

    private:

        int MAX_LEVEL;

        int RandomLevel(void);

        SkipListNode *head;

        SkipListNode *tail;

};

接口的含义还是很清楚的。构造SkipList时给定最大层数(其实是可以让层数动态增长的)，displayList用于打印整个SkipList。

这里假设key是不重复的，所以insertNode实现了插入与修改，deleteNode实现了删除，getData实现了查找。

3.2 构造与析构

首先来看构造函数SkipList(int max_level)：

SkipList::SkipList(int max_level) {

    MAX_LEVEL = max_level > 0? max_level : 1;

    head = new SkipListNode;

    tail = new SkipListNode;

    head->next_nodes = new SkipListNode *[MAX_LEVEL];

    for(int i = 0; i < MAX_LEVEL; ++i)

        head->next_nodes[i] = tail;

}

首先确定SkipList的最大层数MAX_LEVEL，然后生成head与tail节点，head节点显然必须是一个MAX_LEVEL层的节点，让head在每一层上的后继节点都是tail。

用图片来表示SkipLsit(3)的话，就是：

 
深夜学算法之SkipList：让链表飞
5.png

析构函数~SkipList(void)也很简单：

SkipList::~SkipList(void) {

    SkipListNode *curr = nullptr;

    while(head->next_nodes[0] != tail) {

        curr = head->next_nodes[0];

        head->next_nodes[0] = curr->next_nodes[0];

        delete curr->next_nodes;

        delete curr;

    }

    delete head->next_nodes;

    delete head;

    delete tail;

}

第0层的链表是原始链表，上层链表的节点都来自第0层，所以可以利用这个性质，沿着第0层链表释放节点，注意除了释放SkipListNode还要释放里面的next_nodes。

3.3 插入、删除与查找

SkipList的插入、删除与查找一脉相承，理解插入后删除与查找都很简单。但在给出插入算法的代码前，先让我们想想insertNode里需要做哪些工作：

  • 标准有序链表插入前需要定位，通常是确定新节点的前驱节点；SkipList中一个节点至多是MAX_LEVEL层的，需要插入到MAX_LEVEL个有序链表里，所以要确定每层的前驱节点
  • 构造新节点，生成小于MAX_LEVEL的随机数k，作为新节点的层数
  • 将新节点插入到第0层到第(k-1)层的链表中

概括起来还是三步走：找前驱，做节点，插入链表。

第一步，找前驱：

    SkipListNode *update[MAX_LEVEL];

    SkipListNode *curr = head;

    for(int i = MAX_LEVEL - 1; i >= 0; --i) {

        if(curr->next_nodes[i] == tail || curr->next_nodes[i]->key > key)

            update[i] = curr;

        else {

            while(curr->next_nodes[i] != tail && curr->next_nodes[i]->key < key)

                curr = curr->next_nodes[i];

            update[i] = curr;

        }

    }

update是前驱节点数组，curr用来迭代，初始值为head。for循环的大结构是自顶向下遍历每层，找到该层上新节点的前驱节点。

重点在于if-else结构，我们来看第i层。curr只有后继节点不是tail，而且curr第i层后继节点的key比新节点key小的时候才会更新，所以curr满足性质：

curr的后继节点是tail，或者curr->key比key小。

假如curr的后继节点是tail，或者curr的key比新节点的key小，curr的后继节点比新节点的key大的话，新节点的插入位置都正好在curr后面，也就是curr是新节点在第i层的前驱节点。

否则就需要在第i层链表上向后移动curr，直到curr的后继节点是tail，或者curr的后继节点的key大于新节点的key，也就是回到之前的情形。

假设要在下面的SkipList里插入5，来看update数组的计算过程：

 
深夜学算法之SkipList：让链表飞
6.png

  1. i = 2
    curr进入循环时为head，第1层后继节点为curr->next_nodes[2]
    curr->next_nodes[2]不是tail，而且key = 4 < 5
    进入else部分，更新curr为4号节点
    update[2] = 4号节点

  2. i = 1，搜索范围为(4, tail)
    curr进入循环时为4号节点，第1层后继节点为curr->next_nodes[1]
    curr->next_nodes[1]不是tail但key = 6 > 5
    进入if部分，不更新curr
    update[1] = 4号节点

  3. i = 0，搜索范围为(4, 6)
    curr进入循环时为4号节点，后继节点为6号节点
    进入if部分，不更新curr
    update[0] = 4号节点

继续之前搜索范围的说法，搜索的过程可以看做搜索范围（curr, curr->next_nodes[i]）的收紧。初始时为(head, tail)，每层的while循环里收紧下界，curr递增，在逐层下降的for循环里收紧上界，curr->next_nodes[i]递减。

这里为了清晰删除了保证key不重复的代码，后面有完整版。

第二步，做节点

    int level = RandomLevel();

    SkipListNode *temp = new SkipListNode;

    temp->key = key;

    temp->data = data;

    temp->level = level;

    temp->next_nodes = new SkipListNode *[level + 1];

内容非常简单，RandomLevel()之后讨论随机化时再说，总之就是产生一个0到MAX_LEVEL - 1之间的随机数。唯一的坑就是生成next_nodes是要用（level+1）而不是level，考虑level = 0的情形就明白了。

第三步，插入链表

    for(int i = 0; i <= level; ++i) {

        temp->next_nodes[i] = update[i]->next_nodes[i];

        update[i]->next_nodes[i] = temp;

    }

来看完整的insertNode(int key, void *data):

void SkipList::insertNode(int key, void *data) {

    SkipListNode *update[MAX_LEVEL];

    SkipListNode *curr = head;

    // 寻找每一层上待插入节点之前的节点

    for(int i = MAX_LEVEL - 1; i >= 0; --i) {

        if(curr->next_nodes[i] == tail || curr->next_nodes[i]->key > key)

            update[i] = curr;

        else {

            while(curr->next_nodes[i] != tail && curr->next_nodes[i]->key < key)

                curr = curr->next_nodes[i];

            if(curr->next_nodes[i] != tail && curr->next_nodes[i]->key == key) {

                curr->next_nodes[i]->data = data;

                return;

            }

            update[i] = curr;

        }

    }

    // 生成待插入节点

    int level = RandomLevel();

    SkipListNode *temp = new SkipListNode;

    temp->key = key;

    temp->data = data;

    temp->level = level;

    temp->next_nodes = new SkipListNode *[level + 1];

    // 在每层上的链表中插入节点

    for(int i = 0; i <= level; ++i) {

        temp->next_nodes[i] = update[i]->next_nodes[i];

        update[i]->next_nodes[i] = temp;

    }

}

删除与插入完全是对称的，直接来看代码：

void SkipList::deleteNode(int key) {

    SkipListNode *update[MAX_LEVEL];

    SkipListNode *curr = head;

    // 寻找每一层上待删除节点之前的节点

    for(int i = MAX_LEVEL - 1; i >= 0; --i) {

        if(curr->next_nodes[i] == tail || curr->next_nodes[i]->key > key)

            update[i] = nullptr;

        else {

            while(curr->next_nodes[i] != tail && curr->next_nodes[i]->key < key)

                curr = curr->next_nodes[i];

            if(curr->next_nodes[i] != tail && curr->next_nodes[i]->key == key)

                update[i] = curr;

            else

                update[i] = nullptr;

        }

    }

    SkipListNode *temp = nullptr;

    // 在每层上的链表中删除节点

    for(int i = 0; i < MAX_LEVEL; ++i) {

        if(update[i]) {

            temp = update[i]->next_nodes[i];

            update[i]->next_nodes[i] = temp->next_nodes[i];

        }

    }

    // 最终释放节点

    if(temp) {

        delete temp->next_nodes;

        delete temp;

    }

}

同样先查找前驱数组，由于节点不一定在某层中出现，找不到时就把前驱节点标记为nullptr，在该节点出现的层的链表里删除该节点，最终释放节点。

查找就更加简单了，从上到下遍历，找到就返回：

void *SkipList::getData(int key) {

    SkipListNode* curr =  head;

    for(int i = MAX_LEVEL - 1; i >= 0; --i) {

        if(curr->next_nodes[i] == tail || curr->next_nodes[i]->key > key)

            continue;

        else {

            while(curr->next_nodes[i] != tail && curr->next_nodes[i]->key < key)

                curr = curr->next_nodes[i];

            if(curr->next_nodes[i] != tail && curr->next_nodes[i]->key == key)

                return curr->next_nodes[i]->data;

        }

    }

    return nullptr;

}

3.4 随机化

SkipList是一种概率算法，非常依赖于生成的随机数。这里不能用rand() % MAX_LEVEL的简单做法，而要用满足p=1/2几何分布的随机数。

来看RandomLevel()的代码：

int SkipList::RandomLevel(void) {

    int level = 0;

    while(rand() % 2 && level < MAX_LEVEL - 1)

        ++level;

    return level;

}

这里不做太多的数学分析，只做直观解释。考虑MAX_LEVEL = 4的情形，可能的返回值为0、1、2、3，显然出现概率分别为：

P(0) = (1/2)^0 * (1/2) = 1/2
P(1) = (1/2)^1 * (1/2) = 1/4
P(2) = (1/2)^2 * (1/2) = 1/8
P(3) = 1 - P(0) - P(1) - P(2) = 1/8

假设有16个元素的话，可以预计第0层有16个元素，第1层约有16 - 8 = 8个元素，第2层约有16 - 8 - 4 = 4个元素，第3层约有16 - 8 -4 -2 = 2个元素，从底向上每层元素数量大约减少一半。

SkipList层数合适时自顶向下搜索，理想情况下每下降一层，搜索范围减小一半，达到类似二分查找的效果，效率为O(lgn)；最坏情况下也只是curr从head移动到tail，效率为O(n)。

我的实现里最大层数是通过MAX_LEVEL静态指定的，也可以让最大层数动态增长——RandomLevel里不设置最大值，插入节点时得到的level比当前SkipList层数大时就在顶上再加一层，删除节点时如果只有这个节点在高层就去掉高层。

4. 参考资料

 
上一篇：关于Java中常用加密/解密方法的实现


下一篇：2018SDIBT_国庆个人第五场