Java 中的 SkipList 實現

1. 概述

在本文中，我們將探討SkipList資料結構的基礎知識並演練 Java 實作。 SkipLists用途廣泛，可應用於各種領域和問題，因為與平衡樹等更複雜的資料結構相比，它具有高效的搜尋、插入和刪除操作以及相對簡單的實作。

2. 什麼是SkipList ？

SkipList資料結構允許快速搜尋、插入和刪除操作。它透過維護多層排序鍊錶來實現這一點。底層包含清單中的所有元素，而每個連續層充當“快速通道”，包含其下方元素子集的捷徑。

這些快速通道允許SkipLists透過一步跳過多個元素來實現更快的搜尋時間。

3. 基本概念

• 等級： SkipList由多個層級組成。底層（0級）是所有元素的規則鍊錶。每個較高級別都充當“快速通道”，包含較少的元素並跳過較低級別中的多個元素。
• 機率和高度：元素出現的等級數由機率決定。
• 頭指針：每個等級都有一個頭指針，指向該級別的第一個元素，以便於快速存取每個級別的元素。

4.Java實現

對於我們的 Java 實現，我們將專注於支援基本操作的SkipList的簡化版本：搜尋、插入和刪除。為了簡單起見，我們將使用固定的最大等級數，儘管我們可以根據清單的大小動態調整它。

4.1.定義Node類

首先，我們定義一個Node類別來表示SkipList中的一個元素。每個節點將包含一個值和一個指向每個層級的下一個節點的指標數組。

class Node {
 int value;
 Node[] forward; // array to hold references to different levels

 public Node(int value, int level) {
 this.value = value;
 this.forward = new Node[level + 1]; // level + 1 because level is 0-based
 }
 }

4.2. SkipList類

然後，我們需要建立SkipList類別來管理節點和層級：

public class SkipList {
 private Node head;
 private int maxLevel;
 private int level;
 private Random random;

 public SkipList() {
 maxLevel = 16; // maximum number of levels
 level = 0; // current level of SkipList
 head = new Node(Integer.MIN_VALUE, maxLevel);
 random = new Random();
 }
 }

4.3.插入操作

現在，讓我們為SkipList類別新增一個插入方法。此方法會將新元素插入SkipList中，確保結構保持高效率：

public void insert(int value) {
 Node[] update = new Node[maxLevel + 1];
 Node current = this.head;

 for (int i = level; i >= 0; i--) {
 while (current.forward[i] != null && current.forward[i].value < value) {
 current = current.forward[i];
 }
 update[i] = current;
 }

 current = current.forward[0];

 if (current == null || current.value != value) {
 int lvl = randomLevel();

 if (lvl > level) {
 for (int i = level + 1; i <= lvl; i++) {
 update[i] = head;
 }
 level = lvl;
 }

 Node newNode = new Node(value, lvl);
 for (int i = 0; i <= lvl; i++) {
 newNode.forward[i] = update[i].forward[i];
 update[i].forward[i] = newNode;
 }
 }
 }

4.4.搜尋操作

search 方法從頂層向下遍歷SkipList到第 0 層，只要下一個節點的值小於搜尋值，就在每一層向前移動：

public boolean search(int value) {
 Node current = this.head;
 for (int i = level; i >= 0; i--) {
 while (current.forward[i] != null && current.forward[i].value < value) {
 current = current.forward[i];
 }
 }
 current = current.forward[0];
 return current != null && current.value == value;
 }

4.5.刪除操作

最後，刪除操作會從SkipList中刪除一個值（如果存在）。與insert類似，它也需要更新被刪除節點所在各級的前面節點的前向引用：

public void delete(int value) {
 Node[] update = new Node[maxLevel + 1];
 Node current = this.head;

 for (int i = level; i >= 0; i--) {
 while (current.forward[i] != null && current.forward[i].value < value) {
 current = current.forward[i];
 }
 update[i] = current;
 }
 current = current.forward[0];

 if (current != null && current.value == value) {
 for (int i = 0; i <= level; i++) {
 if (update[i].forward[i] != current) break;
 update[i].forward[i] = current.forward[i];
 }

 while (level > 0 && head.forward[level] == null) {
 level--;
 }
 }
 }

5. 時間複雜度

SkipLists的美妙之處在於它們的效率：

• 搜尋、插入和刪除操作的平均時間複雜度為O(log n) ，其中n是清單中的元素數量。
• 考慮到每個元素在多個層級上的附加指針，空間複雜度為O(n) 。

六、優點

當然， SkipLists有其自身的優點和缺點。我們先來探討一下優點：

• 實現的簡單性：與 AVL 或紅黑樹等平衡樹相比， SkipLists更容易實現，並且仍然為搜尋、插入和刪除操作提供類似的平均情況效能。
• 高效率操作： SkipLists為搜尋、插入和刪除操作提供O(log n)的高效率平均情況時間複雜度。
• 機率平衡： SkipLists使用機率方法來維持平衡，而不是嚴格的重新平衡規則（如 AVL 樹或紅黑樹）。這種隨機化通常會導致更均勻的平衡結構，而不需要複雜的重新平衡程式碼。
• 並發性： SkipLists更適合併發訪問/修改。無鎖和細粒度的鎖定策略在SkipLists中更容易實現，使其適合並發應用程式。

7. 缺點

現在，讓我們來看看它們的一些缺點：

• 空間開銷：每個節點儲存多個指向其他節點的前向指針，導致比單鍊錶或二元樹消耗更高的空間。
• 隨機化：雖然有利於平衡和簡單性，但機率方法將隨機性引入結構的性能中。與確定性資料結構不同，運行之間的效能可能略有不同。

八、結論

SkipLists為更傳統的平衡樹結構提供了一種引人注目的替代方案，其機率方法提供了效率和簡單性。我們的 Java 實作為理解SkipLists工作原理提供了堅實的基礎。

本文中的範例程式碼可以在 GitHub 上找到。