目录

1.什么是跳表-skiplist

2.skiplist的效率如何保证？

3.skiplist的实现

3.1节点和成员设计

3.2查找实现

3.3前置节点查找

3.4插入实现

3.5删除实现

3.6随机层数

3.7完整代码

4.skiplist跟平衡搜索树和哈希表的对比

1.什么是跳表-skiplist

skiplist是由William Pugh发明的，最早出现于他在1990年发表的论文《Skip Lists: A
Probabilistic Alternative to Balanced Trees》。
skiplist，顾名思义，首先它是一个list。实际上，它是在有序链表的基础上发展起来的。如果是一个有序的链表，查找数据的时间复杂度是O(N)。

William Pugh开始的优化思路：

1. 假如我们每相邻两个节点升高一层，增加一个指针，让指针指向下下个节点，如下图b所
示。这样所有新增加的指针连成了一个新的链表，但它包含的节点个数只有原来的一半。由
于新增加的指针，我们不再需要与链表中每个节点逐个进行比较了，需要比较的节点数大概
只有原来的一半。

2. 以此类推，我们可以在第二层新产生的链表上，继续为每相邻的两个节点升高一层，增加一个指针，从而产生第三层链表。如下图c，这样搜索效率就进一步提高了。

如图b中，查找8，从头结点出发，6比8小，向右走，跳跃到6；8比9小，当前节点向下走，从下面指针出发，7比8小，跳转到7；8比9小，向下走，走不了了，链表中不存在8.

如图c中，查找19,比9大，向右走，跳跃到9；比21小，向下走，比17大，向右走，跳跃到17，比17大，向右走，跳跃到17，比21小，向下走，跟19相等，找到了。

3. skiplist正是受这种多层链表的想法的启发而设计出来的。实际上，按照上面生成链表的方
式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似
二分查找，使得查找的时间复杂度可以降低到O(log n)。但是这个结构在插入删除数据的时
候有很大的问题，插入或者删除一个节点之后，就会打乱上下相邻两层链表上节点个数严格
的2:1的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也
包括新插入的节点）重新进行调整，这会让时间复杂度重新蜕化成O(n)。

4. skiplist的设计为了避免这种问题，做了一个大胆的处理，不再严格要求对应比例关系，而是插入一个节点的时候随机出一个层数。这样每次插入和删除都不需要考虑其他节点的层数，这样就好处理多了（按时插入删除，我们仍然需要考虑其他节点对应层指针的连接问题）。细节过程入下图：

2.skiplist的效率如何保证？

上面我们说到，skiplist插入一个节点时随机出一个层数，听起来怎么这么随意，如何保证搜索时
的效率呢？
这里首先要细节分析的是这个随机层数是怎么来的。一般跳表会设计一个最大层数maxLevel的限
制，其次会设置一个多增加一层的概率p。那么计算这个随机层数的伪代码如下图：

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

p = 1/4
maxLevel = 32

根据前面randomLevel()的伪码，我们很容易看出，产生越高的节点层数，概率越低。定量的分析
如下：
节点层数至少为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)，

这个推导的过程较为复杂，需要有一定的数据功底，有兴趣的，可以参考以下文章中的讲解：

铁蕾大佬的博客：http://zhangtielei.com/posts/blog-redis-skiplist.html

William_Pugh大佬的论文：ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

3.skiplist的实现

1206. 设计跳表 - 力扣（LeetCode）

3.1节点和成员设计

跳表因为每个节点是层数是随机的，所以我们使用vector容器存储对应指针。

对于一开始的同节点，我们这里设计成一层高，减少后续不必要遍历消耗。

struct SkiplistNode
{int _val;vector<SkiplistNode*> _nextV;SkiplistNode(int val, int level):_val(val), _nextV(level, nullptr){}
};
class Skiplist {typedef SkiplistNode Node;
public:Skiplist() {//为了后续层数随机，这里提供种子srand(time(0));// 头节点，层数是1_head = new SkiplistNode(-1, 1);}private:Node* _head; // 头节点size_t _maxLevel = 32;//层数的最大高度double _p = 0.25;/多增加一层的概率p
};

3.2查找实现

依照跳表的设计，当我们查找一个数时，如果当前层的指针指向的数比要查找的数大，那我们就需要向下走，因为链表是有序的，比较小的数一定在前面，而且层高一定没有当前层指向节点高（如果搞就指向这个更小的数了。）所以我们要找比当前层指向节点小的数，需要向下层走。

反之，如果比当前层指向节点值比要查找的数小，说明要查找的数在后面，我们直接沿当前层指针往后跳转。

	bool search(int target) {Node* cur = _head;int level = _head->_nextV.size() - 1;while (level >= 0){// 目标值比下一个节点值要大，向右走// 下一个节点是空(尾)，目标值比下一个节点值要小，向下走if (cur->_nextV[level] && cur->_nextV[level]->_val < target){// 向右走cur = cur->_nextV[level];}else if (cur->_nextV[level] == nullptr || cur->_nextV[level]-> _val > target){// 向下走--level;}else{return true;}}return false;}

3.3前置节点查找

因为跳表中节点的层高没有严格的比例关系，因此一个节点可能由于层高较高，与前后多个节点有关系，如上图中6有4层，0层上，3指向它，6指向7；1层上头结点指向6,6指向9；2层上，头结点指向6,6指向25；3层上头结点指向6,6指向nullptr。

因此当我们删除或者增加一个节点，我们就需要建立它每一层上指针与其他节点间关系，同时也需要修改其他其他节点。

这就意味着当前要插入/删除节点，就需要从整个跳表中找到每一层指针对应的上一个节点，更新指针指向。

解决的思想是利用查找节点过程，因为当一层指针指向空或者比要查找的值大的值时，我们向下走，这同时也意味着此时这层节点就是当前要插入节点的当前层的上一层节点，同时这届指针指向的下层节点也就是插入节点指针要指向的下一个节点。我们通过查找节点不断向下走的过程，就能找到插入节点每一层的上一个节点和要指向的下一层节点。

需要注意的是当查找节点比当前节点大，直接跳转的过程，我们不能更新上一层节点的记录，因为这是只是同层节点间的跳转，我们不能确定插入节点当前层的上一个节点。

vector<Node*> FindPrevNode(int num){Node* cur = _head;int level = _head->_nextV.size() - 1;// 插入位置每一层前一个节点指针vector<Node*> prevV(level + 1, _head);while (level >= 0){// 目标值比下一个节点值要大，向右走// 下一个节点是空(尾)，目标值比下一个节点值要小，向下走if (cur->_nextV[level] && cur->_nextV[level]->_val < num){// 向右走cur = cur->_nextV[level];}else if (cur->_nextV[level] == nullptr|| cur->_nextV[level]->_val >= num){// 更新level层前一个prevV[level] = cur;// 向下走--level;}}return prevV;}

3.4插入实现

当我们能找到插入节点的每一层对应上一个节点，我们插入节点只需要更新对应的指向，上一个指针指向它，插入节点指向下一个节点。

这里需要注意的是，插入节点的层数我们封装一个函数来给在最大范围内的随机值，跳表的头结点需要确保是跳表中最高的节点，这样才不会出现无法跳转更高层的问题，所以如果当前的随机值如果比头节点高，我们就需要更新下头结点高度。

	void add(int num) {vector<Node*> prevV = FindPrevNode(num);int n = RandomLevel();//随机层数Node* newnode = new Node(num, n);// 如果n超过当前最大的层数，那就升高一下_head的层数if (n > _head->_nextV.size()){_head->_nextV.resize(n, nullptr);prevV.resize(n, _head);}// 链接前后节点for (size_t i = 0; i < n; ++i){newnode->_nextV[i] = prevV[i]->_nextV[i];prevV[i]->_nextV[i] = newnode;}// Print();}

3.5删除实现

删除节点后，我们需要根据找到的每一层的上一个节点，更新一下对应指针将删除节点上一个节点和指向下一个节点相连。

这里加入删除的节点是最高点，我们更新一下头结点的高度，避免每次从很高的位置向下遍历（不过就几层，相对来说影响不大）。

	bool erase(int num) {vector<Node*> prevV = FindPrevNode(num);// 第一层下一个不是val，val不在表中if (prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val !=num){return false;}else{Node* del = prevV[0]->_nextV[0];// del节点每一层的前后指针链接起来for (size_t i = 0; i < del->_nextV.size(); i++){prevV[i]->_nextV[i] = del->_nextV[i];}delete del;// 如果删除最高层节点，把头节点的层数也降一下int i = _head->_nextV.size() - 1;while (i >= 0){if (_head->_nextV[i] == nullptr)--i;elsebreak;}_head->_nextV.resize(i + 1);return true;}}

3.6随机层数

	//产生随机层数int RandomLevel(){size_t level = 1;//每一个节点最少一层。// 因为rand() ->[0, RAND_MAX]之间，所以RAND_MAX * _p的数出现概率就是p// 可以视作rand()/RAND_MAX <= pwhile (rand() <= RAND_MAX * _p && level < _maxLevel){++level;}return level;}//C++中的随机函数库，使用比较麻烦/*int RandomLevel(){static std::default_random_enginegenerator(std::chrono::system_clock::now().time_since_epoch().count());static std::uniform_real_distribution<double> distribution(0.0,1.0);size_t level = 1;while (distribution(generator) <= _p && level < _maxLevel){++level;}return level;}*/

3.7完整代码

struct SkiplistNode
{int _val;vector<SkiplistNode*> _nextV;SkiplistNode(int val, int level):_val(val), _nextV(level, nullptr){}
};
class Skiplist {typedef SkiplistNode Node;
public:Skiplist() {srand(time(0));// 头节点，层数是1_head = new SkiplistNode(-1, 1);}bool search(int target) {Node* cur = _head;int level = _head->_nextV.size() - 1;while (level >= 0){// 目标值比下一个节点值要大，向右走// 下一个节点是空(尾)，目标值比下一个节点值要小，向下走if (cur->_nextV[level] && cur->_nextV[level]->_val < target){// 向右走cur = cur->_nextV[level];}else if (cur->_nextV[level] == nullptr || cur->_nextV[level] -> _val > target){// 向下走--level;}else{return true;}}return false;}vector<Node*> FindPrevNode(int num){Node* cur = _head;int level = _head->_nextV.size() - 1;// 插入位置每一层前一个节点指针vector<Node*> prevV(level + 1, _head);while (level >= 0){// 目标值比下一个节点值要大，向右走// 下一个节点是空(尾)，目标值比下一个节点值要小，向下走if (cur->_nextV[level] && cur->_nextV[level]->_val < num){// 向右走cur = cur->_nextV[level];}else if (cur->_nextV[level] == nullptr|| cur->_nextV[level]->_val >= num){// 更新level层前一个prevV[level] = cur;// 向下走--level;}}return prevV;}void add(int num) {vector<Node*> prevV = FindPrevNode(num);int n = RandomLevel();Node* newnode = new Node(num, n);// 如果n超过当前最大的层数，那就升高一下_head的层数if (n > _head->_nextV.size()){_head->_nextV.resize(n, nullptr);prevV.resize(n, _head);}// 链接前后节点for (size_t i = 0; i < n; ++i){newnode->_nextV[i] = prevV[i]->_nextV[i];prevV[i]->_nextV[i] = newnode;}// Print();}bool erase(int num) {vector<Node*> prevV = FindPrevNode(num);// 第一层下一个不是val，val不在表中if (prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val !=num){return false;}else{Node* del = prevV[0]->_nextV[0];// del节点每一层的前后指针链接起来for (size_t i = 0; i < del->_nextV.size(); i++){prevV[i]->_nextV[i] = del->_nextV[i];}delete del;// 如果删除最高层节点，把头节点的层数也降一下int i = _head->_nextV.size() - 1;while (i >= 0){if (_head->_nextV[i] == nullptr)--i;elsebreak;}_head->_nextV.resize(i + 1);return true;}}int RandomLevel(){size_t level = 1;// rand() ->[0, RAND_MAX]之间while (rand() <= RAND_MAX * _p && level < _maxLevel){++level;}return level;}/*int RandomLevel(){static std::default_random_enginegenerator(std::chrono::system_clock::now().time_since_epoch().count());static std::uniform_real_distribution<double> distribution(0.0,1.0);size_t level = 1;while (distribution(generator) <= _p && level < _maxLevel){++level;}return level;}*/private:Node* _head; // 头节点size_t _maxLevel = 32;double _p = 0.25;
};

4.skiplist跟平衡搜索树和哈希表的对比

1. skiplist相比平衡搜索树(AVL树和红黑树)对比，都可以做到遍历数据有序，时间复杂度也差
不多。skiplist的优势是：a、skiplist实现简单，容易控制。平衡树增删查改遍历都更复杂。
b、skiplist的额外空间消耗更低。平衡树节点存储每个值有三叉链，平衡因子/颜色等消耗。
skiplist中p=1/2时，每个节点所包含的平均指针数目为2；skiplist中p=1/4时，每个节点所包
含的平均指针数目为1.33；


2. skiplist相比哈希表而言，就没有那么大的优势了。相比而言a、哈希表平均时间复杂度是
O(1)，比skiplist快。b、哈希表空间消耗略多一点。skiplist优势如下：a、遍历数据有序
b、skiplist空间消耗略小一点，哈希表存在链接指针和表空间消耗。c、哈希表扩容有性能损
耗。d、哈希表再极端场景下哈希冲突高，效率下降厉害，需要红黑树补足接力。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若转载，请注明出处：http://www.pswp.cn/news/923600.shtml
繁体地址，请注明出处：http://hk.pswp.cn/news/923600.shtml
英文地址，请注明出处：http://en.pswp.cn/news/923600.shtml

如若内容造成侵权/违法违规/事实不符，请联系英文站点网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

html实现右上角有个图标，鼠标移动到该位置出现手型，点击会弹出登录窗口。

html实现右上角有个图标，鼠标移动到该位置出现手型，点击会弹出登录窗口。

写了一段html代码实现的效果&#xff1a;实现右上角有个图标&#xff0c;鼠标移动到该位置出现手型&#xff0c;点击会弹出登录窗口。功能实现前端&#xff0c;没有实现后端。<!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF…
阅读更多...
STM32G4 电流环闭环(二) 霍尔有感运行

STM32G4 电流环闭环(二) 霍尔有感运行

目录一、STM32G4 电流环闭环(二) 霍尔有感运行2. 霍尔有感运行附学习参考网址欢迎大家有问题评论交流 (* ^ ω ^)一、STM32G4 电流环闭环(二) 霍尔有感运行 2. 霍尔有感运行 文章使用的BLDC在定子侧以互差120电角度的位置安装三个霍尔元件Ha&#xff0c;Hb&#xff0c;Hc。当…
阅读更多...
展示框选择

展示框选择

好的&#xff0c;非常感谢您提供更详细的项目情况。这是一个非常典型的父子组件通信场景。 根据您的新需求&#xff0c;我将对代码进行重构&#xff1a; FaultSelect.vue (子组件): 这个组件现在将变得更加“纯粹”。它只负责自身的下拉框逻辑&#xff0c;不关心外部按钮&#…
阅读更多...
第5课：上下文管理与状态持久化

第5课：上下文管理与状态持久化

第5课：上下文管理与状态持久化 课程目标 掌握上下文存储和检索策略 学习会话状态管理 了解数据持久化方案 实践实现上下文管理系统 课程内容 5.1 上下文管理基础 什么是上下文管理？ 上下文管理是Agent系统中维护和利用历史信息的能力，包括： 对话历史：用户与Agent的交互…
阅读更多...
计算机毕业设计 基于大数据技术的医疗数据分析与研究 Python 大数据毕业设计 Hadoop毕业设计选题【附源码+文档报告+安装调试】

计算机毕业设计 基于大数据技术的医疗数据分析与研究 Python 大数据毕业设计 Hadoop毕业设计选题【附源码+文档报告+安装调试】

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python、大数据、人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&…
阅读更多...
K8S集群管理(2)

K8S集群管理(2)

目录 1.什么是Pod的根容器&#xff1f; 2.解释Pod的生命周期。 3.Init类型容器有什么特点&#xff0c;主要用途&#xff1f; 4.Sidecar类型容器和Init容器的区别在哪&#xff1f; 5.什么是静态Pod&#xff1f; 6.说明K8s控制器的作用&#xff1f; 7.什么是ReplicaSet&#xff0…
阅读更多...
视频全模态referring分割：Ref-AVS: Refer and Segment Objects in Audio-Visual Scenes

视频全模态referring分割：Ref-AVS: Refer and Segment Objects in Audio-Visual Scenes

一、TL&#xff1b;DR 为什么要做&#xff1a;传统的referring分割无法使用音频模态&#xff0c;本文提出Reference audio-visual Segmentation本文怎么做&#xff1a;构建首个 Ref-AVS 基准数据集通过充分利用多模态提示&#xff0c;将音频信息通过和文本融合作为载体&#x…
阅读更多...
A股大盘数据-20250916分析

A股大盘数据-20250916分析

&#x1f4ca; 一、大盘数据深度分析1.1 &#x1f9ee; 市场活跃度与资金流向总成交额&#xff1a;沪深京合计约 2.37万亿元&#xff0c;市场交投活跃&#xff0c;深市成交&#xff08;13516.4亿&#xff09;明显高于沪市&#xff08;9897.9亿&#xff09;&#xff0c;显示中小…
阅读更多...
[计算机毕业设计]基于深度学习的噪声过滤音频优化系统研究

[计算机毕业设计]基于深度学习的噪声过滤音频优化系统研究

前言 &#x1f4c5;大四是整个大学期间最忙碌的时光,一边要忙着备考或实习为毕业后面临的就业升学做准备,一边要为毕业设计耗费大量精力。近几年各个学校要求的毕设项目越来越难,有不少课题是研究生级别难度的,对本科同学来说是充满挑战。为帮助大家顺利通过和节省时间与精力投…
阅读更多...
贪心算法应用：NFV功能部署问题详解

贪心算法应用：NFV功能部署问题详解

Java中的贪心算法应用&#xff1a;NFV功能部署问题详解 1. NFV功能部署问题概述 网络功能虚拟化(NFV, Network Function Virtualization)是一种将传统网络设备功能从专用硬件转移到虚拟化软件的技术。在NFV功能部署问题中&#xff0c;我们需要将各种虚拟网络功能(VNFs)部署到有…
阅读更多...
SeriLog测试

SeriLog测试

安装Serilog.Sinks.Seq(5.2.3.0)&#xff0c;Serilog.Sinks.File(7.0.0) 下载Seq安装包并安装&#xff08;https://datalust.co/download&#xff09; 代码如下&#xff1a; private Logger _logger;private void button1_Click(object sender, EventArgs e){_logger new Lo…
阅读更多...
HarmonyOS 5.0应用开发——V2装饰器@param的使用

HarmonyOS 5.0应用开发——V2装饰器@param的使用

【高心星出品】 文章目录V2装饰器param的使用概念使用方法案例V2装饰器param的使用 概念 在鸿蒙ArkTS开发中&#xff0c;Param装饰器是组件间状态管理的重要工具&#xff0c;主要用于父子组件间的单向数据传递&#xff0c;这一点与V1中的prop类似。 Param装饰的变量支持本地…
阅读更多...
SLAM ｜ 无人机视觉/激光雷达集群SLAM技术进展综述

SLAM ｜ 无人机视觉/激光雷达集群SLAM技术进展综述

主要内容如下： 无人机集群SLAM技术概述：介绍无人机集群SLAM的基本概念、重要性及面临的挑战，使用表格对比不同传感器配置的特点。 多传感器融合与协同SLAM架构：分析集中式、分布式和混合式协同架构的特点，使用表格对比不同架构的优缺点。 视觉协同SLAM的技术进展：总结直接…
阅读更多...
信息化系统运维文档资料，运维服务方案，运维巡检方案

信息化系统运维文档资料，运维服务方案，运维巡检方案

1、系统服务内容​1.1 服务目标​1.2 信息资产统计服务​1.3 网络与安全系统运维服务​1.4 主机与存储系统运维服务​1.5 数据库系统运维服务​1.6 中间件运维服务​2、服务管理制度规范​2.1 服务时间管理​2.2 运维人员行为规范​2.3 现场服务支持规范​2.4 问题记录与归档规…
阅读更多...
JavaScript——document对象

JavaScript——document对象

DOM 是 document object model&#xff08;文档对象模型&#xff09;的缩写。它是一种与平台、语言无关的接口&#xff0c;允许程序动态地访问或更新 HTML、XML 文档的内容、结构和样式&#xff0c;且提供了一系列的函数和对象来实现增、删、改、查操作。DOM 对象的一个特点是&…
阅读更多...
UART,IIC,SPI总线（通信协议）

UART,IIC,SPI总线（通信协议）

嵌 入 式 软 件 笔 试 题要求&#xff1a;闭卷考试&#xff08;不能翻书、不能开电脑&#xff09;&#xff1b;作答时间50分钟&#xff1b;共10道题目。volatile的作用有哪些volatile&#xff1a; 防止编译器对代码进行优化&#xff0c;直接从内存中取最新的值 应用场景&#x…
阅读更多...
通信模组性能调优

通信模组性能调优

通信模组性能调优 1 背景 2 高通平台软硬加速 2.1 NSS 2.2 SFE 2.3 PPE 3 CPU 负载均衡设置 3.1 启用内核 RPS&RFS 功能 3.2 网卡队列修改建议 3.3 调整负载前后的 CPU 使用对比 3.4 网卡中断均衡 3.4.1 netdev_max_backlog 3.4.2 中断绑核 3.5 CPU性能模式 3.6 热管理 3.7…
阅读更多...
消息队列kafka的事务特性

消息队列kafka的事务特性

kafka的java客户端producer也支持事务消息吗&#xff1f;具体是啥事务呢&#xff1f; 是的&#xff0c;Kafka的Java客户端Producer确实支持事务消息。让我详细解释Kafka事务的概念和使用方法。 Kafka事务的主要特点&#xff1a; Producer Transactions&#xff1a;确保多个消息…
阅读更多...
用Python实现自动化的Web测试（Selenium）

用Python实现自动化的Web测试（Selenium）

Python作为数据科学和自动化领域的主流语言&#xff0c;在网络爬虫开发中占据着重要地位。本文将全面介绍Python爬虫的技术栈、实现方法和最佳实践。爬虫技术概述网络爬虫&#xff08;Web Crawler&#xff09;是一种按照特定规则自动抓取互联网信息的程序。它可以自动化地浏览网…
阅读更多...
「Memene 摸鱼日报 2025.9.17」上海张江人工智能创新小镇正式启动，华为 DCP 技术获网络顶会奖项

「Memene 摸鱼日报 2025.9.17」上海张江人工智能创新小镇正式启动，华为 DCP 技术获网络顶会奖项

theme: condensed-night-purple 以下内容包括「人工智能生成内容」 上海张江人工智能创新小镇正式启动&#xff0c;华为 DCP 技术获网络顶会奖项 &#x1f44f;在昨天&#xff08;2025.9.16&#xff09;&#xff0c;AI领域有这些内容可能值得你关注&#xff1a; 上海张江人工智…
阅读更多...
最新文章

Copyright @ 2022~2023