跳跃表之java实现

跳跃表是一种特殊的单向有序链表，redis中zset在数据量大时就采用了这种数据结构。

添加，删除，查询的时间复杂度都为O(logn)

package algorithm.array_linked;

import lombok.Data;

import java.util.*;


@Data
public class SkipList {

    //指向最高层索引链表的头节点,由于每层都有一个空的头结点null，因此这个指向最高层的null
    private SkipNode indexHead = new SkipNode<>(null, 0);

    private SkipNode head = new SkipNode<>(null, Integer.MIN_VALUE);
    //一共的层级，包括数据链表层
    private int totalLevel;

    //限制跳跃表的最大层级
    private int maxLevel;

    //初始化层数
    private int initLevel;

    //计算节点是否需要上移一层
    private Random random = new Random();

    @Data
    static class SkipNode {
        //下一个节点，如果该节点是索引节点，指向下一个索引节点
        private SkipNode next;
        //如果该节点是索引节点，指向下一层原始节点
        private SkipNode down;
        //得分，用来排序
        private int score;
        //存储的数据
        private E data;

        public SkipNode(E data, int score){
            this.data = data;
            this.score = score;
        }

        @Override
        public String toString() {
            return "SkipNode{" +
                    "score=" + score +
                    '}';
        }
    }

    public SkipList(int initLevel, int maxLevel) {
        this.maxLevel = maxLevel;
        this.initLevel = initLevel;
        //初始化每一层的头节点，这里初始化完后，数据结构如下
        
        SkipNode curr = new SkipNode<>(null, Integer.MIN_VALUE);
        head.next = curr;
        for (int i = 1; i < initLevel; i++) {
            curr = createIndexNode(curr);
        }
        indexHead.next = curr;
    }


    
    private int getLevel() {
        int level = 1;
        while (random.nextInt(2) == 0 && level <= maxLevel) {
            level ++;
        }
        return level;
    }

    
    private SkipNode createIndexNode(SkipNode node) {
        //得分相同
        SkipNode indexNode = new SkipNode<>(null, node.getScore());
        //索引节点的下一层为传入的节点
        indexNode.down = node;
        return indexNode;
    }

    
    public void add(SkipNode node) {
        SkipNode curr = indexHead.next;
        //保存每层当前节点的prev，便于回溯时添加索引节点
        //下面整个while循环就是为了给这个list添加元素，获取插入的位置。由于往下层走的时候，此层要么走完，要么下一个节点的score大于要插入的节点
        //因此，当前位置一定是需要插入的位置，记录此时的prev
        List> prevList = new ArrayList<>();
        while (curr != null) {
            if (curr.next == null) {
                //说明当前层走到尽头了，把curr指针往下层移动，并且需要记录当前层的prev节点到list中
                SkipNode prev = curr;
                prevList.add(prev);
                curr = curr.down;
                continue;
            }
            while (curr.next != null && curr.next.score < node.score) {
                //当 当前score小于node时，需要继续往右寻找
                curr = curr.next;
            }
            if (curr.score < node.score) {
                //这种情况说明要么下一个节点是null，要么下一个节点的score>node.score，此时需要往下走，和上面一样，保存当前层的前驱节点
                SkipNode prev = curr;
                prevList.add(prev);
                curr = curr.down;
                continue;
            }
        }
        //循环走完以后，说明已经找到了每一层的插入位置，从下往上依次插入每一层的节点
        //按层级从下往上插入节点
        SkipNode last = node;
        int level = getLevel();
        int allowLevel = Math.min(level, maxLevel);
        //代表此时最顶端左边的节点,这个变量的作用是，当插入节点的level大于当前最高level时，需要往上插入一个哨兵节点，把节点索引插入哨兵节点之后
        SkipNode top = indexHead.next;
        for (int i = 1; i <= allowLevel; i++) {
            int index = prevList.size() - i;
            if (index >= 0) {
                //说明有prev节点,只需要在prev节点之后插入即可
                SkipNode prev = prevList.get(index);
                last.next = prev.next;
                prev.next = last;
                last = createIndexNode(last);
            }else {
                //说明level已经超过当前的totalLevel，需要往上新插入哨兵节点和索引节点
                SkipNode temp = new SkipNode<>(null, Integer.MIN_VALUE);
                temp.next = last;
                temp.down = top;
                top = temp;
                last = createIndexNode(last);
                indexHead.next = temp;
            }
        }
        //更新最大层级
        totalLevel = Math.max(totalLevel, allowLevel);
    }

    
    public E search(int score) {
        SkipNode curr = indexHead.next;
        while (curr != null) {
            if (curr.next == null) {
                curr = curr.down;
                continue;
            }
            while (curr.next != null && curr.next.score <= score) {
                curr = curr.next;
            }
            if (curr.score == score) {
                break;
            }
            curr = curr.down;
        }
        if (curr == null) {
            return null;
        }
        while (curr.down != null) {
            curr = curr.down;
        }
        return curr.data;
    }

    @Override
    public String toString() {
        return "SkipList{" +
                "totalLevel=" + totalLevel +
                '}';
    }

    public String print() {
        SkipNode currHead = indexHead.next;
        int i = 0;
        while (currHead != null){
            int curr = Math.max(initLevel, totalLevel) - i;
            SkipNode node = currHead.next;
            System.out.println("第" + curr + "层数据如下:");
            i++;
            while (node != null) {
                System.out.print(node.getData() + ": score = " + node.score + "t");
                node = node.next;
            }
            currHead = currHead.down;
            System.out.println("--------------------------------");
        }
        return "";
    }


    public String print2() {
        SkipNode curr = head.next;
        while (curr != null) {
            System.out.print(curr.getData() + "t");
            curr = curr.next;
        }
        return "";
    }

    public static void main(String[] args) {
//        SkipList skipList = new SkipList<>(4, 20);
//        long start = System.currentTimeMillis();
//        int num = 2000000;
//        for (int i = 0; i < num; i++) {
//            skipList.add(new SkipNode<>(i, i));
//        }
//        System.out.println(skipList.getTotalLevel());
//        //添加10w个元素耗时:33
//        System.out.println("添加" + num + "个元素耗时:" + (System.currentTimeMillis() - start) + "ms");
//        //检索速度
//        start = System.currentTimeMillis();
//        System.out.println(skipList.search(567));
//        System.out.println(num + "个元素查询耗时:" + (System.currentTimeMillis() - start) + "ms");
//        System.out.println(skipList.print());
        test1();
    }

    public static void test1() {
        SkipList skipList = new SkipList<>(4, 20);
        Random random = new Random();
        long start = System.currentTimeMillis();
        int num = 1000000;
        Set nums = new HashSet<>();
        for (int i = 0; i < num; i++) {
            int curr;
            do {
                curr = random.nextInt(10000000);
            } while (!nums.add(curr));
            skipList.add(new SkipNode<>(curr, curr));
        }
        skipList.add(new SkipNode<>(124214, 124214));
        num = nums.size();
        System.out.println(skipList.getTotalLevel());
        //添加1000000个元素耗时:1326ms
        System.out.println("添加" + num + "个元素耗时:" + (System.currentTimeMillis() - start) + "ms");
        //检索速度 0ms
        start = System.currentTimeMillis();
        System.out.println(skipList.search(124214));
        System.out.println(num + "个元素查询耗时:" + (System.currentTimeMillis() - start) + "ms");
//        skipList.print();
    }
}