使用 JavaScript 實現 SkipList 這種資料結構

摘要： 使用JavaScript實現SkipList這種資料結構 程式碼的實現參考了 SkipList.java 前言 為什麼想到使用 JavaScript 把跳錶這種資料結構來實現一遍呢？這個主要是因為我女朋友最近在學習資料結構和演算法，然後遇到了這個問題；非要拉著我跟她一起 來研...

使用JavaScript實現SkipList這種資料結構

程式碼的實現參考了 ofollow,noindex" target="_blank">SkipList.java

前言

為什麼想到使用 JavaScript 把跳錶這種資料結構來實現一遍呢？這個主要是因為我女朋友最近在學習資料結構和演算法，然後遇到了這個問題；非要拉著我跟她一起 來研究一下，然後，然後就有了下面的文章。這種資料結構在 Redis 中使用的比較多，有興趣的朋友可以看看。

SkipList的具體實現

首先我們先粗略的看一下JavaScript版本的程式碼，具體如下所示：

/**
 * author dreamapplehappy
 */

// 程式碼使用了ES6以及更高版本的JavaScript來表示，需要使用Babel之類的工具處理一下才可以在Node或者瀏覽器中執行

// 定義了跳錶索引的最大級數
const MAX_LEVEL = 16;

/**
 * 定義Node類，用來輔助實現跳錶功能
 */
class Node{
// data屬性存放了每個節點的資料
data = -1;
// maxLevel屬性表明了當前節點處於整個跳錶索引的級數
maxLevel = 0;
// refer是一個有著MAX_LEVEL大小的陣列，refer屬性存放著很多個索引
// 如果用p表示當前節點，用level表示這個節點處於整個跳錶索引的級數；那麼p[level]表示在level這一層級p節點的下一個節點
// p[level-n]表示level級下面n級的節點
refer = new Array(MAX_LEVEL);
}

/**
 * 定義SkipList類
 */
class SkipList{
// levelCount屬性表示了當前跳錶索引的總共級數
levelCount = 1;
// head屬性是一個Node類的例項，指向整個連結串列的開始
head = new Node();

// 在跳裡面插入資料的時候，隨機生成索引的級數
static randomLevel() {
let level = 1;
for(let i = 1; i < MAX_LEVEL; i++) {
if(Math.random() < 0.5) {
level++;
}
}
return level;
}

/**
* 向跳錶裡面插入資料
* @param value
*/
insert(value) {
const level = SkipList.randomLevel();
const newNode = new Node();
newNode.data = value;
newNode.maxLevel = level;
const update = new Array(level).fill(new Node());
let p = this.head;
for(let i = level - 1; i >= 0; i--) {
while(p.refer[i] !== undefined && p.refer[i].data < value) {
p = p.refer[i];
}
update[i] = p;
}
for(let i = 0; i < level; i++) {
newNode.refer[i] = update[i].refer[i];
update[i].refer[i] = newNode;
}
if(this.levelCount < level) {
this.levelCount = level;
}
}

/**
* 查詢跳錶裡面的某個資料節點，並返回
* @param value
* @returns {*}
*/
find(value) {
if(!value){return null}
let p = this.head;
for(let i = this.levelCount - 1; i >= 0; i--) {
while(p.refer[i] !== undefined && p.refer[i].data < value) {
p = p.refer[i];
// 標記1，此處用於文章的說明
}
}

if(p.refer[0] !== undefined && p.refer[0].data === value) {
return p.refer[0];
}
return null;
}

/**
* 移除跳錶裡面的某個資料節點
* @param value
* @returns {*}
*/
remove(value) {
let _node;
let p = this.head;
const update = new Array(new Node());
for(let i = this.levelCount - 1; i >= 0; i--) {
while(p.refer[i] !== undefined && p.refer[i].data < value){
p = p.refer[i];
}
update[i] = p;
}

if(p.refer[0] !== undefined && p.refer[0].data === value) {
_node = p.refer[0];
for(let i = 0; i <= this.levelCount - 1; i++) {
if(update[i].refer[i] !== undefined && update[i].refer[i].data === value) {
update[i].refer[i] = update[i].refer[i].refer[i];
}
}
return _node;
}
return null;
}

// 列印跳錶裡面的所有資料
printAll() {
let p = this.head;
while(p.refer[0] !== undefined) {
// console.log(p.refer[0].data)
p = p.refer[0];
}
}
}

如果你看完上面的程式碼，感覺還是沒有太明白；也不要著急，下面我會仔細的講解一下上面程式碼的思路

首先，我們定義了一個 Node 類；這個類生成的例項有三個屬性，分別是 data ， maxLevel 和 refer ； 具體的解釋可以看程式碼裡面的註釋；這裡要注意的是 refer 這個屬性，它是一個長度為 MAX_LEVEL 的陣列， 數組裡面的值是一個指向別的節點的索引。可以大概看下面這張圖來加深一下理解：

不知道上面的圖大家有沒有看得更明白一點，如果沒有的話，也沒有關係；我們先繼續往下面走。

接下來，我們又定義了一個SkipList類，這個類就是我們要實現的跳錶類；SkipList的例項屬性有 levelCount 和 head 關於這兩個屬性的解釋可以看程式碼裡面的註釋；

我們先來看一下 randomLevel 這個類的靜態方法，這個方法用來生成一個不大於 MAX_LEVEL 的值；這個值 可以在我們向SkipList新增元素的時候，生成一個隨機的索引級數； 這個隨機函式這樣設計的原因是為了保證 我們在向SkipList新增元素的時候，每一級索引節點的數量大概能夠是上一級索引節點的2倍。

我們首先來看一下SkipList的 find 方法，如果這個方法你能夠理解的話，那麼SkipList的 remove 和 insert 方法你都能夠快速的理解；我們來試一試吧。

首先我們把整個連結串列的頭指標賦值給 p (這裡你可能會有疑問，為什麼 this.head 就是整個連結串列的頭指標；這個我們會在後面 講解 insert 方法的時候再給大家講解一下)。然後是兩層迴圈，外層是一個 for 迴圈，裡面是一個 while 迴圈； 我們這個時候就可以看下面這張圖了：

首先我們需要知道的是， for 迴圈是從SkipList的頂層索引開始迴圈，方向是從上到下的； while 迴圈則是從某一層的索引開始， 然後從左到右迴圈；當然我們說的從上到下和從左到右，都是對照我們上面的那張圖來進行說明的。

假設我們的SkipList是上面的那張圖表示的那樣，我們現在需要查詢數值9；我們應該怎麼做呢？看一下我們上面的程式碼。

我們首先從頂層開始遍歷，看上面的圖我們知道這個時候SkipList的 levelCount 應該是 4 ，因為我們是從 0 開始計算索引的級數( 第0級索引也就是我們的原始連結串列 )， 所以最頂層的索引的級數應該是 levelCount - 1 也就是 3 ，然後我們就進入了一個 while 迴圈，這個 while 迴圈的終止條件是： 當前節點在本層級的下一個節點(我們用 p1 表示)不為空(undefined)，並且 p1 的 data 值要小於我們所找的數值 。

我們用 l 表示當前索引的級數，用 p 表示當前遍歷到的節點(或者可以理解為一個指標)， 那麼當 l=3 的時候，第一次 while 迴圈， p.refer[3] 表示的是第三級索引的 Node(1) ，因為滿足 while 的迴圈條件， 我們又進行一次操作， p = p.refer[i] ，這表明我們此時遍歷到了 Node(1) ，或者說是當前的指標指向了 Node(1) ； 然後我們準備進行下一次迴圈，但是 p.refer[i] !== undefined && p.refer[i].data < value 這個表示式的值不為真； 因為此時 p 表示的是 Node(1) ， p.refer[i] 表示的是 Node(15) ，因為 p.refer[i].data 大於 9 ，所以內部的 while 迴圈終止。

此時外層的 for 迴圈讓 i 變為了 2 ，然後 p.refer[i] 表示的是第二級索引上面的 Node(1) ，滿足 while 迴圈，然後繼續進行， 這裡就不在繼續描述程式的運行了，我們可以知道，當 p 表示的是第0級索引的 Node(6) 的時候，所有的迴圈都已經結束。

然後我們還需要進行一次判斷，那就是我們當前位置的下一個節點是不是我們需要找的值(為什麼還需要判斷？因為我們迴圈的條件是當前節點 的下一個節點的 data 值要小於我們查詢的 value ，如果迴圈結束，那說明當前節點的下一個節點的值大於或者等於 value 值，所以還需要進行以此判斷)。 如果是的話，就返回 p.refer[i] ，如果不是就返回一個 null 。

我們可以用下面這個表格來表示上面的描述，表格表示的是程式碼中 find 函式裡面註釋的 標記1 ，這個表格的表示應該更直觀一些吧。

執行次數	當前P指向的節點	索引的級數	資料的層數	執行的迴圈
0	head	3	4	-
1	node(1)	3	4	[for, while]
2	node(1)	2	3	[for, while]
3	node(6)	2	3	[while]
4	node(6)	1	2	[for, while]
5	node(6)	0	1	[for, while]

如果上面的描述你都理解的話，那麼 SkipList 的 insert 和 remove 方法你應該很快就明白了； 這兩個方法我們就不再像上面那樣詳細的講解了；我們會大概的說明一下實現的原理。

關於 insert 方法，在插入一個數據的時候，我們首先生成一個隨機的 level 值，用來表示這個資料索引的級數； 然後我們生成一個新的節點 newNode ，接下來我們建立一個 update 陣列，這個陣列的長度是 level ； 裡面存放的是一些節點。

接下來就是熟悉的兩層迴圈，通過上面的那個表格我們可以看到， update 數組裡面儲存的就是 每次 while 迴圈終止的那個節點，就是上面圖片3中紫色線框框起來的節點；然後我們又運行了一個 for 迴圈， 接下來的程式碼很有技巧，我們把新的節點的 refer[i] ( i 表示的是 索引的級數 )指向下一個節點，然後把 update[i] 節點的 refer[i] 指向新的節點 當迴圈完成的時候，我們就把這個資料插入到了原來的 SkipList 當中。更清晰直觀的過程可以看下面的圖片。

然後，我們還需要看一下當前的 level 是否大於 SkipList 的最大級數也就是 levelCount ，如果大於當前的 levelCount ， 我們還需要更新 SkipList 的 levelCount 。

關於 remove 方法，這個方法其實和 remove 方法很相似了；不同點在於，我們首先需要找到要刪除的元素； 如果這個元素在 SkipList 中不存在的話，我們不能夠進行刪除的操作； 只有這個元素在 SkipList 中存在的話，我們才能夠進行刪除操作； 所謂的刪除也就是把 P(pre) 的索引指向 P(next) (其中 P(pre) 表示位於同一級別索引的 P 節點的上一個節點， P(next) 表示位於同一級別索引的 P 節點的下一個節點)， 這樣我們就把這個節點刪除掉了；下面的圖形象地表示了這一個過程。

最後說一下 printAll 方法，這個方法就是打印出我們在 SkipList 儲存的所有資料；因為第0級索引存放的就是 我們的原始資料。到這裡為止，關於程式碼部分我們已經講解完畢了。

測試SkipList相關操作的效率

接下來我們來測試一下 SkipList 相關操作的效率，具體的程式碼可以看這個檔案，我們直接把測試的結果用下面的表格來進行表示：

瀏覽器環境下：

操作資料的樣本數量	查詢操作	插入操作	刪除操作
100	0.08203125ms	0.016845703125ms	0.155029296875ms
1000	0.10302734375ms	0.027099609375ms	0.19189453125ms
10000	0.123046875ms	0.06396484375ms	0.203857421875ms
100000	0.19189453125ms	3.96923828125ms	0.481689453125ms

Node環境下：

操作資料的樣本數量	查詢操作	插入操作	刪除操作
100	0.097ms	0.018ms	0.087ms
1000	0.150ms	0.019ms	0.095ms
10000	0.125ms	0.099ms	0.095ms
100000	0.195ms	1.342ms	0.172ms

如果大家要進行測試的話，要注意一點；當操作的資料樣本數量為100000的時候，因為生成SkipList需要比較長的時間，所以可能要稍稍等一下。

通過上面的表格我們可以看到，使用 SKipList 的效率是很高的。到這裡整篇文章也就算結束啦，文章中可能會有不嚴謹的地方，也歡迎大家指出來，我們一起共同進步。

如果你有什麼想說的，可以在 這裡 發表評論.

版權宣告： 共享-保持署名-非商業性使用-禁止演繹