浅色年华的gravatar头像
浅色年华 2020-08-24 19:06:06
redis跳跃表的实现

最近看到了redis的跳跃表实现,很多牛牛跟我一样对c不了解,所以直接看源码有点吃力,网上搜索的java实现版本代码不全,难以运行,所以决定用java来实现一遍,希望能帮助到你

根据redis的思路,类一共有三个

1.SkipListNode -- 跳跃表节点

package skiplist;

@Data
public class SkipListNode<T> {

    //索引层数组
    private SkipListLevel[] level;

    //后退所指向的节点
    private SkipListNode<T> backword;

    //分值
    private double score;

    //成员对象
    private T obj;

    //初始化头节点时用到的构造方法
    SkipListNode(T obj) {
        this.obj = obj;
        //redis要求索引层数最高是32层
        this.level = new SkipListLevel[32];
        initLevel(this.level, 32);
        this.score = 0;
    }

     //根据"层高"和"分值"新建一个节点,在插入节点时使用
    SkipListNode(T obj, int levelHeight, double score) {
        this.obj = obj;
        this.level = new SkipListLevel[levelHeight];
        initLevel(this.level, levelHeight);
        this.score = score;
    }

    //初始化每一层
    private void initLevel(SkipListLevel[] level, int height) {
        for (int i = 0; i < height; ++i) {
            level[i] = new SkipListLevel();
        }
    }
}

2.SkipListLevel -- 索引层对象

package skiplist;

import lombok.Data;

@Data
public class SkipListLevel {
    //指向下一个节点
    private SkipListNode forward;

    /**
     * 跨度,当前节点和下一个节点间的距离
     * 如果下一个节点为null,当前节点为头节点或尾节点时,跨度为0,否则跨度不为0
     */
    private int span;
}

3. SkipList -- 跳跃表

package skiplist;

import java.util.Random;

public class SkipList <T extends Comparable<? super T>> {
    //头节点
    private SkipListNode<T> header;
    //尾结点
    private SkipListNode<T> tail;

    //跳跃表中节点的数量,(头节点不算)
    private int length;

    //当前跳跃表最高的层数,(头节点不算,头节点的索引层高固定为32)
    private int maxLevel;

    //构造方法初始化SkipList
    public SkipList() {
        //初始化头节点
        SkipListNode<T> node = new SkipListNode<>(null);
        this.header = node;
        this.tail = node;
        this.length = 0;
        this.maxLevel = 0;
    }
}

对于新节点的索引层高,redis使幂次定律来生成,幂次定律是一种理论,并不是代码实现,所以是否生成下一层的概率也不是固定的,redis使用的概率为1/4

     /**
     * 获取随机的层高度
     **/
    private int getRandomHeight() {
        Random random = new Random();
        int i = 1;
        for (; i < 32; ++i) {
            if (random.nextInt(4) == 0) {
                break;
            }
        }
        return i;
    }

插入节点代码如下

    public SkipListNode slInsert(double score, T obj) {
        int i;
        //存放待修改的节点
        SkipListNode[] update = new SkipListNode[32];
        //存放待修改的节点到头节点的距离
        int[] rank = new int[32];
        //当前节点
        SkipListNode node = header;
        //新插入节点的索引层高度
        int level = getRandomHeight();

        //从上往下,从左往右先找到要修改的节点
        for(i = maxLevel -1 ;i>=0;--i){
            //如果左侧已经数好距离,则直接使用,减少数距离的次数
            rank[i] = i==(maxLevel-1)? 0 : rank[i+1];
            SkipListNode<T> next = node.getLevel()[i].getForward();
            //向右一个一个比较,找到最后一个比待插入节点分数小的节点,作为修改节点
            while(next!=null && (score> next.getScore() || (score == next.getScore() && next.getObj().compareTo(obj) <0))){
                rank[i]+= node.getLevel()[i].getSpan();
                node = next;
                next = node.getLevel()[i].getForward();
            }
            update[i] = node;
        }

        //找到新插入节点索引层高比原先节点索引层 高的部分要修改的节点
        if(level > maxLevel){
            for(i =maxLevel;i<level;++i){
                //比原先高的层前一个节点,一定是头节点,span=0,forward = null
                rank[i] = 0;
                update[i] = header;
                //写入头节点到尾结点真实的距离
                update[i].getLevel()[i].setSpan(length);
            }
            maxLevel = level;
        }

        SkipListNode<T> target = new SkipListNode<>(obj, level, score);
        for (i = 0; i < level; i++) {
            //新插入左侧节点的下一个节点就是新插入节点的下一个节点
            target.getLevel()[i].setForward(update[i].getLevel()[i].getForward());
            //新插入节点变成前一个节点的下一个节点
            update[i].getLevel()[i].setForward(target);
            target.getLevel()[i].setSpan(update[i].getLevel()[i].getSpan() - (rank[0] - rank[i]));
            update[i].getLevel()[i].setSpan((rank[0] - rank[i]) + 1);
        }
        for (i = level; i < maxLevel; i++) {
            update[i].getLevel()[i].setSpan(update[i].getLevel()[i].getSpan() + 1);
        }
        //处理后置节点
        target.setBackword(update[0] == header ? null : update[0]);
        if(target.getLevel()[0].getForward()!=null){
            target.getLevel()[0].getForward().setBackword(target);
        }else{
            tail = target;
        }
        length++;
        return target;
    }

测试代码

    public static void main(String[] args) {
        SkipList<String> list= init();
        sout(list);
        list.slInsert2(4.0,"第4个元素");
        System.out.println("____________________________________________________________________________________________________________________________________");
        sout(list);
    }

    public static SkipList init(){
        SkipList<String> list = new SkipList<>();
        list.slInsert2(1.0,"第1个元素");
        list.slInsert2(2.0,"第2个元素");
        list.slInsert2(3.0,"第3个元素");
        list.slInsert2(5.0,"第5个元素");
        list.slInsert2(6.0,"第6个元素");
        list.slInsert2(7.0,"第7个元素");
        return list;
    }

    public static void sout(SkipList list){
        for(int y=10 ;y>=0;y--) {
            SkipListNode node = list.header;
            for (; ; node = node.getLevel()[0].getForward()) {
                if (node != null) {
                    if (y >= node.getLevel().length) {
                        System.out.print("                  |");
                    } else {
                        System.out.print("  " + node.getScore() + ",span="+node.getLevel()[y].getSpan()+","+(node.getLevel()[y].getForward()==null?null:"next")+" |");
                    }
                } else {
                    System.out.println();
                    break;
                }
            }
        }

    }

运行结果如下,因为新插入节点的索引层高是随机的,所以每次运行的结果也不相同

redis跳跃表的实现


打赏

已有1人打赏

最代码官方的gravatar头像
最近浏览
haidaozhi  LV7 2021年12月27日
zhos0212  LV19 2021年9月22日
zhangming12zhang 2021年4月17日
暂无贡献等级
a252529892  LV2 2021年4月13日
wl010101  LV9 2021年3月16日
haoayou  LV8 2021年3月10日
水光浮藻  LV6 2021年3月4日
crazy11crazy  LV30 2021年2月24日
gyjsuper  LV25 2021年2月5日
吴昔泠  LV2 2021年1月25日
顶部 客服 微信二维码 底部
>扫描二维码关注最代码为好友扫描二维码关注最代码为好友