跳跃表原理及java实现跳跃表

对于一个链表的查询和列表不同。如果列表是有序的那么可以用二分查找,时间复杂度为log n，链表即便是有序的，查询一个元素也是要从头遍历，时间复杂度为O(n) 。为了解决链表的查询效率问题，出现了一些特殊的数据结构，例如：树类的包括1、二叉树 2、平衡二叉树（理想最好情况）3、红黑树 4、b 树 5、b+ 树 等等，还有一种区别于树类型的数据结构：跳跃表。跳跃表类似多维链表，最高纬跳跃最大，最低纬就是普通的链表存储了所有的数据。例如链表 7 - 21 - 32 - 37 -71 - 85 如下图

image.png

1、初始化先由下到上创建一个head竖向链表，Node的值为空，无穷小。

2、跳跃表的查找过程，例如查找的是节点32。红线是指针变化过程，虚线是判断过程。如图

image.png

3、插入：首先查找到需要插入节点的最低纬链表的位置指针，并且记录每个维度最左位置的指针。然后随机生成高度。例如插入的数值为35，随机高度为4，如图

image.png

4、性能
查找、插入和删除操作的时间复杂度都为: O(logn)

随机跳跃表表现性能也非常不错，节省了大量复杂的调节平衡树的代码。其效率与红黑树、伸展树等这些平衡树能够说相差不大。
但跳跃表还在并发环境下有优势。在并发环境下。假设要更新数据，跳跃表须要更新的部分就比較少，锁的东西也就比較少。所以不同线程争锁的代价就相对少了，而红黑树有个平衡的过程，牵涉到大量的节点，争锁的代价也就相对较高了。跳跃表的缺点是，存储空间占用相对较大一些。

5、应用
jdk 中有对跳跃表的并发实现：
ConcurrentSkipListMap
ConcurrentSkipListSet

了解过Redis的都知道，Redis有一个非常实用的数据结构：SortSet，基于它，我们能够非常轻松的实现一个Top N的应用。这个SortSet底层就是利用跳表实现的。

总结
作为一种简单的数据结构，在大多数应用中Skip lists可以取代平衡树。Skiplists算法很easy实现、扩展和改动。
Skip lists和进行过优化的平衡树有着相同高的性能 （红黑树）。

java代码实现：

import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.ThreadLocalRandom;

public class SkipList<E, C extends Comparable<? super C>> {
    //最大层级
    static final int MAX_LEVEL = 1 << 6;
    static final int DEFAULT_LEVEL = 4;
    //跳跃表 down node 的层级
    int level;
    //头节点
    Node<E, C> head;
    ThreadLocalRandom random = ThreadLocalRandom.current();

    public SkipList() {
        this(DEFAULT_LEVEL);
    }

    //跳跃表的初始化
    public SkipList(int level) {
        this.level = level;
        int i = level;
        Node<E, C> temp = null;
        Node<E, C> prev = null;
        //从底部节点开始创建链表
        while (i-- != 0) {
            temp = new Node(null, (T) -> -1);
            temp.down = prev;
            prev = temp;
        }
        head = temp;//头节点
    }


    public void put(E val, C score) {
        Node<E, C> t = head;
        //存储每个层级，插入新节点的最左边节点
        List<Node<E, C>> paths = new ArrayList<>();
        //1，找到需要插入的位置
        while (t != null) {
            //表示存在该值的点，表示需要更新该节点
            if (t.score.compareTo(score) == 0) {
                Entity e = t.entity;
                //插入到链表尾部
                e.next = new Entity(val, null);
                return;
            }

            //查找插入的位置
            if (t.next == null || t.next.score.compareTo(score) > 0) {
                paths.add(t);
                t = t.down;
            } else {
                t = t.next;
            }
        }
        //随机生成新节点的层级
        int lev = randomLevel();

        // 如果随机的层级数，大于head节点的层级数
        // 需要更新head这一列的节点数量,保证head列数量最多
        if (lev > level) {
            Node<E, C> temp = null;
            Node<E, C> prev = head;
            while (level++ != lev) {
                temp = new Node(null, (T) -> -1);
                paths.add(0, temp);
                temp.down = prev;
                prev = temp;
            }
            head = temp;
            //更新层级
            level = lev;
        }
        //从后向前遍历path中的每一个节点，在其后面增加一个新的节点
        Node<E, C> down = null, newNade = null, path = null;
        Entity<E> e = new Entity<>(val, null);
        for (int i = level - 1; i >= level - lev; i--) {
            //创建新的节点
            newNade = new Node<E, C>(e, score);
            path = paths.get(i);
            newNade.next = path.next;
            path.next = newNade;
            newNade.down = down;
            down = newNade;
        }
    }

    /**
     * 查找跳跃表中的一个值
     */
    public List<E> get(C score) {
        Node<E, C> t = head;
        while (t != null) {
            if (t.score.compareTo(score) == 0) {
                return t.entity.toList();
            }
            if (t.next == null || t.next.score.compareTo(score) > 0) {
                t = t.down;
            } else {
                t = t.next;
            }
        }
        return null;
    }

    /**
     * 查找跳跃表中指定范围的值
     */
    public List<E> find(final C begin, C and) {
        Node<E, C> t = head;
        Node<E, C> beginNode = null;
        //确定下界索引
        while (t != null) {
            beginNode = t;
            if (t.next == null || t.next.score.compareTo(begin) >= 0) {
                t = t.down;
            } else {
                t = t.next;
            }
        }

        //循环链表
        List<E> list = new ArrayList<>();
        for (Node n = beginNode.next; n != null; n = n.next) {
            if (n.entity != null && n.score.compareTo(and) < 0)
                list.addAll(n.entity.toList());
        }
        return list;
    }

    /**
     * 根据score的值来删除节点。
     */
    public void delete(C score) {
        //1,查找到节点列的第一个节点的前驱
        Node<E, C> t = head;
        while (t != null) {
            if (t.next == null || t.next.score.compareTo(score) > 0) {
                //向下查找
                t = t.down;
            } else if (t.next.score.compareTo(score) == 0) {
                // 在这里说明找到了该删除的节点
                t.next = t.next.next;
                //向下查找
                t = t.down;
            } else {
                //向右查找
                t = t.next;
            }
        }
    }

    /**
     * 高度随机增加一
     */
    private int randomLevel() {
        int lev = 1;
        //产生一个非负整数
        while (random.nextInt() % 2 == 0)
            lev++;
        return Math.min(lev, MAX_LEVEL);
    }

    /**
     * 跳跃表的节点链表
     */
    static class Node<E, C extends Comparable> {
        Entity<E> entity;//存储的数据
        C score; //需要排序的字段
        Node<E, C> next;//指向下一个节点的指针
        Node<E, C> down;//指向下一层的指针

        Node(Entity<E> entity, C score) {
            this.entity = entity;
            this.score = score;
        }

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

    static class Entity<E> {
        E val;
        Entity<E> next;

        Entity(E val, Entity<E> next) {
            this.val = val;
            this.next = next;
        }

        List<E> toList() {
            List<E> list = new ArrayList<>();
            list.add(val);
            for (Entity<E> e = next; e != null; e = e.next) {
                list.add(e.val);
            }
            return list;
        }

        @Override
        public String toString() {
            return "Entity{" + "val=" + val + '}';
        }
    }
}