跳表（Skip List）详解

跳表（Skip List）详解

引用

CSDN

1.

https://blog.csdn.net/xxxmine/article/details/145737615

什么是跳表？

跳表是一种基于有序链表的高效数据结构，通过建立多级索引实现快速查询。它在平均情况下支持O(log n)时间复杂度的搜索、插入和删除操作，性能接近平衡树，但实现更为简单。

核心原理

层级结构

• 底层为完整有序链表（L0层）
• 上层每层都是下层的"快速通道"，节点间隔指数增长
• 最高层数由概率决定（通常P=0.5）

跳表内的所有链表的元素都是排序的。查找时，可以从顶级链表开始找。一旦发现被查找的元素大于当前链表中的取值，就会转入下一层链表继续找。这也就是说在查找过程中，搜索是跳跃式的。

如上图所示，在跳表中查找元素 18。查找 18 的时候原来需要遍历 18 次，现在只需要 7 次即可。针对链表长度比较大的时候，构建索引查找效率的提升就会非常明显。

从上面很容易看出，跳表是一种利用空间换时间的算法。

关键操作复杂度

跳表的好处

对于一个单链表，即使链表是有序的，如果我们想要在其中查找某个数据，也只能从头到尾遍历链表，这样效率自然就会很低。跳表就不一样了。跳表是一种可以用来快速查找的数据结构，有点类似于平衡树。它们都可以对元素进行快速的查找。但一个重要的区别是：对平衡树的插入和删除往往很可能导致平衡树进行一次全局的调整。而对跳表的插入和删除只需要对整个数据结构的局部进行操作即可。这样带来的好处是：在高并发的情况下，你会需要一个全局锁来保证整个平衡树的线程安全。而对于跳表，你只需要部分锁即可。这样，在高并发环境下，你就可以拥有更好的性能。

对比平衡树