跳表（Skip List）查找算法详解

1、原理

跳表是一种概率型数据结构，通过多层有序链表实现高效查找，时间复杂度接近平衡树（O(log n)）。其核心思想是通过层级索引加速搜索，结构类似火车时刻表的“快车-慢车”模式。

关键特性：

1. 多层链表：
   • 第 0 层是完整的有序链表。
   • 上层链表是下层的“快速通道”，节点间隔逐渐增大。
2. 随机层数：插入节点时随机生成层数（如抛硬币，50%概率上升一层）。
3. 跳跃查找：从最高层开始搜索，若下一节点值大于目标，则“下降”到下层继续。

示例：
查找值 6 的路径（从顶层开始）：

Level 3: 1 ---------------------------> 9

Level 2: 1 --------5--------> 9

Level 1: 1 ---3---5---7----> 9

Level 0: 1-2-3-4-5-6-7-8-9

2、性能分析

• 时间复杂度：
  • 查找/插入/删除：平均 O(log n)，最坏 O(n)（取决于随机层数的分布）。
• 空间复杂度：平均 O(n)（每层链表存储部分节点）。
• 对比平衡树：

  特性	跳表	平衡树（如AVL）
  实现复杂度	简单	复杂
  范围查询	高效（顺序遍历底层链表）	需要中序遍历
  并发支持	更易实现锁分段	较难

3、 适用场景

1. 替代平衡树：需要高效查找且实现简单的场景（如 Redis 的有序集合）。
2. 范围查询：查找区间内的所有值（如 [5, 10]）。
3. 动态数据：频繁插入和删除的场景（维护成本低于平衡树）。
4. 内存数据库：适合内存中的高性能数据结构。

不适用场景：

• 对严格 O(log n) 最坏性能有要求的场景。
• 内存极度受限（跳表空间开销略高于数组）。

4、代码实现

Python:

import random  
from typing import Optional  class SkipNode:  def __init__(self, val: int = -1, levels: int = 0):  self.val = val  self.next = [None] * levels  class SkipList:  def __init__(self, max_level: int = 16):  self.max_level = max_level  self.head = SkipNode(levels=self.max_level)  self.level = 0  # 当前最大层数  def _random_level(self) -> int:  level = 1  while random.random() < 0.5 and level < self.max_level:  level += 1  return level  def search(self, target: int) -> bool:  curr = self.head  for i in range(self.level - 1, -1, -1):  while curr.next[i] and curr.next[i].val < target:  curr = curr.next[i]  curr = curr.next[0]  return curr and curr.val == target  def add(self, num: int) -> None:  update = [self.head] * self.max_level  curr = self.head  # 查找插入位置并记录每层的前驱节点  for i in range(self.level - 1, -1, -1):  while curr.next[i] and curr.next[i].val < num:  curr = curr.next[i]  update[i] = curr  # 随机生成层数  new_level = self._random_level()  if new_level > self.level:  for i in range(self.level, new_level):  update[i] = self.head  self.level = new_level  # 创建新节点并更新指针  new_node = SkipNode(num, new_level)  for i in range(new_level):  new_node.next[i] = update[i].next[i]  update[i].next[i] = new_node  # 调用示例  
sl = SkipList()  
sl.add(3)  
sl.add(6)  
sl.add(1)  
print(sl.search(6))  # 输出: True  
print(sl.search(5))  # 输出: False  

golang:

package main  
import (  "fmt"  "math/rand"  "time"  
)  const maxLevel = 16  type SkipNode struct {  val  int  next []*SkipNode  
}  type SkipList struct {  head      *SkipNode  maxLevel  int  currLevel int  
}  func NewSkipList() *SkipList {  rand.Seed(time.Now().UnixNano())  head := &SkipNode{val: -1, next: make([]*SkipNode, maxLevel)}  return &SkipList{head: head, maxLevel: maxLevel, currLevel: 1}  
}  func (sl *SkipList) randomLevel() int {  level := 1  for rand.Float64() < 0.5 && level < sl.maxLevel {  level++  }  return level  
}  func (sl *SkipList) Search(target int) bool {  curr := sl.head  for i := sl.currLevel - 1; i >= 0; i-- {  for curr.next[i] != nil && curr.next[i].val < target {  curr = curr.next[i]  }  }  curr = curr.next[0]  return curr != nil && curr.val == target  
}  func (sl *SkipList) Add(num int) {  update := make([]*SkipNode, sl.maxLevel)  curr := sl.head  // 查找插入位置并记录前驱节点  for i := sl.currLevel - 1; i >= 0; i-- {  for curr.next[i] != nil && curr.next[i].val < num {  curr = curr.next[i]  }  update[i] = curr  }  // 生成随机层数  newLevel := sl.randomLevel()  if newLevel > sl.currLevel {  for i := sl.currLevel; i < newLevel; i++ {  update[i] = sl.head  }  sl.currLevel = newLevel  }  // 创建新节点并更新指针  newNode := &SkipNode{val: num, next: make([]*SkipNode, newLevel)}  for i := 0; i < newLevel; i++ {  newNode.next[i] = update[i].next[i]  update[i].next[i] = newNode  }  
}  // 调用示例  
func main() {  sl := NewSkipList()  sl.Add(3)  sl.Add(6)  sl.Add(1)  fmt.Println(sl.Search(6))  // true  fmt.Println(sl.Search(5))  // false  
}  

php:

<?php  
class SkipNode {  public $val;  public $next = array();  public function __construct($val, $levels) {  $this->val = $val;  $this->next = array_fill(0, $levels, null);  }  
}  class SkipList {  private $maxLevel = 16;  private $head;  private $currentLevel = 1;  public function __construct() {  $this->head = new SkipNode(-1, $this->maxLevel);  }  private function randomLevel() {  $level = 1;  while (mt_rand() / mt_getrandmax() < 0.5 && $level < $this->maxLevel) {  $level++;  }  return $level;  }  public function search($target) {  $curr = $this->head;  for ($i = $this->currentLevel - 1; $i >= 0; $i--) {  while ($curr->next[$i] !== null && $curr->next[$i]->val < $target) {  $curr = $curr->next[$i];  }  }  $curr = $curr->next[0];  return $curr !== null && $curr->val === $target;  }  public function add($num) {  $update = array_fill(0, $this->maxLevel, $this->head);  $curr = $this->head;  // 查找插入位置并记录前驱节点  for ($i = $this->currentLevel - 1; $i >= 0; $i--) {  while ($curr->next[$i] !== null && $curr->next[$i]->val < $num) {  $curr = $curr->next[$i];  }  $update[$i] = $curr;  }  // 生成随机层数  $newLevel = $this->randomLevel();  if ($newLevel > $this->currentLevel) {  for ($i = $this->currentLevel; $i < $newLevel; $i++) {  $update[$i] = $this->head;  }  $this->currentLevel = $newLevel;  }  // 创建新节点并更新指针  $newNode = new SkipNode($num, $newLevel);  for ($i = 0; $i < $newLevel; $i++) {  $newNode->next[$i] = $update[$i]->next[$i];  $update[$i]->next[$i] = $newNode;  }  }  
}  // 调用示例  
$sl = new SkipList();  
$sl->add(3);  
$sl->add(6);  
$sl->add(1);  
echo $sl->search(6) ? 'true' : 'false';  // 输出: true  
echo $sl->search(5) ? 'true' : 'false';  // 输出: false  
?>  

java:

import java.util.Arrays;  
import java.util.Random;  class SkipNode {  int val;  SkipNode[] next;  public SkipNode(int val, int levels) {  this.val = val;  this.next = new SkipNode[levels];  }  
}  public class SkipList {  private static final int MAX_LEVEL = 16;  private SkipNode head;  private int currentLevel;  private Random random;  public SkipList() {  this.head = new SkipNode(-1, MAX_LEVEL);  this.currentLevel = 1;  this.random = new Random();  }  private int randomLevel() {  int level = 1;  while (random.nextDouble() < 0.5 && level < MAX_LEVEL) {  level++;  }  return level;  }  public boolean search(int target) {  SkipNode curr = head;  for (int i = currentLevel - 1; i >= 0; i--) {  while (curr.next[i] != null && curr.next[i].val < target) {  curr = curr.next[i];  }  }  curr = curr.next[0];  return curr != null && curr.val == target;  }  public void add(int num) {  SkipNode[] update = new SkipNode[MAX_LEVEL];  Arrays.fill(update, head);  SkipNode curr = head;  // 查找插入位置并记录前驱节点  for (int i = currentLevel - 1; i >= 0; i--) {  while (curr.next[i] != null && curr.next[i].val < num) {  curr = curr.next[i];  }  update[i] = curr;  }  // 生成随机层数  int newLevel = randomLevel();  if (newLevel > currentLevel) {  for (int i = currentLevel; i < newLevel; i++) {  update[i] = head;  }  currentLevel = newLevel;  }  // 创建新节点并更新指针  SkipNode newNode = new SkipNode(num, newLevel);  for (int i = 0; i < newLevel; i++) {  newNode.next[i] = update[i].next[i];  update[i].next[i] = newNode;  }  }  // 调用示例  public static void main(String[] args) {  SkipList sl = new SkipList();  sl.add(3);  sl.add(6);  sl.add(1);  System.out.println(sl.search(6));  // true  System.out.println(sl.search(5));  // false  }  
}  

5. 核心逻辑

1. 层级索引：上层链表作为快速通道，加速查找。
2. 随机层数：插入时通过概率控制层数，平衡索引密度。
3. 查找路径：从高层向底层逐级下降，缩小搜索范围。

6、优化与扩展

1. 动态调整层数概率：根据数据量调整上升概率（如从 50% 调整为 1/4）。
2. 支持重复值：在节点中增加计数器或链表存储相同值。
3. 范围查询优化：记录每层的边界指针，快速定位区间。

7、总结

跳表通过多层索引和概率平衡，在简单实现的同时达到高效操作，适合需要动态数据管理的场景（如 Redis 有序集合）。其代码实现比平衡树更简洁，且支持高效的范围查询，是替代传统复杂数据结构的优秀选择。