跳表（Skip List）的设计思想基于二叉查找树和链表，它采用了一种多层次的思路，通过随机化的方式在每个节点添加多个后继节点，从而实现快速查找
跳表是一种数据结构，它以一种分层的方式来存储数据，使得查找、插入和删除操作的时间复杂度可以达到O(log n)。跳表的思想可以追溯到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进阶 - 数据结构：底层数据结构详解
