詳解Java中跳躍表的原理和實(shí)現(xiàn)
一、跳躍表的引入
對(duì)有序順序表可以采用二分查找，查找的時(shí)間復(fù)雜度為O (logn)，插入、刪除的時(shí)間復(fù)雜度為 O(n )。但是對(duì)有序鏈表不可以采用二分查找，查找、插入和刪除的時(shí)間復(fù)雜度均為O (n)。
有序鏈表如下圖所示，若查找 8，則必須從第 1 個(gè)節(jié)點(diǎn)開(kāi)始，依次比較 8 次才能查找成功。
如何利用鏈表的有序性來(lái)提高查找效率？如何在一個(gè)有序鏈表中進(jìn)行二分查找？若增加一級(jí)索引，把奇數(shù)位序作為索引，則如下圖所示，若查找 8，則可以先從索引進(jìn)行比較，依次比較 1、3、5、7、9，8 比 7 大但比 9 小，7 向下一層，繼續(xù)向后比較，比較 6 次即可查找成功。
若再增加一級(jí)索引，把索引層的奇數(shù)位序作為索引，則如下圖所示，若查找 7，則可以先從索引開(kāi)始比較，依次 1、5、9，7 比 5 大但比 9 小，5 向下一層，繼續(xù)向后比較，比較 4 次即可查找成功。
在增加兩級(jí)索引后，若查找 5，則比較兩次即可查找成功；若查找比 5 大的數(shù)，則以 5 為界向后查找；若查找比 5 小的數(shù)，則以 5 為界向前查找。這就是一個(gè)可進(jìn)行二分查找的有序鏈表。
二、算法分析
若有 n 個(gè)元素，則增加 h 級(jí)索引后的數(shù)據(jù)結(jié)構(gòu)如下圖所示。
1.時(shí)間復(fù)雜度
底層包含所有元素（n個(gè)），即 2^(h +1)=n ，索引層數(shù) h=logn-1。搜索時(shí)，首先在頂層索引中進(jìn)行查找，然后二分搜索，最多從頂層搜索到底層，最多 O(logn) 層，因此查找的時(shí)間復(fù)雜度為 O(logn)。
2.空間復(fù)雜度
增加索引需要一些輔助空間，那么索引一共有多少個(gè)節(jié)點(diǎn)呢？從上圖中可以看出，每層索引的節(jié)點(diǎn)之和都為 2+2^2 +…+2^h =2^(h +1)-2=n-2，因此空間復(fù)雜度為 O(n )。實(shí)際上，索引節(jié)點(diǎn)并不是原節(jié)點(diǎn)的復(fù)制，只是附加了一些指針建立索引。以上正是跳躍表的實(shí)現(xiàn)原理。
三、跳躍表介紹
跳躍表（Skip list）是有序鏈表的擴(kuò)展，簡(jiǎn)稱跳表，它在原有的有序鏈表上增加了多級(jí)索引，通過(guò)索引來(lái)實(shí)現(xiàn)快速查找，實(shí)質(zhì)上是一種可以進(jìn)行二分查找的有序鏈表。
實(shí)際上，跳躍表并不是簡(jiǎn)單地通過(guò)奇偶次序建立索引的，而是通過(guò)隨機(jī)技術(shù)實(shí)現(xiàn)的，因此也可以說(shuō)它是一種隨機(jī)化的數(shù)據(jù)結(jié)構(gòu)。假如跳躍表每一層的晉升概率都是 1/2，則最理想的索引就是在原始鏈表中每隔一個(gè)元素抽取一個(gè)元素作為一級(jí)索引。其實(shí)在原始鏈表中隨機(jī)選擇 n/2 個(gè)元素作為一級(jí)索引也可以，因?yàn)殡S機(jī)選擇的元素相對(duì)均勻，對(duì)查找效率來(lái)講影響不大。當(dāng)原始鏈表中元素?cái)?shù)量足夠大且抽取足夠隨機(jī)時(shí)，得到的索引是均勻的。因此隨機(jī)選擇 n/2 個(gè)元素作為一級(jí)索引，隨機(jī)選擇 n/4 個(gè)元素作為二級(jí)索引，隨機(jī)選擇 n/8 個(gè)元素作為三級(jí)索引，以此類推，一直到頂層索引。我們可以通過(guò)索引來(lái)提升跳躍表的查找效率。
跳躍表不僅可以提高搜索性能，還可以提高插入和刪除操作的性能。平衡二叉查找樹(shù)在進(jìn)行插入、刪除操作后需要多次調(diào)整平衡，而跳躍表完全依靠隨機(jī)技術(shù)，其性能和平衡二叉查找樹(shù)不相上下，但是原理非常簡(jiǎn)單。跳躍表是一種性能比較優(yōu)秀的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，Redis 中的有序集合 Sorted Set 和 LevelDB 中的 MemTable 都是采用跳躍表實(shí)現(xiàn)的。
四、跳躍表的實(shí)現(xiàn)
1.數(shù)據(jù)結(jié)構(gòu)定義
在每個(gè)節(jié)點(diǎn)都可以設(shè)置向右、向下指針，當(dāng)然，也可以附加向左、向上指針，構(gòu)建四聯(lián)表。通過(guò)四聯(lián)表可以快速地在四個(gè)方向訪問(wèn)前驅(qū)和后繼。在此僅設(shè)置向右指針，在每個(gè)節(jié)點(diǎn)都定義一個(gè)后繼指針數(shù)組，通過(guò)層次控制向下訪問(wèn)。
2.查找
在跳躍表中查找元素 x ，需要從最上層索引開(kāi)始逐層查找，算法步驟如下。
（1）從最上層 Sh 的頭節(jié)點(diǎn)開(kāi)始。
（2）假設(shè)當(dāng)前位置為 p ，p 的后繼節(jié)點(diǎn)的值為 y ，若 x=y，則查找成功；若 x>y ，則 p 向后移一個(gè)位置，繼續(xù)查找；若 x<y ，則 p 向下移動(dòng)一個(gè)位置，繼續(xù)查找。
（3）若到達(dá)底層還要向下移動(dòng)，則查找失敗。
例如，跳躍表如下圖所示，在表中查找元素 36，則先從頂層的頭節(jié)點(diǎn)開(kāi)始，比 20 大，向后為空，p 向下移動(dòng)到第 2 層；比下一個(gè)元素 50 小，p 向下移動(dòng)到第 1 層；比下一個(gè)元素 30 大，p 向右移動(dòng)；比下一個(gè)元素 50 小，p 向下移動(dòng)到第 0 層；與下一個(gè)元素 36 比較，查找成功。
3.插入
在跳躍表中插入一個(gè)元素時(shí)，相當(dāng)于在某一個(gè)位置插入一個(gè)高度為 level 的列。插入的位置可以通過(guò)查找確定，而插入列的高度可以采用隨機(jī)化決策確定。
隨機(jī)化獲取插入元素的層次：
① 初始時(shí) lay=0，可設(shè)定晉升概率P為 0.5 或 0.25。
② 利用隨機(jī)函數(shù)產(chǎn)生 0～1的隨機(jī)數(shù) r。
④ 若 r 小于 P 且 lay 小于最大層次，則 lay+1；否則返回 lay，作為新插入元素的高度。
在跳躍表中插入元素的算法步驟如下。
（1）查找插入位置，在查找過(guò)程中用 updata[i] 記錄經(jīng)過(guò)的每一層的最大節(jié)點(diǎn)位置。
（2）采用隨機(jī)化策略得到插入層次 lay。
（3）創(chuàng)建新節(jié)點(diǎn)，將高度為 lay 的列插入 updata[i] 之后。
例如，跳躍表如下圖所示，在表中插入元素 32。首先在跳躍表中查找 32，然后確定插入位置。在查找過(guò)程中用 updata[i] 記錄經(jīng)過(guò)的每一層的最大節(jié)點(diǎn)位置；假設(shè)隨機(jī)化得到的層次為 2，則 i 為 0～2，將新節(jié)點(diǎn)插入 updata[i] 之后。
4.刪除
在跳躍表中刪除一個(gè)元素，相當(dāng)于刪除這個(gè)元素所在的列。
算法步驟：
（1）查找該元素，在查找過(guò)程中用 updata[i] 記錄經(jīng)過(guò)的每一層的最大節(jié)點(diǎn)位置，實(shí)際上是待刪除節(jié)點(diǎn)在每一層的前一個(gè)元素的位置。若查找失敗，則退出。
（2）利用 updata[i] 將該元素整列刪除。
（3）若有多余空鏈，則刪除空鏈。
例如，跳躍表如下圖所示，在表中刪除元素 20。首先在跳躍表中查找 20，在查找過(guò)程中用 updata[i] 記錄經(jīng)過(guò)的每一層的最大節(jié)點(diǎn)位置；然后利用 updata[i] 將每層的 20 節(jié)點(diǎn)刪除。
刪除 20 所在的列后，最上層的鏈為空鏈，則刪除空鏈，跳躍表的層次減 1。
五、實(shí)戰(zhàn)
1.代碼
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;
}
// 隨機(jī)產(chǎn)生插入元素高度
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;//記錄搜索過(guò)程中各級(jí)走過(guò)的最大節(jié)點(diǎn)位置
}
return p;
}
void Insert(int val) {
Node p, s;
int lay = RandomLevel();
System.out.printf("lay=%d\n", lay);
if (lay > level) //要插入的層 > 現(xiàn)有層數(shù)
level = lay;
p = Find(val); //查詢
s = new Node();//創(chuàng)建一個(gè)新節(jié)點(diǎn)
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();
}
}
}2.測(cè)試結(jié)果
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: 退出
-----------------------------
到此這篇關(guān)于詳解Java中跳躍表的原理和實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java跳躍表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
IDEA的Web項(xiàng)目右鍵無(wú)法創(chuàng)建Servlet問(wèn)題解決辦法
這篇文章主要介紹了IDEA的Web項(xiàng)目右鍵無(wú)法創(chuàng)建Servlet問(wèn)題解決辦法的相關(guān)資料,在IDEA中新建Servlet時(shí)發(fā)現(xiàn)缺失選項(xiàng),可以通過(guò)在pom.xml文件中添加servlet依賴解決,文中通過(guò)圖文介紹的非常詳細(xì),需要的朋友可以參考下2024-10-10
在MyBatis中，自定義映射resultMap可以讓你精確控制如何將數(shù)據(jù)庫(kù)返回的結(jié)果集映射到Java對(duì)象上，本文給介紹了Mybatis之自定義映射resultMap,需要的朋友可以參考下2024-03-03
這篇文章主要介紹了Java局部打印效果不同問(wèn)題解決方案,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-09-09
這篇文章主要為大家介紹了分析Springboot中嵌套事務(wù)失效原因詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步2021-11-11
下面小編就為大家?guī)?lái)一篇老生常談java中的Future模式。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-06-06
Java?SWT中常見(jiàn)彈出框?qū)嵗偨Y(jié)
剛開(kāi)始寫(xiě)Java工具的小伙伴可能不知道怎么寫(xiě)消息對(duì)話框,在這里總結(jié)一些常用的幾種消息彈出框,下面這篇文章主要給大家介紹了關(guān)于Java?SWT中常見(jiàn)彈出框的相關(guān)資料,需要的朋友可以參考下2023-01-01
springboot 配置DRUID數(shù)據(jù)源的方法實(shí)例分析
這篇文章主要介紹了springboot 配置DRUID數(shù)據(jù)源的方法,結(jié)合實(shí)例形式分析了springboot 配置阿里DRUID數(shù)據(jù)源的具體步驟與相關(guān)操作技巧,需要的朋友可以參考下2019-12-12
通過(guò)Java?Reflection實(shí)現(xiàn)編譯時(shí)注解正確處理方法
Java注解是一種標(biāo)記在JDK5及以后的版本中引入，用于Java語(yǔ)言中向程序添加元數(shù)據(jù)的方法，這篇文章主要介紹了通過(guò)Java?Reflection實(shí)現(xiàn)編譯時(shí)注解處理方法,需要的朋友可以參考下2023-06-06
通過(guò)Java實(shí)現(xiàn)文件斷點(diǎn)續(xù)傳功能
用戶上傳大文件,網(wǎng)絡(luò)差點(diǎn)的需要?dú)v時(shí)數(shù)小時(shí)，萬(wàn)一線路中斷，不具備斷點(diǎn)續(xù)傳的服務(wù)器就只能從頭重傳，而斷點(diǎn)續(xù)傳就是，允許用戶從上傳斷線的地方繼續(xù)傳送，這樣大大減少了用戶的煩惱。本文將用Java語(yǔ)言實(shí)現(xiàn)斷點(diǎn)續(xù)傳，需要的可以參考一下2022-05-05
這篇文章主要介紹了Java獲取文件ContentType案例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2020-08-08