數(shù)據(jù)結(jié)構(gòu)與算法--跳表

跳表 = 鏈表 + 多級索引

跳表使用空間換時間的設(shè)計思路，通過構(gòu)建多級索引來提高查詢的效率煮落，實現(xiàn)了基于鏈表的“二分查找”民轴。跳表是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)攻柠，支持快讀的插入、刪除后裸、查找操作瑰钮，時間復(fù)雜度都是O(logn)。

跳表跳表的空間復(fù)雜度是O(n)微驶。跳表的實現(xiàn)非常靈活浪谴，可以通過改變索引構(gòu)建策略，有效平衡執(zhí)行效率和內(nèi)存消耗因苹。跳表的代碼比起紅黑樹來說苟耻，要簡單、易讀扶檐。

鏈表加多級索引的結(jié)構(gòu)凶杖，就是跳表。

對于一個單鏈表款筑，即便鏈表中存儲的數(shù)據(jù)是有序的智蝠，如果要查找某個數(shù)據(jù)，也只能從頭到尾遍歷奈梳，時間復(fù)雜度是O(n)杈湾。

對于鏈表建立一級“索引”，沒兩個結(jié)點提取一個結(jié)點到上一級攘须，把抽出來的那一級叫做索引或索引層漆撞。圖中的 down表示down指針，指向下一級結(jié)點于宙。

這樣就可以先在索引層遍歷浮驳，然后通過索引層結(jié)點的down指針，下降到原始鏈表這一層捞魁，繼續(xù)遍歷抹恳。

比如要查找16，當(dāng)在索引層遍歷到13時署驻，發(fā)現(xiàn)索引層下一個結(jié)點是17大于目標(biāo)16奋献，則可從13的down指針下降到原始鏈表繼續(xù)遍歷健霹。這樣只需要再遍歷2個結(jié)點，就可以找到值等于16的這個結(jié)點了瓶蚂。原來查找16糖埋，需要遍歷10個結(jié)點，加入一層索引后只需要遍歷7個結(jié)點窃这。

加上一層索引之后瞳别，查找一個結(jié)點需要遍歷的結(jié)點個數(shù)減少了，查找效率提高了杭攻。繼續(xù)再加一級索引祟敛，在第一級索引的基礎(chǔ)之上，每兩個結(jié)點就抽出一個結(jié)點到第二級索引≌捉猓現(xiàn)在再查找16馆铁，只需要遍歷6個結(jié)點了，需要遍歷的結(jié)點數(shù)量又減少了锅睛。

下圖是一個包含64個結(jié)點的鏈表埠巨，建立五級索引。

在五級索引的作用下现拒，查找62只需要遍歷11個結(jié)點辣垒。當(dāng)鏈表的長度n比較大時，比如1000印蔬、10000的時候勋桶，在構(gòu)建多級索引之后，查找效率的提升就會非常明顯侥猬。

跳表的時間復(fù)雜度

一個鏈表里有n個結(jié)點例驹，每兩個結(jié)點會抽出一個結(jié)點作為上一級索引的結(jié)點，那第一級索引的結(jié)點個數(shù)大約就是n / 2陵究，第二級索引的結(jié)點個數(shù)大約就是n / 4，第三級索引的結(jié)點個數(shù)大約就是n / 8奥帘，依此類推铜邮，也就是說，第k級索引的結(jié)點個數(shù)就是第k - 1級索引的結(jié)點個數(shù)的1 / 2寨蹋，那第k級索引結(jié)點的個數(shù)就是n / (2 ^ k)松蒜。

假設(shè)索引有h級，最高級的索引有2個結(jié)點已旧，則n / (2 ^ h) = 2秸苗，即h = logn - 1。加上原始鏈表這一層运褪，整個跳表的高度就是logn惊楼。在跳表中查詢某個數(shù)據(jù)的時候玖瘸，如果每一層都要遍歷m個結(jié)點，那在跳表中查詢一個數(shù)據(jù)的時間復(fù)雜度就是O(m * logn)檀咙。

按照每兩個結(jié)點提取一個結(jié)點到上一級建立索引這種數(shù)據(jù)結(jié)構(gòu)雅倒，每一級索引都最多只需要遍歷3個結(jié)點，那么m = 3弧可。

假設(shè)要查找的數(shù)據(jù)是x蔑匣，在第k級索引中遍歷到y(tǒng)結(jié)點之后，發(fā)現(xiàn)x大于y棕诵，小于后面的結(jié)點z裁良，所以通過y的down指針，從第k級索引下降到第k - 1級索引校套。在第k - 1級索引中价脾，y和z之間只有3個結(jié)點（包含y和z），所以在k - 1級索引中最多只需要遍歷3個結(jié)點搔确，依此類推彼棍，每一級索引都最多只需要遍歷3個結(jié)點。

所以在跳表中查詢?nèi)我鈹?shù)據(jù)的時間復(fù)雜度就是O(logn)膳算。

跳表的空間復(fù)雜度分析

假設(shè)原始鏈表大小為n座硕，那第一級索引大約有n / 2個結(jié)點，第二級索引大約有n / 4個結(jié)點涕蜂，以此類推华匾，每上升一級就減少一半，直到剩下2個結(jié)點机隙。每層索引的結(jié)點數(shù)為：
n / 2, n / 4, n / 8, ..., 8, 4, 2
這幾級索引的結(jié)點總和就是 n / 2 + n / 4 + n / 8 + ... + 8 + 4 + 2 = n - 2蜘拉。所以跳表的空間復(fù)雜度是O(n)。

將包含n個結(jié)點的單鏈表構(gòu)造成跳表有鹿，需要額外再用接近n個結(jié)點的存儲空間旭旭。

如果每三個結(jié)點或五個結(jié)點，抽一個結(jié)點到上級索引：

那第一級索引需要大約n / 3個結(jié)點葱跋，第二級索引需要大約n / 9個結(jié)點持寄。每往上一級，索引結(jié)點個數(shù)都除以3娱俺。為了方便計算稍味，假設(shè)最高一級的索引結(jié)點個數(shù)是1。每3個結(jié)點抽一個荠卷，每層索引的結(jié)點數(shù)為：
n / 3, n / 9, n / 27, ..., 9, 3, 1
總的索引結(jié)點個數(shù)為n / 3 + n / 9 + n / 27 + ...+ 9 + 3 + 1 = n / 2模庐。空間復(fù)雜度依然是O(n)油宜，但比每兩個結(jié)點抽一個結(jié)點的索引構(gòu)建方法掂碱，減少了一半的索引結(jié)點存儲空間怜姿。

在實際的軟件開發(fā)中，原始鏈表中存儲的有可能是很大的對象顶吮，而索引結(jié)點只需要存儲關(guān)鍵值和幾個指針社牲，并不需要存儲對象，所以當(dāng)對象比索引結(jié)點大很多時悴了，那索引占用的額外空間就可以忽略了搏恤。

跳表動態(tài)的插入和刪除

跳表插入、刪除操作的時間復(fù)雜度是O(logn)湃交。

對于刪除操作熟空，如果這個結(jié)點在索引中也有出現(xiàn)，刪除原始鏈表中的結(jié)點之后還要刪除對應(yīng)的索引搞莺。

查找要刪除的結(jié)點的時候息罗，一定要獲取前驅(qū)結(jié)點。（雙向鏈表不需要考慮這個問題）

跳表索引動態(tài)更新

不停地往跳表中插入數(shù)據(jù)時才沧，如果不更新索引迈喉，就有可能出現(xiàn)某2個索引結(jié)點之間數(shù)據(jù)非常多的情況。極端情況下温圆，跳表還會退化成單鏈表挨摸。

作為一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，需要某種手段來維護(hù)索引與原始鏈表大小之間的平衡：

如果鏈表中結(jié)點多了岁歉，索引結(jié)點就相應(yīng)地增加一些得运，避免復(fù)雜度退化，以及查找锅移、插入熔掺、刪除操作性能下降。

往跳表中插入數(shù)據(jù)的時候非剃，可以同時將這個數(shù)據(jù)插入到部分索引層中置逻。通過一個隨機函數(shù)，來決定將這個結(jié)點插入到哪幾級索引中备绽，比如隨機函數(shù)生成了值k券坞，就將這個結(jié)點添加到第一級到第k級索引中。

Redis用跳表實現(xiàn)有序集合

Redis中的有序集合是通過跳表來實現(xiàn)的疯坤，嚴(yán)格點講报慕，其實還用到了散列表深浮。

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

插入一個數(shù)據(jù)压怠；
刪除一個數(shù)據(jù)；
查找一個數(shù)據(jù)飞苇；
按照區(qū)間查找數(shù)據(jù)菌瘫；
迭代輸出有序序列蜗顽。

其中，插入雨让、刪除雇盖、查找以及迭代輸出有序序列這幾個操作，紅黑樹也可以完成栖忠，時間復(fù)雜度跟跳表一樣的崔挖。但是，按區(qū)間來查找數(shù)據(jù)這個操作庵寞，紅黑樹的效率沒有跳表高狸相。

對于按照區(qū)間查找數(shù)據(jù)這個操作，跳表可以做到O(logn)的時間復(fù)雜度定位區(qū)間的起點捐川，然后在原始鏈表中順序往后遍歷就可以了脓鹃，這樣做非常高效。

跳表相對紅黑樹而言代碼更容易實現(xiàn)古沥，簡單就意味著可讀性好瘸右，不容易出錯。還有岩齿，跳表更加靈活太颤，它可以通過改變索引構(gòu)建策略，有效平衡執(zhí)行效率和內(nèi)存消耗纯衍。

跳表的簡易代碼實現(xiàn)

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--;
    }

  }

  // 理論來講栋齿，一級索引中元素個數(shù)應(yīng)該占原始數(shù)據(jù)的 50%，二級索引中元素個數(shù)占 25%襟诸，三級索引12.5% 瓦堵，一直到最頂層。
  // 因為這里每一層的晉升概率是 50%歌亲。對于每一個新插入的節(jié)點菇用，都需要調(diào)用 randomLevel 生成一個合理的層數(shù)。
  // 該 randomLevel 方法會隨機生成 1~MAX_LEVEL 之間的數(shù)陷揪，且 ：
  //        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();
    }
  }

}