Go语言实现跳表（SkipList）详解

如上图所示，底层（Level 0）包含所有元素，上层则随机包含部分元素作为索引。查找时从最高层开始，若当前节点值小于目标，则向右；否则向下一层继续。

跳表的核心思想

• 每一层都是一个有序链表
• 底层包含所有元素
• 高层是底层的“快速通道”，元素数量逐层减少
• 插入新元素时，通过抛硬币（随机）决定其层数

Go语言跳表实现步骤

我们将分步实现以下功能：

1. 定义跳表节点（Node）
2. 定义跳表结构（SkipList）
3. 实现查找（Search）
4. 实现插入（Insert）
5. 实现删除（Delete）

1. 定义节点结构

每个节点包含一个值和一个指向各层下一个节点的指针数组：

type Node struct {    value int    forward []*Node // 每一层的下一个节点}// 创建新节点func newNode(value int, level int) *Node {    return &Node{        value:   value,        forward: make([]*Node, level),    }}

2. 定义跳表结构

跳表包含最大层数、当前层数、头节点等信息：

import (    "math/rand"    "time")const (    MaxLevel = 16       // 最大层数    P        = 0.5      // 提升概率)type SkipList struct {    header *Node  // 头节点（不存实际数据）    level  int    // 当前最大有效层数}// 初始化跳表func NewSkipList() *SkipList {    rand.Seed(time.Now().UnixNano())    header := newNode(0, MaxLevel)    return &SkipList{        header: header,        level:  1,    }}

3. 实现查找操作

从最高层开始，逐层向下查找：

func (sl *SkipList) Search(value int) bool {    current := sl.header    // 从最高层开始向下搜索    for i := sl.level - 1; i >= 0; i-- {        for current.forward[i] != nil && current.forward[i].value < value {            current = current.forward[i]        }    }    // 移动到第0层的下一个节点    current = current.forward[0]    return current != nil && current.value == value}

4. 实现插入操作

插入时需先查找插入位置，再随机决定层数，并更新各层指针：

func (sl *SkipList) randomLevel() int {    level := 1    for rand.Float64() < P && level < MaxLevel {        level++    }    return level}func (sl *SkipList) Insert(value int) {    update := make([]*Node, MaxLevel)    current := sl.header    // 找到每层的插入位置    for i := sl.level - 1; i >= 0; i-- {        for current.forward[i] != nil && current.forward[i].value < value {            current = current.forward[i]        }        update[i] = current    }    // 如果已存在，不重复插入    if current.forward[0] != nil && current.forward[0].value == value {        return    }    // 随机生成新节点层数    newLevel := sl.randomLevel()    if newLevel > sl.level {        for i := sl.level; i < newLevel; i++ {            update[i] = sl.header        }        sl.level = newLevel    }    // 创建新节点并更新指针    newNode := newNode(value, newLevel)    for i := 0; i < newLevel; i++ {        newNode.forward[i] = update[i].forward[i]        update[i].forward[i] = newNode    }}

5. 实现删除操作（简要）

删除逻辑类似插入，找到目标后更新各层指针：

func (sl *SkipList) Delete(value int) bool {    update := make([]*Node, MaxLevel)    current := sl.header    for i := sl.level - 1; i >= 0; i-- {        for current.forward[i] != nil && current.forward[i].value < value {            current = current.forward[i]        }        update[i] = current    }    current = current.forward[0]    if current == nil || current.value != value {        return false // 未找到    }    // 更新各层指针    for i := 0; i < sl.level; i++ {        if update[i].forward[i] != current {            break        }        update[i].forward[i] = current.forward[i]    }    // 调整跳表层数    for sl.level > 1 && sl.header.forward[sl.level-1] == nil {        sl.level--    }    return true}

为什么选择跳表？

相比红黑树等平衡树结构，跳表具有以下优势：

• 实现简单，代码清晰
• 天然支持并发（可对不同层加锁）
• Redis 的有序集合（ZSet）就使用了跳表

通过本教程，你已经掌握了 Go语言跳表实现 的核心逻辑。跳表作为一种高效的 跳表数据结构，非常适合用于需要频繁查找、插入和删除的场景。无论你是学习 Go语言SkipList 还是研究 高性能查找结构，跳表都是一个值得深入理解的经典算法。

总结

本文从原理到代码，完整展示了如何用 Go 语言实现一个跳表。你可以在此基础上扩展功能，比如支持泛型、并发安全等。动手实践是掌握数据结构的最佳方式，快去写一写、测一测吧！