跳跃表可视化

操作	平均	最坏
查找	O(log n)	O(n)*
插入	O(log n)	O(n)*
删除	O(log n)	O(n)*

代码实现

import random

class SkipListNode:
    def __init__(self, key, level):
        self.key = key
        self.forward = [None] * (level + 1)

class SkipList:
    def __init__(self, max_level=16, p=0.5):
        self.max_level = max_level
        self.p = p
        self.level = 0
        self.head = SkipListNode(float('-inf'), max_level)
    
    def random_level(self):
        """Generate random level using coin flips"""
        level = 0
        while random.random() < self.p and level < self.max_level:
            level += 1
        return level
    
    def search(self, key):
        """Search for a key in the skip list"""
        current = self.head
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
        current = current.forward[0]
        return current and current.key == key
    
    def insert(self, key):
        """Insert a key into the skip list"""
        update = [None] * (self.max_level + 1)
        current = self.head
        
        # Find position at each level
        for i in range(self.level, -1, -1):
            while current.forward[i] and current.forward[i].key < key:
                current = current.forward[i]
            update[i] = current
        
        # Determine level for new node
        new_level = self.random_level()
        if new_level > self.level:
            for i in range(self.level + 1, new_level + 1):
                update[i] = self.head
            self.level = new_level
        
        # Create and insert new node
        new_node = SkipListNode(key, new_level)
        for i in range(new_level + 1):
            new_node.forward[i] = update[i].forward[i]
            update[i].forward[i] = new_node

# Usage
sl = SkipList(max_level=6, p=0.5)
for val in [3, 6, 7, 9, 12, 19, 21, 25]:
    sl.insert(val)
print(sl.search(19))  # True

import java.util.Random;

public class SkipList {
    private static final int MAX_LEVEL = 16;
    private static final double P = 0.5;
    
    private int level;
    private SkipListNode head;
    private Random random;
    
    public SkipList() {
        this.level = 0;
        this.head = new SkipListNode(Integer.MIN_VALUE, MAX_LEVEL);
        this.random = new Random();
    }
    
    private int randomLevel() {
        int lvl = 0;
        while (random.nextDouble() < P && lvl < MAX_LEVEL) {
            lvl++;
        }
        return lvl;
    }
    
    public boolean search(int key) {
        SkipListNode current = head;
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && 
                   current.forward[i].key < key) {
                current = current.forward[i];
            }
        }
        current = current.forward[0];
        return current != null && current.key == key;
    }
    
    public void insert(int key) {
        SkipListNode[] update = new SkipListNode[MAX_LEVEL + 1];
        SkipListNode current = head;
        
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && 
                   current.forward[i].key < key) {
                current = current.forward[i];
            }
            update[i] = current;
        }
        
        int newLevel = randomLevel();
        if (newLevel > level) {
            for (int i = level + 1; i <= newLevel; i++) {
                update[i] = head;
            }
            level = newLevel;
        }
        
        SkipListNode newNode = new SkipListNode(key, newLevel);
        for (int i = 0; i <= newLevel; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }
    
    public static void main(String[] args) {
        SkipList sl = new SkipList();
        int[] values = {3, 6, 7, 9, 12, 19, 21, 25};
        for (int v : values) sl.insert(v);
        System.out.println(sl.search(19)); // true
    }
}

class SkipListNode {
    int key;
    SkipListNode[] forward;
    
    SkipListNode(int key, int level) {
        this.key = key;
        this.forward = new SkipListNode[level + 1];
    }
}

跳跃表结构

查找过程

插入过程

Redis 有序集合

LevelDB / RocksDB

并发数据结构

代码实现