Java實(shí)現(xiàn)跳躍表(skiplist)的簡單實(shí)例

更新時(shí)間：2017年09月18日 09:32:12 作者：lhever_的博客

這篇文章主要介紹了Java編程中跳躍表的概念和實(shí)現(xiàn)原理，并簡要敘述了它的結(jié)構(gòu)，具有一定參考價(jià)值，需要的朋友可以了解下。

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

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

實(shí)現(xiàn)原理：

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

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

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

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

public class SkipListEntry<v>
{
 public String key;
 public V value;
 public int pos; // 主要為了打印 鏈表用
 public SkipListEntry<v deep="6"> up, down, left, right; // 上下左右 四個(gè)指針
 public static String negInf = new String("-oo"); // 負(fù)無窮
 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<v> entry;
  try
  {
   entry = (SkipListEntry<v>) o; // 檢測類型
  } catch (ClassCastException ex)
  {
   return false;
  }
  return (entry.getKey() == key) && (entry.getValue().equals(value));
 }
 public String toString()
 {
  return "(" + key + "," + value + ")";
 }
}

2 Skip List的具體實(shí)現(xiàn)（包含增、刪、改、查）

import java.util.Random;
/**
 * 跳表的一種簡單實(shí)現(xiàn)。key只能為字符串類型，value可以為任意對象類型
 * @param <v>
 * @author xxx 2017年2月14日 下午9:42:06
 * @version v1.0
 */
public class SkipList<v>
{
 public SkipListEntry<v> head; // 頂層的第一個(gè)元素
 public SkipListEntry<v> tail; // 頂層的最后一個(gè)元素
 public int size; // 跳躍表中的元素個(gè)數(shù)
 public int height; // 跳躍表的高度
 public Random flag; // 投擲硬幣
 /**
  * 默認(rèn)構(gòu)造函數(shù)
  * @author xxx 2017年2月14日 下午9:32:22
  * @since v1.0
  */
 public SkipList() 
 {
  head = new SkipListEntry<v>(SkipListEntry.negInf, null);
  tail = new SkipListEntry<v>(SkipListEntry.posInf, null);
  head.right = tail;
  tail.left = head;
  size = 0;
  height = 0;
  flag = new Random();
 }
 /**
  * 返回元素的個(gè)數(shù)
  * @return
  * @author xxx 2017年2月14日 下午9:35:22
  * @since v1.0
  */
 public int size()
 {
  return size;
 }
  /**
  * 判斷跳表中的元素個(gè)數(shù)是否為零
  * @return
  * @author xxx 2017年2月14日 下午9:35:52
  * @since v1.0
  */
 public boolean isEmpty()
 {
  return (size == 0);
 }
 /**
  * 從最頂層的第一個(gè)元素，也即head元素開始查找，直到找到第0層、要插入的位置前面的那個(gè)key
  * @param k
  * @return
  * @author xxx 2017年2月14日 下午9:42:12
  * @since v1.0
  */
 private SkipListEntry<v> findEntry(String k)
 {
  SkipListEntry<v> p = head;
  while (true)
  {
   /*
    * 一直向右找，例: k=34。 10 ---> 20 ---> 30 ---> 40 ^ | p 會(huì)在30處停止
    */
   while (p.right.key != SkipListEntry.posInf && p.right.key.compareTo(k) <= 0)
   {
    p = p.right;
   }
   // 如果還有下一層，就到下一層繼續(xù)查找
   if (p.down != null)
   {
    p = p.down;
   } else
   {
    break; // 到了最下面一層 就停止查找
   }
  }
  return p; // p.key <= k
 }
 /** 返回和key綁定的值 */
 public V get(String k)
 {
  SkipListEntry<v> p = findEntry(k);
 
  if (k.equals(p.getKey()))
  {
   return p.value;
  } else
  {
   return null;
  }
 }
 /**
  * 往跳表中插入一個(gè)鍵值對，如果鍵已經(jīng)存在，則覆蓋相應(yīng)的值并返回舊值
  * @param k
  * @param v
  * @return
  * @author xxx 2017年2月14日 下午9:48:54
  * @since v1.0
  */
 public V put(String k, V v)
 {
  System.out.println("-----插入[" + k + "]之前的跳躍表是:-----");
  printHorizontal();
 
  SkipListEntry<v> p, q;
 
  p = findEntry(k);
 
  if (k.equals(p.getKey()))
  {
   V old = p.value;
   p.value = v;
   return old;
  }
  q = new SkipListEntry<v>(k, v);
  q.left = p;
  q.right = p.right;
  p.right.left = q;
  p.right = q;
  int currentLevel = 0; // 當(dāng)前層 currentLevel = 0
  // 隨機(jī)值小于0.5，則插入的鍵值對對應(yīng)的鍵需要在上一層建立關(guān)聯(lián)，同時(shí)有可能增加跳表的高度
  while (flag.nextDouble() < 0.5)
  {
   // 如果超出了高度，需要重新建一個(gè)頂層
   if (currentLevel >= height)
   {
    SkipListEntry<v> p1, p2;
    height = height + 1;
    p1 = new SkipListEntry<v>(SkipListEntry.negInf, null);
    p2 = new SkipListEntry<v>(SkipListEntry.posInf, null);
    p1.right = p2;
    p1.down = head;
    p2.left = p1;
    p2.down = tail;
    head.up = p1;
    tail.up = p2;
    head = p1;
    tail = p2;
   }
   while (p.up == null)
   {
    p = p.left;
   }
   p = p.up;
 
   SkipListEntry<v> e;
   /*
    * 注意，本實(shí)現(xiàn)中只有第0層的鏈表持有鍵對應(yīng)的值，1 ~ height 層中的SkipListEntry對象
    * 僅僅持有鍵的引用，值為空，以便節(jié)省空間。
    */
   e = new SkipListEntry<v>(k, null);
   e.left = p;
   e.right = p.right;
   e.down = q;
   p.right.left = e;
   p.right = e;
   q.up = e;
 
   q = e; // q 進(jìn)行下一層迭代
   currentLevel = currentLevel + 1; // 當(dāng)前層 +1
  }
  // 插入一個(gè)鍵值對后總數(shù)加1
  size = size + 1;
 
  System.out.println("-----插入[" + k + "]之后的跳躍表是:-----");
  printHorizontal();
  return null;
 }
 /**
  * 根據(jù)鍵刪除鍵值對
  * @param key
  * @return
  * @author xxx 2017年2月14日 下午10:08:17
  * @since v1.0
  */
 public void remove(String key)
 {
  SkipListEntry<v> p = findEntry(key);
 
  if(!p.getKey().equals(key)) {
   return;
  }
  //刪除元素后重新關(guān)聯(lián)，同時(shí)使被刪除的對象游離，便于垃圾回收
  p.left.right = p.right;
  p.right.left = p.left;
  p.right = null;
  p.left = null;
  //自底向上，使所有鍵等于key的SkipListEntry對象左右兩個(gè)方向的引用置空
  while(p.up != null) {
   p = p.up;
   p.left.right = p.right;
   p.right.left = p.left;
   p.right = null;
   p.left = null;
  }
  //自頂向下，使所有鍵等于key的SkipListEntry對象上下兩個(gè)方向的引用置空
  while(p.down != null) {
   SkipListEntry<v> temp = p.down;
   p.down = null;
   temp.up = null;
   p = temp;
  }
  /*
   * 刪除元素后，如果頂層的鏈表只有head和tail兩個(gè)元素，則刪除頂層。
   * 刪除頂層以后最新的頂層如果依然只有head和tail兩個(gè)元素，則也要被刪除，以此類推。
   */
  while(head.right.key == tail.key && height > 0) {
   SkipListEntry<v> p1, p2;
   p1 = head.down;
   p2 = tail.down;
   head.right = null;
   head.down = null;
   tail.left = null;
   tail.down = null;
   p1.up = null;
   p2.up = null;
   head = p1;
   tail = p2;
   height = height - 1;
  }
  //成功移除一個(gè)元素，大小減1
  size = size - 1;
  System.out.println("-----刪除[" + key + "]后的跳躍表是:-----");
  printHorizontal();
 }
 /**
  * 打印出跳表的圖示結(jié)構(gòu)(水平方向)
  * @author xxx 2017年2月14日 下午10:35:36
  * @since v1.0
  */
 public void printHorizontal()
 {
  String s = "";
  int i;
  SkipListEntry<v> p;
  p = head;
  while (p.down != null)
  {
   p = p.down;
  }
  i = 0;
  while (p != null)
  {
   p.pos = i++;
   p = p.right;
  }
  p = head;
  while (p != null)
  {
   s = getOneRow(p);
   System.out.println(s);
   p = p.down;
  }
 }
 private String getOneRow(SkipListEntry<v> p)
 {
  String s;
  int a, b, i;
  a = 0;
  s = "" + p.key;
  p = p.right;
  while (p != null)
  {
   SkipListEntry<v> q;
   q = p;
   while (q.down != null)
    q = q.down;
   b = q.pos;
   s = s + " <-";
   for (i = a + 1; i < b; i++)
    s = s + "--------";
   s = s + "> " + p.key;
   a = b;
   p = p.right;
  }
  return s;
 }
 /**
  * 打印出跳表的圖示結(jié)構(gòu)(垂直方向)
  * @author xxx 2017年2月14日 下午10:35:36
  * @since v1.0
  */
 public void printVertical()
 {
  String s = "";
  SkipListEntry<v> p;
  p = head;
  while (p.down != null)
   p = p.down;
  while (p != null)
  {
   s = getOneColumn(p);
   System.out.println(s);
   p = p.right;
  }
 }
 private String getOneColumn(SkipListEntry<v> p)
 {
  String s = "";
  while (p != null)
  {
   s = s + " " + p.key;
   p = p.up;
  }
  return (s);
 }
}

3 測試

public class Test
{
 public static void main(String[] args)
 {
  SkipList<String> s = new SkipList<String>();
  s.put("ABC", "");
  s.put("DEF", "");
  s.put("KLM", "");
  s.put("HIJ", "");
  s.put("GHJ", "");
  s.put("AAA", "");
  s.remove("ABC");
  s.remove("DEF");
  s.remove("KLM");
  s.remove("HIJ");
  s.remove("GHJ");
  s.remove("AAA");
  s.put("ABC", "");
  s.put("DEF", "");
  s.put("KLM", "");
  s.put("HIJ", "");
  s.put("GHJ", "");
  s.put("AAA", "");
 }
}
//運(yùn)行測試后結(jié)果示例如下（注意：由于跳表的特性，每次運(yùn)行結(jié)果都不一樣）

-----插入[ABC]之前的跳躍表是:-----
-oo <-> +oo
-----插入[ABC]之后的跳躍表是:-----
-oo <-> ABC <-> +oo
-oo <-> ABC <-> +oo
-----插入[DEF]之前的跳躍表是:-----
-oo <-> ABC <-> +oo
-oo <-> ABC <-> +oo
-----插入[DEF]之后的跳躍表是:-----
-oo <---------> DEF <-> +oo
-oo <-> ABC <-> DEF <-> +oo
-oo <-> ABC <-> DEF <-> +oo
-----插入[KLM]之前的跳躍表是:-----
-oo <---------> DEF <-> +oo
-oo <-> ABC <-> DEF <-> +oo
-oo <-> ABC <-> DEF <-> +oo
-----插入[KLM]之后的跳躍表是:-----
-oo <---------> DEF <-> KLM <-> +oo
-oo <-> ABC <-> DEF <-> KLM <-> +oo
-oo <-> ABC <-> DEF <-> KLM <-> +oo
-----插入[HIJ]之前的跳躍表是:-----
-oo <---------> DEF <-> KLM <-> +oo
-oo <-> ABC <-> DEF <-> KLM <-> +oo
-oo <-> ABC <-> DEF <-> KLM <-> +oo
-----插入[HIJ]之后的跳躍表是:-----
-oo <---------> DEF <---------> KLM <-> +oo
-oo <-> ABC <-> DEF <---------> KLM <-> +oo
-oo <-> ABC <-> DEF <-> HIJ <-> KLM <-> +oo
-----插入[GHJ]之前的跳躍表是:-----
-oo <---------> DEF <---------> KLM <-> +oo
-oo <-> ABC <-> DEF <---------> KLM <-> +oo
-oo <-> ABC <-> DEF <-> HIJ <-> KLM <-> +oo
-----插入[GHJ]之后的跳躍表是:-----
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <---------> DEF <-> GHJ <---------> KLM <-> +oo
-oo <-> ABC <-> DEF <-> GHJ <---------> KLM <-> +oo
-oo <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo
-----插入[AAA]之前的跳躍表是:-----
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <---------> DEF <-> GHJ <---------> KLM <-> +oo
-oo <-> ABC <-> DEF <-> GHJ <---------> KLM <-> +oo
-oo <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo
-----插入[AAA]之后的跳躍表是:-----
-oo <-------------------------> GHJ <-----------------> +oo
-oo <-------------------------> GHJ <-----------------> +oo
-oo <-------------------------> GHJ <-----------------> +oo
-oo <-------------------------> GHJ <-----------------> +oo
-oo <-------------------------> GHJ <-----------------> +oo
-oo <-> AAA <-----------------> GHJ <-----------------> +oo
-oo <-> AAA <---------> DEF <-> GHJ <---------> KLM <-> +oo
-oo <-> AAA <-> ABC <-> DEF <-> GHJ <---------> KLM <-> +oo
-oo <-> AAA <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo
-----刪除[ABC]后的跳躍表是:-----
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-----------------> GHJ <-----------------> +oo
-oo <-> AAA <---------> GHJ <-----------------> +oo
-oo <-> AAA <-> DEF <-> GHJ <---------> KLM <-> +oo
-oo <-> AAA <-> DEF <-> GHJ <---------> KLM <-> +oo
-oo <-> AAA <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo
-----刪除[DEF]后的跳躍表是:-----
-oo <---------> GHJ <-----------------> +oo
-oo <---------> GHJ <-----------------> +oo
-oo <---------> GHJ <-----------------> +oo
-oo <---------> GHJ <-----------------> +oo
-oo <---------> GHJ <-----------------> +oo
-oo <-> AAA <-> GHJ <-----------------> +oo
-oo <-> AAA <-> GHJ <---------> KLM <-> +oo
-oo <-> AAA <-> GHJ <---------> KLM <-> +oo
-oo <-> AAA <-> GHJ <-> HIJ <-> KLM <-> +oo
-----刪除[KLM]后的跳躍表是:-----
-oo <---------> GHJ <---------> +oo
-oo <---------> GHJ <---------> +oo
-oo <---------> GHJ <---------> +oo
-oo <---------> GHJ <---------> +oo
-oo <---------> GHJ <---------> +oo
-oo <-> AAA <-> GHJ <---------> +oo
-oo <-> AAA <-> GHJ <---------> +oo
-oo <-> AAA <-> GHJ <---------> +oo
-oo <-> AAA <-> GHJ <-> HIJ <-> +oo
-----刪除[HIJ]后的跳躍表是:-----
-oo <---------> GHJ <-> +oo
-oo <---------> GHJ <-> +oo
-oo <---------> GHJ <-> +oo
-oo <---------> GHJ <-> +oo
-oo <---------> GHJ <-> +oo
-oo <-> AAA <-> GHJ <-> +oo
-oo <-> AAA <-> GHJ <-> +oo
-oo <-> AAA <-> GHJ <-> +oo
-oo <-> AAA <-> GHJ <-> +oo
-----刪除[GHJ]后的跳躍表是:-----
-oo <-> AAA <-> +oo
-oo <-> AAA <-> +oo
-oo <-> AAA <-> +oo
-oo <-> AAA <-> +oo
-----刪除[AAA]后的跳躍表是:-----
-oo <-> +oo
-----插入[ABC]之前的跳躍表是:-----
-oo <-> +oo
-----插入[ABC]之后的跳躍表是:-----
-oo <-> ABC <-> +oo
-----插入[DEF]之前的跳躍表是:-----
-oo <-> ABC <-> +oo
-----插入[DEF]之后的跳躍表是:-----
-oo <---------> DEF <-> +oo
-oo <---------> DEF <-> +oo
-oo <---------> DEF <-> +oo
-oo <---------> DEF <-> +oo
-oo <-> ABC <-> DEF <-> +oo
-----插入[KLM]之前的跳躍表是:-----
-oo <---------> DEF <-> +oo
-oo <---------> DEF <-> +oo
-oo <---------> DEF <-> +oo
-oo <---------> DEF <-> +oo
-oo <-> ABC <-> DEF <-> +oo
-----插入[KLM]之后的跳躍表是:-----
-oo <---------> DEF <---------> +oo
-oo <---------> DEF <---------> +oo
-oo <---------> DEF <---------> +oo
-oo <---------> DEF <---------> +oo
-oo <-> ABC <-> DEF <-> KLM <-> +oo
-----插入[HIJ]之前的跳躍表是:-----
-oo <---------> DEF <---------> +oo
-oo <---------> DEF <---------> +oo
-oo <---------> DEF <---------> +oo
-oo <---------> DEF <---------> +oo
-oo <-> ABC <-> DEF <-> KLM <-> +oo
-----插入[HIJ]之后的跳躍表是:-----
-oo <---------> DEF <-----------------> +oo
-oo <---------> DEF <-----------------> +oo
-oo <---------> DEF <-----------------> +oo
-oo <---------> DEF <-> HIJ <---------> +oo
-oo <-> ABC <-> DEF <-> HIJ <-> KLM <-> +oo
-----插入[GHJ]之前的跳躍表是:-----
-oo <---------> DEF <-----------------> +oo
-oo <---------> DEF <-----------------> +oo
-oo <---------> DEF <-----------------> +oo
-oo <---------> DEF <-> HIJ <---------> +oo
-oo <-> ABC <-> DEF <-> HIJ <-> KLM <-> +oo
-----插入[GHJ]之后的跳躍表是:-----
-oo <---------> DEF <-------------------------> +oo
-oo <---------> DEF <-------------------------> +oo
-oo <---------> DEF <-------------------------> +oo
-oo <---------> DEF <---------> HIJ <---------> +oo
-oo <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo
-----插入[AAA]之前的跳躍表是:-----
-oo <---------> DEF <-------------------------> +oo
-oo <---------> DEF <-------------------------> +oo
-oo <---------> DEF <-------------------------> +oo
-oo <---------> DEF <---------> HIJ <---------> +oo
-oo <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo
-----插入[AAA]之后的跳躍表是:-----
-oo <-----------------> DEF <-------------------------> +oo
-oo <-----------------> DEF <-------------------------> +oo
-oo <-----------------> DEF <-------------------------> +oo
-oo <-----------------> DEF <---------> HIJ <---------> +oo
-oo <-> AAA <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo

總結(jié)

以上所述就是本文關(guān)于Java編程實(shí)現(xiàn)一個(gè)簡單的跳躍表的實(shí)現(xiàn)方法實(shí)例，希望對大家有所幫助，感謝大家對本站的支持！

您可能感興趣的文章: