跳表（skip list）java實(shí)現(xiàn)
WiKi
【轉(zhuǎn)載】http://blog.csdn.net/brillianteagle/article/details/52206261
Skip list是一個(gè)用于有序元素序列快速搜索的數(shù)據(jù)結(jié)構(gòu)，由美國(guó)計(jì)算機(jī)科學(xué)家William Pugh發(fā)明于1989年趴乡。它的效率和紅黑樹(shù)以及 AVL 樹(shù)不相上下含末，但實(shí)現(xiàn)起來(lái)比較容易贬堵。作者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是一個(gè)“概率型”的數(shù)據(jù)結(jié)構(gòu)屈扎，可以在很多應(yīng)用場(chǎng)景中替代平衡樹(shù)此蜈。Skip list算法與平衡樹(shù)相比抠璃，有相似的漸進(jìn)期望時(shí)間邊界塔沃，但是它更簡(jiǎn)單腰奋，更快单起，使用更少的空間。
Skip list是一個(gè)分層結(jié)構(gòu)多級(jí)鏈表劣坊，最下層是原始的鏈表馏臭，每個(gè)層級(jí)都是下一個(gè)層級(jí)的“高速跑道”。
跳躍的表的性質(zhì)包括：
某個(gè)i層的元素，出現(xiàn)在i+1層的概率p是固定的括儒，例如常取p=1/2或p=1/4绕沈；
平均來(lái)講，每個(gè)元素出現(xiàn)在1/(1-p)個(gè)鏈表中帮寻；
最高的元素乍狐，例如head通常采用Int.MIN_VALUE作為的最小值，會(huì)出現(xiàn)在每一層鏈表中固逗；
跳躍表的空間復(fù)雜度為O(n)贝攒，插入刪除的時(shí)間復(fù)雜度是
相關(guān)資料
Skip list的維基百科；
《算法導(dǎo)論》網(wǎng)易公開(kāi)課Skip list梨熙。
跳躍表的構(gòu)建
這里描述一下網(wǎng)易公開(kāi)課《算法導(dǎo)論》“跳躍表”這一節(jié)的內(nèi)容开镣。
空的跳躍表頭尾相連的雙向鏈表。
向鏈表中放入key-value咽扇，假如key是1邪财。
此時(shí)，不斷投擲硬幣质欲，如果是反面树埠，則不提升該節(jié)點(diǎn)，停止投擲硬幣把敞；否則不斷提升該節(jié)點(diǎn)弥奸，并且垂直方向進(jìn)行節(jié)點(diǎn)連接。
如果上一步?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……,所以某一個(gè)節(jié)點(diǎn)提升很多層的概率是很低的。這也是為什么說(shuō)跳躍表是一種概率型數(shù)據(jù)結(jié)構(gòu)的來(lái)源谍婉。
跳躍表的查詢(xún)也比較簡(jiǎn)單舒憾。例如要查找key是3的節(jié)點(diǎn)，則從最上層開(kāi)始查找穗熬，直到找到大于或等于3的位置镀迂，然后返回上一個(gè)節(jié)點(diǎn)，再往下一層繼續(xù)向右尋找唤蔗。例如三層的跳躍表查詢(xún)路徑如下探遵。
這樣，就跳過(guò)了很多節(jié)點(diǎn)措译，所以叫做“跳躍表”别凤。
Java實(shí)現(xiàn)
這里參考了“跳躍表(Skip List)-實(shí)現(xiàn)(Java)”饰序，將其更改為模版形式领虹，并多處進(jìn)行了重構(gòu)。
節(jié)點(diǎn)類(lèi)
/**
* 跳躍表的節(jié)點(diǎn),包括key-value和上下左右4個(gè)指針
* 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; // 上下左右 四個(gè)指針
public static final int HEAD_KEY = Integer.MIN_VALUE; // 負(fù)無(wú)窮
public static final int TAIL_KEY = Integer.MAX_VALUE; // 正無(wú)窮
public SkipListNode(int k,T v) {
// TODO Auto-generated constructor stub
key = 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; // 檢測(cè)類(lèi)型
} catch (ClassCastException ex) {
return false;
}
return (ent.getKey() == key) && (ent.getValue() == value);
}
@Override
public String toString() {
// TODO Auto-generated method stub
return "key-value:"+key+"-"+value;
}
}
跳躍表實(shí)現(xiàn)塌衰。
import java.util.Random;
/**
* 不固定層級(jí)的跳躍表
* 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é)點(diǎn)總數(shù)
private int listLevel;//層數(shù)
private Random random;// 用于投擲硬幣
private static final double PROBABILITY=0.5;//向上提升一個(gè)的概率
public SkipList() {
// TODO Auto-generated constructor stub
random=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;
}
/**
* 在最下面一層蝠嘉，找到要插入的位置前面的那個(gè)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;
}
/**
* 查找是否存儲(chǔ)key最疆，存在則返回該節(jié)點(diǎn)，否則返回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值相同蚤告，替換原來(lái)的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)前所在的層級(jí)是0
//拋硬幣
while (random.nextDouble()<PROBABILITY) {
//如果超出了高度努酸，需要重新建一個(gè)頂層
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移動(dòng)到上一層
while (p.up==null) {
p=p.left;
}
p=p.up;
SkipListNode<T> e=new SkipListNode<T>(k, null);//只保存key就ok
backLink(p, e);//將e插入到p的后面
vertiacallLink(e, q);//將e和q上下連接
q=e;
currentLevel++;
}
nodes++;//層數(shù)遞增
}
//node1后面插入node2
private 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ù)
* */
@Override
public String toString() {
// TODO Auto-generated method stub
if (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();
}
}
下面進(jìn)行一下測(cè)試杜恰。
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
SkipList<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");//測(cè)試同一個(gè)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获诈。
有序的情況下：
? 在非多線(xiàn)程的情況下，應(yīng)當(dāng)盡量使用TreeMap（紅黑樹(shù)實(shí)現(xiàn)）心褐。
? 對(duì)于并發(fā)性相對(duì)較低的并行程序可以使用Collections.synchronizedSortedMap將TreeMap進(jìn)行包裝舔涎，也可以提供較好的效率。但是對(duì)于高并發(fā)程序逗爹，應(yīng)當(dāng)使用ConcurrentSkipListMap亡嫌。
無(wú)序情況下：
? 并發(fā)程度低，數(shù)據(jù)量大時(shí)，ConcurrentHashMap 存取遠(yuǎn)大于ConcurrentSkipListMap挟冠。
? 數(shù)據(jù)量一定于购，并發(fā)程度高時(shí)，ConcurrentSkipListMap比ConcurrentHashMap效率更高知染。
