interview/questions/08-算法与数据结构/跳表原理.md

跳表 (Skip List)

数据结构原理

什么是跳表？

跳表是一种概率性的数据结构，通过在多个层级上维护有序的链表来提供高效的查找、插入和删除操作。它是一种在平衡二叉搜索树和链表之间的折中方案，实现简单且性能优异。

跳表的核心概念

1. 层级：跳表由多个层级组成，最高层是稀疏的，最低层是稠密的
2. 节点：每个节点在不同层级中有多个指针
3. 索引：高层级作为低层级的索引，快速定位
4. 概率性平衡：通过随机算法保证树的平衡性

跳表的工作原理

1. 查找：从最高层开始，向右查找，无法向右时向下继续
2. 插入：随机决定插入的层级，在相应层级插入节点
3. 删除：在所有层级中删除对应节点
4. 平衡：通过随机概率保持树的平衡性

图解说明

跳表结构示例（最大层级 4）：

Level 3:  ---1---10---40---70---
Level 2:  ---1-----10-----70---
Level 1:  ---1------10-----70---
Level 0:  1->2->3->4->5->6->7->8->9->10->11->...->70

查找过程（查找 7）：
- Level 3: 从 1 开始，无法向右，向下到 Level 2
- Level 2: 从 1 开始，无法向右，向下到 Level 1
- Level 1: 从 1 开始，无法向右，向下到 Level 0
- Level 0: 从 1 开始，遍历到 7

跂表节点结构

SkipListNode {
    value: 7
    next[0] -> 8
    next[1] -> 10
    next[2] -> 10
    next[3] -> 40
}

层级选择算法

// 随机生成层级
int level = 0;
while (random() < 0.5 && level < MAX_LEVEL) {
    level++;
}

Java 代码实现

节点类定义

class SkipListNode<T extends Comparable<T>> {
    T value;
    SkipListNode<T>[] next;

    @SuppressWarnings("unchecked")
    public SkipListNode(T value, int level) {
        this.value = value;
        this.next = new SkipListNode[level + 1];
    }
}

跳表实现

import java.util.Random;

public class SkipList<T extends Comparable<T>> {
    private static final int MAX_LEVEL = 16;
    private static final double PROBABILITY = 0.5;

    private SkipListNode<T> header;
    private int level;
    private int size;
    private Random random;

    @SuppressWarnings("unchecked")
    public SkipList() {
        this.header = new SkipListNode<>(null, MAX_LEVEL);
        this.level = 0;
        this.size = 0;
        this.random = new Random();
    }

    // 随机生成层级
    private int randomLevel() {
        int lvl = 0;
        while (lvl < MAX_LEVEL && random.nextDouble() < PROBABILITY) {
            lvl++;
        }
        return lvl;
    }

    // 插入操作
    public void insert(T value) {
        SkipListNode<T>[] update = new SkipListNode[MAX_LEVEL + 1];
        SkipListNode<T> current = header;

        // 从最高层开始查找插入位置
        for (int i = level; i >= 0; i--) {
            while (current.next[i] != null &&
                   current.next[i].value.compareTo(value) < 0) {
                current = current.next[i];
            }
            update[i] = current;
        }

        // 确定新节点的层级
        int newLevel = randomLevel();

        // 如果新层级大于当前层级，更新高层级的指针
        if (newLevel > level) {
            for (int i = level + 1; i <= newLevel; i++) {
                update[i] = header;
            }
            level = newLevel;
        }

        // 创建新节点并插入
        SkipListNode<T> newNode = new SkipListNode<>(value, newLevel);
        for (int i = 0; i <= newLevel; i++) {
            newNode.next[i] = update[i].next[i];
            update[i].next[i] = newNode;
        }

        size++;
    }

    // 查找操作
    public boolean contains(T value) {
        SkipListNode<T> current = header;

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

        current = current.next[0];
        return current != null && current.value.compareTo(value) == 0;
    }

    // 删除操作
    public void delete(T value) {
        SkipListNode<T>[] update = new SkipListNode[MAX_LEVEL + 1];
        SkipListNode<T> current = header;

        // 查找要删除的节点
        for (int i = level; i >= 0; i--) {
            while (current.next[i] != null &&
                   current.next[i].value.compareTo(value) < 0) {
                current = current.next[i];
            }
            update[i] = current;
        }

        current = current.next[0];
        if (current != null && current.value.compareTo(value) == 0) {
            // 从所有层级中删除
            for (int i = 0; i <= level; i++) {
                if (update[i].next[i] != current) {
                    break;
                }
                update[i].next[i] = current.next[i];
            }

            // 更新当前层级
            while (level > 0 && header.next[level] == null) {
                level--;
            }

            size--;
        }
    }

    // 获取最小值
    public T getMin() {
        SkipListNode<T> current = header.next[0];
        return current != null ? current.value : null;
    }

    // 获取最大值
    public T getMax() {
        SkipListNode<T> current = header;
        for (int i = level; i >= 0; i--) {
            while (current.next[i] != null) {
                current = current.next[i];
            }
        }
        return current.value;
    }

    // 跳表大小
    public int size() {
        return size;
    }

    // 是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 打印跳表结构
    public void printList() {
        for (int i = level; i >= 0; i--) {
            SkipListNode<T> node = header.next[i];
            System.out.print("Level " + i + ": ");
            while (node != null) {
                System.out.print(node.value + " ");
                node = node.next[i];
            }
            System.out.println();
        }
    }

    // 中序遍历
    public void traverse() {
        SkipListNode<T> current = header.next[0];
        while (current != null) {
            System.out.print(current.value + " ");
            current = current.next[0];
        }
        System.out.println();
    }
}

完整的实现（包括范围查询）

// 跳表完整实现
public class EnhancedSkipList<T extends Comparable<T>> {
    private static final int MAX_LEVEL = 16;
    private static final double PROBABILITY = 0.5;

    private static class Node<T> {
        T value;
        Node<T>[] next;

        @SuppressWarnings("unchecked")
        public Node(T value, int level) {
            this.value = value;
            this.next = new Node[level + 1];
        }
    }

    private Node<T> header;
    private int level;
    private int size;
    private Random random;

    public EnhancedSkipList() {
        this.header = new Node<>(null, MAX_LEVEL);
        this.level = 0;
        this.size = 0;
        this.random = new Random();
    }

    // 范围查询
    public List<T> rangeQuery(T start, T end) {
        List<T> result = new ArrayList<>();
        if (start.compareTo(end) > 0) {
            return result;
        }

        Node<T> current = header;

        // 找到 start 的位置
        for (int i = level; i >= 0; i--) {
            while (current.next[i] != null &&
                   current.next[i].value.compareTo(start) < 0) {
                current = current.next[i];
            }
        }

        current = current.next[0];
        while (current != null && current.value.compareTo(end) <= 0) {
            result.add(current.value);
            current = current.next[0];
        }

        return result;
    }

    // 获取前驱节点
    public T predecessor(T value) {
        Node<T> current = header;
        T predecessor = null;

        for (int i = level; i >= 0; i--) {
            while (current.next[i] != null &&
                   current.next[i].value.compareTo(value) < 0) {
                current = current.next[i];
                if (i == 0) {
                    predecessor = current.value;
                }
            }
        }

        return predecessor;
    }

    // 获取后继节点
    public T successor(T value) {
        if (!contains(value)) {
            return null;
        }

        Node<T> current = header;

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

        current = current.next[0];
        return current != null ? current.value : null;
    }

    // 统计小于某值的元素个数
    public int countLessThan(T value) {
        Node<T> current = header;
        int count = 0;

        for (int i = level; i >= 0; i--) {
            while (current.next[i] != null &&
                   current.next[i].value.compareTo(value) < 0) {
                count += Math.pow(2, i); // 近似计算
                current = current.next[i];
            }
        }

        return count;
    }

    // 获取统计信息
    public SkipListStats getStats() {
        SkipListStats stats = new SkipListStats();
        stats.size = size;
        stats.height = level + 1;

        // 计算每个层级的节点数
        int[] levelCounts = new int[MAX_LEVEL + 1];
        Node<T> current = header;

        for (int i = 0; i <= level; i++) {
            levelCounts[i] = 0;
        }

        current = header.next[0];
        while (current != null) {
            for (int i = 0; i <= level && i <= current.next.length - 1; i++) {
                levelCounts[i]++;
            }
            current = current.next[0];
        }

        stats.levelCounts = levelCounts;
        return stats;
    }

    public static class SkipListStats {
        public int size;
        public int height;
        public int[] levelCounts;
    }
}

时间复杂度分析

操作时间复杂度

操作	时间复杂度	说明
查找	O(log n)	最多遍历 log n 层
插入	O(log n)	查找位置 + 随机决定层级
删除	O(log n)	查找节点 + 从所有层级删除
范围查询	O(log n + k)	k 是结果集大小
最值查找	O(1)	直接访问首尾节点

空间复杂度

• O(n log n) - 每个节点平均存在 log n 层
• 需要额外空间维护多层级指针

概率分析

1. 期望层级：对于 n 个元素，期望层级为 log n
2. 期望指针数量：每个节点期望有 2 个指针
3. 查找效率：O(log n) 概率保证

实际应用场景

1. Redis 有序集合

• zset 实现：Redis 的有序集合使用跳表实现
• 范围查询：支持高效的区间查询
• 分数排序：基于分数进行排序

// Redis 有序集合模拟
public class RedisSortedSet {
    private EnhancedSkipList<Double, String> skipList;

    public void add(double score, String member) {
        skipList.insert(score, member);
    }

    public List<String> rangeByScore(double min, double max) {
        return skipList.rangeQuery(min, max);
    }

    public boolean contains(String member) {
        return skipList.contains(member);
    }
}

2. 数据库索引

• 内存索引：用于内存数据库的索引
• 范围查询：支持高效的范围查找
• 插入性能：比 B 树实现简单

// 数据库索引实现
public class DatabaseIndex {
    private EnhancedSkipList<Object, Row> index;

    public void insert(Object key, Row row) {
        index.insert(key, row);
    }

    public List<Row> rangeQuery(Object start, Object end) {
        return index.rangeQuery(start, end);
    }

    public Row find(Object key) {
        return index.find(key);
    }
}

3. 网络路由

• 路由表：IP 地址范围查找
• ACL 控制：访问控制列表匹配

// 路由表实现
public class RoutingTable {
    private EnhancedSkipList<String, Route> routes;

    public Route findRoute(String ip) {
        return routes.find(ip);
    }

    public List<Route> findRoutesInSubnet(String subnet) {
        return routes.rangeQuery(subnet, subnet + "255");
    }
}

4. 缓存系统

• 多级缓存：实现分层缓存
• 缓存查找：快速定位缓存项

// 多级缓存实现
public class MultiLevelCache {
    private EnhancedSkipList<String, Object> l1Cache;
    private EnhancedSkipList<String, Object> l2Cache;

    public Object get(String key) {
        Object value = l1Cache.find(key);
        if (value != null) {
            return value;
        }
        value = l2Cache.find(key);
        if (value != null) {
            l1Cache.insert(key, value);
        }
        return value;
    }
}

与其他数据结构的对比

数据结构	查找时间	插入时间	删除时间	适用场景
跳表	O(log n)	O(log n)	O(log n)	内存数据、范围查询
平衡二叉树	O(log n)	O(log n)	O(log n)	内存数据、查找密集
哈希表	O(1)	O(1)	O(1)	精确查找、内存数据
B 树	O(log n)	O(log n)	O(log n)	磁盘存储、索引
数组	O(n)	O(n)	O(n)	小规模、有序数据

跳表的优势

1. 实现简单：相比平衡二叉树，实现更简单
2. 并发友好：部分操作可以并发执行
3. 内存效率：空间使用比平衡树更合理
4. 概率平衡：不需要复杂的旋转操作
5. 支持范围查询：链表结构天然支持范围操作

跳表的劣势

1. 内存使用：比普通链表使用更多内存
2. 最坏情况：概率性数据结构，最坏情况较差
3. 常数因子：比平衡树的常数因子大

常见面试问题

Q1: 跳表和平衡二叉树有什么区别？

答： 主要区别：

1. 实现复杂度：跳表实现简单，平衡树需要复杂的旋转操作
2. 内存使用：跳表使用更多内存（多层级指针），平衡树内存使用更紧凑
3. 并发性能：跳表某些操作更容易并发执行
4. 平衡机制：跳表是概率性平衡，平衡树是确定性平衡
5. 查找性能：平衡树常数因子更好，跳表略差

Q2: 跳表的最大层级如何确定？为什么？

答： 最大层级的确定：

1. 经验值：通常设置为 16-32，足够处理大多数情况
2. 概率保证：对于 n 个元素，期望层级为 log n
3. 空间考虑：最大层级决定最坏情况的内存使用
4. 性能平衡：太高浪费内存，太低影响性能

Q3: 跳表的时间复杂度如何证明？

答： 时间复杂度分析：

1. 查找分析：每层需要遍历的节点数逐渐减少
2. 几何级数：每层节点数呈几何级数减少
3. 期望层数：每个节点的期望层数为 2
4. 总查找步数：期望查找步数为 O(log n)

Q4: Redis 为什么选择跳表实现有序集合？

答： 选择跳表的原因：

1. 实现简单：相比平衡树更容易实现
2. 内存效率：相比平衡树内存使用更合理
3. 并发性能：跳表某些操作可以并发执行
4. 范围查询：天然支持范围查询操作
5. 性能足够：对于大多数场景性能足够好

Q5: 跳表如何保证查找效率？

答： 保证效率的关键：

1. 层级设计：高层级作为低层级的索引
2. 概率平衡：通过随机算法保证树的平衡性
3. 快速定位：从高层级快速定位到大致位置
4. 层数控制：每个节点只存在于适当数量的层级中

Q6: 如何优化跳表的内存使用？

答： 内存优化策略：

1. 动态层级：根据实际数据动态调整最大层级
2. 压缩层级：合并过空的层级
3. 节点复用：复用不再使用的节点
4. 缓存友好：优化内存布局，提高缓存命中率
5. 惰性删除：延迟删除，减少内存碎片

Q7: 跳表在并发环境下如何处理？

答： 并发处理方案：

1. 细粒度锁：对不同层使用不同的锁
2. 无锁设计：使用 CAS 操作实现无锁跳表
3. 版本控制：使用版本号实现乐观并发控制
4. 分段锁：将跳表分段，每段独立加锁
5. 读无锁：读操作不加锁，写操作加锁

// 并发跳表简化实现
public class ConcurrentSkipList<T extends Comparable<T>> {
    private final ReentrantLock[] locks;
    private final int lockCount;

    public ConcurrentSkipList() {
        this.lockCount = 16;
        this.locks = new ReentrantLock[lockCount];
        for (int i = 0; i < lockCount; i++) {
            locks[i] = new ReentrantLock();
        }
    }

    private int getLockIndex(T value) {
        return Math.abs(value.hashCode() % lockCount);
    }

    public void insert(T value) {
        int lockIndex = getLockIndex(value);
        locks[lockIndex].lock();
        try {
            // 插入逻辑
        } finally {
            locks[lockIndex].unlock();
        }
    }
}

Q8: 跳表的性能如何随数据量变化？

答： 性能变化规律：

1. 时间复杂度：保持 O(log n) 不变
2. 空间复杂度：随数据量线性增长
3. 常数因子：数据量越大，常数因子影响越小
4. 缓存影响：数据量较大时，缓存命中率下降
5. 内存压力：大数据量时内存使用成为瓶颈

Q9: 如何处理跳表中的重复数据？

答： 重复数据处理：

1. 允许重复：修改插入逻辑，允许相同值存在
2. 去重处理：在插入时检查是否已存在
3. 多值节点：在节点中存储值的集合
4. 计数器：在节点中增加计数器
5. 策略选择：根据业务需求选择合适的处理方式

Q10: 跳表和 B 树有什么相似之处？

答： 相似之处：

1. 分层结构：都是多层结构，高层级作为索引
2. 查找效率：都是 O(log n) 时间复杂度
3. 范围查询：都支持高效的范围查询
4. 平衡性：都维护数据的平衡性
5. 空间局部性：都考虑数据的局部性原理

主要区别：

• 跳表是基于链表的概率结构
• B 树是基于数组块的确定性结构
• 跳表适用于内存，B 树适用于磁盘