什么是跳表

跳表全稱為跳躍列表褒颈，它允許快速查詢，插入和刪除一個(gè)有序連續(xù)元素的數(shù)據(jù)鏈表励堡。跳躍列表的平均查找和插入時(shí)間復(fù)雜度都是O(logn)谷丸。快速查詢是通過維護(hù)一個(gè)多層次的鏈表应结，且每一層鏈表中的元素是前一層鏈表元素的子集（見右邊的示意圖）刨疼。一開始時(shí)，算法在最稀疏的層次進(jìn)行搜索鹅龄，直至需要查找的元素在該層兩個(gè)相鄰的元素中間揩慕。這時(shí)，算法將跳轉(zhuǎn)到下一個(gè)層次扮休，重復(fù)剛才的搜索漩绵，直到找到需要查找的元素為止。

image

一張?zhí)S列表的示意圖肛炮。每個(gè)帶有箭頭的框表示一個(gè)指針, 而每行是一個(gè)稀疏子序列的鏈表止吐；底部的編號(hào)框（黃色）表示有序的數(shù)據(jù)序列。查找從頂部最稀疏的子序列向下進(jìn)行, 直至需要查找的元素在該層兩個(gè)相鄰的元素中間侨糟。

跳表的演化過程

對(duì)于單鏈表來說碍扔，即使數(shù)據(jù)是已經(jīng)排好序的，想要查詢其中的一個(gè)數(shù)據(jù)秕重，只能從頭開始遍歷鏈表不同，這樣效率很低，時(shí)間復(fù)雜度很高，是 O(n)二拐。
那我們有沒有什么辦法來提高查詢的效率呢服鹅？我們可以為鏈表建立一個(gè)“索引”，這樣查找起來就會(huì)更快百新，如下圖所示企软，我們?cè)谠兼湵淼幕A(chǔ)上，每?jī)蓚€(gè)結(jié)點(diǎn)提取一個(gè)結(jié)點(diǎn)建立索引饭望，我們把抽取出來的結(jié)點(diǎn)叫做索引層或者索引仗哨，down 表示指向原始鏈表結(jié)點(diǎn)的指針。

image

通過這個(gè)例子我們可以看出來，通過建立一個(gè)索引層媚狰，我們查找一個(gè)基點(diǎn)需要遍歷的次數(shù)變少了岛杀，也就是查詢的效率提高了。

那么如果我們給索引層再加一層索引呢崭孤？遍歷的結(jié)點(diǎn)會(huì)不會(huì)更少呢类嗤，效率會(huì)不會(huì)更高呢？我們?cè)囋嚲椭懒恕?/p>

image

現(xiàn)在我們?cè)賮聿檎?15辨宠，我們從第二級(jí)索引開始遗锣，最后找到 15，一共遍歷了 6 個(gè)結(jié)點(diǎn)嗤形，果然效率更高精偿。

當(dāng)然，因?yàn)槲覀兣e的這個(gè)例子數(shù)據(jù)量很小，所以效率提升的不是特別明顯笔咽，如果數(shù)據(jù)量非常大的時(shí)候搔预，我們多建立幾層索引，效率提升的將會(huì)非常的明顯叶组，感興趣的可以自己試一下拯田，這里我們就不舉例子了。

這種通過對(duì)鏈表加多級(jí)索引的機(jī)構(gòu)扶叉，就是跳表了勿锅。

跳表具體有多快

通過上邊的例子我們知道，跳表的查詢效率比鏈表高枣氧，那具體高多少呢溢十？下面我們一起來看一下。

衡量一個(gè)算法的效率我們可以用時(shí)間復(fù)雜度达吞，這里我們也用時(shí)間復(fù)雜度來比較一下鏈表和跳表张弛。前面我們已經(jīng)講過了，鏈表的查詢的時(shí)間復(fù)雜度為 O(n)酪劫，那跳表的呢吞鸭？

如果一個(gè)鏈表有 n 個(gè)結(jié)點(diǎn)，如果每?jī)蓚€(gè)結(jié)點(diǎn)抽取出一個(gè)結(jié)點(diǎn)建立索引的話覆糟，那么第一級(jí)索引的結(jié)點(diǎn)數(shù)大約就是 n/2刻剥，第二級(jí)索引的結(jié)點(diǎn)數(shù)大約為 n/4，以此類推第 m 級(jí)索引的節(jié)點(diǎn)數(shù)大約為 n/(2^m)滩字。

假如一共有 m 級(jí)索引造虏，第 m 級(jí)的結(jié)點(diǎn)數(shù)為兩個(gè)，通過上邊我們找到的規(guī)律麦箍，那么得出 n/(2^m)=2漓藕，從而求得 m=log(n)-1。如果加上原始鏈表挟裂，那么整個(gè)跳表的高度就是 log(n)享钞。我們?cè)诓樵兲淼臅r(shí)候，如果每一層都需要遍歷 k 個(gè)結(jié)點(diǎn)诀蓉，那么最終的時(shí)間復(fù)雜度就為 O(k*log(n))栗竖。

那這個(gè) k 值為多少呢，按照我們每?jī)蓚€(gè)結(jié)點(diǎn)提取一個(gè)基點(diǎn)建立索引的情況渠啤，我們每一級(jí)最多需要遍歷兩個(gè)個(gè)結(jié)點(diǎn)狐肢，所以 k=2。為什么每一層最多遍歷兩個(gè)結(jié)點(diǎn)呢埃篓？

因?yàn)槲覀兪敲績(jī)蓚€(gè)結(jié)點(diǎn)提取一個(gè)結(jié)點(diǎn)建立索引处坪，最高一級(jí)索引只有兩個(gè)結(jié)點(diǎn)，然后下一層索引比上一層索引兩個(gè)結(jié)點(diǎn)之間增加了一個(gè)結(jié)點(diǎn)，也就是上一層索引兩結(jié)點(diǎn)的中值同窘，看到這里是不是想起來我們前邊講過的二分查找玄帕，每次我們只需要判斷要找的值在不在當(dāng)前結(jié)點(diǎn)和下一個(gè)結(jié)點(diǎn)之間即可。

image

如上圖所示想邦，我們要查詢紅色結(jié)點(diǎn)裤纹，我們查詢的路線即黃線表示出的路徑查詢，每一級(jí)最多遍歷兩個(gè)結(jié)點(diǎn)即可丧没。

所以跳表的查詢?nèi)我鈹?shù)據(jù)的時(shí)間復(fù)雜度為 O(2*log(n))鹰椒，前邊的常數(shù) 2 可以忽略，為 O(log(n))呕童。

跳表是用空間來?yè)Q時(shí)間

跳表的效率比鏈表高了漆际，但是跳表需要額外存儲(chǔ)多級(jí)索引，所以需要的更多的內(nèi)存空間夺饲。

跳表的空間復(fù)雜度分析并不難奸汇，如果一個(gè)鏈表有 n 個(gè)結(jié)點(diǎn)，如果每?jī)蓚€(gè)結(jié)點(diǎn)抽取出一個(gè)結(jié)點(diǎn)建立索引的話往声，那么第一級(jí)索引的結(jié)點(diǎn)數(shù)大約就是 n/2擂找，第二級(jí)索引的結(jié)點(diǎn)數(shù)大約為 n/4，以此類推第 m 級(jí)索引的節(jié)點(diǎn)數(shù)大約為 n/(2^m)浩销，我們可以看出來這是一個(gè)等比數(shù)列贯涎。

這幾級(jí)索引的結(jié)點(diǎn)總和就是 n/2+n/4+n/8…+8+4+2=n-2，所以跳表的空間復(fù)雜度為 o(n)慢洋。

那么我們有沒有辦法減少索引所占的內(nèi)存空間呢塘雳？可以的，我們可以每三個(gè)結(jié)點(diǎn)抽取一個(gè)索引且警，或者沒五個(gè)結(jié)點(diǎn)抽取一個(gè)索引粉捻。這樣索引結(jié)點(diǎn)的數(shù)量減少了礁遣，所占的空間也就少了斑芜。

跳表的插入和刪除

我們想要為跳表插入或者刪除數(shù)據(jù)，我們首先需要找到插入或者刪除的位置祟霍，然后執(zhí)行插入或刪除操作杏头，前邊我們已經(jīng)知道了，跳表的查詢的時(shí)間復(fù)雜度為 O(logn）沸呐，因?yàn)檎业轿恢弥蟛迦牒蛣h除的時(shí)間復(fù)雜度很低醇王，為 O(1)，所以最終插入和刪除的時(shí)間復(fù)雜度也為 O(longn)崭添。

我么通過圖看一下插入的過程寓娩。

image

刪除操作的話，如果這個(gè)結(jié)點(diǎn)在索引中也有出現(xiàn)，我們除了要?jiǎng)h除原始鏈表中的結(jié)點(diǎn)棘伴，還要?jiǎng)h除索引中的寞埠。因?yàn)閱捂湵碇械膭h除操作需要拿到要?jiǎng)h除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，然后通過指針操作完成刪除焊夸。所以在查找要?jiǎng)h除的結(jié)點(diǎn)的時(shí)候仁连，一定要獲取前驅(qū)結(jié)點(diǎn)。當(dāng)然阱穗，如果我們用的是雙向鏈表饭冬，就不需要考慮這個(gè)問題了。

如果我們不停的向跳表中插入元素揪阶，就可能會(huì)造成兩個(gè)索引點(diǎn)之間的結(jié)點(diǎn)過多的情況昌抠。結(jié)點(diǎn)過多的話，我們建立索引的優(yōu)勢(shì)也就沒有了鲁僚。所以我們需要維護(hù)索引與原始鏈表的大小平衡扰魂，也就是結(jié)點(diǎn)增多了，索引也相應(yīng)增加蕴茴，避免出現(xiàn)兩個(gè)索引之間結(jié)點(diǎn)過多的情況劝评，查找效率降低。

跳表是通過一個(gè)隨機(jī)函數(shù)來維護(hù)這個(gè)平衡的倦淀，當(dāng)我們向跳表中插入數(shù)據(jù)的的時(shí)候蒋畜，我們可以選擇同時(shí)把這個(gè)數(shù)據(jù)插入到索引里，那我們插入到哪一級(jí)的索引呢撞叽，這就需要隨機(jī)函數(shù)姻成，來決定我們插入到哪一級(jí)的索引中。

這樣可以很有效的防止跳表退化愿棋，而造成效率變低科展。

跳表的代碼實(shí)現(xiàn)

最后我們來看一下跳變用代碼怎么實(shí)現(xiàn)。

package skiplist;

import java.util.Random;

/**
 * 跳表的一種實(shí)現(xiàn)方法糠雨。
 * 跳表中存儲(chǔ)的是正整數(shù)才睹，并且存儲(chǔ)的是不重復(fù)的。
 */
public class SkipList {

  private static final int MAX_LEVEL = 16;

  private int levelCount = 1;

  private Node head = new Node();  // 帶頭鏈表

  private Random r = new Random();

  public Node find(int value) {
    Node p = head;
    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] = head;
    }

    // record every level largest value which smaller than insert value in update[]
    Node p = head;
    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 = head;
    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];
        }
      }
    }
  }

  // 隨機(jī) level 次甘邀，如果是奇數(shù)層數(shù) +1琅攘，防止偽隨機(jī)
 private int randomLevel() {
    int level = 1;
    for (int i = 1; i < MAX_LEVEL; ++i) {
      if (r.nextInt() % 2 == 1) {
        level++;
      }
    }

    return level;
  }

  public void printAll() {
    Node p = head;
    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();
    }
  }

}