- 综合排序
- 最热优先
- 最新优先
- 来自专栏golang算法架构leetcode技术php
golang刷leetcode 经典（4） 实现跳表
跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。 例如，一个跳表包含 [30, 40, 50, 60, 70, 90]，然后增加 80、45 到跳表中，以下图的方式操作： 跳表中有很多层，每一层是一个短的链表。 skiplist.add(1); skiplist.add(2); skiplist.add(3); skiplist.search(0); // 返回 false skiplist.add(4) 3，SkipList基本数据结构及其实现 一个跳表，应该具有以下特征： 1>,一个跳表应该有几个层（level）组成； 2>,跳表的第一层包含所有的元素； 3>,每一层都是一个有序的链表； 4>,如果元素 x出现在第i层，则所有比i小的层都包含x； 5>,每个节点包含key及其对应的value和一个指向同一层链表的下个节点的指针数组 4，注意问题 1>,如果放任增长，高度失去控制会影响效果，所以一般会限制最高高度
34110编辑于 2022-08-02 - 来自专栏阿伟的个人博客
跳表
增加了向前指针的链表叫作跳表。跳表全称叫做跳跃表，简称跳表。跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。 以上图为例，若待插入的结点为4， 其生成的高度为3。 （对于高度，例如头结点从下往上一次为第一层， 第二层，第三层，第四层） 首先从头结点的第三层开始，发现其下一个位置是5大于4了，因此知道在第三层，应该插入到头结点后面。 对于第二层首先发现一个结点为3，小于4，继续后移，发现下一个结点为5，因此第二层插入到3后面。 对于第一层，发现3的下一个结点为5，大于4，插入3后面即可。 还是以该跳表为例，若我们待删除的元素为3。
53930发布于 2020-08-12 - 来自专栏机械之心
跳表
# 跳表的时间复杂度 在一个具有多级索引的跳表中，第一级索引的结点个数大约就是 n/2 ，第二级索引的结点个数大约就是 n/4 ，第三级索引的结点个数大约就是 n/8 ，依次类推，也就是说，第 k 级索引的结点个数是第 所以跳表查询数据的时间复杂度就是 O(logn) 。 # 跳表的空间复杂度 比起单纯的单链表，跳表需要存储多级索引，肯定要消耗更多的存储空间。 假设原始链表大小为 n，那第一级索引大约有 n/2 个结点，第二级索引大约有 n/4 个结点，以此类推，每上升一级就减少一半，直到剩下 2 个结点。 索引节点数 = n/2 + n/4 + n/8 … + 8 + 4 + 2 = n-2 所以，跳表的空间复杂度是 O(n) 。 跳表的存储空间其实还有压缩空间。 # 为什么需要跳表 跳表是一种动态数据结构，支持快速的插入、删除、查找操作，时间复杂度都是 O(logn) 。 跳表的空间复杂度是 O(n) 。
50620编辑于 2023-04-07 - 来自专栏程序猿~
跳表 - skipList
简介 SkipList(跳表)这种数据结构是由William Pugh于1990年在在 Communications of the ACM June 1990, 33(6) 668-676 发表了Skip String> concurrentSkipListSet = new ConcurrentSkipListSet<>(); 2.Redis Redis当中的Sorted-set这种有序的集合，正是对于跳表的改进和应用 3.Google的著名项目Bigtable 跳表java实现 版本1 public class SkipList{ //结点“晋升”的概率 private static final double System.out.println(); } //链表结点类 public class Node { public int data; //跳表结点的前后和上下都有指针 list.printList(); list.search(50); list.remove(50); list.search(50); } } 参考 漫画：什么是 “跳表
63030发布于 2020-08-27 - 来自专栏C/C＋＋、数据结构、算法
DS高阶：跳表
一般跳表会设计一个最大层数maxLevel的限制，其次会设置一个多增加一层的概率p。 那么计算这个随机层数的伪代码如下图： 一个节点的平均层数（也即包含的平均指针数目），计算如下： 现在很容易计算出： 当p=1/2时，每个节点所包含的平均指针数目为2； 当p=1/4时，每个节点所包含的平均指针数目为 时间复杂度：logN 具体的分析可以看下面的文章：Redis内部数据结构详解(6)——skiplist 2、skiplist的模拟实现 力扣有一道设计跳表的题. - 力扣（LeetCode）设计跳表 基本的调表需要实现4个函数：构造函数、搜索、插入、删除。 平衡树节点存储每个值有三叉链，平衡因子/颜色等消耗skiplist中p=1/2时，每个节点所包含的平均指针数目为2；skiplist中p=1/4时，每个节点所包含的平均指针数目为1.33； 2. skiplist
28500编辑于 2024-05-26 - 来自专栏山行AI
浅析skiplist(跳表)
skiplist(跳表)的应用场景 1. 跳表 1. 结构 跳表由William Pugh 1989年发明。 跳表特性 一个普通的有序链表: ? 如果从上面的列表中查找23需要遍历4次，查找59时需要遍历6次。而对这个链表，我们没法使用二分查找。 于是我们对数据节点加上一级索引如下图： ? 相比于二叉查找树，跳表维持结构平衡的成本比较低，完全靠随机。而二叉查找树需要Rebalance来重新调整平衡的结构。 4. java实现 存储结构一般为: ? jdk中提供的实现主要有：ConcurrentSkipListMap与ConcurrentSkipListSet，其中后者是基于前者实现的。
2.8K40发布于 2019-06-28 - 来自专栏慕枫技术笔记
这玩意叫跳表？
跳表介绍 跳表结构 在说明跳表数据结构特点之前，我们先来回顾下链表的数据结构。 length; //跳表长度 int level; //跳表的层级 } zskiplist; 上文中我们提到过跳表的本质是具备多级索引的链表，因此只要知道了头节点或者尾节点就可以访问整个跳表数据了 另外跳表长度表示跳表中包含的跳表节点数，而level则表示跳表拥有多少层检索索引。 了解了跳表的结构之后，我们在深入看下跳表中的节点是怎样的结构，如下所示： //跳表节点结构体 typedef struct zskiplistNode { //跳表元素 sds ele; Redis中跳表的数据检索流程大致如下： 总结 本文主要对跳表这个不常用的数据结构进行了介绍，同时分析了二分查找思想在跳表中的应用，重点阐述了跳表的数据结构特征。
60610编辑于 2023-03-20 - 来自专栏C++&linux
【数据结构】跳表
一、跳表是什么？ 1. （话说的太绕了，大家可以直接看图） 4. 既然层数增长是概率性的，那其实我们可以粗略的直接以概率来算出每层节点的个数，最高层节点个数趋近于1，那从最高层开始逐渐向下查找的过程，每次排除非目标的关键字，还是类似于二分查找的，下图的时间复杂度就约等于log以4为底 设计跳表 1. 在实现跳表的时候，一定要对照着图来实现，如果纯靠脑子，很容易把某些特殊情况给遗漏掉，至于图的话，就拿跳表论文里面的这个图就可以，这个图画的是最板正的。 依旧拿下图为例，如果是add 17的话，如果17的层数恰好是最高层数4，那么从头结点开始迭代，17>6，cur跳到6结点的第四层，然后6结点的第四层存储的是nullptr，此时就说明6结点就是第四层，要插入结点
54810编辑于 2024-02-23 - 来自专栏用户4352451的专栏
跳跃表（跳表）
如上图当你查找16的时候，你只需要遍历7次就可以得到结果值 ， 先去第一层索引查到，遍历到13的时候 发现下一个节点是17 那我们就知道此时16就在这两个节点之间，所以我们进行down进入下一层 继续遍历这个时候我们只需要遍历两个节点就可以找到了，所以我们遍历16在建立上层索引的情况下是只需要遍历7次，但是单链表便利需要10次，那我们在继续添加及层索引如下图:
59320发布于 2020-08-26 - 来自专栏JMCui
跳表（SkipList） 和 ConcurrentSkipListMap
一、跳表（SkipList） 对于单链表，即使链表是有序的，如果想要在其中查找某个数据，也只能从头到尾遍历链表，这样效率自然就会很低，跳表就不一样了。 就查询的性能而言，跳表的时间复杂度是 O(logn)。 跳表的本质，其实是同时维护了多个链表，并且链表是分层的： ? 其中最低层的链表，维护了跳表内所有的元素，每往上一层链表，都是下面一层的子集。 跳表内每一层链表的元素都是有序的。查找时，可以从顶级链表开始找。 ConcurrentSkipListMap 的存取性能逊色于 ConcurrentHashMap（在 4 线程 1.6 万数据的条件下，ConcurrentHashMap 存取速度是 ConcurrentSkipListMap 的 4倍左右），它的优势在于跳表内的所有元素都是有序的。
1.3K20发布于 2020-03-19 - 来自专栏叽叽西
数据结构-跳表
前面讲的这种链表加多级索引的结构，就是跳表。我通过例子给你展示了跳表是如何减少查询次数的，现在你应该比较清晰地知道，跳表确实是可以提高查询效率的。接下来，我会定量地分析一下，用跳表查询到底有多快。 按照我们刚才讲的，每两个结点会抽出一个结点作为上一级索引的结点，那第一级索引的结点个数大约就是 n/2，第二级索引的结点个数大约就是 n/4，第三级索引的结点个数大约就是 n/8，依次类推，也就是说，第 跳表的空间复杂度分析并不难，我在前面说了，假设原始链表大小为 n，那第一级索引大约有 n/2 个结点，第二级索引大约有 n/4 个结点，以此类推，每上升一级就减少一半，直到剩下 2 个结点。 这几级索引的结点总和就是 n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空间复杂度是 O(n)。 跳表索引动态更新 跳表索引动态更新当我们不停地往跳表中插入数据时，如果我们不更新索引，就有可能出现某 2 个索引结点之间数据非常多的情况。极端情况下，跳表还会退化成单链表。
53010编辑于 2022-05-17 - 来自专栏Michael阿明学习之路
数据结构--跳表SkipList
对单链表查找一个元素的时间复杂度是 O(n) 通过对链表建立多级索引的结构，就是跳表，查找任意数据、插入数据、删除数据的时间复杂度均为 O(log n) 前提：建立了索引，用空间换时间的思路 (每两个节点建立一个索引 )索引节点总和 n/2+n/4+n/8+…+8+4+2 = n-2，空间复杂度 O(n) 插入和删除后，动态更新索引，避免局部链表元素过多或者过少，退化成单链表 ? skiplist.h /** * @description: 跳表 * @author: michael ming * @date: 2019/4/22 22:21 * @modified by unsigned int UINT; template <class T> class skipNode { public: T data; skipNode<T> **next; //跳表节点的 << endl; } } }; #endif //SKIPLIST_SKIPLIST_H test_skiplist.cpp /** * @description: 测试跳表
41320发布于 2021-02-20 - 来自专栏程序员小灰
漫画：什么是 “跳表” ？
假设原始链表有n个结点，那么各层索引的结点总数是n/2+n/4+n/8+n/16+......2，约等于n。 也就是说，优化之后的数据结构所占空间，是原来的2倍。这是典型的以空间换时间的做法。 假设我们要插入的结点是10，首先我们按照跳表查找结点的方法，找到待插入结点的前置结点（仅小于待插入结点）： 接下来，按照一般链表的插入方式，把结点10插入到结点9的下一个位置： 这样是不是插入工作就完成了呢 假设我们要从跳表中删除结点10，首先我们按照跳表查找结点的方法，找到待删除的结点： 接下来，按照一般链表的删除方式，把结点10从原始链表当中删除： 这样是不是删除工作就完成了呢？并不是。 程序中跳表采用的是双向链表，无论前后结点还是上下结点，都各有两个指针相互指向彼此。 2. 程序中跳表的每一层首位各有一个空结点，左侧的空节点是负无穷大，右侧的空节点是正无穷大。 代码中的跳表就像下图这样： public class SkipList{ //结点“晋升”的概率 private static final double PROMOTE_RATE =
85760发布于 2020-08-27 - 来自专栏皮皮星球
golang实现跳表(SkipList)
跳表这种数据结构利用空间换时间，性能和红黑树比肩，还能支持区间搜索，在redis和leveldb等开源项目中都用被应用。 跳表的结构如图所示： image.png 在最底层包含了所有的数据节点，每一层链表都有一个指向下一层和自己相同的节点，向后的指针指向随机的同一层比自己大的数据。 时间复杂度分析 不难理解，对于一个有n个节点的链表，如果每两个节点会提取出一个节点作为索引节点，那么第一层的节点个数为n/2，再往上一层，节点数变成n/4，以此类推，第k层的索引个数为n/(2^k)，假设层数有 x层，并且第x层的节点个数为2，也就是n/(2^x) = 2，所以x = (logn - 1)，而第0层是链表本身，所以整个跳表的高度就是logn，如果每一层都需要遍历m个节点，那么在跳表中查询某个数的时间复杂度就是 简单的单向跳表实现: skiplist
1.5K10发布于 2020-09-23 - 来自专栏算法之名
ConcurrentSkipListMap跳表原理解析
//竞争成功的，退出'for (;;)'循环 break outer; } } //到此时表示已经节点已经put成功了，但对于跳表来说 level <= (max = h.level)) { //根据层数level不断创建新增节点的下层索引 //注意此时只是新增了新节点的索引，并没有关联到跳表的真实体中 >[level+1]; //根据层数level不断创建新增节点的下层索引,并放入数组中 //此时只是新增了新节点的索引，并没有关联到跳表的真实体中 r.right; continue; } } //如果j为跳表原层数 for (;;) { //获取原始头索引以及该头索引的链表后续索引，当ConcurrentSkipListMap刚初始化的时候，r为null //但是我们查找肯定不会在空的跳表中查找
67110发布于 2019-12-03 - 来自专栏小明说Java
Redis压缩列表和跳表
Redis 的压缩列表（ziplist）和跳表（skiplist）是两种不同的数据结构，它们在 Redis 中被用于实现不同的功能。压缩列表实际上类似于一个数组，数组中的每一个元素都对应保存一个数据。 跳表（skiplist）有序链表只能逐一查找元素，导致操作起来非常缓慢，于是就出现了跳表，时间复杂度为O(N)。 此时，我们只需要4次查找就能定位到元素33了。如果我们还想再快，可以再增加二级索引：从一级索引中，再抽取部分元素作为二级索引。例如，从一级索引中抽取1、27、100作为二级索引，二级索引指向一级索引。 当数据量很大时，跳表的查找复杂度就是O(logN)。总之，压缩列表和跳表是两种不同的数据结构，它们在 Redis 中被用于实现不同的功能。 压缩列表用于存储短的列表或集合，而跳表用于实现可以在对数时间内进行搜索、插入和删除操作的有序集合。我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！
1.2K10编辑于 2023-11-21 - 来自专栏烟草的香味
数据结构之跳表
跳表来了, 顾名思义, 跳表就是可以跳跃的表, 我简单画了张图: 在原来链表的基础上, 建立一个新的索引链表, 原链表没两个建立一个 原来查找节点5的访问顺序是: 1->2->3->4->5->6, 原来链表访问节点128需要遍历128次, 现在只需要遍历14次就可以, 很明显的看出, 跳表确实可以提高查询效率 时间复杂度 在一个链表种, 查询时间复杂度是O(n) 那么, 添加了索引之后, 跳表的查询时间复杂度能优化多少呢 n/4 总占用空间=n+n/2+n/4+...+2=2n-2 所以, 其空间复杂度为O(n) 插入和删除 当链表有了高效的查找时, 高效的删除和插入也就是顺理成章的事了. 那么如何保证跳表的平衡, 避免跳表因为插入而出现复杂度退化呢? , 比如: 链表共又3级索引, 随机数是2, 那么就将新插入的节点添加到第一、二级索引中, 如下图: 以上, 就是跳表的简单介绍!!
56530发布于 2019-07-25 - 来自专栏Redis源码学习系列
Redis源码学习之跳表
score，以及每个节点的层数结构，每层都包含着前进指针与跨度；除此之外，每个节点还包含一个后退指针，假设跳表只有一层，那么整个跳表将退化为双端链表。 跳表，持有跳表的结构包括指向跳表表头和表尾的指针，以及整个跳表的长度（即第一层的节点数，但不包含头结点），还有整个跳表最高层的层数。 ，以下图为例： 在一个长度为4，高度为5的跳表中插入score为20，值为字符串c的节点，首先由上至下遍历每层查找插入位置，同时维护每层的rank值和update节点，遍历完之后，rank和update 数组如图中所示，我们将其中的4层（即i=3）拿出来分析一下。 在插入节点之前，update[3]指向头结点,rank[3]=0，rank[0]=2，第三层左边节点到右边节点的跨度是4，那么从图中可以看出，新节点的跨度=左边节点（即插入节点的前驱）跨度-（rank[
14.6K108发布于 2018-10-11 - 来自专栏yuyy.info技术专栏
跳表：为什么Redis一定要用跳表来实现有序集合？
假设原始链表大小为n，那第一级索引大约有n/2个结点，第二级索引大约有n/4个结点，以此类推，每上升一级就减少一半，直到剩下2个结点。也就是计算这棵二叉树的节点数 - 叶子节点数 - 根节点。 索引层的结点总和就是n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空间复杂度是O(n)。 调整策略，两个节点取一个索引节点改为三个节点取一个索引节点，看看时间和空间复杂度变化。 跳表索引动态更新 当我们不停地往跳表中插入数据时，如果我们不更新索引，就有可能出现某2个索引结点之间数据非常多的情况。极端情况下，跳表还会退化成单链表。 随机函数的选择很有讲究，从概率上来讲，能够保证跳表的索引大小和数据大小平衡性，不至于性能过度退化。 为什么Redis要用跳表来实现有序集合，而不是红黑树？ 当然，Redis之所以用跳表来实现有序集合，还有其他原因。 跳表相对于红黑树来说更简单。 跳表更加灵活，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗。
1K11编辑于 2022-11-16 - 来自专栏计算机技术
Skiplist跳表的通俗理解
跳表就是跨越层级的管理，这种管理结构就存在多样性了： 总经理-部门经理-总监-组长-基层员工。 这一管理层级肯定存在。 总经理-部门经理-组长-基层员工。这一管理层级可能存在。 这种跨层管理就是跳表，跳表有什么好处就是执行命令速度快，总经理可以直接给基层员工安排任务。所以跳表要解决的问题就是提高有序表的查询速度。 ret = skip_list.search(3) print(3, "find", ret) 运行结果： 0层 : 2,4,6, 1层 : 2,6, 2层 : 2,6, 3层 : 2, 4层 : 5层 : 6层 : 7层 : 8层 : 9层 : after delete 4 0层 : 2,6, 1层 : 2, 2层 : 2, 3层 : 2, 4层 : 5层 : 6层 : 7层 : 8层 : 9层 : 2 find True 4 find False 0层 : 2,3,6, 1层 : 2,3, 2层 : 2,3, 3层 : 2,3, 4层 : 3, 5层 : 6层 : 7层 : 8层 : 9
56090编辑于 2022-04-02
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号