一、概念

跳表（SkipList）是一种增加多级索引结构的链表。相比一般的链表，有更高的查找效率，跳表的查找、插入、删除时间复杂度都是O(logn)，在某些场景下使用跳表相较于红黑树更合适。
许多知名的开源软件（库）中的数据结构都采用了跳表这种数据结构。例如：

  • Redis中的有序集合zset
  • LevelDB、RocksDB、HBase中Memtable
  • ApacheLucene中的TermDictionary、Posting List

    二、底层原理

    单链表在做查询操作时，只能从头到尾遍历链表，查询的时间复杂度为O(n)：
    image.png
    对链表建立一级索引，每两个节点提取一个节点到上一级。图中的down指针指向下一级节点：
    image.png
    如果现在要查找某个结点，比如 16。可以先在索引层遍历，当遍历到索引层中值为 13 的结点时，我们发现下一个结点是 17，那要查找的结点 16 肯定就在这两个结点之间。然后通过索引层结点的 down 指针，下降到原始链表这一层，继续遍历。这个时候，只需要再遍历 2 个结点，就可以找到值等于 16 的这个结点了。这样，原来如果要查找 16，需要遍历 10 个结点，现在只需要遍历 7 个结点。
    image.png
    通过增加多级索引层，可以看出，原来没有索引的时候，查找 62 需要遍历 62 个结点，现在只需要遍历 11 个结点。所以当链表的长度 n 比较大时，比如 1000、10000 的时候，在构建索引之后，查找效率的提升就会非常明显。

跳表结构其实就是利用空间置换时间。比起单纯的链表，跳表需要存储多级索引，空间复杂度是O(n)。
但实际上，在软件开发中，我们不必太在意索引占用的额外空间。在讲数据结构和算法时，我们习惯性地把要处理的数据看成整数，但是在实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。

三、代码实现

  1. package com.study.skiplist;
  3. import java.util.Random;
  5. /**
  6.  * 1，跳表的一种实现方法，用于练习。跳表中存储的是正整数，并且存储的是不重复的。
  7.  * 2，本类是参考作者zheng ，自己学习，优化了添加方法
  8.  * 3，看完这个，我觉得再看ConcurrentSkipListMap 源码，会有很大收获
  9.  * Author：ldb
  10.  */
  11. public class SkipList2 {
  13.     private static final int MAX_LEVEL = 16;
  14.     private int levelCount = 1;
  16.     /**
  17.      * 带头链表
  18.      */
  19.     private Node head = new Node(MAX_LEVEL);
  20.     private Random r = new Random();
  22.     public Node find(int value) {
  23.         Node p = head;
  24.         // 从最大层开始查找，找到前一节点，通过--i，移动到下层再开始查找
  25.         for (int i = levelCount - 1; i >= 0; --i) {
  26.             while (p.forwards[i] != null && p.forwards[i].data < value) {
  27.                 // 找到前一节点
  28.                 p = p.forwards[i];
  29.             }
  30.         }
  32.         if (p.forwards[0] != null && p.forwards[0].data == value) {
  33.             return p.forwards[0];
  34.         } else {
  35.             return null;
  36.         }
  37.     }
  39.     /**
  40.      * 优化了作者zheng的插入方法
  41.      *
  42.      * @param value 值
  43.      */
  44.     public void insert(int value) {
  45.         int level = head.forwards[0] == null ? 1 : randomLevel();
  46.         // 每次只增加一层，如果条件满足
  47.         if (level > levelCount) {
  48.             level = ++levelCount;
  49.         }
  50.         Node newNode = new Node(level);
  51.         newNode.data = value;
  52.         Node update[] = new Node[level];
  53.         for (int i = 0; i < level; ++i) {
  54.             update[i] = head;
  55.         }
  57.         Node p = head;
  58.         // 从最大层开始查找，找到前一节点，通过--i，移动到下层再开始查找
  59.         for (int i = levelCount - 1; i >= 0; --i) {
  60.             while (p.forwards[i] != null && p.forwards[i].data < value) {
  61.                 // 找到前一节点
  62.                 p = p.forwards[i];
  63.             }
  64.             // levelCount 会 > level，所以加上判断
  65.             if (level > i) {
  66.                 update[i] = p;
  67.             }
  69.         }
  70.         for (int i = 0; i < level; ++i) {
  71.             newNode.forwards[i] = update[i].forwards[i];
  72.             update[i].forwards[i] = newNode;
  73.         }
  75.     }
  77.     /**
  78.      * 优化了作者zheng的插入方法2
  79.      *
  80.      * @param value 值
  81.      */
  82.     public void insert2(int value) {
  83.         int level = head.forwards[0] == null ? 1 : randomLevel();
  84.         // 每次只增加一层，如果条件满足
  85.         if (level > levelCount) {
  86.             level = ++levelCount;
  87.         }
  88.         Node newNode = new Node(level);
  89.         newNode.data = value;
  90.         Node p = head;
  91.         // 从最大层开始查找，找到前一节点，通过--i，移动到下层再开始查找
  92.         for (int i = levelCount - 1; i >= 0; --i) {
  93.             while (p.forwards[i] != null && p.forwards[i].data < value) {
  94.                 // 找到前一节点
  95.                 p = p.forwards[i];
  96.             }
  97.             // levelCount 会 > level，所以加上判断
  98.             if (level > i) {
  99.                 if (p.forwards[i] == null) {
  100.                     p.forwards[i] = newNode;
  101.                 } else {
  102.                     Node next = p.forwards[i];
  103.                     p.forwards[i] = newNode;
  104.                     newNode.forwards[i] = next;
  105.                 }
  106.             }
  108.         }
  110.     }
  112.     /**
  113.      * 作者zheng的插入方法，未优化前，优化后参见上面insert()
  114.      *
  115.      * @param value
  116.      * @param level 0 表示随机层数，不为0，表示指定层数，指定层数
  117.      *              可以让每次打印结果不变动，这里是为了便于学习理解
  118.      */
  119.     public void insert(int value, int level) {
  120.         // 随机一个层数
  121.         if (level == 0) {
  122.             level = randomLevel();
  123.         }
  124.         // 创建新节点
  125.         Node newNode = new Node(level);
  126.         newNode.data = value;
  127.         // 表示从最大层到低层，都要有节点数据
  128.         newNode.maxLevel = level;
  129.         // 记录要更新的层数，表示新节点要更新到哪几层
  130.         Node update[] = new Node[level];
  131.         for (int i = 0; i < level; ++i) {
  132.             update[i] = head;
  133.         }
  135.         /**
  136.          *
  137.          * 1，说明：层是从下到上的，这里最下层编号是0，最上层编号是15
  138.          * 2，这里没有从已有数据最大层（编号最大）开始找，（而是随机层的最大层）导致有些问题。
  139.          *    如果数据量为1亿，随机level=1 ，那么插入时间复杂度为O（n）
  140.          */
  141.         Node p = head;
  142.         for (int i = level - 1; i >= 0; --i) {
  143.             while (p.forwards[i] != null && p.forwards[i].data < value) {
  144.                 p = p.forwards[i];
  145.             }
  146.             // 这里update[i]表示当前层节点的前一节点，因为要找到前一节点，才好插入数据
  147.             update[i] = p;
  148.         }
  150.         // 将每一层节点和后面节点关联
  151.         for (int i = 0; i < level; ++i) {
  152.             // 记录当前层节点后面节点指针
  153.             newNode.forwards[i] = update[i].forwards[i];
  154.             // 前一个节点的指针，指向当前节点
  155.             update[i].forwards[i] = newNode;
  156.         }
  158.         // 更新层高
  159.         if (levelCount < level) levelCount = level;
  160.     }
  162.     public void delete(int value) {
  163.         Node[] update = new Node[levelCount];
  164.         Node p = head;
  165.         for (int i = levelCount - 1; i >= 0; --i) {
  166.             while (p.forwards[i] != null && p.forwards[i].data < value) {
  167.                 p = p.forwards[i];
  168.             }
  169.             update[i] = p;
  170.         }
  172.         if (p.forwards[0] != null && p.forwards[0].data == value) {
  173.             for (int i = levelCount - 1; i >= 0; --i) {
  174.                 if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
  175.                     update[i].forwards[i] = update[i].forwards[i].forwards[i];
  176.                 }
  177.             }
  178.         }
  179.     }
  181.     /**
  182.      * 随机 level 次，如果是奇数层数 +1，防止伪随机
  183.      *
  184.      * @return
  185.      */
  186.     private int randomLevel() {
  187.         int level = 1;
  188.         for (int i = 1; i < MAX_LEVEL; ++i) {
  189.             if (r.nextInt() % 2 == 1) {
  190.                 level++;
  191.             }
  192.         }
  193.         return level;
  194.     }
  196.     /**
  197.      * 打印每个节点数据和最大层数
  198.      */
  199.     public void printAll() {
  200.         Node p = head;
  201.         while (p.forwards[0] != null) {
  202.             System.out.print(p.forwards[0] + " ");
  203.             p = p.forwards[0];
  204.         }
  205.         System.out.println();
  206.     }
  208.     /**
  209.      * 打印所有数据
  210.      */
  211.     public void printAll_beautiful() {
  212.         Node p = head;
  213.         Node[] c = p.forwards;
  214.         Node[] d = c;
  215.         int maxLevel = c.length;
  216.         for (int i = maxLevel - 1; i >= 0; i--) {
  217.             do {
  218.                 System.out.print((d[i] != null ? d[i].data : null) + ":" + i + "-------");
  219.             } while (d[i] != null && (d = d[i].forwards)[i] != null);
  220.             System.out.println();
  221.             d = c;
  222.         }
  223.     }
  225.     /**
  226.      * 跳表的节点，每个节点记录了当前节点数据和所在层数数据
  227.      */
  228.     public class Node {
  229.         private int data = -1;
  230.         /**
  231.          * 表示当前节点位置的下一个节点所有层的数据，从上层切换到下层，就是数组下标-1，
  232.          * forwards[3]表示当前节点在第三层的下一个节点。
  233.          */
  234.         private Node forwards[];
  236.         /**
  237.          * 这个值其实可以不用，看优化insert()
  238.          */
  239.         private int maxLevel = 0;
  241.         public Node(int level) {
  242.             forwards = new Node[level];
  243.         }
  245.         @Override
  246.         public String toString() {
  247.             StringBuilder builder = new StringBuilder();
  248.             builder.append("{ data: ");
  249.             builder.append(data);
  250.             builder.append("; levels: ");
  251.             builder.append(maxLevel);
  252.             builder.append(" }");
  253.             return builder.toString();
  254.         }
  255.     }
  257.     public static void main(String[] args) {
  258.         SkipList2 list = new SkipList2();
  259.         list.insert(1, 3);
  260.         list.insert(2, 3);
  261.         list.insert(3, 2);
  262.         list.insert(4, 4);
  263.         list.insert(5, 10);
  264.         list.insert(6, 4);
  265.         list.insert(8, 5);
  266.         list.insert(7, 4);
  267.         list.printAll_beautiful();
  268.         list.printAll();
  269.         /**
  270.          * 结果如下：
  271.          *                                         null:15-------
  272.          *                                         null:14-------
  273.          *                                         null:13-------
  274.          *                                         null:12-------
  275.          *                                         null:11-------
  276.          *                                         null:10-------
  277.          *                                            5:9-------
  278.          *                                            5:8-------
  279.          *                                            5:7-------
  280.          *                                            5:6-------
  281.          *                                            5:5-------
  282.          *                                            5:4-------                     8:4-------
  283.          *                                  4:3-------5:3-------6:3-------7:3-------8:3-------
  284.          * 1:2-------2:2-------             4:2-------5:2-------6:2-------7:2-------8:2-------
  285.          * 1:1-------2:1-------3:1-------4:1-------5:1-------6:1-------7:1-------8:1-------
  286.          * 1:0-------2:0-------3:0-------4:0-------5:0-------6:0-------7:0-------8:0-------
  287.          * { data: 1; levels: 3 } { data: 2; levels: 3 } { data: 3; levels: 2 } { data: 4; levels: 4 }
  288.          * { data: 5; levels: 10 } { data: 6; levels: 4 } { data: 7; levels: 4 } { data: 8; levels: 5 }
  289.          */
  290.         // 优化后insert()
  292.         SkipList2 list2 = new SkipList2();
  293.         list2.insert2(1);
  294.         list2.insert2(2);
  295.         list2.insert2(6);
  296.         list2.insert2(7);
  297.         list2.insert2(8);
  298.         list2.insert2(3);
  299.         list2.insert2(4);
  300.         list2.insert2(5);
  301.         System.out.println();
  302.         list2.printAll_beautiful();
  303.     }
  304. }

随机函数

  1. private int randomLevel1() {
  2.     int level = 1;
  3.     for (int i = 1; i < MAX_LEVEL; ++i) {
  4.         if (r.nextInt() % 2 == 1) {
  5.             level++;
  6.         }
  7.     }
  8.     return level;
  9. }
  11. private int randomLevel2() {
  12.     int level = 1;
  13.     while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)
  14.         level += 1;
  15.     return level;
  16. }

理论来讲，一级索引中元素个数应该占原始数据的 50%，二级索引中元素个数占 25%，三级索引12.5% ，一直到最顶层。因为这里每一层的晋升概率是 50%。对于每一个新插入的节点，都需要调用 randomLevel 生成一个合理的层数。该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ：

  • 50%的概率返回 1
  • 25%的概率返回 2

  • 12.5%的概率返回 3 …

    四、使用场景

    Redis 中的有序集合是通过跳表来实现的，严格点讲，其实还用到了散列表。如果查看 Redis 的开发手册，就会发现，Redis 中的有序集合支持的核心操作主要有下面这几个：

  • 插入一个数据；

  • 删除一个数据；
  • 查找一个数据；
  • 按照区间查找数据（比如查找值在[100, 356]之间的数据）；
  • 迭代输出有序序列。

其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。
对于按照区间查找数据这个操作，跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了，这样做非常高效。

参考资料：《数据结构与算法之美》- 17 | 跳表：为什么Redis一定要用跳表来实现有序集合？