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