文科生都能看明白的数据结构——图解跳跃表(SkipList)
mhr18 2024-12-07 22:14 14 浏览 0 评论
为什么选择跳跃表
目前经常使用的平衡数据结构有：B树，红黑树，AVL树，Splay Tree, Treep等。想象一下，给你一张草稿纸，一只笔，一个编辑器，你能立即实现一颗红黑树，或者AVL树出来吗？ 很难吧，这需要时间，要考虑很多细节，要参考一堆算法与数据结构之类的树，还要参考网上的代码，相当麻烦。用跳表吧，跳表是一种随机化的数据结构，目前开源软件 Redis 和 LevelDB 都有用到它，它的效率和红黑树以及 AVL 树不相上下，但跳表的原理相当简单，只要你能熟练操作链表，就能轻松实现一个 SkipList。
有序表的搜索
考虑一个有序表：
从该有序表中搜索元素 < 23, 43, 59 > ，需要比较的次数分别为 < 2, 4, 6 >，总共比较的次数
为 2 + 4 + 6 = 12 次。有没有优化的算法吗? 链表是有序的，但不能使用二分查找。类似二叉
搜索树，我们把一些节点提取出来，作为索引。得到如下结构：
这里我们把 < 14, 34, 50, 72 > 提取出来作为一级索引，这样搜索的时候就可以减少比较次数了。
我们还可以再从一级索引提取一些元素出来，作为二级索引，变成如下结构：
这里元素不多，体现不出优势，如果元素足够多，这种索引结构就能体现出优势来了。
跳跃表
下面的结构是就是跳表：
其中 -1 表示 INT_MIN， 链表的最小值，1 表示 INT_MAX，链表的最大值。
跳表具有如下性质：
(1) 由很多层结构组成
(2) 每一层都是一个有序的链表
(3) 最底层(Level 1)的链表包含所有元素
(4) 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。
(5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。
跳表的搜索
例子：查找元素 117
(1) 比较 21， 比 21 大，往后面找
(2) 比较 37, 比 37大，比链表最大值小，从 37 的下面一层开始找
(3) 比较 71, 比 71 大，比链表最大值小，从 71 的下面一层开始找
(4) 比较 85， 比 85 大，从后面找
(5) 比较 117， 等于 117， 找到了节点。
跳表的插入
先确定该元素要占据的层数 K（采用丢硬币的方式，这完全是随机的）
然后在 Level 1 ... Level K 各个层的链表都插入元素。
例子：插入 119， K = 2
如果 K 大于链表的层数，则要添加新的层。
例子：插入 119， K = 4
丢硬币决定 K
插入元素的时候，元素所占有的层数完全是随机的。
相当与做一次丢硬币的实验，如果遇到正面，继续丢，遇到反面，则停止，
用实验中丢硬币的次数 K 作为元素占有的层数。显然随机变量 K 满足参数为 p = 1/2 的几何分布，
K 的期望值 E[K] = 1/p = 2. 就是说，各个元素的层数，期望值是 2 层。
跳表的高度。
n 个元素的跳表，每个元素插入的时候都要做一次实验，用来决定元素占据的层数 K，
跳表的高度等于这 n 次实验中产生的最大 K，待续。。。
跳表的空间复杂度分析
根据上面的分析，每个元素的期望高度为 2， 一个大小为 n 的跳表，其节点数目的
期望值是 2n。
跳表的删除
在各个层中找到包含 x 的节点，使用标准的 delete from list 方法删除该节点。
例子：删除 71
随机的层高level-相关资料
相关推荐
- Spring Boot3 连接 Redis 竟有这么多实用方式
-
各位互联网大厂的后端开发精英们，在日常开发中，想必大家都面临过系统性能优化的挑战。当系统数据量逐渐增大、并发请求不断增多时，如何提升系统的响应速度和稳定性，成为了我们必须攻克的难题。而Redis，这...
- 隧道 ssh -L 命令总结 和 windows端口转发配置
-
摘要：隧道ssh-L命令总结和windows端口转发配置关键词：隧道、ssh-L、端口转发、网络映射整体说明最近在项目中，因为内网的安全密级比较高，只能有一台机器连接内网数据库，推送...
- 火爆BOOS直聘的13个大厂Java社招面经(5年经验)助你狂拿offer
-
火爆BOOS直聘的13个大厂Java社招面经（5年经验）助你狂拿offer综上所述，面试遇到的所有问题，整理成了一份文档，希望大家能够喜欢！！Java面试题分享（Java中高级核心知识全面解析）一、J...
- 「第五期」游服务器一二三面 秋招 米哈游
-
一面下午2点，35分钟golang内存模型golang并发模型golanggc原理过程channel用途，原理redis数据结构，底层实现跳跃表查询插入复杂度进程，线程，协程kill原理除了kil...
- RMQ——支持合并和优先级的消息队列
-
业务背景在一个项目中需要实现一个功能，商品价格发生变化时将商品价格打印在商品主图上面，那么需要在价格发生变动的时候触发合成一张带价格的图片，每一次触发合图时计算价格都是获取当前最新的价格。上游价格变化...
- Redis 中的 zset 为什么要用跳跃表，而不是B+ Tree 呢?
-
Redis中的有序集合使用的是一种叫做跳跃表（SkipList）的数据结构来实现，而不是使用B+Tree。本文将介绍为什么Redis中使用跳跃表来实现有序集合，而不是B+Tree，并且探讨跳跃表...
- 一文让你彻底搞懂 WebSocket 的原理
-
作者：木木匠转发链接：https://juejin.im/post/5c693a4f51882561fb1db0ff一、概述上一篇文章《图文深入http三次握手核心问题【思维导图】》我们分析了简单的一...
- Redis与Java整合的最佳实践
-
Redis与Java整合的最佳实践在这个数字化时代，数据处理速度决定了企业的竞争力。Redis作为一款高性能的内存数据库，以其卓越的速度和丰富的数据结构，成为Java开发者的重要伙伴。本文将带你深入了...
- Docker与Redis:轻松部署和管理你的Redis实例
-
在高速发展的云计算时代，应用程序的部署和管理变得越来越复杂。面对各种操作系统、依赖库和环境差异，开发者常常陷入“在我机器上能跑”的泥潭。然而，容器化技术的兴起，尤其是Docker的普及，彻底改变了这一...
- Java开发中的缓存策略:让程序飞得更快
-
Java开发中的缓存策略：让程序飞得更快缓存是什么？首先，让我们来聊聊什么是缓存。简单来说，缓存是一种存储机制，它将数据保存在更快速的存储介质中，以便后续使用时能够更快地访问。比如，当你打开一个网页时...
- 国庆临近，字节后端开发3+4面，终于拿到秋招第一个offer
-
字节跳动，先面了data部门，3面技术面之后hr说需要实习转正，拒绝，之后另一个部门捞起，四面技术面，已oc分享面经，希望对大家有所帮助，秋招顺利在文末分享了我为金九银十准备的备战资源库，包含了源码笔...
- “快”就一个字!Redis凭什么能让你的APP快到飞起?
-
咱们今天就来聊一个字——“快”！在这个信息爆炸、耐心越来越稀缺的时代，谁不希望自己手机里的APP点一下“嗖”就打开，刷一下“唰”就更新？谁要是敢让咱用户盯着个小圈圈干等，那简直就是在“劝退”！而说到让...
- 双十一秒杀，为何总能抢到?Redis功不可没!
-
一年一度的双十一“剁手节”，那场面，简直比春运抢票还刺激！零点的钟声一敲响，亿万个手指头在屏幕上疯狂戳戳戳，眼睛瞪得像铜铃，就为了抢到那个心心念念的半价商品、限量版宝贝。你有没有发现一个奇怪的现象？明...
- 后端开发必看!为什么说Redis是天然的幂等性?
-
你在做后端开发的时候，有没有遇到过这样的困扰：高并发场景下，同一个操作重复执行多次，导致数据混乱、业务逻辑出错？别担心，很多同行都踩过这个坑。某电商平台就曾因订单创建接口在高并发时不具备幂等性，用户多...
- 开发一个app需要哪些技术和工具
-
APP开发需要一系列技术和工具的支持，以下是对这些技术的清晰归纳和分点表示：一、前端开发技术HTML用于构建页面结构。CSS用于样式设计和布局。JavaScript用于页面交互和逻辑处理。React...
欢迎 你 发表评论:
- 一周热门
- 最近发表
- 标签列表
-
- oracle位图索引 (63)
- oracle批量插入数据 (62)
- oracle事务隔离级别 (53)
- oracle 空为0 (50)
- oracle主从同步 (55)
- oracle 乐观锁 (51)
- redis 命令 (78)
- php redis (88)
- redis 存储 (66)
- redis 锁 (69)
- 启动 redis (66)
- redis 时间 (56)
- redis 删除 (67)
- redis内存 (57)
- redis并发 (52)
- redis 主从 (69)
- redis 订阅 (51)
- redis 登录 (54)
- redis 面试 (58)
- 阿里 redis (59)
- redis 搭建 (53)
- redis的缓存 (55)
- lua redis (58)
- redis 连接池 (61)
- redis 限流 (51)