skiplist的原理及简单实现

起因是因为问到了redis中sort_set的底层实现，OK我们当然知道是跳表了，首先我们看看skiplist的数据结构吧。

skiplistnode

这个我们可以看一下源码的底层结构设计是怎样的。

typedef struct zskiplistnode{
    //后退指针
    struct zskiplistnode *backward;

    //分值,用于排序用
    double score;

    //成员对象
    robj *obj;

    //层
    struct zskiplistLevel{
        //前进指针
        struct zskiplistnode *forward;

        //跨度，根据跨度可以确定自己的位置
        unsigned int span;
    }level[];
}zskiplistnode;

解释一个各个变量的作用，跳表是一种空间换时间的数据结构，层数越多，我们访问节点的速度就越快。

  1. 前进指针：用于从表头方向向表尾方向访问节点。
  2. 跨度：记录两个节点之间的距离，可以通过跨度确定节点的位置。
  3. 后退指针：用于从表尾方向向表头方向访问节点。
  4. 分值和成员：分值是用于排序的变量，成员一般是一个sds字符串。

以上就是skiplistnode的数据结构了，当然我们还有一个skiplist的数据结构

skiplist

typedef struct zskiplist{
    //指向头节点和尾节点，头节点通常是一个32层的节点，尾节点则是有数据的
    struct skiplistnode *head,*tail;
    //表中节点数量
    unsigned long length;
    //表中层数最大的节点的层数
    int level;

}zskiplist

skiplist简单实现

class Skiplist {
    Node head = new Node(null, null, 0);
    Random rand = new Random();
    Node[] stack = new Node[64];
    static class Node {
        int val;
        Node right, down;

        public Node(Node r, Node d, int val) {
            right = r;
            down = d;
            this.val = val;
        }
    }
}

skiplist的查找

我们如何进行查找的呢，一般是从最高层开始，向右向下进行查找，给出简单的实现。

    public boolean search(int target) {
        // 先往右再往下，缩小区间，套路都是这个套路
        for (Node p = head; p != null; p = p.down) {
            while (p.right != null && p.right.val < target) {
                p = p.right;
            }
            if (p.right != null && p.right.val == target) {
                return true;
            }
        }
        return false;
    }

skiplist的插入

插入的时候我们需要保存遍历的每个最右节点。保存之后然后回溯的插入节点，还需要根据幂次定律，即抛硬币的方式决定是否插入(代码中体现为rand.nextInt()&1)。如果说可以抛到最上层了，结束还可以再插入一层，那么我们需要创建新的一层。一般来说不超过32。

    public void add(int num) {
        int lv = -1;
        for (Node p = head; p != null; p = p.down) {
            while (p.right != null && p.right.val < num) {
                p = p.right;
            }
            stack[++lv] = p;
        }
        boolean insertUp = true;
        Node downNode = null;
        while (insertUp && lv >= 0) {
            Node insert = stack[lv--];
            insert.right = new Node(insert.right, downNode, num);
            downNode = insert.right;
            insertUp = (rand.nextInt() & 1) == 0;
        }
        if (insertUp) {
            head = new Node(new Node(null, downNode, num), head, 0);
        }
    }

skiplist的节点删除

删除方法较为简单，从最上面一层开始遍历即可，一层删除完了就遍历下一层。

    public boolean erase(int num) {
        boolean exists = false;
        for (Node p = head; p != null; p = p.down) {
            while (p.right != null && p.right.val < num) {
                p = p.right;
            }
            if (p.right != null && p.right.val <= num) {
                exists = true;
                p.right = p.right.right;
            }
        }
        return exists;
    }