Java實現(xiàn)跳躍表(skiplist)的簡單實例
跳躍鏈表是一種隨機化數(shù)據(jù)結(jié)構(gòu),基于并聯(lián)的鏈表,其效率可比擬于二叉查找樹(對于大多數(shù)操作需要O(log n)平均時間),并且對并發(fā)算法友好。
基本上,跳躍列表是對有序的鏈表增加上附加的前進鏈接,增加是以隨機化的方式進行的,所以在列表中的查找可以快速的跳過部分列表(因此得名)。所有操作都以對數(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)。當時印象最深的就是一篇跳躍表(Skip List)-實現(xiàn)(Java)的文章,因為這篇文章中的Skip List的實現(xiàn)方式最讓人容易理解,我最初也是通過這篇文章對跳表有了更進一步的認識,所以,真的要在這里感謝這篇文章的主人。一年之后,我發(fā)現(xiàn)自己對跳表的認識又模糊不清了,所以最先想到的也是這篇文章。今天再次拜讀此文,同時實現(xiàn)了其中未給出的刪除方法。并增加了泛型,但泛型也只是對value采用了泛型,對Key依然采用原文中的String類型。所以依然比較簡單和局限。之所以貼出來,是為了增進自己對Skip List的理解和作為備忘。原文的鏈接如之前所述,原文具體作者其實我也不知道是誰,只想在此默默的說聲感謝。當然了,若原文作者覺得我有什么冒犯或侵權(quán)的行為,我會立馬刪帖。
關(guān)于跳表的定義和介紹,讀者可以參考原文。這里就直接給出原碼了,這里的原碼與原文的唯一的一點區(qū)別就是,我這里給出了原文沒給出的刪除方法(原文其實參考的是一篇英文文章,英文文章給出了刪除方法,我直到后來才發(fā)現(xiàn),不過自己的實現(xiàn)和英文文章想比,代碼略顯多余,此處貼出來的是我自己實現(xiàn)的刪除方法)??赡軐崿F(xiàn)上比較糟糕,所以也懇請大家批評指正?。?!
1 對跳表中各個元素(鍵值對)的封裝類SkipListEntry.java
public class SkipListEntry<v>
{
public String key;
public V value;
public int pos; // 主要為了打印 鏈表用
public SkipListEntry<v deep="6"> 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<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的具體實現(xiàn)(包含增、刪、改、查 )
import java.util.Random;
/**
* 跳表的一種簡單實現(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; // 頂層的第一個元素
public SkipListEntry<v> tail; // 頂層的最后一個元素
public int size; // 跳躍表中的元素個數(shù)
public int height; // 跳躍表的高度
public Random flag; // 投擲硬幣
/**
* 默認構(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();
}
/**
* 返回元素的個數(shù)
* @return
* @author xxx 2017年2月14日 下午9:35:22
* @since v1.0
*/
public int size()
{
return size;
}
/**
* 判斷跳表中的元素個數(shù)是否為零
* @return
* @author xxx 2017年2月14日 下午9:35:52
* @since v1.0
*/
public boolean isEmpty()
{
return (size == 0);
}
/**
* 從最頂層的第一個元素,也即head元素開始查找,直到找到第0層、要插入的位置前面的那個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 會在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;
}
}
/**
* 往跳表中插入一個鍵值對,如果鍵已經(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; // 當前層 currentLevel = 0
// 隨機值小于0.5,則插入的鍵值對對應(yīng)的鍵需要在上一層建立關(guān)聯(lián),同時有可能增加跳表的高度
while (flag.nextDouble() < 0.5)
{
// 如果超出了高度,需要重新建一個頂層
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;
/*
* 注意,本實現(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 進行下一層迭代
currentLevel = currentLevel + 1; // 當前層 +1
}
// 插入一個鍵值對后總數(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),同時使被刪除的對象游離,便于垃圾回收
p.left.right = p.right;
p.right.left = p.left;
p.right = null;
p.left = null;
//自底向上,使所有鍵等于key的SkipListEntry對象左右兩個方向的引用置空
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對象上下兩個方向的引用置空
while(p.down != null) {
SkipListEntry<v> temp = p.down;
p.down = null;
temp.up = null;
p = temp;
}
/*
* 刪除元素后,如果頂層的鏈表只有head和tail兩個元素,則刪除頂層。
* 刪除頂層以后最新的頂層如果依然只有head和tail兩個元素,則也要被刪除,以此類推。
*/
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;
}
//成功移除一個元素,大小減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", "");
}
}
//運行測試后結(jié)果示例如下(注意:由于跳表的特性,每次運行結(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編程實現(xiàn)一個簡單的跳躍表的實現(xiàn)方法實例,希望對大家有所幫助,感謝大家對本站的支持!
相關(guān)文章
Java 實現(xiàn)多線程切換等待喚醒交替打印奇偶數(shù)
這篇文章主要介紹了Java 實現(xiàn)多線程切換等待喚醒交替打印奇偶數(shù) ,本文通過實例代碼給大家介紹的非常詳細,具有一定的參考借鑒價值,需要的朋友可以參考下2019-05-05
SpringBoot中實現(xiàn)Redis緩存預(yù)熱
緩存預(yù)熱是一種在系統(tǒng)啟動后,但在實際使用前將數(shù)據(jù)加載到緩存中的技術(shù),本文主要來和大家一起探討如何在Spring Boot應(yīng)用程序中實現(xiàn)Redis緩存預(yù)熱,以確保系統(tǒng)在處理請求前就已經(jīng)處于最佳狀態(tài),感興趣的可以了解下2023-11-11
詳解Java如何優(yōu)雅的調(diào)用dubbo同時不使用其它jar包
這篇文章主要介紹了如何在不使用他人jar包的情況下優(yōu)雅的進行dubbo調(diào)用,文中通過示例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)吧2023-02-02
Seata?AT獲取數(shù)據(jù)表元數(shù)據(jù)源碼詳解
這篇文章主要為大家介紹了Seata?AT獲取數(shù)據(jù)表元數(shù)據(jù)源碼詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2022-11-11

