跳表 Skip List

数据结构 · 给有序链表加几层「快车道」

什么是跳表

有序链表查一个值得从头一个一个走，O(n)。跳表的点子很妙：在它上面再架几层快车道——最底层是全部元素，每往上一层只保留一部分做索引，像高速公路的出入口越往上越稀。

查找从最高层快车道往右大步走，一旦「下一个就超过目标」，就下沉一层接着走，到最底层看命中没。这里固定放了 8 个值、4 层（最底层全有，往上折半）。查一个值，看它怎么走楼梯、怎么一步跳过中间一串。

亲手试试

输入一个值「查找」——看它怎么在高层快车道上大步跳。

因为高层一步能跨过好几个元素，平均查找只要 O(log n)，比有序链表快得多，又比平衡树好实现。那插入时新元素该升到第几层？靠抛硬币随机决定（大约一半概率再往上升一层）——所以跳表是概率型结构，期望层数 O(log n)。本质上，它就是一摞多层链表。

Redis 有序集合 zset：底层就是跳表 + 哈希表。
需要有序 + 范围查询又想好实现的场景，常拿它替代平衡树。
并发场景：跳表的无锁 / 细粒度锁实现比平衡树好做（如 Java ConcurrentSkipListMap）。

它是链表家族里「用空间换时间」的漂亮一招——也是这趟结构之旅里的进阶一站。