共计 6956 个字符，预计需要花费 18 分钟才能阅读完成。
排行榜
懂行的老哥一看这个小标题，就晓得我要以排行榜作为切入点，去讲 Redis 的 zset 了。
是的，经典面试题，请实现一个排行榜，大部分状况下就是在考验你知不知道 Redis 的 zset 构造，和其对应的操作。
当然了，排行榜咱们也能够基于其余的解决方案。比方 mysql。
我已经就基于 mysql 做过排行榜，一条 sql 就能搞定。然而仅限于数据量比拟少，性能要求不高的场景（我过后只有 11 支队伍做排行榜，一分钟刷新一次排行榜）。
对于这种经典的面试八股文，网上一找一大把，所以本文就不去做相干解析了。
说好的只是一个切入点。
如果你不晓得具体怎么实现，或者基本就不晓得这题在问啥，那肯定记得看完本文后要去看看相干的文章。最好本人实操一下。
置信我，八股文，得背，这题会考。
zset 的外部编码
家喻户晓，Redis 对外提供了五种根本数据类型。然而每一种根本类型的外部编码却是另外一番风光：
其中 list 数据结构，在 Redis 3.2 版本中还提供了 quicklist 的外部编码。不是本文重点，我提一嘴就行，有趣味的敌人本人去理解一下。
本文次要探讨的是上图中的 zset 数据结构。
zset 的外部编码有两种：ziplist 和 skiplist。
其实你也别感觉这个货色有多神奇。因为对于这种对外一套，对内又是一套的“双标党”其实你曾经很相熟了。
它就是 JDK 的一个汇合类，来敌人们，大胆的喊出它的名字：HashMap。
HashMap 除了根底的数组构造之外，还有另外两个数据结构：一个链表，一个红黑树。
这样一联想是不是就感觉也不过如此，心里至多有个底了。
当链表长度大于 8 且数组长度大于 64 的时候，HashMap 中的链表会转红黑数。
对于 zset 也是一样的，肯定会有条件触发其外部编码 ziplist 和 skiplist 之间的变动？
这个问题的答案就藏在 redis.conf 文件中，其中有两个配置：
上图中配置的含意是，当有序汇合的元素个数小于 zset-max-ziplist-entries 配置的值，且每个元素的值的长度都小于 zset-max-ziplist-value 配置的值时，zset 的外部编码是 ziplist。
反之则用 skiplist。
实践铺垫上了，接下我给大家演示一波。
首先，咱们给 memberscore 这个有序汇合的 key 设置两个值，而后看看其外部编码：
此时有序汇合的元素个数是 2，能够看到，外部编码采纳的是 ziplist 的构造。
为了大家不便了解这个贮存，我给大家画个图：
而后咱们须要触发外部编码从 ziplist 到 skiplist 的变动。
先验证 zset-max-ziplist-value 配置，往 memberscore 元素中塞入一个长度大于 64 字节（zset-max-ziplist-value 默认配置）的值：
这个时候 key 为 memberscore 的有序汇合中有 3 个元素了，其中有一个元素的值特地长，超过了 64 字节。
此时的外部编码采纳的是 skiplist。
接下来，咱们往 zset 中多塞点值，验证一下元素个数大于 zset-max-ziplist-entries 的状况。
咱们搞个新的 key，取值为 whytestkey。
首先，往 whytestkey 中塞两个元素，这是其外部编码还是 ziplist：
那么问题来了，从配置来看 zset-max-ziplist-entries 128。
这个 128 是等于呢还是大于呢？
没关系，我也不晓得，试一下就行了。
当初曾经有两个元素了，再追加 126 个元素，看看：
通过试验咱们发现，当 whytestkey 中的元素个数是 128 的时候，其外部编码还是 ziplist。
那么触发其从 ziplist 转变为 skiplist 的条件是 元素个数大于 128，咱们再退出一个试一试：
果然，外部编码从 ziplist 转变为了 skiplist。
实践验证结束，zset 的确是有两幅脸孔。
本文次要探讨 skiplist 这个外部编码。
它就是题目说的：基于运气的数据结构。
什么是 skiplist？
这个构造是一个叫做 William Pugh 的哥们在 1990 年公布的一篇叫做《Skip Lists: A Probabilistic Alternative to Balanced Trees》的论文中提出的。
论文地址：ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf
我呢，写文章个别遇到大佬的时候我都习惯性的去网上搜一下大佬长什么样子。也没别的意思。次要是关注一下他们的发量稠密与否。
在找论文作者的照片之前，我叫他 William 学生，找到之后，我想给他起个“外号”，就叫火男：
他的主页就只放了这一张落拓不羁的照片。而后，我点进了他的 website：
外面提到了他的汗马功劳。
我一眼瞟去，感兴趣的就是我圈起来的三个中央。
- 第一个是创造跳表。
- 第二个是参加了 JSR-133《Java 内存模型和线程标准订正》的工作。
- 第三个是这个哥们在谷歌的时候，学会了吞火。我寻思谷歌真是人才济济啊，还教这玩意呢？
eat fire，大佬的喜好的确是不一样。
感觉他的确是喜爱玩火，那我就叫他火男吧：
火男的论文摘要外面，是这样的介绍跳表的：
摘要外面说： 跳表是一种能够用来代替均衡树的数据结构，跳表应用概率均衡而不是严格的均衡，因而，与均衡树相比，跳表中插入和删除的算法要简略得多，并且速度要快得多。
论文外面，在对跳表算法进行详细描述的中央他是这样说的：
首先火男大佬说，对于一个有序的链表来说，如果咱们须要查找某个元素，必须对链表进行遍历。比方他给的示意图的 a 局部。
我独自截取一下：
这个时候，大家还能跟上，对吧。链表查找，一一遍历是基本操作。
那么，如果这个链表是有序的，咱们能够搞一个指针，这个指针指向的是该节点的下下个节点。
意思就是往上抽离一部分节点。
怎么抽离呢，每隔一个节点，就抽一个进去，和下面的 a 示意图比起来，变动就是这样的：
抽离进去有什么益处呢？
假如咱们要查问的节点是 25。
当就是一般有序链表的时候，咱们从头节点开始遍历，须要遍历的门路是：
head -> 3 -> 6 -> 7 -> 9 -> 12 -> 17 -> 19 -> 21 -> 25
须要 9 次查问能力找到 25。
然而当构造略微一变，变成了 b 示意图的样子之后，查问门路就是：
第二层的 head -> 6 -> 9 -> 17 -> 21 -> 25。
5 次查问就找到了 25。
这个状况下咱们找到指定的元素，不会超过 (n/2)+1 个节点：
那么这个时候有个小问题就来了：怎么从 21 间接到 25 的呢？
看论文中的图片，略微有一点不容易明确。
所以，我给大家从新画个示意图：
看到了吗？“多了”一个向下的指针。其实也不是多了，只是论文外面没有明示而已。
所以，查问 25 的门路是这样的，空心箭头批示的方向：
在 21 到 26 节点之间，往下了一层，逻辑也很简略。
21 节点有一个右指针指向 26，先判断右指针的值大于查问的值了。
于是下指针就起到作用了，往下一层，再持续进行右指针的判断。
其实每个节点的判断逻辑都是这样，只是后面的判断后果是进行走右指针。
依照这个往上抽节点的思维，假如咱们抽到第四层，也就是论文中的这个示意图：
咱们查问 25 的时候，只须要通过 2 次。
第一步就间接跳过了 21 之前的所有元素。
怎么样，爽不爽？
然而，它是有缺点的。
火男的论文外面是这样说的：
This data structure could be used for fast searching, but insertion and deletion would be impractical.
查问的确飞快。然而对于插入和删除 would be impractical。
impractical 是什么意思？
你看，又学一个四级单词。
对于插入和删除简直是难以实现的。
你想啊，下面那个最底层的有序链表，我一开始就拿进去给你了。
而后我就说基于这个有序链表每隔一个节点抽离到上一层去，再构建一个链表。那么这样上上层节点比例应该是 2:1。巴拉巴拉的 …..
然而理论状况应该是咱们最开始的时候连这个有序链表都没有，须要本人去创立的。
就假如要在现有的这个跳表构造中插入一个节点，毋庸置疑，必定是要插入到最底层的有序链表中的。
然而你毁坏了上上层 1:2 的比例了呀？
怎么办，一层层的调整呗。
能够，然而请你考虑一下编码实现起来的难度和对应的工夫复杂度？
要这样搞，间接就是一波劝退。
这就受不了了？
我还没说删除的事呢。
那怎么办？
看看论文外面怎么说到：
首先咱们关注一下第一段划红线的中央。
火男写到：50% 的节点在第一层，25% 的节点在第二层，12.5% 的节点在第三层。
你认为他在给你说什么？
他要表白的意思除了每一层节点的个数之外，还阐明了层级：
没有第 0 层，至多论文外面没有说有第 0 层。
如果你非要说最上面那个有全副节点的有序链表叫做第 0 层，我感觉也能够。然而，我感觉叫它根底链表更加适合一点。
而后我再看第二段划线的中央。
火男提到了一个关键词：randomly，意思是随机。
说进去你可能不信，然而跳表是用随机的形式解决下面提出的插入（删除）之后调整结构的问题。
怎么随机呢？抛硬币。
是的，没有骗你，真的是“抛硬币”。
跳表中的“硬币”
当跳表中插入一个元素的时候，火男示意咱们上上层之间能够不严格遵循 1:2 的节点关系。
如果插入的这个元素须要建设索引，那么把索引建设在第几层，都是由抛硬币决定的。
或者说：由抛硬币的概率决定的。
我问你，一个硬币抛出去之后，是侧面的概率有多大？
是不是 50%？
如果咱们把这个概率记为 p，那么 50%，即 p=1/2。
下面咱们提到的概率，到底是怎么用的呢？
火男的论文中有一大节是这样的写的：
随机抉择一个层级。他说咱们假如概率 p=1/2，而后叫咱们看图 5。
图 5 是这样的：
十分要害的一张图啊。
短短几行代码，形容的是如何抉择层级的随机算法。
首先定义初始层级为 1（lvl := 1）。
而后有一行正文：random() that returns a random value in [0…1)
random() 返回一个 [0…1) 之间的随机值。
接下来一个 while…do 循环。
循环条件两个。
第一个：random() < p。因为 p = 1/2，那么该条件成立的概率也是 1/2。
如果每随机一次，满足 random() < p，那么层级加一。
那假如你运气爆棚，接连一百次随机进去的数都是小于 p 的怎么办？岂不是层级也到 100 层了？
第二个条件 lvl < MaxLevel，就是避免这种状况的。能够保障算进去的层级不会超过指定的 MaxLevel。
这样看来，尽管每次都是基于概率决定在那个层级，然而总体趋势是趋近于 1/2 的。
带来的益处是，每次插入都是独立的，只须要调整插入前后节点的指针即可。
一次插入就是一次查问加更新的操作，比方上面的这个示意图：
另外对于这个概率，其实火男在论文专门写了一个小标题，还给出了一个图表：
最终得出的论断是，火男倡议 p 值取 1/4。如果你次要关怀的是执行工夫的变动，那么 p 就取值 1/2。
说一下我的了解。首先跳表这个是一个典型的空间换工夫的例子。
一个有序的二维数组，查找指定元素，实践上是二分查找最快。而跳表就是在根底的链表上一直的抽节点（或者叫索引），造成新的链表。
所以，当 p=1/2 的时候，就近似于二分查找，查问速度快，然而层数比拟高，占的空间就大。
当 p=1/4 的时候，元素降级层数的概率就低，总体层高就低，尽管查问速度慢一点，然而占的空间就小一点。
在 Redis 中 p 的取值就是 0.25，即 1/4，MaxLevel 的取值是 32（视版本而定：有的版本是 64）。
论文外面还花了大量的篇幅去推理工夫复杂度，有趣味的能够去看着论文一起推理一下：
跳表在 Java 中的利用
跳表，尽管是一个接触比拟少的数据结构。
其实在 java 中也有对应的实现。
先问个问题：Map 家族中大多都是无序的，那么请问你晓得有什么 Map 是有序的呢？
TreeMap，LinkedHashMap 是有序的，对吧。
然而它们不是线程平安的。
那么既是线程平安的，又是有序的 Map 是什么？
那就是它，一个存在感也是低的不行的 ConcurrentSkipListMap。
你看它这个名字多吊，又有 list 又有 Map。
看一个测试用例：
`public class MainTest {
public static void main(String[] args) {
ConcurrentSkipListMap<Integer, String> skipListMap = new ConcurrentSkipListMap<>();
skipListMap.put(3,”3″);
skipListMap.put(6,”6″);
skipListMap.put(7,”7″);
skipListMap.put(9,”9″);
skipListMap.put(12,”12″);
skipListMap.put(17,”17″);
skipListMap.put(19,”19″);
skipListMap.put(21,”21″);
skipListMap.put(25,”25″);
skipListMap.put(26,”26″);
System.out.println(“skipListMap = ” + skipListMap);
}
}
`
输入后果是这样的，的确是有序的：
略微的分析一下。首先看看它的三个要害构造。
第一个是 index：
index 外面蕴含了一个节点 node、一个右指针（right）、一个下指针（down）。
第二个是 HeadIndex:
它是继承自 index 的，只是多了一个 level 属性，记录是位于第几层的索引。
第三个是 node：
这个 node 没啥说的，一看就是个链表。
这三者之间的关系就是示意图这样的：
咱们就用后面的示例代码，先 debug 一下，把下面的示意图，用实在的值填充上。
debug 跑起来之后，能够看到以后是有两个层级的：
咱们先看看第二层的链表是怎么的，也就是看第二层头节点的 right 属性：
所以第二层的链表是这样的：
第二层的 HeadIndex 节点除了咱们刚刚剖析的 right 属性外，还有一个 down，指向的是下一层，也就是第一层的 HeadIndex：
能够看到第一层的 HeadIndex 的 down 属性是 null。然而它的 right 属性是有值的：
能够画出第一层的链表构造是这样的：
同时咱们能够看到其 node 属性外面其实是整个有序链表（其实每一层的 HeadIndex 外面都有）：
所以，整个跳表构造是这样的：
然而当你拿着同样的程序，本人去调试的时候，你会发现，你的跳表不长这样啊？
当然不一样了，一样了才是撞了鬼了。
别忘了，索引的层级是随机产生的。
ConcurrentSkipListMap 是怎么随机的呢？
带大家看看 put 局部的源码。
标号为 ① 的中央代码很多，然而核心思想是把指定元素保护进最底层的有序链表中。就不进行解读了，所以我把这块代码折叠起来了。
标号为 ② 的中央是 (rnd & 0x80000001) == 0。
这个 rnd 是上一行代码随机进去的值。
而 0x80000001 对应的二进制是这样的：
一头一尾都是 1，其余位都是 0。
那么只有 rnd 的一头一尾都是 0 的时候，才会满足 if 条件，(rnd & 0x80000001) == 0。
二进制的一头一尾都是 0，阐明是一个正偶数。
随机进去一个正偶数的时候，表明须要对其进行索引的保护。
标号为 ③ 的中央是判断以后元素要保护到第几层索引中。
((rnd >>>= 1) & 1) != 0，已知 rnd 是一个正偶数，那么从其二进制的低位的第二位（第一位必定是 0 嘛）开始，有几个间断的 1，就保护到第几层。
不明确？没关系，我举个例子。
假如随机进去的正偶数是 110，其二进制是 01101110。因为有 3 个间断的 1，那么 level 就是从 1 间断自增 3 次，最终的 level 就是 4。
那么问题就来了，如果咱们以后最多只有 2 层索引呢？间接就把索引干到第 4 层吗？
这个时候标号为 ④ 的代码的作用就进去了。
如果新增的层数大于现有的层数，那么只是在现有的层数上进行加一。
这个时候咱们再回过头去看看火男论文外面的随机算法：
所以，你当初晓得了，因为有随机数的呈现，所以即便是雷同的参数，每次都能够构建出不一样的跳表构造。
比方还是后面演示的代码，我 debug 截图的时候有两层索引。
然而，其实有的时候我也会碰到 3 层索引的状况。
别问为什么，用心去感触，你心里应该无数。
另外，开篇用 redis 做为了切入点，其实 redis 的跳表整体思维是大同的，然而也是有小异的。
比方 Redis 在 skiplist 的 forward 指针（相当于 index）上，每个 forward 指针都减少了 span 属性。
在《Redis 深度历险》一书外面对该属性进行了形容：
最初说一句（求关注）
好了，那么这次的文章就到这里啦。
满腹经纶，难免会有纰漏，如果你发现了谬误的中央，能够提出来，我对其加以批改。感谢您的浏览，我保持原创，非常欢送并感谢您的关注。
我是 why，一个被代码耽搁的文学创作者，不是大佬，然而喜爱分享，是一个又暖又有料的四川好男人。
欢送关注我呀。
