页面加载中...

手写一个跳表

| 算法与数据结构 | 0 条评论 | 640浏览

跳表简述

一开始认识到跳表（Skiplist）这个数据结构时，是在redis中，redis的set底层使用跳表数据结构来实现。

跳表本质上其实就是一个链表，只不过在链表之上，为其加入了一层索引，索引同样还是链表，因此，在索引之上，还可以再加入索引，如此往复，直到加入了足够多层的索引。比如redis中索引层最大为32。

用一个动图来描述：

https://blog.abreaking.com/upload/2021/02/qnmcpainreih1raiq2798fj4fq.gif

就就这样，当我们要找链表中某个值时，就可以自顶向下比较每层索引，直到找到为止。因此，它的查找复杂度同平衡二叉树一样，都是O(logN)。

跳表的更多描述，可见这篇文章：Redis内部数据结构详解(6)——skiplist

跳表实现

跳表实现的主要难度在于插入(add)算法。只要把add方法搞明白之后，一切都迎刃而解了。

关于跳表的插入，一张图即可描述出来， https://blog.abreaking.com/upload/2021/02/5h6hegbvikglto95k71f6aqbaj.png

图片来自 http://zhangtielei.com/posts/blog-redis-skiplist.html

通过这张图，可以先确定跳表中每个节点的数据结构：

class Node{
    Integer value; //节点值
    Node[] next; // 节点在不同层的下一个节点

    public Node(Integer value,int size) { // 用size表示当前节点在跳表中索引几层
        this.value = value;
        this.next = new Node[size];
    }
}

然后就需要考虑：我插入一个节点Node，它到底应该是索引到第几层呢？

一开始我还想着如何准确的维护上一层是下一层的1/2，发现越想越复杂；然后通过相关资料，发现人家早就给出一个解决方案：随机出来一个层数。

这里有一个疑惑：就凭随机出来的一个层数，能保证查询与插入性能吗？

在分析之前，我们还需要着重指出的是，执行插入操作时计算随机数的过程，是一个很关键的过程，它对skiplist的统计特性有着很重要的影响。这并不是一个普通的服从均匀分布的随机数，它的计算过程如下： 首先，每个节点肯定都有第1层指针（每个节点都在第1层链表里）。 如果一个节点有第i层(i>=1)指针（即节点已经在第1层到第i层链表中），那么它有第(i+1)层指针的概率为p。 节点最大的层数不允许超过一个最大值，记为MaxLevel。 这个计算随机层数的伪码如下所示：

int randomLevel()
    int level = 1;
    while (Math.random()<p && level<MaxLevel){
        level ++ ;
    }
    return level;

randomLevel()的伪码中包含两个参数，一个是p，一个是MaxLevel。在Redis的skiplist实现中，这两个参数的取值为：

p = 1/4
MaxLevel = 32

from : http://zhangtielei.com/posts/blog-redis-skiplist.html

知道了层数，这下就好办了。思路如下：

  1. 先随机出来一个层数，new要插入的节点，先叫做插入节点newNode；

  2. 根据跳表实际的总层数从上往下分析，要插入一个节点newNode时，先找到节点在该层的位置：因为是链表，所以需要一个节点node，满足插入插入节点newNode的值刚好不大于node的下一个节点值，当然，如果node的下个节点为空，那么也是满足的。

我们先把找节点在某一层位置的方法封装起来：

/**
* 找到level层 value 刚好不小于node 的节点
* @param node 从哪个节点开始找
* @param levelIndex 所在层
* @param value 要插入的节点值
* @return
*/
private Node findClosest(Node node,int levelIndex,int value){
    while ((node.next[levelIndex])!=null && value >node.next[levelIndex].value){
        node = node.next[levelIndex];
    }
    return node;
}

  1. 确定插入节点newNode在该层的位置后，先判断下newNode的随机层数是否小于当前跳表的总层数，如果是，则用链表的插入方法将newNode插入即可。

  2. 如此循环，直到最底层插入newNode完毕。

  3. 循环完毕后，还需要判断下newNode随机出来的层数是否比跳表的实际层数还要大，如果是，直接将超过实际层数的跳表的头节点指向newNode即可，该跳表的实际层数也就变为newNode的随机层数了。

以上就是插入的算法。

理解了插入算法后，查找跟删除就简单多了。

不管是插入、查找还是删除，均是从跳表上层往下层分析，复用上面的findClosest方法，找到要查询的值 在该层closest的节点。比如查询，只需要判断findClosest出来的节点值是否等于该查询值即可，是就返回，不是则继续往下层判断。删除方法思想也是一致的。

代码

class Skiplist {
        /**
         * 最大层数
         */
        private static int DEFAULT_MAX_LEVEL = 32;
        /**
         * 随机层数概率，也就是随机出的层数，在 第1层以上(不包括第一层)的概率，层数不超过maxLevel，层数的起始号为1
         */
        private static double DEFAULT_P_FACTOR = 0.25;

        Node head = new Node(null,DEFAULT_MAX_LEVEL); //头节点

        int currentLevel = 1; //表示当前nodes的实际层数，它从1开始


        public Skiplist() {
        }

        public boolean search(int target) {
            Node searchNode = head;
            for (int i = currentLevel-1; i >=0; i--) {
                searchNode = findClosest(searchNode, i, target);
                if (searchNode.next[i]!=null && searchNode.next[i].value == target){
                    return true;
                }
            }
            return false;
        }

        /**
         *
         * @param num
         */
        public void add(int num) {
            int level = randomLevel();
            Node updateNode = head;
            Node newNode = new Node(num,level);
            // 计算出当前num 索引的实际层数，从该层开始添加索引
            for (int i = currentLevel-1; i>=0; i--) {
                //找到本层最近离num最近的list
                updateNode = findClosest(updateNode,i,num);
                if (i<level){
                    if (updateNode.next[i]==null){
                        updateNode.next[i] = newNode;
                    }else{
                        Node temp = updateNode.next[i];
                        updateNode.next[i] = newNode;
                        newNode.next[i] = temp;
                    }
                }
            }
            if (level > currentLevel){ //如果随机出来的层数比当前的层数还大，那么超过currentLevel的head 直接指向newNode
                for (int i = currentLevel; i < level; i++) {
                    head.next[i] = newNode;
                }
                currentLevel = level;
            }

        }

        public boolean erase(int num) {
            boolean flag = false;
            Node searchNode = head;
            for (int i = currentLevel-1; i >=0; i--) {
                searchNode = findClosest(searchNode, i, num);
                if (searchNode.next[i]!=null && searchNode.next[i].value == num){
                    //找到该层中该节点
                    searchNode.next[i] = searchNode.next[i].next[i];
                    flag = true;
                    continue;
                }
            }
            return flag;
        }

        /**
         * 找到level层 value 大于node 的节点
         * @param node
         * @param levelIndex
         * @param value
         * @return
         */
        private Node findClosest(Node node,int levelIndex,int value){
            while ((node.next[levelIndex])!=null && value >node.next[levelIndex].value){
                node = node.next[levelIndex];
            }
            return node;
        }


        /**
         * 随机一个层数
         */
        private static int randomLevel(){
            int level = 1;
            while (Math.random()<DEFAULT_P_FACTOR && level<DEFAULT_MAX_LEVEL){
                level ++ ;
            }
            return level;
        }


        class Node{
            Integer value;
            Node[] next;

            public Node(Integer value,int size) {
                this.value = value;
                this.next = new Node[size];
            }

            @Override
            public String toString() {
                return String.valueOf(value);
            }
        }

    }

参考文章

发表评论

最新评论

    来第一个评论吧！

手写一个跳表

发表评论

最新评论