跳表（skip list）

ゞ浴缸里的玫瑰 2022-11-11 14:59 134阅读 0赞

前面博文（[链表相关的][Link 1]）有提过，链表查询一个元素的时间复杂度是O(n)。数组根据下标查找的时间复杂度是O(1)，前面的文章也提到过二分查找算法对于元素查找的改变，但是二分查找算法的底层其实是依赖于数组的随机访问特性，但是对于数组，分配内存时，是需要连续的空间，有时候给数组分配内存时可能会引发频繁的GC。那既然二分查找算法查找性能那么高，但是底层使用数组对内存的要求很高，那可否使用链表来代替元素的存储，即如果元素底层是基于链表存储时能不能有相应效率的“二分查找算法”？

其实可以稍微对链表进行改造，就可以支持类似二分查找算法，把改造之后的数据结构叫 **跳表（Skip List）**

Redis中的有序集合（Sorted Set）其中一种实现就是依赖于跳表的。

普通的链表是下面这样的，当需要查询一个元素时，需要从前往后依次遍历，查询效率是很低的。

![20210321151716210.png][]其实这样的查询是很低效的，需要一个节点一个节点往后查询，那有没有什么办法，可以一次往后多走几个节点？  
就像一本技术书籍，当没有目录时，如果需要查找某一节的内容，需要一页一页的往后翻。如果页数很多时，查找的效率就会很低下。但是当有目录时查找效率就不一样了。比如通过目录可以很快的查找到数组相关的从 x 页开始，链表相关的从 y 页开始，二叉树相关的从 z 页开始。那当需要查找二叉树相关时，就可以直接根据目录跳转到 z 页开始，然后再依次往后查。当然我们还可以更加细分，如 二叉树 下，满二叉树从 z1 页开始，完全二叉树从 z2 页开始等等，查询的效率就更高了。

其实也可以对链表建立类似于书籍目录的索引，查询时根据索引很快的进行跳转，跳过中间的一个元素或者是多个元素的比较，如下图，建立一级索引。如果此时要查找元素7，我们可以通过一级索引，查找 2 4 6 三个元素，然后再到下一层找元素7，遍历的节点少了。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16][]

从上面这个例子，可以看出，加一层索引之后，查找元素时需要遍历的节点个数少了。也就是要查找的效率提高了，那如果我们再加一级索引，效率会不会提高呢？如下图所示。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 1][]建了两级索引之后，我们可以看到，查询元素 **7** 的路径图如下：可以看出，需要查询的元素少了

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 2][]  
上面说的这种数据结构其实就是跳表。

--------------------

代码实现和分析

1、索引最大可以有多少层？

首先看一下在redis中是怎么定义的，redis中的定义如下

#define ZSKIPLIST_MAXLEVEL 64 /* Should be enough for 2^64 elements */

此处定义为 ZSKIPLIST\_MAXLEVEL = 16

2、哪一些元素需要加入到索引层，需要加入到哪几层索引？  
上面画的图都假设每两个元素提一个元素到上一层，也就是原始数组中元素的个数是 N ，第一层数组中元素的个数为N/2。第二级索引中元素的个数为 N/2 \*1/2 = N/4。第三级索引依此类推，那这个如何实现，也就是加入一个元素时，如何确定该元素需要加入到哪些层级的索引。其实可以换一个角度想，当加入一个元素时，原始数组肯定是要加进入的，也就是100%的概率，需要加入到第一层索引的概率是 50%，需要加入到第三层索引的概率是25%。那可以实现一个这样的函数，用来生成需要加入的索引层级。下面看下redis中生成level的函数，代码如下：

#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */
    
    /* Returns a random level for the new skiplist node we are going to create.
     * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
     * (both inclusive), with a powerlaw-alike distribution where higher
     * levels are less likely to be returned. */
    int zslRandomLevel(void) {
        int level = 1;
        while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
            level += 1;
        return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
    }

redis中定义的ZKIPLIST\_P=0.25，其实原理是一样的。我们代码中定义为0.5。

下面看下代码实现，代码的框架大概如下。结合下面一张图可能更好理解Node节点中forwards数组的定义：

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

public class SkipList {
        private static final int ZSKIPLIST_MAXLEVEL = 16;
        private static final float ZSKIPLIST_P = 0.5f;
        private int levelCount = 1;
        //头结点
        private Node head = new Node(ZSKIPLIST_MAXLEVEL);
    
        public Node find(int value) {
            
        }
    
        /**
         * 插入节点
         *
         * @param value
         */
        public void insert(int value) {
            
        }
    
        /**
         * 删除给定的值
         *
         * @param value
         */
        public void delete(int value) {
            
        }
    
        public void printList() {
            for (int i = levelCount - 1; i >= 0; i--) {
                Node p = head;
                while (p.forwards[i] != null) {
                    System.out.print(p.forwards[i] + " -> ");
                    p = p.forwards[i];
                }
                System.out.println();
            }
        }
    
        private int randomLevel() {
            int level = 1;
            while (Math.random() < ZSKIPLIST_P && level < ZSKIPLIST_MAXLEVEL) {
                level += 1;
            }
            return level;
        }
    
        public class Node {
            private int data = -1;
            private Node forwards[];
            private int maxLevel = 0;
    
            public Node(int level) {
                this.maxLevel = level;
                forwards = new Node[level];
            }
        }
    }

看上面的代码框架其实就主要有三个方法：find insert delete，其实和单链表的查找，插入，删除是一个道理的。我们先看下单链表的插入：

如下单链表，需要在 2 和 4 之间插入元素 3（node\_3） ，其实实现逻辑比较简单，先找到待插入位置的前驱节点，此处前驱是元素 2（node\_2） 所在的节点。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 4][]先执行node\_3.next = node\_2.next，如下所示

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 5][]再执行node\_2.next = node\_3即可，如下所示

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 6][]

其实跳表也是类似的，只是现在跳表的前驱节点不是一个节点了，而是多个节点，比如如下图所示，现在需要在位置插入元素 3（level = 4）

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 7][]

插入后变为如下形式。从图中可以看出，其实前驱就比较好找了![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 8][]

delete 和 find与单链表是类似的，此处直接给出完整的代码

package com.Ycb.list;
    
    public class SkipList {
        private static final int ZSKIPLIST_MAXLEVEL = 16;
        private static final float ZSKIPLIST_P = 0.5f;
        private int levelCount = 1;
        //头结点
        private Node head = new Node(ZSKIPLIST_MAXLEVEL);
    
        public Node find(int value) {
            Node p = head;
            for (int i = levelCount - 1; i >= 0; i--) {
                while (p.forwards[i] != null && p.forwards[i].data < value) {
                    p = p.forwards[i];
                }
            }
            if (p.forwards[0] != null && p.forwards[0].data == value) {
                return p.forwards[0];
            }
            return null;
        }
    
        /**
         * 插入节点
         *
         * @param value
         */
        public void insert(int value) {
            //获得索引层级
            int level = randomLevel();
            //存储前驱节点
            Node[] update = new Node[level];
            //查找所有层级的前驱
            Node p = head;
            for (int i = level - 1; i >= 0; i--) {
                while (p.forwards[i] != null && p.forwards[i].data < value) {
                    p = p.forwards[i];
                }
                update[i] = p;
            }
            //已经存在
            if (p.forwards[0] != null && p.forwards[0].data == value) return;
    
            //创建新插入的节点
            Node newNode = new Node(level);
            newNode.data = value;
            newNode.maxLevel = level;
    
            //单链表的插入是一样的
            for (int i = 0; i < level; i++) {
                newNode.forwards[i] = update[i].forwards[i];
                update[i].forwards[i] = newNode;
            }
    
            if (level > levelCount) {
                levelCount = level;
            }
        }
    
        /**
         * 删除给定的值
         *
         * @param value
         */
        public void delete(int value) {
            Node[] update = new Node[levelCount];
            Node p = head;
            //查找前驱节点
            for (int i = levelCount - 1; i >= 0; i--) {
                while (p.forwards[i] != null && p.forwards[i].data < value) {
                    p = p.forwards[i];
                }
                update[i] = p;
            }
    
            //删除节点
            for (int i = 0; i < levelCount; i++) {
                if (update[i] != null && update[i].forwards[i] != null) {
                    update[i].forwards[i] = update[i].forwards[i].forwards[i];
                }
            }
        }
    
        public void printList() {
            for (int i = levelCount - 1; i >= 0; i--) {
                Node p = head;
                while (p.forwards[i] != null) {
                    System.out.print(p.forwards[i] + " -> ");
                    p = p.forwards[i];
                }
                System.out.println();
            }
        }
    
        private int randomLevel() {
            int level = 1;
            while (Math.random() < ZSKIPLIST_P && level < ZSKIPLIST_MAXLEVEL) {
                level += 1;
            }
            return level;
        }
    
        public class Node {
            private int data = -1;
            private Node forwards[];
            private int maxLevel = 0;
    
            public Node(int level) {
                this.maxLevel = level;
                forwards = new Node[level];
            }
    
            @Override
            public String toString() {
                StringBuilder builder = new StringBuilder();
                builder.append("{ data: ");
                builder.append(data);
                builder.append("; levels: ");
                builder.append(maxLevel);
                builder.append(" }");
    
                return builder.toString();
            }
        }
    }

但是当某一层的节点全部删除后，索引层级需要相应的缩减，此处后续再分析了，分析了再完善，

以上文章个人总结

参考文章：

[17 | 跳表：为什么Redis一定要用跳表来实现有序集合？-极客时间][17 _ _Redis_-]

[SkipList 浅析\_Just for Fun la-CSDN博客][SkipList _Just for Fun la-CSDN]

[Link 1]: https://blog.csdn.net/ycb1914845451/article/details/114106998
[20210321151716210.png]: /images/20221022/af3f1bf01c2a48b5970836922de21f22.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/65abb28b8b054749a9a7e11de2102706.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5paw6aOe5qKm,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/b50cb148451d41e1b36372fde8d099dd.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5paw6aOe5qKm,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/4f26aa748cea4e90aabf59fd1f4aed94.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5paw6aOe5qKm,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/9f6149b9c1fc45a69cd9e2a009047ad3.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5paw6aOe5qKm,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/917eedf92a35471087a867a18172a165.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5paw6aOe5qKm,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 5]: https://img-blog.csdnimg.cn/7559db24e7bc4e64b11c3742048f3b9e.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5paw6aOe5qKm,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 6]: https://img-blog.csdnimg.cn/092741343b7c4e08b9cf22a98ca4f9da.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5paw6aOe5qKm,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 7]: https://img-blog.csdnimg.cn/41438aed976d411da6b9efcb4c2da265.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5paw6aOe5qKm,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5paw6aOe5qKm_size_20_color_FFFFFF_t_70_g_se_x_16 8]: https://img-blog.csdnimg.cn/5a31bffc726645c78163ceac4a1505f1.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5paw6aOe5qKm,size_20,color_FFFFFF,t_70,g_se,x_16
[17 _ _Redis_-]: https://time.geekbang.org/column/article/42896
[SkipList _Just for Fun la-CSDN]: https://blog.csdn.net/kisimple/article/details/38706729