数据结构与算法--跳表

跳表 = 链表 + 多级索引

跳表使用空间换时间的设计思路，通过构建多级索引来提高查询的效率，实现了基于链表的“二分查找”。跳表是一种动态数据结构，支持快读的插入、删除、查找操作，时间复杂度都是O(logn)。

跳表跳表的空间复杂度是O(n)。跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。跳表的代码比起红黑树来说，要简单、易读。

链表加多级索引的结构，就是跳表。

对于一个单链表，即便链表中存储的数据是有序的，如果要查找某个数据，也只能从头到尾遍历，时间复杂度是O(n)。

对于链表建立一级“索引”，没两个结点提取一个结点到上一级，把抽出来的那一级叫做索引或索引层。图中的 down表示down指针，指向下一级结点。

这样就可以先在索引层遍历，然后通过索引层结点的down指针，下降到原始链表这一层，继续遍历。

比如要查找16，当在索引层遍历到13时，发现索引层下一个结点是17大于目标16，则可从13的down指针下降到原始链表继续遍历。这样只需要再遍历2个结点，就可以找到值等于16的这个结点了。原来查找16，需要遍历10个结点，加入一层索引后只需要遍历7个结点。

加上一层索引之后，查找一个结点需要遍历的结点个数减少了，查找效率提高了。继续再加一级索引，在第一级索引的基础之上，每两个结点就抽出一个结点到第二级索引。现在再查找16，只需要遍历6个结点了，需要遍历的结点数量又减少了。

下图是一个包含64个结点的链表，建立五级索引。

在五级索引的作用下，查找62只需要遍历11个结点。当链表的长度n比较大时，比如1000、10000的时候，在构建多级索引之后，查找效率的提升就会非常明显。

跳表的时间复杂度

一个链表里有n个结点，每两个结点会抽出一个结点作为上一级索引的结点，那第一级索引的结点个数大约就是n / 2，第二级索引的结点个数大约就是n / 4，第三级索引的结点个数大约就是n / 8，依此类推，也就是说，第k级索引的结点个数就是第k - 1级索引的结点个数的1 / 2，那第k级索引结点的个数就是n / (2 ^ k)。

假设索引有h级，最高级的索引有2个结点，则n / (2 ^ h) = 2，即h = logn - 1。加上原始链表这一层，整个跳表的高度就是logn。在跳表中查询某个数据的时候，如果每一层都要遍历m个结点，那在跳表中查询一个数据的时间复杂度就是O(m * logn)。

按照每两个结点提取一个结点到上一级建立索引这种数据结构，每一级索引都最多只需要遍历3个结点，那么m = 3。

假设要查找的数据是x，在第k级索引中遍历到y结点之后，发现x大于y，小于后面的结点z，所以通过y的down指针，从第k级索引下降到第k - 1级索引。在第k - 1级索引中，y和z之间只有3个结点（包含y和z），所以在k - 1级索引中最多只需要遍历3个结点，依此类推，每一级索引都最多只需要遍历3个结点。

所以在跳表中查询任意数据的时间复杂度就是O(logn)。

跳表的空间复杂度分析

假设原始链表大小为n，那第一级索引大约有n / 2个结点，第二级索引大约有n / 4个结点，以此类推，每上升一级就减少一半，直到剩下2个结点。每层索引的结点数为：
n / 2, n / 4, n / 8, ..., 8, 4, 2
这几级索引的结点总和就是 n / 2 + n / 4 + n / 8 + ... + 8 + 4 + 2 = n - 2。所以跳表的空间复杂度是O(n)。

将包含n个结点的单链表构造成跳表，需要额外再用接近n个结点的存储空间。

如果每三个结点或五个结点，抽一个结点到上级索引：

那第一级索引需要大约n / 3个结点，第二级索引需要大约n / 9个结点。每往上一级，索引结点个数都除以3。为了方便计算，假设最高一级的索引结点个数是1。每3个结点抽一个，每层索引的结点数为：
n / 3, n / 9, n / 27, ..., 9, 3, 1
总的索引结点个数为n / 3 + n / 9 + n / 27 + ...+ 9 + 3 + 1 = n / 2。空间复杂度依然是O(n)，但比每两个结点抽一个结点的索引构建方法，减少了一半的索引结点存储空间。

在实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。

跳表动态的插入和删除

跳表插入、删除操作的时间复杂度是O(logn)。

对于删除操作，如果这个结点在索引中也有出现，删除原始链表中的结点之后还要删除对应的索引。

查找要删除的结点的时候，一定要获取前驱结点。（双向链表不需要考虑这个问题）

跳表索引动态更新

不停地往跳表中插入数据时，如果不更新索引，就有可能出现某2个索引结点之间数据非常多的情况。极端情况下，跳表还会退化成单链表。

作为一种动态数据结构，需要某种手段来维护索引与原始链表大小之间的平衡：

如果链表中结点多了，索引结点就相应地增加一些，避免复杂度退化，以及查找、插入、删除操作性能下降。

往跳表中插入数据的时候，可以同时将这个数据插入到部分索引层中。通过一个随机函数，来决定将这个结点插入到哪几级索引中，比如随机函数生成了值k，就将这个结点添加到第一级到第k级索引中。

Redis用跳表实现有序集合

Redis中的有序集合是通过跳表来实现的，严格点讲，其实还用到了散列表。

Redis中的有序集合支持的核心操作主要有：

• 插入一个数据；
• 删除一个数据；
• 查找一个数据；
• 按照区间查找数据；
• 迭代输出有序序列。

其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表一样的。但是，按区间来查找数据这个操作，红黑树的效率没有跳表高。

对于按照区间查找数据这个操作，跳表可以做到O(logn)的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了，这样做非常高效。

跳表相对红黑树而言代码更容易实现，简单就意味着可读性好，不容易出错。还有，跳表更加灵活，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗。

跳表的简易代码实现

public class SkipList {

  private static final float SKIPLIST_P = 0.5f;
  private static final int MAX_LEVEL = 16;

  private int levelCount = 1;

  private Node cls = new Node();  // 带头链表

  public Node find(int value) {
    Node p = cls;
    for (int i = levelCount - 1; i >= 0; --i) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
    }

    if (p.forwards[0] != null && p.forwards[0].data == value) {
      return p.forwards[0];
    } else {
      return null;
    }
  }

  public void insert(int value) {
    int level = randomLevel();
    Node newNode = new Node();
    newNode.data = value;
    newNode.maxLevel = level;
    Node update[] = new Node[level];
    for (int i = 0; i < level; ++i) {
      update[i] = cls;
    }

    // record every level largest value which smaller than insert value in update[]
    Node p = cls;
    for (int i = level - 1; i >= 0; --i) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
      update[i] = p;// use update save node in search path
    }

    // in search path node next node become new node forwords(next)
    for (int i = 0; i < level; ++i) {
      newNode.forwards[i] = update[i].forwards[i];
      update[i].forwards[i] = newNode;
    }

    // update node hight
    if (levelCount < level) levelCount = level;
  }

  public void delete(int value) {
    Node[] update = new Node[levelCount];
    Node p = cls;
    for (int i = levelCount - 1; i >= 0; --i) {
      while (p.forwards[i] != null && p.forwards[i].data < value) {
        p = p.forwards[i];
      }
      update[i] = p;
    }

    if (p.forwards[0] != null && p.forwards[0].data == value) {
      for (int i = levelCount - 1; i >= 0; --i) {
        if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
          update[i].forwards[i] = update[i].forwards[i].forwards[i];
        }
      }
    }

    while (levelCount>1&&cls.forwards[levelCount]==null){
      levelCount--;
    }

  }

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

    while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)
      level += 1;
    return level;
  }

  public void printAll() {
    Node p = cls;
    while (p.forwards[0] != null) {
      System.out.print(p.forwards[0] + " ");
      p = p.forwards[0];
    }
    System.out.println();
  }

  public class Node {
    private int data = -1;
    private Node forwards[] = new Node[MAX_LEVEL];
    private int maxLevel = 0;

    @Override
    public String toString() {
      StringBuilder builder = new StringBuilder();
      builder.append("{ data: ");
      builder.append(data);
      builder.append("; levels: ");
      builder.append(maxLevel);
      builder.append(" }");

      return builder.toString();
    }
  }

}