SkipList原理及实现

跳表（skiplist）是一个查询/插入/删除 复杂度o(lgn)的数据结构。在查询上跟平衡树的复杂度一致，因此是替代平衡树的方案。 在 redis 的zset，leveldb都有应用 。发现这个算法也解决了我一个问题。各种平衡树在工业界是广泛应用，帮助我们快速查找，插入数据，但其思想的复杂也让大家不是那么容易接触。当时想直接对有序链表进行二分搜索，那岂不是很容易做到相同复杂度且容易理解，不过链表并不能像数组随机访问，只能从头一个个遍历。跳表为节点设置了快速访问的指针，不同在一个个遍历，可以跨越节点进行访问，这也是跳表的名字的含义。

上面就是跳表的引子，下图就是它的数据结构

1.2 跳表如何构建

当插入一个数据时，随机获得这个节点的高度，没错，就是随机！每涨一层的概率为p，这个认为设置，一般为0.25或者0.5,这样层数越高的节点就越少（这种结构跟平衡树有点像）。

1.3 如何搜索

如上图所示，我们检索19这个值，遍历路径如下图所示

可以看到高层级的节点相当于一个快速通道，让搜索进行了节点的跳跃，而不是一个个的遍历。

2.编码实现

基于 java 我实现了一个具有增删查的跳表: github.com/yangzhenkun…

2.1 搜索

搜索实现按照上面的思路，从顶层往下遍历，每层之间就是普通链表遍历。

public T get(Integer key) {

    SkipNode cur = head;

    for (int l = maxLevel - 1; l >= 0; l--) {

        if (cur.forward[l] == null) {
            continue;
        }

        while (cur.forward[l] != null && key > cur.forward[l].key) {
            cur = cur.forward[l];
        }

        if (cur.forward[l] != null && key == cur.forward[l].key) {
            return (T) cur.forward[l].value;
        }
    }
    return null;
}
复制代码

2.2 插入

插入的思路是要找到插入的点，并且在遍历的同时，记录下需要更新层数 快速通道指针的地方，在最后进行处理。

例如插入17，并且在17节点随机获得层数是2.这样节点9的第2层（从下往上数）需要指向新的节点17，12的第1层也要指向17。可以看出需要更新的就是每一层最后遍历过的节点。

public boolean set(int key, T value) {
        SkipNode newNode = initNode(key, value);
        int newNodeMaxLevel = newNode.forward.length;
        SkipNode cur = head;
        SkipNode[] update = new SkipNode[newNodeMaxLevel];//记录更新的节点

        /**
         * 遍历找到插入的节点，并记录下需要更新层指针的节点
         */
        for (int l = maxLevel - 1; l >= 0; l--) {

            if (cur.forward[l] == null) {
                if (l < newNodeMaxLevel) {
                    update[l] = cur;
                }
                continue;
            }

            while (cur.forward[l] != null && key > cur.forward[l].key) {
                cur = cur.forward[l];
            }

            if (cur.forward[l] != null && key == cur.forward[l].key) {
                return false;
            }
            if (l < newNodeMaxLevel) {
                update[l] = cur;
            }
        }
        /**
         * 执行插入更新操作
         */
        for (int l = newNodeMaxLevel - 1; l >= 0; l--) {
            newNode.forward[l] = update[l].forward[l];
            update[l].forward[l] = newNode;
        }


        return true;
    }
复制代码

2.3 删除

对get和set方法了解后，删除方法的实现已经没有理解的压力了。同理需要记录下搜索的过程中每一层最后遍历的节点。在找到删除节点后，把每一层中指向删除节点的 指针指向被删除节点每层的后续指针。

public boolean remove(int key) {
        SkipNode cur = head;
        SkipNode[] update = new SkipNode[maxLevel];//因为不知道被删除的节点有几层，所以需要把全部的层数记录下来
        SkipNode delete = null;

        /**
         * 遍历找到要删除的节点，并记录下需要更新层指针的节点
         */
        for (int l = maxLevel - 1; l >= 0; l--) {

            if (cur.forward[l] == null) {
                continue;
            }

            while (cur.forward[l] != null && key > cur.forward[l].key) {
                cur = cur.forward[l];
            }

            if (cur.forward[l] != null && key == cur.forward[l].key) {
                delete = cur.forward[l];
                update[l] = cur;
            }

        }
        if (delete == null) {
            return false;
        }

        /**
         * 更新指针
         */
        for (int l = delete.forward.length - 1; l >= 0; l--) {
            update[l].forward[l] = delete.forward[l];
            delete.forward[l] = null;//help gc
        }

        return true;
    }
复制代码

3.原理证明

3.1 最大层级证明

把最底层的链表叫做level0，最大层数包括最底层

在数据结构小节中已经说到最大层级为

MaxLevel  =\log_\frac{1}{p} n
复制代码

证明方式论文也提到

文中一开始也提到一种情况，16个节点，level1可能是9个，level2 3个，level3 3个，level14 1个。如果我们从第14层开始搜索，有很多无效的工作，因为顶层太过稀疏。文中提到最顶层应该是1/p个节点。

很容易得到每一层的节点数

L(k)=n*p^{k-1}
复制代码

这样就能推导出

1/p = n*p^{k-1}

n=(1/p)^{k}

k=log_\frac{1}{p} n
复制代码

这样就得到了最大层数

3.2复杂度证明

文中也对查找的复杂度进行了证明，我截取了部分图，可以去原文查看

这里利用递推的思想来进行了证明。

文中基于搜索路径回溯的方式进行了证明，往上和左进行遍历。假设当前位置在第i层，要访问的值为x，i到x之间的层数是k层。用c(k)表式遍历k层访问到x的步数。在回溯的任何一个节点的移动中，都入下图所示。当我们处于情况a的时候，我们下一步一定是情况b或者c。 情况c的概率为什么是p呢？因为基于当前层，下一层有该节点的概率为p。那么情况b自然就是1-p。 这样就得出递推公式

C(k)=(1-p)(1+C(k))+p(1+C(k-1))

同时C(0)=0

便可归纳出 搜索k层需要的步数为: c(k)=k/p

我们一次遍历最大层数上面已经推导出，带入步数公式得到一次搜索的步数

c=\frac{1}{p}log_\frac{1}{p} n

复制代码

因为p是概率常数，一般为1/4或者1/2，这样复杂度就是O(lgn)级

文中数据结构的截图也是来自论文。 论文地址（请在PC端访问）： ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

PS:文中公式在本地显示正常