00:00
好,同学们,我们继续对于哈希结构以Java程序员的基础都清楚,KV建制对,无非就是在层面上我们调用一个h set命令,底层有一大堆dictionary字典的映射,对于它我们不用过多的展开,因为面试也还不是考它,面试考的是z list,这个是我们本节的重中之重。好了,来吧,说了那么多,Z please,犹抱琵琶半遮面,下面。一窥庐山真面目开工首先是什么能干什么?为什么我们写个h set,一开始的时候只要没超过这个峰值哦,它用z list呢?有什么好处?我们来,同学们请先看zli.c。老规矩六这个版本。来吧,给你做了相关的权面的介绍,OK,有这么多,那么这是最权威的官方文档,那么同学们我们尝试一下解读,开工把这段话给弟兄们做一下翻译,一样的啊,弟兄们都是抓过来的啊,我就不再反复切换了,他直接告诉你z list压缩列表是一种紧凑的编码格式,总体思想是多画时间来换空间。
01:22
哎,那么只要是Z有压缩解读的时候,就要有解压,压缩解压,压缩解压当然要比原生的要耗点时间了,好处就是牺牲时间来赢得了我们的什么空间,所以它是以部分读写性能为代价来换取极高的内存空间利用率。因此。只会用于字段个数少,就是那个F的字段比较少的,且字段值也比较小,那个value值也在64以内的这样的小场景,小而美。用哈希底层的zli压缩列表内,这个利用率极高的原因就是与其连续内存的特性是分不开的。哎,压缩呢,大家的好处什么?紧凑,紧凑就不容易有碎片,当然它有其他的缺点啊,后面我们聊,那么在这块压缩列表,同学们请看一下,还记不记得我们在学习GVM的时候给大家讲过一种机器的垃圾回收机制啊,标记压缩算法,那么一句话,先标记再压缩对吧?那么这个时候当然要耗时一,但是压缩了它的空间是不是就节约出来了?所以当一个哈希对象只包含少量的建制对,且每个键持队的键和值要么就是小整数,要么就是长度比较短的字符串,那么它直接用z list作为底层实现好。
02:42
那杨哥这个Li list的概念用途我明白了,无非就是什么,压缩了以后干嘛呢?时间换空间嘛,对不对?我们这呢也直接明白了,那他长什么样呢?请看replace的总体大纲来,他就长这个样,下面听我解读好。
03:06
首先the please c啊,它是为了节约内存而开发的压缩嘛,内存空间肯定占的少,那么由连续内存块组成的顺序型的数据结构有点类似于数组啊,来吧,首先z list是一个经过特殊编码的什么东东,双向链表有点类似于我们Java的link list,但是注意。它不存储指向前一个链表节点的。和指向下一个链表节点的next,就说我一个节点一般双向链表嘛,对吧,就像一个挂一个火车一样的火车车厢,我前车厢后车厢。Bra。和next next它应该有,但是对不起,不存储,我这稍微改了一下,它反而是存储上一个节点的长度和当前节点的长度,通过牺牲部分的读写性能来换取高效的内存空间利用力。节约内存是一种时间换空间的思想,只在字段个数少、字段小的场景里面使用。好,同学们先把这一段总干整明白,那么接下来我们对照着就来看看那杨哥,我明白了,瑞哈希它有一种数据结构叫压缩列表,那么这个列表是一种特殊的双向链表,没有存指向我前一个节点和指向我下一个节点的指针,而是存储了上一个节点的长度和当前节点的长度。哎,用长度替换了前后指针。那么它长什么样呢?同学们请看,就长这么一个ZL,是z list压缩列表的缩写,就。
04:49
告诉你每一个压缩列表,它的结构长这样,Zip list的直接缩zip please的为z list的长度,然后中间是一个en en en en,一个实体,对吧?有点像我们Java里面的哈,Map的那个node节点你丢进去K建指对实际而言是把你封装成一个no的节点,那么这个no的节点其实也就是N,一个个N垂实体,最后是压缩列表的N结尾,所以。
05:18
这么解读,首先压缩列表的结构就长这样,它记录了压缩列表占用的内存字节束,记录了尾节点至起始节点的偏移量,记录了节点的数量多少个,那么这个是一个一个的节点,从一到N相当于一个火车车厢,一节节的车厢。压缩列表包含了各个节点,节点长度又具体内容搞定。最后是特殊值0XFF标记压缩列表的尾部对应的十进制的就是255 OK,好,那么同学们我们先明白,现在我们就会得到一个压缩列表,它底子就是有这么多构成,说白了,1234。
06:06
然后呢,总体的占用的字节数,尾部长度和结尾标识符中间就是一个一个的N出,这个里面就是有点类似于我们的K键之对,好,那么它的各个单元组成是什么意思呢?来弟兄们老啊,首先。这个是zip list的字节,记录整个压缩列表占用的内存字节速,哎,那么它记录了以后,后续我扩缩容的时候,它容易进行内存的重新分配和计算,因为有个固定值。第二个z please的tell记录压缩列表尾节点距离压缩列表起始节点有多少地址,通过这个偏移量能不能什么好处啊,你不需要遍历整个压缩列表就可以确定表尾节点的地址。第三一个总体长度,那么记录了压缩列表包含的节点数量,那么当小于这个时候,那么这个属性就是压缩列表包含节点的数量就是65535,那么当这个值等于这个的时候,那么需要整个变例才能计算出它有一个什么分隔点,最后就是列表的节点多少个呢?不定,那么压缩列表各个节点,那么这个呢?由我们的保存前面的长度所决定,最后是什么?
07:23
特殊值相当于说是压缩列表的尾端,OK,好,同学们先有这么一个大致的了解,我们就会清楚zip list是什么,长什么样,以及每个字段的单元格是什么。重点是这个N除以X,就是里面有一个个的车厢,听懂了吧?那么最终我们保存的放在这,好,先了解z list,它长什么样。通过上一讲我们了解了zli这样的一种数据结构,这是red哈希结构一种特有的,那么它呢,由这样的一种东东构成,前三个字节,尾部长度,最后是z list end,那么中间就是一个一个一个的车厢,对吧?那么所以我们现在呢,就来看一下它的接下来的操作。
08:19
The entry,也就是每一节车厢真真正正装数据的这个,它装了一些什么东东?换句话说,也就是我们常说的压缩列表节点。那么在开始之前,请允许我对比性的向同学们介绍,咱们先来唠一唠第一个。希望同学们熟悉的Java哈希,我一说Java的哈希map,那么大家呢,百分百都懂,好,先写一下尿哈西map.put然后假设我这是一,这是ABC,那么我相信这个是K,这是value,怎么进来的?不用多说,我下面就问大家一个问题,都清楚哈希map底层是数组加列秒加红黑数这个结构,对吧?那么下面我的问题是。
09:11
什么类型的数组?我的问题来了,就是哈希它为了保存它封装了一个什么类型的数组,OK,好,那么这个呢,大家呢,请思考一下,我呢,继续写。那么接下来啊,我们这个呢,是我们的red哈希,自然而然它也会封装出一种数据结构,封装一个构新的特有的数据结构,那么也就是我们这的z list,好,那么同学们,下面这个你想起来是什么类型的数组了吗?大家还有印象吗?那么来啊,听好,我这儿是不是有种东西叫。
10:02
节点。一般的英语单词叫什么?是不是叫not?所以大家请看源码,这是我们加va哈希的啊,最经典的哈西map put1put,我叠弟兄们什么鬼哦,原来我丢进去的KV建职队,人家不是存进去一个KV建职队这么简单。把这个KV建制队封装进了no的节点,也就是我们所谓的每一个KV建制队的哈西no的节点,它从是从一个no的节点类型相关的数组,所以隔到这儿,同学们请看这个是不是叫map.en。能理解了吗?所以说这个时候这个静态的内部类实现了map.entry这么一个实体接口,那么每一个no哈希KV请看是不是又保留着指向下一个节点的,因为速度加链表嘛,链表无非就是单向链表和双向链表,那么如果是单向链表就是next,如果双向链表除了有nextx以外,还是不是还有一个previous?
11:11
OK,所以这个才是我们得到的一个结论,我们封装的什么类型的速度no的类型,OK。好了,那么接下来。一样的对比着来学习这种思维方式啊,那么我们从Java哈希过渡到我们的瑞哈希,人家呢也封装了一种特有的数据结构,这个数据结构就叫zip list压缩列表,OK,那么每一个压缩列表里面同学们我们看了1234首三个尾,一个是它的特殊的结构体对应的属性,那么接下来真真真正我们干活包含数据的就有点像我们这我们的数据丢进去的是KV,然后人家包装成是不是叫一个node节点,俗称哈西node,那么一样,现在我们的哈希,人家封装一种数据类型叫z list,那么丢进去的这么一个entry entry ENT ENT,大家请看,这个时候叫map entry,那么自然而然我们这边给到的是不是也叫z list,简称zl entry,俗称压缩列表节点,听懂了吗?
12:25
哎,我相信这样对比的来说,弟兄们应该更好理解一些啊,不要慌啊,以前我带着大家读面试题源码的时候,也没有很多同学答错,是就把这个KV丢进map,不是的,人家map里面丢进去的是一个no的节点,是封装了一个静态里,不对,OK,也记哈希,Map数组加链表加红黑数,人家马上会问你是什么类型的数组,一定要答是node类型的数组,OK,好,那么接下来压力给到red这边,那么下面就要聊聊压缩节点。他又是个什么东东?那么z list entry,那么大家请看官方源码首先来自于z list.c那么来弟兄们说人话的意思就是我们现在已经明白了整个z list是由这么多构成,那么一个一个的节点,它长什么样?好,那么同学们往下走,大家呢,可以非常清楚的看到在这有一个z l entry,它呢就有这些定义的内容,然后相当于封装一个类,只不过我们前面讲过这种在C语言里面的语法叫结构体,所以搁到这官网源码直接拷贝过来就不再切换关到这儿,那么来啊,杨哥请解读一下,那这些分别是些什么东西,对吧?那么请问好,那接下来我们就给同学们介绍一下z and z list entry,也就是压缩列表节点实体,它里面这些结构所定义的字段分别代表什么含义?那么来,同学们请跟着我来看一下实体结构对应字段的解析。
13:59
请看。
14:01
这个呢是代表previous,若length size上一个链表节点占用的长度A。先说一个,它记录的是上一个链表节点,你可以把它理解为我前一个车厢,这个呢,存储上一个链表节点的长度数值所需要的字节数,这个呢是到这才是存储当前链表节点长度数值所要的字节数,这个呢是当前链表节点它占用的长度。接下来这三个是后面部分,那么分别是当前列表节点的头部大小。然后呢,编码方式,然后呢,压缩链表,以字符串的形式保存该指针指向当前节点的起始位置。好,那么同学们,这个就是我们对z l en垂对应压缩列表节点构成它所做的介绍。那么基于此,我们介绍了两个东西,一个叫z list,每个z list它呢,里面有多个NT垂节点,OK,你可把理解为这个就是一个K,每一个K里面干嘛一个field和value就是一个一个的N,它呢,就以这样一种结构来进行存取。介绍完了z list。
15:21
也明白了,每一个zip list里面专有一个到多个zip list的NT垂压缩列表节点,那么接下来数据结构是什么?搞懂了,那它这个存取情况,它是怎么来完成这个动作的呢?那么来同学们请大家看啊,假设性的杨哥delete user01好,删掉,重新来h set user01id是一号,然后呢,现在呢,C name是王五这个人age是25岁,弟兄们没有任何问题吧,H get war,那么USER01这个是不是一个最经典的?
16:07
哈西key对应的使用和结果展现,那么好,我object including,然后呢,USER0些,请大家告诉我现在这个是不是1ZIP list,那么请问h get war,我们就会明白,那么现在在这么一个key,这个key目前它就是一个啊,当然没有超过我们的峰值,那么超过了转成哈西table,那么现在在这个zip list里面,你告诉我包含有几个N出,是不是就包含着有三个N醇IDC name和A啊,那么每一个N里面又记录了什么?是不是记录了这些东道,尤其是这它为什么要记录前一个或者叫上一个链表节点占用的长度?好,那接下来同学们老眼我们现在第一波啊,我们先明白我一点点讲,杨哥这呢现在呢先有了一个z list。
17:05
叫USER01这个key,现在它安装进去了三个值,现在USER01它的值的编码类型是什么东东?Zip list也记,我有一个z list,现在这个里面你告诉我有几个值,N除以一,N除以二,N除以三,咱们是不是有IDC name h有三个,OK,那么每一个entry list最重要的也就是我们这所看到的前一个上一个节点的长度,然后你自己的encoding编码,然后你的N垂date,你自己承担的数据又是什么?OK,那么来弟兄们,我这个ID1号记录客户名字叫王五,年龄是25岁,那么结合下来他就长成这么一个样,这个就代表我们的name姆,比如说to a级是25,这个是什么,它的职业等等等等,那么告诉我是不是在一个Z的结构体里面封装进去了三个field。
18:05
啊,以及三个KV建制,对呀,所以它的整体结果从左到右一个Z,一个z list压缩列表里面有多个ZLN垂节点,OK,弟兄们到这儿应该清楚了吧,那么每一个进制对它主要记录最重要的就三个啊,就是这么多,那杨哥我是不是都要把它背下来,不用真真正正关键的就三个也记记录了。前一个节点的长度,然后呢,当前节点实际数据的类型和长度,最后就是你实际数据是什么就是什么,OK,它的存取关系大概是这样,好,那么来解析一下每个压缩列表里面的ZLN除以节点的结构,它有前一个节点的长度、编码和N里面的数据三部分构成,从上到下有这么多,这是它的结构体,每一个结构体我都给大家呢标注完清楚了,我们对应的注解,假设这个是上一个节点的长度,这个上一个节上一个节点,这个呢是上一个节点长度所占的子节数,而这个呢,是上一个节点的长度,好,特别强调上一个节点,那么接下来这些我就不在照本宣科的读了,那么给我听好。
19:23
我们在这儿为什么要强调刚才的上一个节点,它有它自己的考虑,涉及到链表的便利,听我解释最重要的z list,它另辟蹊径,它没有用Java里面的link list那样的双端链表,有没有发现它永远记得是上一个节点,他可没有给你记录什么,一般我们定义列表里面的previous和什么next,人家没记这个动作,哪怕像我们Java里面的node,是不是也记了一个next?人家盯着的是我上一个,好,那么同学们请听杨哥分解前节点啊,就这个表示前一个。
20:10
ZLN垂的长度,那么前置N垂的长度一般有两种,取值一个字节或者是五个字节,那么取值一个字节的时候,表示上一个节点的长度小于254个字节,虽然一个字节能表示的值的范围是零到255,但是压缩列表当中ZLN的默认值是255,还记不记得就是我们在这儿啊说过这是不是说过ZLN的就代表它是?结束符了,尽量不要跟这个冲突,那么特殊值0XFF10进去就是255,所以说我们这达到极限,我们这解析了以后。你压缩列表中ZR的默认值是255,避免冲突,因此就默认255表示整个压缩列表的结束,其他表示长度的地方就不要再写255这个值,以免产生混淆和奇迹。所以当上一个N垂的长度小于255字节时,那么pre length的取值就为一字节,否则就取为五字节,那么一或者是五常用的啊,那么记录长度的好处,内存占用极小,一个或五个字节,那么第二个就是它的靠的这个编码,我们只说最重要的三个值啊,跟我们相关的前一个的还有当前的编码,记住当前内容的保存数据的类型和长度和一些编码。那么接下来来看,那么也就是我们这儿所说的,这怎么着实际保存数据的内容OK,那么来,所以说弟兄们整个they entry,他呢?
21:44
当前节点。要记录的上一个前一个节点的长度就这个,然后呢,它自己的信息分别以这几个字段来进行保存好,那么这张图已经非常清晰的表达了我们所需要获取的知识以及相关的信息,对应到我们这就是每一个ZL节点封装进去的值就进去这么多,那么它有什么用呢?你这个ZLN垂节点为什么要这么设计?思考一下数组和链表数据结构对比一下,那么弟兄们啊,我们呢,最简单的大家都清楚有两个啊,一个呢是叫数组对吧?另外一个是不是我们学过一个东西叫链表。
22:31
他们在增删时间、复杂度上面有哪些问题大家都清楚。对于我们一个数组而言,它的查询按照下标是不是比较快对吧?那么它的便利的时间复杂度是on,即便是什么。他的。查找是非常非常快的,但是删除好不好,删除不大好,那么大家都清楚啊。假设我现在这。
23:01
有一个数组对不对?假设就这么三个或者是四个吧,我们大家都清楚,如果我把中间这个干掉了上走,那么后面的是不是要往前攒一位,哎,数组是不是查找比较方便,删除比较麻烦啊,那么我们的链表我们大家都清楚,非常的easy,这个节点啊,还有这个节点那么干嘛?你要是有next指针,我就指向下一个,如果说你现在要把我干掉,那太简单了,我把这个指针直接呢,绕开你,以前是指向你,现在对不起,我不指向你了,我指向它,那这个如果前后都没有节点的话,默认是不是就被我们认为是什么已经是一个无效的节点,退出我们的序列就被拿掉了,能理解,所以说这哥们属于什么?删除增删比较方便,但是便利的话是不是比较痛苦,哎,所以说red大神是不能够接受这么慢的,他想一下我这个Z牙的N垂也能不能变利,也像速度一样那么快呢?好,那么下面漏E它为什么要记录前置节点的长度,那么这个呢?都可以用编码方式推导,真正有变化的是这个。
24:31
内容,那么假设我重新写一次,他的名字就变成了叫王五五。长度,假设另外一个用户变成101,那么这个是ID啊,这些数字说长度变化了,内容有变化,但是这个长度是记录在encoding里面的,因此N垂的长度我们就知道了,这个实体N垂的总长度就等于前置节点的这个字节数,再加上这个和自身的这个内容就可以获得。那么它为什么要这么设计呢?要记录前一个节点呢?下面重点请听讲每一个key现在是个z list,这个这个这个这个三个,这四个金黄色的就是我们的结构,这个结构里面住着多个entry,每个N垂最重要的就是它的前置啊编码和它的N垂的date内容,所以我们得到在链表在内存当中一般是不连续的,它不像内存这样是连续的开片,大家都清楚,一个内存写个你有中括号是不是内存连续开片链表一般不连续,它都是靠指针随便戳。
25:37
或那么这个时候呢,它的链表的便历相对呢就比较慢一些,而zli它新开发这种数据结构就是可以解决链表变力慢这个问题,如果我们知道了当前的起始节点,由于这个N出在塞在这个里面的话,它是连续的,那么这个时候我们N垂之后一定是指向另外一个N垂,就像是火车车厢之间是不是有钩子连接起来,那么我要是想知道下一个节点的地址啊,那么是不是只需要将当前的起始地址啊,假设是这个,再加上当前我这个N的总长度这个数字一碰,因为每一个节点是不是要记录上一个节点的它的长度,那么两个数字一样了,那么是不是就马上就可以变列到下一个,那么如果还想便利下一个节点,一便利二,二想便利?三那么是不是可以如法炮制啊,就解决了我们普通链表在内存中不?
26:37
连续便利,相对较慢这样的问题啊。接下来来看一个面试题,明明已经有链表了,为什么要出来一个压缩链表?哎,都是围着这些面试题再进行梳理和讲解啊,说白了都是为了应付面试啊,否则神经病啊,去读这些什么C语言的语言代码,所以呢,量体裁衣,我们呢,把握这个度,不用竹行,竹行给你解析,大体明白,能够对于这些八股文有一个总结性的陈述,跟面试官能过两招就行了啊,你放心,我不相信这个面试官,你有本事去阅读这些无聊的东西,对吧?除非你自己去写。所以呢,各位同学耐着性子跟着来,前面我们已经介绍了the please是什么?
27:25
然后也通过前面的案例给大家说清楚了,整个key目前的结构是个zip list zip list的结构就长这样,每个zip list里面有个entry,这个ENT就是我们所编写的field value field value OK,那么它的存取情况结合数组加链表,它是为了内存不连续,里面的链表也能够便利的比较快。如果你明白了这个设计思路,那么回答这个面试题应该不难。好,那么同学们搁到这儿,我们呢,来简单的过一遍。
28:01
首先已经有链表了,为什么要出来一个压缩链表?在开始讲之前,允许我回到我们的Java,一般说链表大家在link list这个里面不陌生吧,这样的方法同学们。点开ADD,这是不是就link last这个方法,再点开告诉你是个note,注意现在是link list,再点开,请看link list里面封装了一个什么,也是一个node节点,但是人家这种中规中矩的,一般我们口述性所表达的链表,人家是有前置指针和next下一个指针,它是有两个指针,注意,但是我们偏偏我们的z l entry人家没有用指针,人家给你记录是上一个前节点相关的大小和信息,哎,这个是靠指针指着下一个,人家这个是记录着什么前一个上一个节点的信息,这是完全两种不同的思路,为什么要这么干?请看我们普通的双向链表都会有两个指针,不陌生吧,都是加二的东西。
29:16
在存储数据很小的情况下,我们存储的实际数据的大小可能还没有指针占用的内存大,得不偿失。所以z list是一个特殊的双向链表,有维护双向职称。再次强调z list没有这两个东西。OK,这货它是存储了上一个N垂的长度和当前N垂的长度,通过长度推算下一个元素在什么地方。吸山读取的性能而获得高效的存储空间,因为减短字符串,这种情况下存储指针比存储N垂的长度更费内存,就是典型的压缩解压,用时间来换空间,OK,这是第一点。第二个链表在内存当中一般是不连续的,那么便历相对比较慢,但是呢,The它呢就可以很好的解决这个问题。那么普通数组的便历是根据数组里存储的数据找到下一个,比如说in特类型的数组,反问下个元素时,只需要移动s of in就行。那么这个阳哥,这个s of什么意思?C语言里面就是说实际上获取数据在内存中所占有的存储空间以字节为单位啊,这是C元的一个函数,那么如果是普通的一个数组,假设in特型的,那么找的话,你每次移动的就是个in特,那么大小的就行了,但是z list呢,每个节点的长度可能是不一样的,我们强调过了,这个是个数字。这块可能是往。
30:44
五很多很长,所以它每一个是不一样的,那么我们面对不同长度的节点,你不可能说每次但是整齐划一的,对吧,都来一个这么大小吧,也不能说只兼顾这个最大的不可以。所以z list要解决这样内存不连续,类型不一致的,只好将一些必要的偏移量记录在每个节点,自己带着做减法以后,使之能跳到上一个节点或下一个节点,这是它的第二个优势,第三个头节点里面。
31:15
同时还有一个参数是lengths,和死存类型提到的SDS是类似的,那么这里呢,是用来记录链表的长度,因此获取链表长度时间就不用再遍历整个链表,哎,直接拿到认值就可以了,这个时间复杂度是OE听懂,所以说这个z list我们也前面说过,你看1234,这个是尾,这个呢是节点数量,那多少个节点这给你记着了,你不用再给我去变例了,OK,好,那么这个也就是我们得到了,为什么已经有链表了,人家再次强调啊,没有这样的什么两个指针直接是记录。节点之间的上下,它们的所占用的自己的长度跳过去就OK了,所以呢,我们这就可以获得这道题目对应的一个回答,那么最终z list它的优点和缺点我们来说一下,那么来首先呢,节约内存压缩嘛,肯定要节约内存时间换空间,内存连续紧凑,双向链表可以在时间复杂度为OE的情况下从头部尾部进行。
32:22
增删新增或更新元素可能会出现连锁更新现象,哎,这个就是面试回答的第二个重点。已经有Z了。为什么要要用list pack替换?只有一个原因,最重最主要的啊,但是它有其他,我个人认为就是因为连锁更新现象所导致z list被推翻重建,被紧凑列表list pack所替代。OK,好,那么这个我们待会说,最终我们会明白,Zip list不能保存过多的元素,否则查询效率也会降低啊,数量小内容小的情况下可以使用。这个就是我们在RA6我们所需要了解的它的数据结构和类型,一句话,基于RED6下面的哈希结构,它主要是靠哈table和Z。
我来说两句