跳表：高效索引的神奇算法
创作时间:
作者:
@小白创作中心
跳表：高效索引的神奇算法
引用
CSDN
1.
https://blog.csdn.net/why_still_confused/article/details/136581513
跳表（Skip List）是一种基于链表的高效数据结构，通过引入多级索引和随机化策略，实现了对数时间复杂度的查找、插入和删除操作。本文将详细介绍跳表的基本原理、特点以及具体的实现细节，并提供完整的Java实现代码。
跳表的设计思想基于二叉查找树和链表，它采用了一种多层次的思路，通过随机化的方式在每个节点添加多个后继节点，从而实现快速查找。跳表的思想可以追溯到1989年，由William Pugh提出。
具体来说，跳表由多个层组成，每个层都是一个有序链表。最低层是一个普通的链表，每个节点包含一个指向下一个节点的指针。而在更高层，每个节点包含多个指针，分别指向不同后继节点。这些指针按一定的概率分布添加到各层，使得查找、插入和删除操作可以在对数时间内完成。
基本原理
对于有序的单链表来说，如果要查询链表元素，只能从头到尾依次遍历链表，时间复杂度为O(n)，效率不高。
跳表通过使用多级索引来加速查找操作。每个索引层都是原链表的一个子集，其中每个节点具有指向下一层和同一层的节点的指针。通过这种方式，跳表可以在平均情况下实现对数时间O(log n)复杂度的查找、插入和删除操作。
是经典的以空间换时间的思想，通过索引层的存在，让跳表具有类似于二分查找的性质，从而提高了操作效率。
特点
跳表的设计思想具有以下特点：
- 分层结构：跳表采用多层次的思路，每个层次都是一个有序链表。通过增加层次，可以使得查找、插入和删除操作的时间复杂度降低。
- 随机化：在跳表的每一层，节点的指针不是固定的，而是随机化的。这种随机化可以保证在查找、插入和删除操作中，数据在各层之间的分布相对均匀，从而提高查找效率。
- 动态调整：跳表的层次不是固定的，可以根据需要进行动态调整。当插入或删除操作导致某一层的元素数量过少时，可以将其与下一层合并；反之，当某一层的元素数量过多时，可以将其拆分成两个层。这种动态调整可以保持跳表的性能稳定。
- 空间换时间：跳表需要额外的空间来存储各层的节点和指针。但是，由于跳表的查找、插入和删除操作的时间复杂度较低，因此可以认为是以空间换取了时间。
实现细节
跳表的实现涉及到一些细节，包括索引层的构建和维护、插入和删除操作的处理、以及查找操作的实现等。具体操作的图文推荐参考Redis进阶 - 数据结构：底层数据结构详解。
随机性
跳表的索引层是通过随机化构建的，通过一定的概率来决定节点是否添加到上一级索引中。这种随机性的引入有助于跳表在平均情况下提供对数时间复杂度的查找操作。
当原始链表中元素数量足够大，且抽取足够随机的话，得到的索引是均匀的（固定间隔时容易造成索引分布不均匀）。
private int randomLevel() {
int lv = 1;
/* 随机生成 lv */
while (random.nextDouble() < P_FACTOR && lv < MAX_LEVEL) {
lv++;
}
return lv;
}
Redis 的 zset 中 P_FACTOR 设定的 0.25
插入
- 从跳表的顶层索引开始，逐层向下遍历，记录每层要插入的位置（最右边小于待插入元素的节点）
- 根据一定的概率，决定是否在较低层次上插入新节点
- 对于需要插入的层，逐层赓续索引，插入新节点
public void add(int num) {
// 记录一下插入位置每层前一位置的节点, 需要将他们的指向全部更新为插入节点
SkiplistNode[] update = new SkiplistNode[MAX_LEVEL];
Arrays.fill(update, head);
SkiplistNode curr = this.head;
for (int i = level - 1; i >= 0; i--) {
/* 找到第 i 层小于且最接近 num 的元素*/
while (curr.forward[i] != null && curr.forward[i].val < num) {
curr = curr.forward[i];
}
update[i] = curr;
}
int lv = randomLevel();
level = Math.max(level, lv);
SkiplistNode newNode = new SkiplistNode(num, lv);
for (int i = 0; i < lv; i++) {
/* 对第 i 层的状态进行更新，将当前元素的 forward 指向新的节点 */
newNode.forward[i] = update[i].forward[i];
update[i].forward[i] = newNode;
}
}
删除
- 从跳表的顶层索引开始，逐层向下遍历，记录每层要删除的位置（最右边小于待插入元素的节点）
- 从最底层开始，逐层向上遍历，更新索引层的指针，将指向被删除元素的节点指针更新为右侧节点
- 从顶层索引依次遍历，若该层已空，更新层数
public boolean erase(int num) {
SkiplistNode[] update = new SkiplistNode[MAX_LEVEL];
SkiplistNode curr = this.head;
for (int i = level - 1; i >= 0; i--) {
/* 找到第 i 层小于且最接近 num 的元素*/
while (curr.forward[i] != null && curr.forward[i].val < num) {
curr = curr.forward[i];
}
update[i] = curr;
}
curr = curr.forward[0];
/* 如果值不存在则返回 false */
if (curr == null || curr.val != num) {
return false;
}
for (int i = 0; i < level; i++) {
if (update[i].forward[i] != curr) {
break;
}
/* 对第 i 层的状态进行更新，将 forward 指向被删除节点的下一跳 */
update[i].forward[i] = curr.forward[i];
}
/* 更新当前的 level */
while (level > 1 && head.forward[level - 1] == null) {
level--;
}
return true;
}
查找
跳表的查询操作利用了索引层的结构，通过逐层向下遍历来快速定位目标元素。每一层的遍历都是基于上一层的结果，根据比较结果决定向右还是向下移动。这样的设计可以提高查询效率。
- 从跳表的顶层索引开始，逐层向下遍历，直到找到目标元素或者达到原链表的最底层
- 目标值大于下一个节点时，搜索当前层的下一个节点（向右移动）
- 目标值小于下一个节点时，搜索下一层（向下移动）
- 比较搜索到的最底层节点值，相等则返回；否则表示目标元素不存在于跳表中
public boolean search(int target) {
SkiplistNode curr = this.head;
for (int i = level - 1; i >= 0; i--) {
/* 找到第 i 层小于且最接近 target 的元素*/
while (curr.forward[i] != null && curr.forward[i].val < target) {
curr = curr.forward[i];
}
}
curr = curr.forward[0];
/* 检测当前元素的值是否等于 target */
if (curr != null && curr.val == target) {
return true;
}
return false;
}
Java 实现源码
class Skiplist {
static final int MAX_LEVEL = 32;
static final double P_FACTOR = 0.25;
private SkiplistNode head;
private int level;
private Random random;
public Skiplist() {
this.head = new SkiplistNode(-1, MAX_LEVEL);
this.level = 0;
this.random = new Random();
}
public boolean search(int target) {
SkiplistNode curr = this.head;
for (int i = level - 1; i >= 0; i--) {
/* 找到第 i 层小于且最接近 target 的元素*/
while (curr.forward[i] != null && curr.forward[i].val < target) {
curr = curr.forward[i];
}
}
curr = curr.forward[0];
/* 检测当前元素的值是否等于 target */
if (curr != null && curr.val == target) {
return true;
}
return false;
}
public void add(int num) {
// 记录一下插入位置每层前一位置的节点, 需要将他们的指向全部更新为插入节点
SkiplistNode[] update = new SkiplistNode[MAX_LEVEL];
Arrays.fill(update, head);
SkiplistNode curr = this.head;
for (int i = level - 1; i >= 0; i--) {
/* 找到第 i 层小于且最接近 num 的元素*/
while (curr.forward[i] != null && curr.forward[i].val < num) {
curr = curr.forward[i];
}
update[i] = curr;
}
int lv = randomLevel();
level = Math.max(level, lv);
SkiplistNode newNode = new SkiplistNode(num, lv);
for (int i = 0; i < lv; i++) {
/* 对第 i 层的状态进行更新，将当前元素的 forward 指向新的节点 */
newNode.forward[i] = update[i].forward[i];
update[i].forward[i] = newNode;
}
}
public boolean erase(int num) {
SkiplistNode[] update = new SkiplistNode[MAX_LEVEL];
SkiplistNode curr = this.head;
for (int i = level - 1; i >= 0; i--) {
/* 找到第 i 层小于且最接近 num 的元素*/
while (curr.forward[i] != null && curr.forward[i].val < num) {
curr = curr.forward[i];
}
update[i] = curr;
}
curr = curr.forward[0];
/* 如果值不存在则返回 false */
if (curr == null || curr.val != num) {
return false;
}
for (int i = 0; i < level; i++) {
if (update[i].forward[i] != curr) {
break;
}
/* 对第 i 层的状态进行更新，将 forward 指向被删除节点的下一跳 */
update[i].forward[i] = curr.forward[i];
}
/* 更新当前的 level */
while (level > 1 && head.forward[level - 1] == null) {
level--;
}
return true;
}
private int randomLevel() {
int lv = 1;
/* 随机生成 lv */
while (random.nextDouble() < P_FACTOR && lv < MAX_LEVEL) {
lv++;
}
return lv;
}
}
class SkiplistNode {
int val;
SkiplistNode[] forward;
public SkiplistNode(int val, int maxLevel) {
this.val = val;
this.forward = new SkiplistNode[maxLevel];
}
}
参考资料：
- Skip List–跳表
- Redis进阶 - 数据结构：底层数据结构详解
热门推荐
耳石症患者如何复位治疗
种植牙后是否还能进行牙齿矫正？医生为您解答这个常见疑问
AC米兰历史最佳阵容发布！现役球员无一人入选 卡卡都落榜了？
AC米兰历史最佳阵容发布！现役球员无一人入选卡卡都落榜了？
当心！你爱吃的食物里可能有寄生虫，千万要少吃！
为什么要做肠镜检查的原因
沙畹论泰山信仰：一个神明是如何建立的
喝醋真的能降糖，但绝对不可以这样喝
增强数据分析能力的技能培训方法
中国饮食文化的意义，你知道吗？
得了银屑病需要注意什么？
麻醉评估是怎么做的
为什么时间在变快？假如地球停止自转，会发生什么？
探索宇宙背景噪声：我们能否通过“听到”宇宙揭开暗物质的秘密
服装工厂小工具的进化：技能与思维的进退之辩
107家券商2024年分类评价出炉！九大加分项、五大扣分点 旨在突出机构功能性
工业氮气的全面解析：性质、生产、应用及安全注意事项
哈尼族媳妇：将民族团结种在千年梯田之上
《注会经济法考点与真题全解析》——应试必看！
小鸡怎么养
周六001 大宫松鼠VS山口雷诺的历史交锋记录及近期伤停情况的综合分析
备份照片怎么合并
中介买卖房的收费标准是什么？这种标准对买卖双方有何影响？
勾股定理：揭秘直角三角形的奥秘
固态发蜡能带上飞机吗（固体发蜡120g能带上飞机吗）
G9811中线高速水潮互通建设进度过半
国债逆回购到底靠谱吗？你必须知道的投资真相！
如何理解国债逆回购的交易规则？这种交易规则对资金流动性有何影响？
善于总结前人的经验，元朝科学家郭守敬，更敢于大胆探索创新
额外关税：解析全球贸易政策对我国出口企业的影响