线性表3：跳表SkipList
链表的查询劣势
链表，即使是有序的链表，在插入、删除，查找之前都需要就行查找操作以确认操作位置。而查找过程只能通过遍历完成，使得很多时候，数据的操作都要有O(n)的时间复杂度。
链表优化
那么，我们能否构建一条快速通道，在元素小于目标元素的时候跳过大多数小于当前数据的元素，从而实现快速查找呢？
3： 【5】
↓
2：【1】 —————————> 【5】—————————> 【10】
↓ ↓ ↓
1：【1】【2】【3】【4】【5】【6】【7】【8】【9】【10】如上图，当我们需要查找6的时候，我们先从顶部5开始查找，当前元素小于6，但是后续没有节点，于是向下查找，还是5，小于6但是后续节点比6大，于是再向下查找，最后查找到6的位置。
这样我们跳过了从1到4的遍历比较过程。通过层层降级获得了极高的查找性能。
跳表
跳表（Skip List）是一种基于概率的、多层的有序链表数据结构，其设计目的是在保持有序性的同时提供接近平衡树的查询效率（平均时间复杂度为O(log n)）。
跳表实现起来要比树简单很多，在链表基础上构建多层结构，以达到构建快速通道的目的。Redis的有序List就是基于跳表实现的。
跳表节点的层级是随机生成的，随机数的生成规则遵循幂次法则（2-8定律，百分之20的关键节点，百分之八十的常规节点）
private static final double P = 0.25;
/**
* 生成符合幂次定理的level
* @return
*/
private int randomLevel() {
int level = 0;
// 每次只有四分之一的机会加一
while (random.nextDouble() < P)
level += 1;
return Math.min(level, MAX_LEVEL);
} 实现：
package cn.lishiyuan.algorithm.list;
import java.util.Objects;
import java.util.Random;
/**
* 跳表
*
* head * ↓ * head ——————> 5 * ↓ ↓ * head -> 1 -> 5 -> 10 * ↓ ↓ ↓ ↓ * head -> 1->4->5->6->10 * */
public class SkipList<T extends Comparable<T>> {
// 最多32层
public static final int MAX_LEVEL = (32 - 1);
Node<T> head = null;
private int size = 0;
private Random random = new Random();
public final static class Node<T extends Comparable<T>>{
T data;
// 层级
LevelInfo<T>[] levelInfos;
public final static class LevelInfo<T extends Comparable<T>>{
// 同层上一个元素
Node<T> prev = null;
// 同层的下一个元素
Node<T> next = null;
// 下一层元素
Node<T> down = null;
}
}
public SkipList(){
size = 0;
// 首节点
head = newNode(MAX_LEVEL, null);
}
public void add(T data) {
if(Objects.isNull(data)){
throw new IllegalArgumentException("不能为空");
}
int level = randomLevel();
Node<T> node = newNode(level,data);
Node<T> prev = head;
// 循环插入节点
for(int i = level;i >= 0; i--){
// 查询每一层的节点查找第一个大于当前元素的node
while (prev.levelInfos[i].next != null && prev.levelInfos[i].next.data.compareTo(data) <= 0){
// 继续向后查找
prev = prev.levelInfos[i].next;
}
// 当前元素的下个元素就是下个元素
node.levelInfos[i].next = prev.levelInfos[i].next;
node.levelInfos[i].prev = prev;
// 下个元素是当前元素
if(prev.levelInfos[i].next != null){
prev.levelInfos[i].next.levelInfos[i].prev = node;
}
prev.levelInfos[i].next = node;
}
size++;
}
public T remove(T data) {
if(Objects.isNull(data)){
throw new IllegalArgumentException("不能为空");
}
if(isEmpty()){
return null;
}
Node<T> node = findNode(data);
if(node == null){
return null;
}
for (int i = node.levelInfos.length - 1; i >= 0; i--) {
// 本层元素的上一个元素
Node<T> prev = node.levelInfos[i].prev;
prev.levelInfos[i].next = node.levelInfos[i].next;
if(node.levelInfos[i].next != null){
// 本层元素的下个元素的上个元素是当前元素的上个元素
node.levelInfos[i].next.levelInfos[i].prev = prev;
}
// 垃圾回收
node.levelInfos[i].next = null;
node.levelInfos[i].prev = null;
}
size--;
return node.data;
}
public T search(T data) {
if(Objects.isNull(data)){
throw new IllegalArgumentException("不能为空");
}
Node<T> node = findNode(data);
return node!=null ? node.data : null;
}
public boolean contains(T data){
if(Objects.isNull(data)){
throw new IllegalArgumentException("不能为空");
}
Node<T> node = findNode(data);
return node != null;
}
private Node<T> findNode(T data){
if(isEmpty()){
return null;
}
int i = MAX_LEVEL;
Node<T> now = head;
// 查询每一层的节点查找第一个大于当前元素的node
while (now != null){
// 头节点
if(now.data==null){
if(now.levelInfos[i].next == null || now.levelInfos[i].next.data.compareTo(data) > 0){
// 向下
now = now.levelInfos[i].down;
i--;
}else{
// 向右
now = now.levelInfos[i].next;
}
continue;
}
if(now.data.compareTo(data) == 0){
// 如果当前元素等于元素则直接返回
return now;
}else if(now.data.compareTo(data) < 0 && (now.levelInfos[i].next== null || now.levelInfos[i].next.data.compareTo(data) > 0)){
// 如果当前元素的next为null 或者next大于当前元素则向下查找
now = now.levelInfos[i].down;
i--;
}else if(now.data.compareTo(data) < 0 && (now.levelInfos[i].next.data.compareTo(data) <= 0)){
// 如果当前元素小于目标元素，下个元素小于目标i元素则走向下个元素
now = now.levelInfos[i].next;
}
// else {
// // 当前元素大于目标，则没有找到，这种情况不可能发生
// return null;
// }
}
return null;
}
public int size(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
// 构建节点
private Node<T> newNode(int level, T data){
Node<T> node = new Node<>();
node.data = data;
node.levelInfos = new Node.LevelInfo[level+1];
Node<T> downNode = null;
for (int i = 0; i <= level; i++) {
Node.LevelInfo<T> levelInfo = new Node.LevelInfo<T>();
levelInfo.down = downNode;
node.levelInfos[i] = levelInfo;
downNode = node;
}
return node;
}
private static final double P = 0.25;
/**
* 生成符合幂次定理的level
* @return
*/
private int randomLevel() {
int level = 0;
// 每次只有四分之一的机会加一
while (random.nextDouble() < P)
level += 1;
return Math.min(level, MAX_LEVEL);
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
for (int i = MAX_LEVEL; i >= 0; i--) {
Node<T> node = head;
while (node != null) {
sb.append("--> ").append(node.data).append(" ");
node = node.levelInfos[i].next;
}
sb.append("\n");
}
return sb.toString();
}
}通过构建层级数组LevelInfo，记录当前节点在每一层的前后节点与下层节点。跳表通过“以空间换时间”的策略，在链表的基础上实现了接近平衡树的效率，同时保持了动态操作的灵活性和实现的简洁性。
时间复杂度
查找、插入、删除操作
跳表通过多级索引实现高效的查找逻辑。每一层索引的节点数约为下一层的 1/p（通常取 p=0.5），因此总层数为 O(logn)。
- 在查找时，从最高层开始逐层下探，每层最多遍历常数个节点（如3个），最终时间复杂度为 O(logn)
- 插入和删除操作需要先定位目标节点（O(logn)），再更新各层指针（O(1) per level），总时间复杂度仍为 O(logn)
层数生成
通过概率模型（如以 p=0.25 的概率增加一层），生成节点的随机层数，期望层数为 O(logn)，不会显著影响整体复杂度
空间复杂度
节点存储
每个节点的平均层数为 1/(1−p)（如 p=0.5 时平均层数为2），因此总空间复杂度为 O(n)，其中 n 是节点总数。
- 例如，若每层索引的节点数为 n/2,n/4,…，总节点数为 n+n/2+n/4+⋯=2n，即空间复杂度为 O(n)
概率模型的影响
通过调整概率 p，可以在时间效率与空间消耗之间权衡。较小的 p（如 p=0.25）会减少索引层数，降低空间开销，但可能略微增加查找时间
评论已关闭