跳躍表原理和實戰-創新互聯
對有序順序表可以采用二分查找，查找的時間復雜度為O (logn)，插入、刪除的時間復雜度為 O(n )。但是對有序鏈表不可以采用二分查找，查找、插入和刪除的時間復雜度均為O (n)。
有序鏈表如下圖所示，若查找 8，則必須從第 1 個節點開始，依次比較 8 次才能查找成功。
如何利用鏈表的有序性來提高查找效率？如何在一個有序鏈表中進行二分查找？若增加一級索引，把奇數位序作為索引，則如下圖所示，若查找 8，則可以先從索引進行比較，依次比較 1、3、5、7、9，8?比 7 大但比 9 小，7 向下一層，繼續向后比較，比較 6 次即可查找成功。
若再增加一級索引，把索引層的奇數位序作為索引，則如下圖所示，若查找 7，則可以先從索引開始比較，依次 1、5、9，7 比 5 大但比 9?小，5 向下一層，繼續向后比較，比較 4 次即可查找成功。
在增加兩級索引后，若查找 5，則比較兩次即可查找成功；若查找比 5 大的數，則以 5 為界向后查找；若查找比 5 小的數，則以 5 為界向前查找。這就是一個可進行二分查找的有序鏈表。
二?算法分析若有 n 個元素，則增加 h 級索引后的數據結構如下圖所示。
底層包含所有元素（n個），即 2^(h +1)=n ，索引層數 h=logn-1。搜索時，首先在頂層索引中進行查找，然后二分搜索，最多從頂層搜索到底層，最多 O(logn) 層，因此查找的時間復雜度為 O(logn)。
2?空間復雜度增加索引需要一些輔助空間，那么索引一共有多少個節點呢？從上圖中可以看出，每層索引的節點之和都為 2+2^2 +…+2^h =2^(h +1)-2=n-2，因此空間復雜度為 O(n )。實際上，索引節點并不是原節點
的復制，只是附加了一些指針建立索引。以上正是跳躍表的實現原理。
三?跳躍表介紹跳躍表（Skip list）是有序鏈表的擴展，簡稱跳表，它在原有的有序鏈表上增加了多級索引，通過索引來實現快速查找，實質上是一種可以進行二分查找的有序鏈表。
實際上，跳躍表并不是簡單地通過奇偶次序建立索引的，而是通過隨機技術實現的，因此也可以說它是一種隨機化的數據結構。假如跳躍表每一層的晉升概率都是 1/2，則最理想的索引就是在原始鏈表中每隔一個元素抽取一個元素作為一級索引。其實在原始鏈表中隨機選擇 n/2 個元素作為一級索引也可以，因為隨機選擇的元素相對均勻，對查找效率來講影響不大。當原始鏈表中元素數量足夠大且抽取足夠隨機時，得到的索引是均勻的。因此隨機選擇 n/2 個元素作為一級索引，隨機選擇 n/4 個元素作為二級索引，隨機選擇 n/8 個元素作為三級索引，以此類推，一直到頂層索引。我們可以通過索引來提升跳躍表的查找效率。
跳躍表不僅可以提高搜索性能，還可以提高插入和刪除操作的性能。平衡二叉查找樹在進行插入、刪除操作后需要多次調整平衡，而跳躍表完全依靠隨機技術，其性能和平衡二叉查找樹不相上下，但是原理非常簡單。跳躍表是一種性能比較優秀的動態數據結構，Redis 中的有序集合 Sorted Set 和 LevelDB 中的 MemTable 都是采用跳躍表實現的。
四?跳躍表的實現 1?數據結構定義在每個節點都可以設置向右、向下指針，當然，也可以附加向左、向上指針，構建四聯表。通過四聯表可以快速地在四個方向訪問前驅和后繼。在此僅設置向右指針，在每個節點都定義一個后繼指針數組，通過層次控制向下訪問。
2?查找在跳躍表中查找元素 x ，需要從最上層索引開始逐層查找，算法步驟如下。
（1）從最上層 Sh 的頭節點開始。
（2）假設當前位置為 p ，p 的后繼節點的值為 y ，若 x=y，則查找成功；若 x>y ，則 p 向后移一個位置，繼續查找；若 x （3）若到達底層還要向下移動，則查找失敗。 例如，跳躍表如下圖所示，在表中查找元素 36，則先從頂層的頭節點開始，比 20 大，向后為空，p 向下移動到第 2 層；比下一個元素 50?小，p 向下移動到第 1 層；比下一個元素 30 大，p 向右移動；比下一個元素 50 小，p 向下移動到第 0 層；與下一個元素 36 比較，查找成功。 在跳躍表中插入一個元素時，相當于在某一個位置插入一個高度為 level 的列。插入的位置可以通過查找確定，而插入列的高度可以采用隨機化決策確定。 隨機化獲取插入元素的層次： ① 初始時 lay=0，可設定晉升概率P為 0.5 或 0.25。 ② 利用隨機函數產生 0～1的隨機數 r。 ④ 若 r 小于 P 且?lay 小于大層次，則 lay+1；否則返回 lay，作為新插入元素的高度。 在跳躍表中插入元素的算法步驟如下。 （1）查找插入位置，在查找過程中用 updata[i] 記錄經過的每一層的大節點位置。 （2）采用隨機化策略得到插入層次 lay。 （3）創建新節點，將高度為 lay 的列插入 updata[i] 之后。 例如，跳躍表如下圖所示，在表中插入元素 32。首先在跳躍表中查找 32，然后確定插入位置。在查找過程中用 updata[i] 記錄經過的每一層的大節點位置；假設隨機化得到的層次為 2，則 i 為 0～2，將新節點插入 updata[i] 之后。 在跳躍表中刪除一個元素，相當于刪除這個元素所在的列。 算法步驟： （1）查找該元素，在查找過程中用 updata[i] 記錄經過的每一層的大節點位置，實際上是待刪除節點在每一層的前一個元素的位置。若查找失敗，則退出。 （2）利用 updata[i] 將該元素整列刪除。 （3）若有多余空鏈，則刪除空鏈。 例如，跳躍表如下圖所示，在表中刪除元素 20。首先在跳躍表中查找 20，在查找過程中用 updata[i] 記錄經過的每一層的大節點位置；然后利用 updata[i] 將每層的 20 節點刪除。 刪除 20 所在的列后，最上層的鏈為空鏈，則刪除空鏈，跳躍表的層次減 1。 Please select: ----------------------------- 1:??插入 2:??刪除 3:??查找 4:??遍歷 5:??遍歷所有層 0:??退出 ----------------------------- 1 1 lay=0 Please select: ----------------------------- 1:??插入 2:??刪除 3:??查找 4:??遍歷 5:??遍歷所有層 0:??退出 ----------------------------- 5 level 0:??1?? Please select: ----------------------------- 1:??插入 2:??刪除 3:??查找 4:??遍歷 5:??遍歷所有層 0:??退出 ----------------------------- 1 4 lay=5 Please select: ----------------------------- 1:??插入 2:??刪除 3:??查找 4:??遍歷 5:??遍歷所有層 0:??退出 ----------------------------- 5 level 5:??4?? level 4:??4?? level 3:??4?? level 2:??4?? level 1:??4?? level 0:??1??4?? Please select: ----------------------------- 1:??插入 2:??刪除 3:??查找 4:??遍歷 5:??遍歷所有層 0:??退出 ----------------------------- 1 7 lay=1 Please select: ----------------------------- 1:??插入 2:??刪除 3:??查找 4:??遍歷 5:??遍歷所有層 0:??退出 ----------------------------- 5 level 5:??4?? level 4:??4?? level 3:??4?? level 2:??4?? level 1:??4??7?? level 0:??1??4??7?? Please select: ----------------------------- 1:??插入 2:??刪除 3:??查找 4:??遍歷 5:??遍歷所有層 0:??退出 ----------------------------- 1 2 lay=0 Please select: ----------------------------- 1:??插入 2:??刪除 3:??查找 4:??遍歷 5:??遍歷所有層 0:??退出 ----------------------------- 5 level 5:??4?? level 4:??4?? level 3:??4?? level 2:??4?? level 1:??4??7?? level 0:??1??2??4??7?? Please select: ----------------------------- 1:??插入 2:??刪除 3:??查找 4:??遍歷 5:??遍歷所有層 0:??退出 ----------------------------- 3 3 find fail! Please select: ----------------------------- 1:??插入 2:??刪除 3:??查找 4:??遍歷 5:??遍歷所有層 0:??退出 ----------------------------- 3 2 find success! Please select: ----------------------------- 1:??插入 2:??刪除 3:??查找 4:??遍歷 5:??遍歷所有層 0:??退出 ----------------------------- 2 2 2 Please select: ----------------------------- 1:??插入 2:??刪除 3:??查找 4:??遍歷 5:??遍歷所有層 0:??退出 ----------------------------- 5 level 5:??4?? level 4:??4?? level 3:??4?? level 2:??4?? level 1:??4??7?? level 0:??1??4??7?? Please select: ----------------------------- 1:??插入 2:??刪除 3:??查找 4:??遍歷 5:??遍歷所有層 0:??退出 ----------------------------- 你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧
網頁名稱：跳躍表原理和實戰-創新互聯
成都網站建設公司_創新互聯，為您提供服務器托管、商城網站、小程序開發、App設計、ChatGPT、網站制作
聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源：
創新互聯
2?測試結果package com.platform;
import java.util.Scanner;
public class SkipList {
private static int INF = 0x7fffffff;
private static float P = 0.5f;
private static int MAX_LEVEL = 16;
static class Node {
int val;
Node forward[] = new Node[MAX_LEVEL];
}
Node head = new Node();
Node updata[] = new Node[MAX_LEVEL];
public SkipList() {
for (int i = 0; i< updata.length; i++) {
updata[i] = new Node();
}
}
void Init() {
level = 0;
head = new Node();
for (int i = 0; i< MAX_LEVEL; i++)
head.forward[i] = null;
head.val = -INF;
}
// 隨機產生插入元素高度
static int RandomLevel() {
int lay = 0;
while ((float) Math.random()< P && lay< MAX_LEVEL - 1)
lay++;
return lay;
}
Node Find(int val) {//查找最接近val的元素
Node p = head;
for (int i = level; i >= 0; i--) {
while (p.forward[i] != null && p.forward[i].val< val)
p = p.forward[i];
updata[i] = p;//記錄搜索過程中各級走過的大節點位置
}
return p;
}
void Insert(int val) {
Node p, s;
int lay = RandomLevel();
System.out.printf("lay=%d\n", lay);
if (lay >level) //要插入的層 >現有層數
level = lay;
p = Find(val); //查詢
s = new Node();//創建一個新節點
s.val = val;
for (int i = 0; i< MAX_LEVEL; i++)
s.forward[i] = null;
for (int i = 0; i<= lay; i++) {//插入操作
s.forward[i] = updata[i].forward[i];
updata[i].forward[i] = s;
}
}
void Delete(int val) {
Node p = Find(val);
if (p.forward[0] != null && p.forward[0].val == val) {
System.out.printf("%d\n", p.forward[0].val);
for (int i = level; i >= 0; i--) { // 刪除操作
if (updata[i].forward[i] != null && updata[i].forward[i].val == val)
updata[i].forward[i] = updata[i].forward[i].forward[i];
}
while (level >0 && head.forward[level] == null) // 刪除空鏈
level--;
}
}
void print(int i) { // 遍歷
Node p = head.forward[i];
if (p == null) return;
while (p != null) {
System.out.printf("%d ", p.val);
p = p.forward[i];
}
System.out.printf("\n");
}
void printall() { // 遍歷所有層
for (int i = level; i >= 0; i--) {
System.out.printf("level %d: ", i);
print(i);
}
}
void show() {
System.out.printf("Please select:\n");
System.out.printf("-----------------------------\n");
System.out.printf(" 1: 插入\n");
System.out.printf(" 2: 刪除\n");
System.out.printf(" 3: 查找\n");
System.out.printf(" 4: 遍歷\n");
System.out.printf(" 5: 遍歷所有層\n");
System.out.printf(" 0: 退出\n");
System.out.printf("-----------------------------\n");
}
int level;
public static void main(String[] args) {
Scanner sn = new Scanner(System.in);
SkipList skipList = new SkipList();
skipList.Init();
int n, x;
skipList.show();
while (true){
n = sn.nextInt();
switch (n) {
case 1:
x = sn.nextInt();
skipList.Insert(x);
break;
case 2:
x = sn.nextInt();
skipList.Delete(x);
break;
case 3:
x = sn.nextInt();
Node p;
p = skipList.Find(x);
if (p.forward[0] != null && p.forward[0].val == x) {
System.out.printf("find success!\n");
} else {
System.out.printf("find fail!\n");
}
break;
case 4:
skipList.print(0);
break;
case 5:
skipList.printall();
break;
}
skipList.show();
}
}
}
當前URL：http://vcdvsql.cn/article20/hsoco.html
- 手機網站建設注意事項及優化常識 2016-03-07
- 如何合理的把網站排名提上去？ 2014-07-11
- 提高采集內容收錄量和排名的方法是什么? 2015-10-01
- seo收錄不如從前，如何解決？ 2015-04-11
- 進步的網絡應用程序意味著你的網站和搜索引擎優化 2014-12-24
- 網站有收錄卻沒排名是什么原因? 2015-12-26
- 如何利用全網營銷超越競爭對手？ 2015-08-04
- 如何利用微信小程序做微信營銷? 2015-08-04
- 成都做網站：網站建設清晰網站用處和定位，網站營銷就成功了一半 2022-08-19
- 移動手機網站如何優化？簡單 2016-10-02
- 企業網站建設之網站結構對網站營銷的重要性 2016-04-30
- 淺談營銷型網站建設優化工作的關鍵所在 2016-08-13