跳表数据结构与算法



在 Redis 的 skiplist 实现中，这两个参数的取值为：

• 节点层数至少为 1。而大于 1 的节点层数，满足一个概率分布。
• 节点层数恰好等于 1 的概率为 1-p。
• 节点层数大于等于 2 的概率为 p，而节点层数恰好等于 2 的概率为 p(1-p)。
• 节点层数大于等于 3 的概率为 p^2，而节点层数恰好等于 3 的概率为 p^2*(1-p)。
• 节点层数大于等于 4 的概率为 p^3，而节点层数恰好等于 4 的概率为 p^3*(1-p)。
• ……

因此，一个节点的平均层数（也即包含的平均指针数目），计算如下：

• 当 p=1/2 时，每个节点所包含的平均指针数目为 2。
• 当 p=1/4 时，每个节点所包含的平均指针数目为 1.33。

跳表的平均时间复杂度为 O(logN)。

可以了解学习：Redis 内部数据结构详解 —— skiplist-CSDN博客

力扣对应题目链接：1206. 设计跳表 - 力扣（LeetCode）

了解更多，可以参考：跳表 - OI Wiki (oi-wiki.org)

skiplist 相比平衡搜索树（AVL 树和红黑树）对比，都可以做到遍历数据有序，时间复杂度也差不多。

skiplist 的优势是：

1. skiplist 实现简单，容易控制。而平衡树增删查改遍历都更复杂。
2. skiplist 的额外空间消耗更低。而平衡树节点存储每个值有三叉链，平衡因子/颜色等消耗。

skiplist 中当 p=1/2 时，每个节点所包含的平均指针数目为 2。

skiplist 中当 p=1/4 时，每个节点所包含的平均指针数目为 1.33。

skiplist 相比哈希表而言，就没有那么大的优势了。相比而言：

• 哈希表非极端场景下哈希冲突的平均时间复杂度是 O(1)，比 skiplist 快。
• 哈希表空间消耗略多一点。

skiplist 优势如下：

1. 遍历数据有序。
2. skiplist 空间消耗略小一点，哈希表存在链接指针和表空间消耗。
3. 哈希表扩容有性能损耗。
4. 哈希表在极端场景下哈希冲突高，效率下降厉害，需要红黑树补足接力。 

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.mushiming.com/mjsbk/10894.html