数据结构与算法跳表(SkipList)
我们都知道Redis支持以下五种数据类型: 字符串-String 列表-List 哈希-Hash 集合-Set 有序集合-SortedSet
redis基础知识回顾
Java高频面试题- 每日三连问?「Day1」—Redis篇
Java高频面试题- 每日三连问?「Day2」—Redis篇2
现在将焦点锁定在有序集合-SortedSet上,有序集合是如何实现的呢?
带着这个问题开始今天的内容:跳表(Skip List)
何为"跳表"
猜数游戏我想大家都玩过,我们用这个例子来理解一下跳表思想:
1~100之间,给定一个数字让你来猜,这个游戏过程可能是这样的 你:50
我:小了
你:75
我:大了
你:65
我:小了
你:70
我:小了
你:72
我:大了
你:71 (猜中!)
分析一下整个过程,在前五轮的猜数中,你用类似二分的思路迅速将目标数字缩小到了70~72之间,于是快速猜中目标数字71,这就是跳表的思想。
跳表模型
跳表是基于链表实现的
数据结构与算法--链表(Linked list)
我们用上面的案例先创建一个数字1~100的链表:
接下来你猜数的过程在跳表中是这样实现的:
可以看到我们在基础数据的上层增加了一层,在跳表中叫做:索引链
于是跳表命中数字71的路线是这样的:
你可以想象一下,如果没有索引链层,由于链表不支持像数组那样根据下标随机访问,所以我们如果想命中数字71,就需要从链表的第一个元素开始依次循环70次,跳表让我们的查询更快,这就是跳表的优势。
多级索引链
现在我们更改一下游戏规则,数字范围从1~100变为1~10000,这样再让你猜是不是头都大了?即便你建立了索引链,但索引链的长度依然可想而知。
那么跳表是怎么做的呢?
答案是:既然一层索引链不够,就在索引链的上层再建立索引,层层嵌套,直到索引链足够小,形成多级索引:
你也许会想到,多级索引将会导致内存消耗,其实这也是数据结构高效的一个通用思路:用内存换效率。
以上就是今天的内容,关于跳表的篇幅比较简短,相信大家很容易理解,觉得有帮助的话不妨收藏分享,我们下期继续。