其它高阶数据结构⑦_Skiplist跳表_概念+实现+对比

2024-05-25 13:52
文章标签 实现 数据结构 概念 高阶 对比 跳表 skiplist

本文主要是介绍其它高阶数据结构⑦_Skiplist跳表_概念+实现+对比，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

1. Skiplist跳表的概念

2. Skiplist跳表的效率

3. Skiplist跳表的实现

3.1 力扣1206. 设计跳表

3.2 Skiplist的初始化和查找

3.3 Skiplist的增加和删除

3.4 Skiplist的源码和OJ测试

4. 跳表和平衡搜索树/哈希表的对比

本篇完。

1. Skiplist跳表的概念

        skiplist是由美国计算机科学家William Pugh（威廉 普格）于1989年发明。skiplist本质上是一种查找结构，用于解决算法中的查找问题，跟平衡搜索树和哈希表的价值是 一样的，可以作为key或者key/value的查找模型。skiplist，顾名思义，首先它是一个list。实际上，它是在有序链表的基础上发展起来的。我们知道在对一个有序链表进行查找，它的时间复杂度为O(N)。

William Pugh开始了他的优化思路：

假如我们每相邻两个节点升高一层，增加一个指针，让指针指向下下个节点，如下图所示：

        这样新增的一层指针通过连接可以形成新的链表，它包含了整个链表节点的一半，由此需要在这一层进行比较、筛除的个数也就降低了一半。

        以此类推，继续增加一层指针，新链表的节点数下降，查找的效率自然而然也就提高了。按照上述每增加一层，节点数就少一半，其查找的过程类似于二分查找，使得查找的时间复杂度可以降低到O（logN）。

        上述查找的前提是一个有序的链表。无论是对其中的链表新增节点，还是删除节点，都可能打乱原有维持的指针连接，从而导致跳表失效。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度重新退化成O（N）。

        随机层数: 为了避免这种情况，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）的证明，这推导的过程较为复杂，下面的两篇中英文章有详细讲解：

铁蕾大佬的博客：Redis内部数据结构详解(6)——skiplist - 铁蕾的个人博客

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

3. Skiplist跳表的实现

力扣上有一道实现跳表的题，可以在这上面完成跳表的测试：

3.1 力扣1206. 设计跳表

1206. 设计跳表

难度 困难

不使用任何库函数，设计一个 跳表 。

跳表 是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。

例如，一个跳表包含 [30, 40, 50, 60, 70, 90] ，然后增加 80、45 到跳表中，以下图的方式操作：

跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n))，空间复杂度是 O(n)。

了解更多 : 跳表 - OI Wiki

在本题中，你的设计应该要包含这些函数：

  • bool search(int target) : 返回target是否存在于跳表中。
  • void add(int num): 插入一个元素到跳表。
  • bool erase(int num): 在跳表中删除一个值，如果 num 不存在，直接返回false. 如果存在多个 num ，删除其中任意一个即可。

注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。

示例 1:

输入
["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"]
[[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]
输出
[null, null, null, null, false, null, true, false, true, false]解释
Skiplist skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0);   // 返回 false
skiplist.add(4);
skiplist.search(1);   // 返回 true
skiplist.erase(0);    // 返回 false，0 不在跳表中
skiplist.erase(1);    // 返回 true
skiplist.search(1);   // 返回 false，1 已被擦除

提示:

  • 0 <= num, target <= 2 * 10^4
  • 调用search, add,  erase操作次数不大于 5 * 10^4 
class Skiplist {
public:Skiplist() {}bool search(int target) {}void add(int num) {}bool erase(int num) {}
};/*** Your Skiplist object will be instantiated and called as such:* Skiplist* obj = new Skiplist();* bool param_1 = obj->search(target);* obj->add(num);* bool param_3 = obj->erase(num);*/

3.2 Skiplist的初始化和查找

Skiplist的初始化：

        跳表不仅仅是要存储数据 _data，还需要有next指针，当然这些next指针也不止一个 这取决于当前节点的层数。

结合此图就可以知道next指针应该在一个数组中：

class SkiplistNode
{
public:int _val;vector<SkiplistNode*> _nextV;SkiplistNode(int val, int level):_val(val), _nextV(level, nullptr){}
};class Skiplist
{
private:typedef SkiplistNode Node;Node* _head;size_t _maxLevel = 32;double _p = 0.5;
public:Skiplist(){_head = new SkiplistNode(-1, 1); // 头节点，层数是1}
}

Skiplist的search查找：

        查找的过程：查找是要和下一个节点的值相比，并不是和当前节点的值相比一开始cur在哨兵位头节点的最高层 head，开始进行比较。设要查找的值为target，如果下一个节点为空或者下一个节点的值比target大，那么cur需要向下一层走，如果下一个节点的值比targe小，那么cur向右走。重复上述过程，直至找到或者没找到（没找到的话，cur会到第-1层，层数是从第0层开始的）

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 Skiplist的增加和删除

Skiplist的add增加：

假设要增加17，要怎么操作？

  1. 获得这个结点的层数：RandomLevel( );
  2. 找到这个结点的前后链接关系（此过程就像查找这个结点每一层的前一个结点，后面的删除结点也需要用到，所以封装成一个FindPrevNode函数）：比如查找17的话就是prev_val < 17 < next_val，需要从头结点开始找，记录每一层的前一个指针。
	Skiplist(){srand(time(nullptr)); // 构造函数种下随机数种子_head = new SkiplistNode(-1, 1); // 头节点，层数是1}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){prevV[level] = cur; // 更新level层前一个--level; //下一个节点是空(尾)，目标值比下一个节点值要小，向下走}}return prevV;}void add(int num){vector<Node*> prevV = FindPrevNode(num);int n = RandomLevel();Node* newnode = new Node(num, n);if (n > _head->_nextV.size()) // 如果n超过当前最大的层数，那就升高一下_head的层数{_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;}}int RandomLevel(){size_t level = 1; // rand() ->[0, RAND_MAX]之间while (rand() <= RAND_MAX * _p && level < _maxLevel){++level;}return level;}

这里的RandomLevel()是以一种巧妙的方式完成的：

        通过_p可以控制最终值产生范围的概率。如_p是0.5的话，生成的随机数小于RAND_MAX的一半才可能增加层数。

Skiplist的erase删除：

删除怎么操作？假设现在要删除17：

        删除的操作和增加的操作几乎一样，通过FindPrevNode找到该结点的所有前驱结点，让所有前驱结点指向被删除结点的next即可。

	bool erase(int num){vector<Node*> prevV = FindPrevNode(num);if (prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num){return false; // 第一层下一个不是val，val不在表中}else{Node* del = prevV[0]->_nextV[0];for (size_t i = 0; i < del->_nextV.size(); i++) // del节点每一层的前后指针链接起来{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.4 Skiplist的源码和OJ测试

class SkiplistNode
{
public:int _val;vector<SkiplistNode*> _nextV;SkiplistNode(int val, int level):_val(val), _nextV(level, nullptr){}
};class Skiplist
{
private:typedef SkiplistNode Node;Node* _head;size_t _maxLevel = 32;double _p = 0.5;
public:Skiplist(){srand(time(nullptr)); // 构造函数种下随机数种子_head = new SkiplistNode(-1, 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){prevV[level] = cur; // 更新level层前一个--level; //下一个节点是空(尾)，目标值比下一个节点值要小，向下走}}return prevV;}void add(int num){vector<Node*> prevV = FindPrevNode(num);int n = RandomLevel();Node* newnode = new Node(num, n);if (n > _head->_nextV.size()) // 如果n超过当前最大的层数，那就升高一下_head的层数{_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;}}int RandomLevel(){size_t level = 1; // rand() ->[0, RAND_MAX]之间while (rand() <= RAND_MAX * _p && level < _maxLevel){++level;}return level;}bool erase(int num){vector<Node*> prevV = FindPrevNode(num);if (prevV[0]->_nextV[0] == nullptr || prevV[0]->_nextV[0]->_val != num){return false; // 第一层下一个不是val，val不在表中}else{Node* del = prevV[0]->_nextV[0];for (size_t i = 0; i < del->_nextV.size(); i++) // del节点每一层的前后指针链接起来{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;}}
};/*** Your Skiplist object will be instantiated and called as such:* Skiplist* obj = new Skiplist();* bool param_1 = obj->search(target);* obj->add(num);* bool param_3 = obj->erase(num);*/

4. 跳表和平衡搜索树/哈希表的对比

跳表和平衡搜索树的对比：

        跳表相比平衡搜索树（AVL树和红黑树）对比都可以做到遍历数据有序，时间复杂度也差不多，都是O（logN）。不过跳表与平衡搜索树相比，跳表的优势在于：

  • 跳表实现简单，容易控制。平衡树增删查改遍历都更复杂。
  • 跳表的额外空间消耗更低。平衡树节点存储每个值有三叉链，平衡因子/颜色等消耗。可是跳表可以通过p来调整每个节点的指针个数，那是个可接受的数量。

跳表和哈希表的对比：

        跳表相比哈希表而言，跳表在查找效率上更差一点。哈希表平均时间复杂度是O（1），比跳表的O（logN）快。

skiplist与哈希表相比，skiplist的优势在于：

  • 遍历数据有序。
  • skiplist空间消耗略小一点，哈希表存在链接指针和表空间消耗。
  • 哈希表在极端场景下哈希冲突高，效率下降厉害，需要红黑树补足接力。

本篇完。

高阶数据结构到这先暂告一段落了。

这篇关于其它高阶数据结构⑦_Skiplist跳表_概念+实现+对比的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1001693。

相关文章

Spring Boot 实现 IP 限流的原理、实践与利弊解析

Spring Boot 实现 IP 限流的原理、实践与利弊解析

《SpringBoot实现IP限流的原理、实践与利弊解析》在SpringBoot中实现IP限流是一种简单而有效的方式来保障系统的稳定性和可用性,本文给大家介绍SpringBoot实现IP限... 目录一、引言二、IP 限流原理2.1 令牌桶算法2.2 漏桶算法三、使用场景3.1 防止恶意攻击3.2 控制资源
阅读更多...
springboot下载接口限速功能实现

springboot下载接口限速功能实现

《springboot下载接口限速功能实现》通过Redis统计并发数动态调整每个用户带宽,核心逻辑为每秒读取并发送限定数据量,防止单用户占用过多资源,确保整体下载均衡且高效,本文给大家介绍spring... 目录 一、整体目标 二、涉及的主要类/方法✅ 三、核心流程图解（简化） 四、关键代码详解1️⃣ 设置
阅读更多...
Nginx 配置跨域的实现及常见问题解决

Nginx 配置跨域的实现及常见问题解决

《Nginx配置跨域的实现及常见问题解决》本文主要介绍了Nginx配置跨域的实现及常见问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来... 目录1. 跨域1.1 同源策略1.2 跨域资源共享（CORS）2. Nginx 配置跨域的场景2.1
阅读更多...
Python中提取文件名扩展名的多种方法实现

Python中提取文件名扩展名的多种方法实现

《Python中提取文件名扩展名的多种方法实现》在Python编程中,经常会遇到需要从文件名中提取扩展名的场景,Python提供了多种方法来实现这一功能,不同方法适用于不同的场景和需求,包括os.pa... 目录技术背景实现步骤方法一：使用os.path.splitext方法二：使用pathlib模块方法三
阅读更多...
CSS实现元素撑满剩余空间的五种方法

CSS实现元素撑满剩余空间的五种方法

《CSS实现元素撑满剩余空间的五种方法》在日常开发中，我们经常需要让某个元素占据容器的剩余空间，本文将介绍5种不同的方法来实现这个需求，并分析各种方法的优缺点，感兴趣的朋友一起看看吧... css实现元素撑满剩余空间的5种方法 在日常开发中，我们经常需要让某个元素占据容器的剩余空间。这是一个常见的布局需求
阅读更多...
CSS中的Static、Relative、Absolute、Fixed、Sticky的应用与详细对比

CSS中的Static、Relative、Absolute、Fixed、Sticky的应用与详细对比

《CSS中的Static、Relative、Absolute、Fixed、Sticky的应用与详细对比》CSS中的position属性用于控制元素的定位方式，不同的定位方式会影响元素在页面中的布... css 中的 position 属性用于控制元素的定位方式，不同的定位方式会影响元素在页面中的布局和层叠关
阅读更多...
HTML5 getUserMedia API网页录音实现指南示例小结

HTML5 getUserMedia API网页录音实现指南示例小结

《HTML5getUserMediaAPI网页录音实现指南示例小结》本教程将指导你如何利用这一API，结合WebAudioAPI，实现网页录音功能,从获取音频流到处理和保存录音，整个过程将逐步... 目录1. html5 getUserMedia API简介1.1 API概念与历史1.2 功能与优势1.3
阅读更多...
Java实现删除文件中的指定内容

Java实现删除文件中的指定内容

《Java实现删除文件中的指定内容》在日常开发中,经常需要对文本文件进行批量处理,其中,删除文件中指定内容是最常见的需求之一,下面我们就来看看如何使用java实现删除文件中的指定内容吧... 目录1. 项目背景详细介绍2. 项目需求详细介绍2.1 功能需求2.2 非功能需求3. 相关技术详细介绍3.1 Ja
阅读更多...
使用Python和OpenCV库实现实时颜色识别系统

使用Python和OpenCV库实现实时颜色识别系统

《使用Python和OpenCV库实现实时颜色识别系统》：本文主要介绍使用Python和OpenCV库实现的实时颜色识别系统,这个系统能够通过摄像头捕捉视频流,并在视频中指定区域内识别主要颜色（红... 目录一、引言二、系统概述三、代码解析1. 导入库2. 颜色识别函数3. 主程序循环四、HSV色彩空间详解
阅读更多...
PostgreSQL中MVCC 机制的实现

PostgreSQL中MVCC 机制的实现

《PostgreSQL中MVCC机制的实现》本文主要介绍了PostgreSQL中MVCC机制的实现,通过多版本数据存储、快照隔离和事务ID管理实现高并发读写,具有一定的参考价值,感兴趣的可以了解一下... 目录一 MVCC 基本原理python1.1 MVCC 核心概念1.2 与传统锁机制对比二 Postg
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2