Redis中的跳表数据结构详解-CSDN博客

本文链接：https://blog.csdn.net/classify233/article/details/85267796

跳表是一种随机化的数据结构，常用于高效查询，其查询效率接近于二叉查找树。基本思想是在有序链表上添加前进链接，形成多层结构。跳表的特征包括多层有序链表，每层包含所有元素等。插入操作涉及随机选择层数，并自顶向下插入。删除操作与插入类似。Redis中的跳表实现包括SkipListNode类、AbstractSortedSet类、SkipList类和SkipListIterator类，分别负责节点、集合、整个跳表和迭代器的功能。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

著名开源软件Redis使用跳表。

跳表

一种随机化的数据结构，基于并联的链表，查询效率可以比拟二叉查找树，对于大多数操作需要O(logn)时间

基本思想：在有序的链表上，附加前进链接。

跳表的特征：

（1）跳表由多层组成

（2）每一层都是有序的链表

（3）第一层包含所有元素

（4）如果x出现在第i层，所有比i小的层都包含x

（5）第i层的元素通过一个down指针指向下一层拥有相同值的元素

（6）在每一层中都包含-1和1两个元素，分别表示INT_MIN和INT_MAX

（7）Top指针指向最高层的第一个元素

跳表的插入：

STEP1：查找到每一层的待插入位置

STEP2：随机产生一个层数

STEP3：从高层往下插入，插入算法与普通链表相同。

删除操作与插入类似，找到每一层需要删除的位置，之后删除操作与普通链表一样。

注：如果该结点层数最大，需要更新跳表的level。

代码实现：

SkipListNode类：

成员变量：value 记录值

nextnodes[i] 表示第i层的下一个结点

成员函数：level() 记录最高层数

import java.util.ArrayList;
import java.util.List;

public class SkipListNode<E> {
    private E value;
    public List<SkipListNode<E> > nextnodes;   //每一层的下一个结点集合

    public E getValue() {
        return value;
    }

    public SkipListNode(E data){
        this.value = data;
        nextnodes = new ArrayList<>();
    }

    public int level(){
        return nextnodes.siz