前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构与算法:跳表(Skip List)

数据结构与算法:跳表(Skip List)

作者头像
浩说编程
发布2021-09-10 15:57:34
3470
发布2021-09-10 15:57:34
举报
文章被收录于专栏:Java经验之谈

我们都知道Redis支持以下五种数据类型:

  1. 字符串-String
  2. 列表-List
  3. 哈希-Hash
  4. 集合-Set
  5. 有序集合-SortedSet

redis基础

Java高频面试题- 每日三连问?【Day1】 — Redis篇

Java高频面试题- 每日三连问?【Day2】 — Redis篇2

现在将焦点锁定在有序集合-SortedSet上,有序集合是如何实现的呢?

带着这个问题开始今天的内容:跳表(Skip List)

01

何为'跳表'

猜数游戏我想大家都玩过,我们用这个例子来理解一下跳表思想:

1~100之间,给定一个数字让你来猜,这个游戏过程可能是这样的

你:50 我:小了 你:75 我:大了 你:65 我:小了 你:70 我:小了 你:72 我:大了 你:71 (猜中!)

分析一下整个过程,在前五轮的猜数中,你用类似二分的思路迅速将目标数字缩小到了70~72之间,于是快速猜中目标数字71,这就是跳表的思想。

02

跳表模型

跳表是基于链表实现的

链表回顾

数据结构与算法--链表(Linked list)

我们用上面的案例先创建一个数字1~100的链表:

接下来你猜数的过程在跳表中是这样实现的:

可以看到我们在基础数据的上层增加了一层,在跳表中叫做:索引链

于是跳表命中数字71的路线是这样的:

你可以想象一下,如果没有索引链层,由于链表不支持像数组那样根据下标随机访问。所以我们如果想命中数字71,就需要从链表的第一个元素开始依次循环70次,跳表让我们的查询更快,这就是跳表的优势。

03

多级索引链

现在我们更改一下游戏规则,数字范围从1~100变为1~10000,这样再让你猜是不是头都大了?即便你建立了索引链,但索引链的长度依然可想而知。

那么跳表是怎么做的呢?

答案是:既然一层索引链不够,就在索引链的上层再建立索引,层层嵌套,直到索引链足够小,形成多级索引:

你也许会想到,多级索引将会导致内存消耗,其实这也是数据结构高效的一个通用思路:用内存换效率。

以上就是今天的内容,关于跳表的篇幅比较简短,相信大家很容易理解,觉得有帮助的话不妨收藏分享,我们下期继续。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-08-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 浩说编程 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
云数据库 Redis
腾讯云数据库 Redis(TencentDB for Redis)是腾讯云打造的兼容 Redis 协议的缓存和存储服务。丰富的数据结构能帮助您完成不同类型的业务场景开发。支持主从热备,提供自动容灾切换、数据备份、故障迁移、实例监控、在线扩容、数据回档等全套的数据库服务。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档