定义

跳表(SkipList，全称跳跃表)是用于有序元素序列快速搜索查找的一个数据结构，跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。它在性能上和红黑树，AVL树不相上下，但是跳表的原理非常简单，实现也比红黑树简单很多。

层: 一个节点在第几层是随机的，如果节点在低层3，那么底层3以及3一下都要修改一下节点的指向，操作同链表，看图基本上可以理解跳跃表的实现了。

每一层都是一个有序的列表。image.png

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

实现

  1. /**
  2.  * <ul>
  3.  *     <li>1、一个跳表应该有几个层组成，第一层包含所有的元素</li>
  4.  *     <li>2、每一层都是有序链表</li>
  5.  *     <li>3、如果元素x出现在第i层，则所有比i小的层都包含x</li>
  6.  *     <li>4、第i层的元素通过一个down指针指向下一层拥有相同值的元素</li>
  7.  * </ul>
  8.  *
  9.  * @author chenshun00@gmail.com
  10.  * @since 2022/2/12 3:37 下午
  11.  */
  12. public class SkipList<E> {
  14.     private static final double p = 0.25D;
  16.     int MAX_LEVEL = 32;
  18.     /**
  19.      * 跳表实际层数
  20.      */
  21.     int level;
  23.     /**
  24.      * 跳表头节点
  25.      */
  26.     SkipListNode<E> header;
  28.     public static void main(String[] args) {
  29.         SkipList<String> list = new SkipList<>();
  30.         list.add(3, "耳朵听声音");
  31.         list.add(7, "镰刀来割草");
  32.         list.add(6, "口哨嘟嘟响");
  33.         list.add(4, "红旗迎风飘");
  34.         list.add(2, "小鸭水上漂");
  35.         list.add(9, "勺子能吃饭");
  36.         list.add(1, "铅笔细又长");
  37.         list.add(5, "秤钩来买菜");
  38.         list.add(8, "麻花扭一扭");
  39.         list.printList();
  40.         System.out.println("1==" + list.get(1));
  41.         list.remove(1);
  42.         System.out.println("====");
  43.         System.out.println("1==" + list.get(1));
  44.         list.printList();
  45.     }
  47.     /**
  48.      * 创建节点
  49.      *
  50.      * @param level 节点所在层数
  51.      * @param key   节点key
  52.      * @param value 节点value
  53.      * @return {@link SkipListNode<E>}
  54.      */
  55.     private SkipListNode<E> createNode(int level, int key, E value) {
  56.         return new SkipListNode<E>(key, value, level);
  57.     }
  60.     /**
  61.      * 初始化跳跃表
  62.      * 1、初始化level为1级
  63.      * 2、填充header的的next指针为null
  64.      */
  65.     public SkipList() {
  66.         this.level = 0;
  67.         this.header = createNode(MAX_LEVEL, Integer.MIN_VALUE, null);
  68.         for (int i = 0; i < MAX_LEVEL; i++) {
  69.             this.header.forwards[i] = null;
  70.         }
  71.     }
  74.     /**
  75.      * 添加节点到跳跃表
  76.      *
  77.      * @param key   ke3y
  78.      * @param value value
  79.      */
  80.     public void add(int key, E value) {
  81.         final int randomLevel = getRandomLevel();
  82.         final SkipListNode<E> node = createNode(randomLevel, key, value);
  84.         //从高层开始向底层遍历，为每一层补充节点信息，操作方式同链表
  85.         for (int i = level - 1; i >= 0; i--) {
  86.             SkipListNode<E> closable = header;
  87.             //找到这一层的下一个节点
  88.             while (closable.forwards[i] != null) {
  89.                 if (key == closable.forwards[i].key) {
  90.                     closable.forwards[i].value = value;
  91.                     return;
  92.                 } else if (key > closable.forwards[i].key) {
  93.                     closable = closable.forwards[i];
  94.                 } else {
  95.                     break;
  96.                 }
  97.             }
  98.             if (randomLevel > i) {
  99.                 if (closable.forwards[i] == null) {
  100.                     closable.forwards[i] = node;
  101.                 } else {
  102.                     final SkipListNode<E> next = closable.forwards[i];
  103.                     closable.forwards[i] = node;
  104.                     node.forwards[i] = next;
  105.                 }
  106.             }
  107.         }
  108.         if (randomLevel > level) { //如果随机出来的层数比当前的层数还大，那么超过currentLevel的head 直接指向newNode
  109.             for (int i = level; i < randomLevel; i++) {
  110.                 header.forwards[i] = node;
  111.             }
  112.             this.level = randomLevel;
  113.         }
  114.     }
  116.     public E get(int key) {
  117.         SkipListNode<E> closable = header;
  118.         for (int i = level - 1; i >= 0; i--) {
  119.             //找到这一层的下一个节点
  120.             while (closable.forwards[i] != null) {
  121.                 if (key == closable.forwards[i].key) {
  122.                     return closable.forwards[i].value;
  123.                 } else if (key > closable.forwards[i].key) {
  124.                     closable = closable.forwards[i];
  125.                 } else {
  126.                     break;
  127.                 }
  128.             }
  129.             if (closable.forwards[i] != null && closable.forwards[i].key == key) {
  130.                 return closable.forwards[i].value;
  131.             }
  132.         }
  133.         return null;
  134.     }
  136.     public void remove(int key) {
  137.         SkipListNode<E> closable = header;
  139.         for (int i = level - 1; i >= 0; i--) {
  140.             //找到这一层的下一个节点
  141.             while (closable.forwards[i] != null) {
  142.                 if (key > closable.forwards[i].key) {
  143.                     closable = closable.forwards[i];
  144.                 } else {
  145.                     break;
  146.                 }
  147.             }
  148.             if (closable.forwards[i] != null && closable.forwards[i].key == key) {
  149.                 final SkipListNode<E> current = closable.forwards[i];
  150.                 final SkipListNode<E> next = current.forwards[i];
  151.                 closable.forwards[i] = next;
  152.             }
  153.         }
  154.     }
  156.     public void printList() {
  157.         for (int i = level - 1; i >= 0; i--) {
  158.             SkipListNode<E> curNode = this.header.forwards[i];
  159.             System.out.print("HEAD->");
  160.             while (curNode != null) {
  161.                 String line = String.format("(%s,%s)->", curNode.key, curNode.value);
  162.                 System.out.print(line);
  163.                 curNode = curNode.forwards[i];
  164.             }
  165.             System.out.println("NIL");
  166.         }
  167.     }
  169.     private int getRandomLevel() {
  170.         int lvl = 1;
  171.         //Math.random() 返回一个介于 [0,1) 之间的数字
  172.         while (lvl < MAX_LEVEL && Math.random() < p) {
  173.             lvl++;
  174.         }
  175.         return lvl;
  176.     }
  178.     private static class SkipListNode<E> {
  179.         /**
  180.          * key 信息
  181.          * <p>
  182.          * 这个是什么？index 吗？
  183.          */
  184.         int key;
  185.         /**
  186.          * 存放的元素
  187.          */
  188.         E value;
  189.         /**
  190.          * 向前的指针
  191.          * <p>
  192.          * 跳表是多层的，这个向前的指针，最多和层数一样。
  193.          *
  194.          * @since 0.0.4
  195.          */
  196.         SkipListNode<E>[] forwards;
  198.         @SuppressWarnings("all")
  199.         public SkipListNode(int key, E value, int level) {
  200.             this.key = key;
  201.             this.value = value;
  202.             this.forwards = new SkipListNode[level];
  203.         }
  205.         @Override
  206.         public String toString() {
  207.             return "SkipListNode{" +
  208.                     "key=" + key +
  209.                     ", value=" + value +
  210.                     ", forwards=" + Arrays.toString(forwards) +
  211.                     '}';
  212.         }
  213.     }
  214. }

参考链接