轉(zhuǎn)載自?【算法導(dǎo)論33】跳躍表（Skip list）原理與java實現(xiàn)

Skip list是一個用于有序元素序列快速搜索的數(shù)據(jù)結(jié)構(gòu)，由美國計算機科學(xué)家William Pugh發(fā)明于1989年。它的效率和紅黑樹以及 AVL 樹不相上下，但實現(xiàn)起來比較容易。作者William Pugh是這樣介紹Skip list的：?
Skip lists are a probabilistic data structure that seem likely to supplant balanced trees as the implementation method of choice for many applications. Skip list algorithms have the same asymptotic expected time bounds as balanced trees and are simpler, faster and use less space.?
Skip list是一個“概率型”的數(shù)據(jù)結(jié)構(gòu)，可以在很多應(yīng)用場景中替代平衡樹。Skip list算法與平衡樹相比，有相似的漸進期望時間邊界，但是它更簡單，更快，使用更少的空間。?
Skip list是一個分層結(jié)構(gòu)多級鏈表，最下層是原始的鏈表，每個層級都是下一個層級的“高速跑道”。?
?
跳躍的表的性質(zhì)包括：?
某個i層的元素，出現(xiàn)在i+1層的概率p是固定的，例如常取p=1/2或p=1/4；?
平均來講，每個元素出現(xiàn)在1/(1-p)個鏈表中；?
最高的元素，例如head通常采用Int.MIN_VALUE作為的最小值，會出現(xiàn)在每一層鏈表中；?
原始的鏈表元素如果是n，則鏈表最多層。例如，p=1/2時，層數(shù)為。?
跳躍表的空間復(fù)雜度為O(n)，插入刪除的時間復(fù)雜度是。例如，p=1/2時，復(fù)雜度為。

相關(guān)資料

Skip list的維基百科；?
《算法導(dǎo)論》網(wǎng)易公開課Skip list。

跳躍表的構(gòu)建

這里描述一下網(wǎng)易公開課《算法導(dǎo)論》“跳躍表”這一節(jié)的內(nèi)容。?
空的跳躍表頭尾相連的雙向鏈表。

向鏈表中放入key-value，假如key是1。?

此時，不斷投擲硬幣，如果是反面，則不提升該節(jié)點，停止投擲硬幣；否則不斷提升該節(jié)點，并且垂直方向進行節(jié)點連接。?

如果上一步?jīng)]有提升，再插入key-value，key等于2，然后不斷投擲硬幣，發(fā)現(xiàn)是投了一次正面，需要提升一次。但第二次投的是反面，不再提升。?

再插入key-value，key等于3，然后不斷投擲硬幣，發(fā)現(xiàn)第一次就投了反面，不提升。?

這樣的規(guī)則一直持續(xù)下去。由于連續(xù)投正面的概率是0.5，0.5*0.5……,所以某一個節(jié)點提升很多層的概率是很低的。這也是為什么說跳躍表是一種概率型數(shù)據(jù)結(jié)構(gòu)的來源。?
跳躍表的查詢也比較簡單。例如要查找key是3的節(jié)點，則從最上層開始查找，直到找到大于或等于3的位置，然后返回上一個節(jié)點，再往下一層繼續(xù)向右尋找。例如三層的跳躍表查詢路徑如下。?

這樣，就跳過了很多節(jié)點，所以叫做“跳躍表”。

Java實現(xiàn)

這里參考了“跳躍表(Skip List)-實現(xiàn)(Java)”，將其更改為模版形式，并多處進行了重構(gòu)。?

節(jié)點類

/*** 跳躍表的節(jié)點,包括key-value和上下左右4個指針* created by 曹艷豐，2016-08-14* 參考：http://www.acmerblog.com/skip-list-impl-java-5773.html* */ public class SkipListNode <T>{public int key;public T value;public SkipListNode<T> up, down, left, right; // 上下左右 四個指針public static final int HEAD_KEY = Integer.MIN_VALUE; // 負無窮public static final int TAIL_KEY = Integer.MAX_VALUE; // 正無窮public SkipListNode(int k,T v) {// TODO Auto-generated constructor stubkey = k;value = v;}public int getKey() {return key;}public void setKey(int key) {this.key = key;}public T getValue() {return value;}public void setValue(T value) {this.value = value;}public boolean equals(Object o) {if (this==o) {return true;}if (o==null) {return false;}if (!(o instanceof SkipListNode<?>)) {return false;}SkipListNode<T> ent;try {ent = (SkipListNode<T>) o; // 檢測類型} catch (ClassCastException ex) {return false;}return (ent.getKey() == key) && (ent.getValue() == value);}@Overridepublic String toString() {// TODO Auto-generated method stubreturn "key-value:"+key+"-"+value;} }

跳躍表實現(xiàn)。

import java.util.Random;/*** 不固定層級的跳躍表* created by 曹艷豐，2016-08-14* 參考：http://www.acmerblog.com/skip-list-impl-java-5773.html* */ public class SkipList <T>{private SkipListNode<T> head,tail;private int nodes;//節(jié)點總數(shù)private int listLevel;//層數(shù)private Random random;// 用于投擲硬幣private static final double PROBABILITY=0.5;//向上提升一個的概率public SkipList() {// TODO Auto-generated constructor stubrandom=new Random();clear();}/***清空跳躍表* */public void clear(){head=new SkipListNode<T>(SkipListNode.HEAD_KEY, null);tail=new SkipListNode<T>(SkipListNode.TAIL_KEY, null);horizontalLink(head, tail);listLevel=0;nodes=0;}public boolean isEmpty(){return nodes==0;}public int size() {return nodes;}/*** 在最下面一層，找到要插入的位置前面的那個key* */private SkipListNode<T> findNode(int key){SkipListNode<T> p=head;while(true){while (p.right.key!=SkipListNode.TAIL_KEY&&p.right.key<=key) {p=p.right;}if (p.down!=null) {p=p.down;}else {break;}}return p;}/*** 查找是否存儲key，存在則返回該節(jié)點，否則返回null* */public SkipListNode<T> search(int key){SkipListNode<T> p=findNode(key);if (key==p.getKey()) {return p;}else {return null;}}/*** 向跳躍表中添加key-value* * */public void put(int k,T v){SkipListNode<T> p=findNode(k);//如果key值相同，替換原來的vaule即可結(jié)束if (k==p.getKey()) {p.value=v;return;}SkipListNode<T> q=new SkipListNode<T>(k, v);backLink(p, q);int currentLevel=0;//當(dāng)前所在的層級是0//拋硬幣while (random.nextDouble()<PROBABILITY) {//如果超出了高度，需要重新建一個頂層if (currentLevel>=listLevel) {listLevel++;SkipListNode<T> p1=new SkipListNode<T>(SkipListNode.HEAD_KEY, null);SkipListNode<T> p2=new SkipListNode<T>(SkipListNode.TAIL_KEY, null);horizontalLink(p1, p2);vertiacallLink(p1, head);vertiacallLink(p2, tail);head=p1;tail=p2;}//將p移動到上一層while (p.up==null) {p=p.left;}p=p.up;SkipListNode<T> e=new SkipListNode<T>(k, null);//只保存key就okbackLink(p, e);//將e插入到p的后面vertiacallLink(e, q);//將e和q上下連接q=e;currentLevel++;}nodes++;//層數(shù)遞增}//node1后面插入node2private void backLink(SkipListNode<T> node1,SkipListNode<T> node2){node2.left=node1;node2.right=node1.right;node1.right.left=node2;node1.right=node2;}/*** 水平雙向連接* */private void horizontalLink(SkipListNode<T> node1,SkipListNode<T> node2){node1.right=node2;node2.left=node1;}/*** 垂直雙向連接* */private void vertiacallLink(SkipListNode<T> node1,SkipListNode<T> node2){node1.down=node2;node2.up=node1;}/*** 打印出原始數(shù)據(jù)* */@Overridepublic String toString() {// TODO Auto-generated method stubif (isEmpty()) {return "跳躍表為空！";}StringBuilder builder=new StringBuilder();SkipListNode<T> p=head;while (p.down!=null) {p=p.down;}while (p.left!=null) {p=p.left;}if (p.right!=null) {p=p.right;}while (p.right!=null) {builder.append(p);builder.append("\n");p=p.right;}return builder.toString();}}

下面進行一下測試。

public class Main {public static void main(String[] args) {// TODO Auto-generated method stubSkipList<String> list=new SkipList<String>();System.out.println(list);list.put(2, "yan");list.put(1, "co");list.put(3, "feng");list.put(1, "cao");//測試同一個key值list.put(4, "曹");list.put(6, "豐");list.put(5, "艷");System.out.println(list);System.out.println(list.size());} }

Java中的跳躍表

Java API中提供了支持并發(fā)操作的跳躍表ConcurrentSkipListSet和ConcurrentSkipListMap。下面摘錄”Java多線程（四）之ConcurrentSkipListMap深入分析“中的一些結(jié)論。?
有序的情況下：?
? 在非多線程的情況下，應(yīng)當(dāng)盡量使用TreeMap（紅黑樹實現(xiàn)）。?
? 對于并發(fā)性相對較低的并行程序可以使用Collections.synchronizedSortedMap將TreeMap進行包裝，也可以提供較好的效率。但是對于高并發(fā)程序，應(yīng)當(dāng)使用ConcurrentSkipListMap。?
無序情況下：?
? 并發(fā)程度低，數(shù)據(jù)量大時，ConcurrentHashMap 存取遠大于ConcurrentSkipListMap。?
? 數(shù)據(jù)量一定，并發(fā)程度高時，ConcurrentSkipListMap比ConcurrentHashMap效率更高。

總結(jié)

以上是生活随笔為你收集整理的跳跃表（Skip list）原理与java实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。