redis sorted set底层跳跃表简单实现（Java）

逃离我推掉我的手 2023-07-12 05:15 17阅读 0赞

起因： 以前了解过跳跃表这种数据结构，大致知道是怎么回事，于是很想去实现它。

参考：  
[C语言头文件][C]  
[主要实现的C源码][C 1]

问题：给你一个链表，怎么实现才能不以O（n）时间复杂度去查找一个元素呢？？（有什么更快的实现方式？答案就是跳跃表）

跳跃表长这个样：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTEzNzY5OQ_size_16_color_FFFFFF_t_70]  
链表加索引这种形式。

如果我们想查找5，那我们先从1开始查找，发现1小于5，直接到4，这，小于5，但是4next指针为null,所以我们继续从4往下找，再往后查找一个格子就能找到。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTEzNzY5OQ_size_16_color_FFFFFF_t_70 1]  
这样大大减少了，查询的步长。

分析一下每一个节点的数据结构。

class ZskipListNode {
        
    
        Integer obj;             // 节点存储信息
        double score;           // 排位分数
        ZskipListNode backward; // 后置指针
        ZskipListLevel level[]; // 节点层数组
    
        public ZskipListNode(int level) {
        
            this.level = new ZskipListLevel[level];
            for (int i = 0;i < level;i++) {
        
                this.level[i] = new ZskipListLevel();
            }
        }
    
    }
    
    class ZskipListLevel {
        
    
        ZskipListNode forward;  // 前置指针
    
    }

大致就是这样的，不过level层数，每次都是随机出来的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTEzNzY5OQ_size_16_color_FFFFFF_t_70 2]

接下来就是主要代码

class ZskipListLevel {
        
    
        ZskipListNode forward;  // 前置指针
    
    }
    
    class ZskipListNode {
        
    
        Integer obj;             // 节点存储信息
        double score;           // 排位分数
        ZskipListNode backward; // 后置指针
        ZskipListLevel level[]; // 节点层数组
    
        public ZskipListNode(int level) {
        
            this.level = new ZskipListLevel[level];
            for (int i = 0;i < level;i++) {
        
                this.level[i] = new ZskipListLevel();
            }
        }
    
    }
    
    class ZskipList {
        
    
        ZskipListNode header,tail;
        long length;      // list长度
        int level;        // 最大层数
    
        /*
            创建节点
         */
        public ZskipListNode Zslcreate(int level,double score,Integer obj) {
        
    
            ZskipListNode zn = new ZskipListNode(level);
            zn.obj = obj;
            zn.score = score;
            return zn;
        }
    
        /*
            创建ZskipList节点
         */
        public ZskipList () {
        
            int j;
            this.level = 1;
            this.length = 0;
            this.header = Zslcreate(32,0,null);
            for (j = 0;j < 32;j++) {
        
                this.header.level[j].forward = null;
            }
            this.header.backward = null;
            this.tail = null;
        }
    
        /*
            插入list节点,返回被插入的节点
         */
        public ZskipListNode zslInsert(ZskipList zsl,double score,Integer obj) throws Exception {
        
    
            ZskipListNode[] update = new ZskipListNode[32];
            ZskipListNode x;
            int i,level;
    
            if (score < 0) {
        
                throw new Exception("这tm到底想插入个啥啊 ！");
            }
    
            // 插入前寻找插入的位置,之前的32列的前一个点存在update
            x = zsl.header;
            for (i = zsl.level -1;i >= 0;i--) {
        
                while (x.level[i].forward != null &&
                        (x.level[i].forward.score < score || (x.level[i].forward.score == score &&
                                x.level[i].forward.obj.compareTo(obj) < 0))) {
        
                    x = x.level[i].forward;
                }
                update[i] = x;
            }
    
    
            // 寻找插入位置
            level = RandomZslLevel();
            // 初始化最大的层rank[i]
            if (level > zsl.level) {
        
    
                for (i = zsl.level;i < level;i++) {
        
    
                    // 多余的层还是保留指向头节点
                    update[i] = zsl.header;
                    // 多余的层的跨度长为当前最长
                }
                zsl.level= level;
            }
    
    
            // 生成节点
            x = Zslcreate(level,score,obj);
            for (i = 0;i < level;i++) {
        
                x.level[i].forward = update[i].level[i].forward;
                update[i].level[i].forward = x;
            }
    
    
            // 维护节点前后的backward指针
            x.backward = (update[0] == zsl.header) ? null:update[0];
            if (x.level[0].forward != null) {
        
                // 维护下一个节点的backward指针
                x.level[0].forward.backward = x;
            } else {
        
                // 当前下一个节点不存在,那么当前指针肯定在最后一个,所以更新zsl.tail尾指针
                zsl.tail = x;
            }
            // 新增一个节点，长度加1
            zsl.length++;
            return x;
        }
    
        public void DeleteNode(int value) {
        
    
            ZskipListNode[] update = new ZskipListNode[32];
            ZskipListNode x = this.header;
    
            // 存储update数组
            for (int i = this.level-1;i >= 0;i--) {
        
                while (x.level[i].forward != null && x.level[i].forward.obj < value) {
        
                    x = x.level[i].forward;
                }
                update[i] = x;
            }
    
            // 当前被删除节点存在,才删除
            if (x.level[0].forward.obj == value) {
        
                for (int i = 0; i < this.level; i++) {
        
                    if (update[i].level[i].forward != null && update[i].level[i].forward.obj.equals(value)) {
        
                        update[i].level[i].forward = update[i].level[i].forward.level[i].forward;
                    }
                }
    
                // 更新被删除节点的x和前进和后退指针
                if (x.level[0].forward != null) {
        
                    x.level[0].forward.backward= x;
                } else {
        
                    this.tail = x.backward;
                }
    
    
                while (this.level > 1 && this.header.level[this.level - 1].forward == null) {
        
                    this.level--;
                }
                // 长度减1
                this.length--;
            }
        }
    
        private int RandomZslLevel() {
        
            int level = 1;
            while ((Math.random() < 0.25 ) && (level < 32)) {
        
                level++;
            }
            return level;
        }
    
    
        public  void print() {
        
            for (int i = this.level - 1;i >= 0;i--) {
        
                ZskipListNode x = this.header.level[i].forward;
                while (x != null) {
        
                    System.out.print(x.obj + "->");
                    x = x.level[i].forward;
                }
                System.out.println("NIL");
            }
    
        }
    
        public ZskipListNode find(Integer s) {
        
            ZskipListNode x;
            x = this.header;
            int i = this.level -1;
            for (;i >= 0;i--) {
        
                while (x.level[i].forward != null && x.level[i].forward.obj < s ) {
        
                    x = x.level[i].forward;
                }
                if (x.level[i].forward != null && x.level[i].forward.obj.equals(s)) {
        
                    return x.level[i].forward;
                }
            }
            return null;
        }
    
    
        public int RandomZslLevels() {
        
            int level = 1;
            while ((Math.random() < 0.25 ) && (level < 32)) {
        
                level++;
            }
            return level;
        }
    
    }
    
    
    
    public class ZskipListTest {
        
    
        public static void main(String[] args) throws Exception {
        
    
            ZskipListTest t = new ZskipListTest();
    
    
            ZskipList root= new ZskipList();
    
            root.zslInsert(root,10,10);
            root.zslInsert(root,20,20);
            root.zslInsert(root,20,32);
            root.zslInsert(root,5,5);
            root.zslInsert(root,1,1);
            root.zslInsert(root,80,80);
            root.zslInsert(root,60,60);
            root.zslInsert(root,30,30);
            root.zslInsert(root,100,100);
            root.zslInsert(root,101,101);
            root.zslInsert(root,102,102);
    
            root.print();
     		System.out.println("查找");
            System.out.println("find:"+root.find(102).obj);
    
            System.out.println("删除102");
            root.DeleteNode(102);
            root.print();
            System.out.println("删除32");
            root.DeleteNode(32);
            root.print();
    
            System.out.println("删除10");
            root.DeleteNode(10);
            root.print();
            System.out.println("删除1");
            root.DeleteNode(1);
            root.print();
    
          
        }

测试一波：

60->NIL
    60->NIL
    60->101->NIL
    1->5->10->20->32->30->60->80->100->101->102->NIL
    查找
    find:102
    删除102
    60->NIL
    60->NIL
    60->101->NIL
    1->5->10->20->32->30->60->80->100->101->NIL
    删除32
    60->NIL
    60->NIL
    60->101->NIL
    1->5->10->20->30->60->80->100->101->NIL
    删除10
    60->NIL
    60->NIL
    60->101->NIL
    1->5->20->30->60->80->100->101->NIL
    删除1
    60->NIL
    60->NIL
    60->101->NIL
    5->20->30->60->80->100->101->NIL

[C]: https://github.com/huangz1990/redis-3.0-annotated/blob/unstable/src/redis.h
[C 1]: https://github.com/huangz1990/redis-3.0-annotated/blob/unstable/src/t_zset.c
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTEzNzY5OQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200307115241975.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTEzNzY5OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTEzNzY5OQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200307115654893.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTEzNzY5OQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTEzNzY5OQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020030712413059.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zOTEzNzY5OQ==,size_16,color_FFFFFF,t_70