SkipList 跳表的原理以及實(shí)現(xiàn)
一、概念
何為跳表呢？
我們先維基百科對(duì)其定義繼續(xù)剖析：
跳躍列表是一種數(shù)據(jù)結(jié)構(gòu)。它允許快速查詢(xún)一個(gè)有序連續(xù)元素的數(shù)據(jù)鏈表,而其快速查詢(xún)是通過(guò)維護(hù)一個(gè)多層次的鏈表，且每一層鏈表中的元素是前一層鏈表元素的子集。
一開(kāi)始時(shí)，算法在最稀疏的層次進(jìn)行搜索，直至需要查找的元素在該層兩個(gè)相鄰的元素中間。這時(shí)，算法將跳轉(zhuǎn)到下一個(gè)層次，重復(fù)剛才的搜索，直到找到需要查找的元素為止。跳過(guò)的元素的方法可以是隨機(jī)性選擇或確定性選擇，其中前者更為常見(jiàn)。
什么意思呢？
我們知道二分法查詢(xún)是依賴(lài)數(shù)組的隨機(jī)訪問(wèn)，也只能應(yīng)用于數(shù)組結(jié)構(gòu)，而鏈表基于｀二分法查詢(xún)｀類(lèi)似的查詢(xún)也就成了我們所講的跳表結(jié)構(gòu)。
其原理就是對(duì)有序的鏈表增加上附加的前進(jìn)鏈接，增加是以隨機(jī)化的方式進(jìn)行的，所以在列表中的查找可以快速的跳過(guò)部分列表，因此得名。所有操作都以對(duì)數(shù)隨機(jī)化的時(shí)間進(jìn)行。
跳表最底層是一個(gè)全量的有序鏈表，上層可以說(shuō)是下層的“快速跑道”
二、性質(zhì)
（1）由很多層結(jié)構(gòu)組成；
（2）每一層都是一個(gè)有序的鏈表；
（3）最底層(Level 1)的鏈表包含所有元素；
（4）如果一個(gè)元素出現(xiàn)在 Level i 的鏈表中，則它在 Level i 之下的鏈表也都會(huì)出現(xiàn)；
（5）每個(gè)節(jié)點(diǎn)包含兩個(gè)指針，一個(gè)指向同一鏈表中的下一個(gè)元素，一個(gè)指向下面一層的元素。
三、實(shí)現(xiàn)
（一）初始化
// 構(gòu)建一個(gè)跳表節(jié)點(diǎn)屬性
private static class SkipListNode<T>{
T val; 
SkipListNode<T> next,down; 
double sorce;
SkipListNode(){}
SkipListNode(T val,double sorce){
this.val = val;
this.sorce =sorce;
}
}
// 層數(shù)
private int level = 0;
// 頂層節(jié)點(diǎn)
private SkipListNode<T> top;
public SkipList(int level){
this.level=level;
int i = level;
SkipListNode<T> temp = null;
SkipListNode<T> pre = null;
while (i--!==0){
temp = new SkipListNode<T>(null,Double.MIN_VALUE);
temp.down = pre;
pre = temp;
}
top = temp;
}
（二）查找
public T get(double socre){
SkipListNode<T> t = top;
while (t!=null){
if(t.sorce==socre){
return t.val;
}
if(t.next==null){
if(t.down!=null){
t = t.down;
continue;
}else {
return null;
}
}
if(t.next.sorce>socre){
t = t.down;
}else {
t = t.next;
}
}
return null;
}
（三）插入
public void put(double socre,T val){
//1，找到需要插入的位置
SkipListNode<T> t = top, cur = null;//若cur不為空，表示當(dāng)前score值的節(jié)點(diǎn)存在
List<SkipListNode<T>> path = new ArrayList<>();//記錄每一層當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)
while (t != null) {
if (t.score == score) {
cur = t;
break;//表示存在該值的點(diǎn)，表示需要更新該節(jié)點(diǎn)
}
if (t.next == null) {
path.add(t);//需要向下查找，先記錄該節(jié)點(diǎn)
if (t.down != null) {
t = t.down;
continue;
} else {
break;
}
}
if (t.next.score > score) {
path.add(t);//需要向下查找，先記錄該節(jié)點(diǎn)
if (t.down == null) {
break;
}
t = t.down;
} else
t = t.next;
}
if (cur != null) {
while (cur != null) {
cur.val = val;
cur = cur.down;
}
} else {//當(dāng)前表中不存在score值的節(jié)點(diǎn)，需要從下到上插入
int lev = getRandomLevel();
if (lev > level) {//需要更新top這一列的節(jié)點(diǎn)數(shù)量，同時(shí)需要在path中增加這些新的首節(jié)點(diǎn)
SkipListNode<T> temp = null;
SkipListNode<T> prev = top;//前驅(qū)節(jié)點(diǎn)現(xiàn)在是top了
while (level++ != lev) {
temp = new SkipNode<T>(null, Double.MIN_VALUE);
path.add(0, temp);//加到path的首部
temp.down = prev;
prev = temp;
}
top = temp;//頭節(jié)點(diǎn)
level = lev;//level長(zhǎng)度增加到新的長(zhǎng)度
}
//從后向前遍歷path中的每一個(gè)節(jié)點(diǎn)，在其后面增加一個(gè)新的節(jié)點(diǎn)
SkipListNode<T> downTemp = null, temp = null, prev = null;
// System.out.println("當(dāng)前深度為"+level+",當(dāng)前path長(zhǎng)度為"+path.size());
for (int i = level - 1; i >= level - lev; i--) {
temp = new SkipNode<T>(val, score);
prev = path.get(i);
temp.next = prev.next;
prev.next = temp;
temp.down = downTemp;
downTemp = temp;
}
}
}
private int getRandomLevel(){
int lev = 1;
while (random.nextInt() % 2 == 0)
lev++;
return lev;
}
（四）刪除
public void delete(double sorce){
SkipListNode<T> t = top;
while (t != null) {
if (t.next == null) {
t = t.down;
continue;
}
if (t.next.score == score) {
// 在這里說(shuō)明找到了該刪除的節(jié)點(diǎn)
t.next = t.next.next;
t = t.down;
//刪除當(dāng)前節(jié)點(diǎn)后，還需要繼續(xù)查找之后需要?jiǎng)h除的節(jié)點(diǎn)
continue;
}
if (t.next.score > score)
t = t.down;
else
t = t.next;
}
}來(lái)源：https://juejin.cn/post/6844903869873389582