跳跃表介绍

简介: 有序集合在生活中比较常见,例如根据成绩对学生排名,根据得分对玩家排名等。对于有序集合的底层实现,可以用数组、平衡树、链表等。数组不便元素的插入、删除;平衡树或红黑树虽然效率高但结构复杂;链表查询需要遍历所有效率低。

1、简介



有序集合在生活中比较常见,例如根据成绩对学生排名,根据得分对玩家排名等。对于有序集合的底层实现,可以用数组、平衡树、链表等。数组不便元素的插入、删除;平衡树或红黑树虽然效率高但结构复杂;链表查询需要遍历所有效率低。Redis采用的是跳跃表。跳跃表效率堪比红黑树,实现远比红黑树简单。


2、实例



对比有序链表和跳跃表,从链表中查询出51


  1. 有序链表:


b727f77858434563855e370871ac91bd.png

要查找值为51的元素,需要从第一个元素开始依次查找、比较才能找到。共需要6次比较。


    2.跳跃表


8be53e3e03cf49309cc0d20bc8c0896a.png


从第2层开始,1节点比51节点小,向后比较。

21节点比51节点小,继续向后比较,后面就是NULL了,所以从21节点向下到第1层

在第1层,41节点比51节点小,继续向后,61节点比51节点大,所以从41向下

在第0层,51节点为要查找的节点,节点被找到,共查找4次。

从此可以看出跳跃表比有序链表效率要高

相关文章
|
6月前
|
弹性计算 Linux 网络安全
阿里云服务器迁移中心SMC实战指南:跨平台业务迁移教程参考
现在越来越多的个人和企业用户选择将其他云平台或者服务商的业务迁移到阿里云,但是如何快速且安全完成迁移是很多用户比较关注的问题,我们可以选择使用阿里云提供的服务器迁移中心(Server Migration Center,简称SMC),这个产品是阿里云提供给您的迁移平台,专注于提供能力普惠、体验一致、效率至上的迁移服务,满足您在阿里云的迁移需求。本文为大家展示使用阿里云服务器迁移中心SMC将其他云平台业务迁移至阿里云的教程,以供参考。
|
算法 Python 容器
基于最低水平面的三维装箱问题的启发式算法
基于最低水平面的三维装箱问题的启发式算法
263 0
|
人工智能 自然语言处理 语音技术
使用AI识别语音和B站视频并通过GPT生成思维导图原创
AI脑图现新增语音及B站视频内容识别功能,可自动生成思维导图。用户可通过发送语音或上传语音文件,系统自动转换为文本并生成结构化的思维导图;对于B站视频,仅需提供链接即可。其工作流程包括:语音转文本、文本结构化、生成Markdown、Markdown转思维导图HTML以及输出最终的思维导图图片给用户。
702 0
|
开发工具 git
Git使用经验总结2-配置用户名邮箱
Git使用经验总结2-配置用户名邮箱
242 0
|
JavaScript 前端开发 UED
js的节流
js的节流
173 0
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)(上)
深度优先搜索(DFS、深搜)和广度优先搜索(BFS、广搜)
|
分布式计算 DataWorks NoSQL
DataWorks中mongo同步到odps后时间多了8小时?
DataWorks中mongo同步到odps后时间多了8小时?
298 0
|
图形学
Unity——音乐、音效
Unity——音乐、音效
257 0
|
人工智能 达摩院 供应链
重磅发布丨数智乡村,振兴在“云”
重磅发布丨数智乡村,振兴在“云”
658 0
重磅发布丨数智乡村,振兴在“云”
|
存储 算法 文件存储
Android V1及V2签名原理简析
Android V1及V2签名原理简析
891 0
Android V1及V2签名原理简析