您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

Go 語言實現跳表：核心原理與完整代碼詳解

編輯：關於C++

前言

跳表是 Redis、LevelDB 等高性能存储引擎的核心数据结构。本文將從原理出發，用 Go 語言從零實現一個功能完整的跳表，包含插入、查找、刪除與列印操作，幫助你深入理解「以空間換時間」的經典設計。

核心原理：從鏈表到多層索引

普通鏈表查找時間複雜度為 O(n)。跳表的靈感來自於「為鏈表加索引」：在插入節點時，通過隨機算法決定該節點的層數，越高層的節點越少、跨度越大。查找時從最高層開始向右遍歷，遇到大於目標值則下降一層，最終在底層定位。這將查找、插入、刪除的平均複雜度降至 O(log n)。

關鍵常數與結構定義

const (
    MAX_LEVEL = 16 // 最大層數，足以應對 2^16 個元素
    P         = 4  // 隨機層數的概率分母，值越大層數越低
)

type Node struct {
    Value int
    Next  []*Node // 每層的下一個節點指針
}

type SkipList struct {
    Header *Node // 頭節點，不存儲數據
    Level  int   // 當前最高層數
}

隨機層數生成

使用 rand.Int31() 產生隨機數，通過位運算模擬拋硬幣過程，決定節點層數：

func (sl *SkipList) randomLevel() int {
    level := 1
    for (rand.Int31() & 0xFFFF) % P == 0 {
        level++
    }
    if level > MAX_LEVEL {
        return MAX_LEVEL
    }
    return level
}

插入操作

插入分兩步：首先從高層到低層尋找每層的插入位置（記錄在 update 數組），然後按節點層數逐層修改指針完成鏈接。

func (sl *SkipList) Insert(key int) {
    update := make([]*Node, MAX_LEVEL)
    cur := sl.Header
    // 從高層往低層找每層的前驅節點
    for i := sl.Level - 1; i >= 0; i-- {
        for cur.Next[i] != nil && cur.Next[i].Value < key {
            cur = cur.Next[i]
        }
        update[i] = cur
    }

    level := sl.randomLevel()
    if level > sl.Level {
        for i := sl.Level; i < level; i++ {
            update[i] = sl.Header
        }
        sl.Level = level
    }

    newNode := &Node{Value: key, Next: make([]*Node, level)}
    for i := 0; i < level; i++ {
        newNode.Next[i] = update[i].Next[i]
        update[i].Next[i] = newNode
    }
}

查找與刪除

查找同樣從高層向低層推進；刪除需先找到各層前驅節點，再逐層跳過目標節點。

func (sl *SkipList) Search(key int) bool {
    cur := sl.Header
    for i := sl.Level - 1; i >= 0; i-- {
        for cur.Next[i] != nil && cur.Next[i].Value < key {
            cur = cur.Next[i]
        }
    }
    cur = cur.Next[0]
    return cur != nil && cur.Value == key
}

func (sl *SkipList) Delete(key int) {
    update := make([]*Node, MAX_LEVEL)
    cur := sl.Header
    for i := sl.Level - 1; i >= 0; i-- {
        for cur.Next[i] != nil && cur.Next[i].Value < key {
            cur = cur.Next[i]
        }
        update[i] = cur
    }
    cur = cur.Next[0]
    if cur == nil || cur.Value != key {
        return
    }
    for i := 0; i < sl.Level; i++ {
        if update[i].Next[i] == cur {
            update[i].Next[i] = cur.Next[i]
        }
    }
    // 更新最高層數
    for sl.Level > 1 && sl.Header.Next[sl.Level-1] == nil {
        sl.Level--
    }
}

完整可運行示例

以下代碼可直接複製運行，演示插入 100~1、查找、刪除 55 後的結構變化：

package main

import (
    "fmt"
    "math/rand"
    "time"
)

func main() {
    rand.Seed(time.Now().UnixNano())
    sl := NewSkipList()
    for i := 100; i > 0; i-- {
        sl.Insert(i)
    }
    fmt.Println("初始跳表：")
    sl.Print()

    fmt.Println("\n查找 20, 36, 93：")
    for _, k := range []int{20, 36, 93} {
        if sl.Search(k) {
            fmt.Printf("Found %d\n", k)
        }
    }

    sl.Delete(55)
    fmt.Println("\n刪除 55 後：")
    sl.Print()
}

輸出效果展示

初始跳表：
Level 5: 93
Level 4: 36 93
Level 3: 6 22 36 47 61 75 93
Level 2: 1 6 10 22 23 25 36 42 47 54 61 72 75 78 82 89 93
Level 1: 1 2 3 ... 100 (全部元素)

刪除 55 後：
Level 5: 93
Level 4: 36 93
Level 3: 6 22 36 47 61 75 93
Level 2: 1 6 10 22 23 25 36 42 47 54 61 72 75 78 82 89 93
Level 1: 1 2 3 ... 54 56 ... 100 (55 消失)