跳躍鏈表是一種隨機化數(shù)據(jù)結(jié)構(gòu)，基于并聯(lián)的鏈表，其效率可比擬于二叉查找樹(對于大多數(shù)操作需要O(log n)平均時間)，并且對并發(fā)算法友好。

創(chuàng)新互聯(lián)公司是一家專注于做網(wǎng)站、成都網(wǎng)站設(shè)計與策劃設(shè)計,甘南網(wǎng)站建設(shè)哪家好?創(chuàng)新互聯(lián)公司做網(wǎng)站,專注于網(wǎng)站建設(shè)10余年,網(wǎng)設(shè)計領(lǐng)域的專業(yè)建站公司;建站業(yè)務(wù)涵蓋:甘南等地區(qū)。甘南做網(wǎng)站價格咨詢:18982081108

基本上，跳躍列表是對有序的鏈表增加上附加的前進鏈接，增加是以隨機化的方式進行的，所以在列表中的查找可以快速的跳過部分列表(因此得名)。所有操作都以對數(shù)隨機化的時間進行。

實現(xiàn)原理：

跳躍表的結(jié)構(gòu)是：假如底層有10個節(jié)點， 那么底層的上一層理論上就有5個節(jié)點，再上一層理論上就有2個或3個節(jié)點，再上一層理論上就有1個節(jié)點。所以從這里可以看出每一層的節(jié)點個數(shù)為其下一層的1/2個元素，以此類推。從這里我們可以看到，從插入時我們只要保證上一層的元素個數(shù)為下一層元素個數(shù)的1/2，我們的跳躍表就能成為理想的跳躍表。那么怎么才能保證我們插入時上層元素個數(shù)是下層元素個數(shù)的1/2呢，？很簡單 拋硬幣就可以解決了，假設(shè)元素X要插入跳躍表，最底層是肯定要插入X的，那么次低層要不要插入呢，我們希望上層元素個數(shù)是下層的1/2，那么我們有1/2的概率要插入到次低層，這樣就來拋硬幣吧，正面就插入，反面就不插入，次次底層相對于次低層，我們還是有1/2的概率插入，那么就繼續(xù)拋硬幣吧 ， 以此類推元，素X插入第n層的概率是(1/2)的n次。這樣，我們能在跳躍表中插入一個元素了。

第一次知道跳表這種數(shù)據(jù)結(jié)構(gòu)的時間大概是在一年前（說這句話時候可能就被無數(shù)同胞鄙視了），但自己卻不知道如何實現(xiàn)。當(dāng)時印象最深的就是一篇跳躍表(Skip List)-實現(xiàn)(Java)的文章，因為這篇文章中的Skip List的實現(xiàn)方式最讓人容易理解，我最初也是通過這篇文章對跳表有了更進一步的認識，所以，真的要在這里感謝這篇文章的主人。一年之后，我發(fā)現(xiàn)自己對跳表的認識又模糊不清了，所以最先想到的也是這篇文章。今天再次拜讀此文，同時實現(xiàn)了其中未給出的刪除方法。并增加了泛型，但泛型也只是對value采用了泛型，對Key依然采用原文中的String類型。所以依然比較簡單和局限。之所以貼出來，是為了增進自己對Skip List的理解和作為備忘。原文的鏈接如之前所述，原文具體作者其實我也不知道是誰，只想在此默默的說聲感謝。當(dāng)然了，若原文作者覺得我有什么冒犯或侵權(quán)的行為，我會立馬刪帖。

關(guān)于跳表的定義和介紹，讀者可以參考原文。這里就直接給出原碼了，這里的原碼與原文的唯一的一點區(qū)別就是，我這里給出了原文沒給出的刪除方法（原文其實參考的是一篇英文文章，英文文章給出了刪除方法，我直到后來才發(fā)現(xiàn)，不過自己的實現(xiàn)和英文文章想比，代碼略顯多余，此處貼出來的是我自己實現(xiàn)的刪除方法）?？赡軐崿F(xiàn)上比較糟糕，所以也懇請大家批評指正?。。?/p>

1 對跳表中各個元素（鍵值對）的封裝類SkipListEntry.java

public class SkipListEntry
{
 public String key;
 public V value;
 public int pos; // 主要為了打印 鏈表用
 public SkipListEntry up, down, left, right; // 上下左右 四個指針
 public static String negInf = new String("-oo"); // 負無窮
 public static String posInf = new String("+oo"); // 正無窮
 public SkipListEntry(String k, V v)
 {
  key = k;
  value = v;
  up = down = left = right = null;
 }
 public V getValue()
 {
  return value;
 }
 public String getKey()
 {
  return key;
 }
 public V setValue(V val)
 {
  V oldValue = value;
  value = val;
  return oldValue;
 }
 @SuppressWarnings("unchecked")
 public boolean equals(Object o)
 {
  SkipListEntry entry;
  try
  {
   entry = (SkipListEntry) o; // 檢測類型
  } catch (ClassCastException ex)
  {
   return false;
  }
  return (entry.getKey() == key) && (entry.getValue().equals(value));
 }
 public String toString()
 {
  return "(" + key + "," + value + ")";
 }
}

分享文章：Java實現(xiàn)跳躍表(skiplist)的簡單實例-創(chuàng)新互聯(lián)
文章位置：http://weahome.cn/article/dhpjdh.html