00:00
好,各位同学,我们继续通过前面的讲解,对于READY6哈系统数据结构已经明白了,哈希加zip list,那么六版本结束并掌握的前提下,进入到我们的七,几乎一模一样,唯一的区别就是把zli替换为了link pack,所以在这儿就是我们前面所说的这张图,一句话,哈希在七以后,哈希表加紧凑列表,那么我们的所有知识只需要围绕它展开即可啊,学习曲线没有六这么多,或者说前面六吃过的苦,理解七也就不难了。来,同学们打开还是熟悉的配方,还是熟悉的案例,来吧,咱们呢,先来看一下,先说理论,再说实操,那么这个时候从七以后对。
01:00
Z list退居幕后,因为它有连锁更新的问题,导致被替换。那连锁更新是什么,我们后面聊,那么现在和之前一回事,请看好,那么这个呢,那杨哥为什么你一执行这一个默认值的话。会出现四条记录呢,RED7为了兼容和过渡,依旧保留thep,它有点像Java里面的deprecated,不再推荐你使用了,但是你不能说在这个结构上我把它干掉了啊,就说没人用了,但是我保留着保证上下版本的前后兼容性和一个过度的使用,但是实际真真正正起作用的是list pack紧凑列表,所以有前面的基础,我们这一看,大家呢就会马上秒懂。这个entrance呢,就是个数,这个values呢,元素的最大长度不说了,那么一句话,如果哈希键值的个数小于这个,然后呢,值也小于这个的话,它就用什么list派来存储前数条件,任意一个不满足,立刻转换成我们的including。
02:10
H哈希table,所以同学们请看,这个呢,是RED7啊,一开始哈希开头的全给你录下来,有四个,但是起作用的这两个,那么大家请看,我这没在设置zip list了啊,我设置是list pack,三跟五的话请大家看。什么效果?诶,我改的是list pack,但是z list也对应着进行了更新,哎,它们两个是连带的,好,那么接下来我们再来试试啊。那既然这样的话呢,Z list的修改会影响啊,抱歉口误,既然上一步this pack的修改会影响zip list,那么我们反过来,这次我动用zip list的修改会不会影响我们的list呢?那么大家请看。
03:01
什么鬼,我把它从三和五改成两个一样,我改的是z list,你会发现紧凑列表list pack也被改了,所以说它们两个,你可以把它理解为两个入口,实质而言起作用的是它只有一个落地。好,那么下面再来看,如果我现在设置啊。这个是二,然后设置这个是多少,这个是四,跟前面的道理是一样的,那么哈西set ID是一,Name是一张三两个字段,这个时候including多少啊,是list park,但是如果超过了以后,同学们请看,又变成了什么哈西table,哎,我相信这个应该很好理解对吧?好,那么同学们理论上我们就说到这儿,那么这个呢,是我们的六,那接下来呢,我们把我们的七呢,直接呢连上了,好那么同学们看f get哈西开头的,那么大家请看。
04:06
基本上是不是也就是我们的512和64啊,这个理论值就不多说了,那么我们就干脆做个实验好吧,那么这是N出,这是四啊,因为由于在六上面做过这个呢,只是给大家演示一下七好吧,那么看赛此时我们所修改的是紧凑列表的个数,我们把它从512对吧,改成三个,好,我们再说紧凑列表的值,好,那么同学们,我们把它从三改成五个,我相信大家没什么问题吧,那么再来哈希啊一查看大家请看我改了紧凑列表,但是压缩列表是不是也被联动着被进行修改了,OK,好,那么来我们接下来呢,H set user,零,二,那么ID是2c name,张三,弟兄们两个远远达不到我们的要求,那么object。
05:06
Including user02弟兄们请看,此时出现的是不是就变成了我们的list pack,而不再是z list了,说明从六到7ZIP list的地位已经被list pack所取代,这也就从根本上证明了原来我们在小白篇。给大家强调过的这句话,RE7的新特性,这句话大家我相信应该是有非常非常明显的体会了,It park替代了z list OK,这是RED7的新特性,所以啊,这个数据结构你100%要掌握,逃不掉。回到我们的案例,自然而然,弟兄们,如果现在杨哥继续写age级25,然后过88分,那么来吧,再看看它的编码是不是一下子从紧凑列表就变成了我们的哈table,总体套路是不是跟我们的READY6几乎一致?那么当然那个value我就不测了,我相信再这么做下去,你就会嫌我啰嗦了。好,懂这个意思就OK,那么基于此我们就会明白。
06:20
在RE7哈希结构下面,紧凑列表的entrance代表保存集合中的最大元素个数,那么这个呢,代表它的长度。那么所以说结论啊,默认哈希对象存储的键值如果数量小于512个,或者说所有键值对键和值的字符串长度都小于64个字节的话,我们就要用list派,反之,我们用哈sh table,如果从list派紧凑列表升级到哈table是可以,反过来从has table降级为list pack是不可以的。OK,那么继续基于此,我们流程上面和前面一样,只不过z list修改为了list pack,那么这张图我都没有重新画,同学们。
07:07
应该马上秒懂好吧,所以说呢,就是把这块the换成了我们的什么list pack,那么这个就是我们七对应的修改,那么接下来由有六的基础这块我们就快快的过,那接下来我们就抓七来说一下源码分析学习并认识一下list pack紧凑列表这种数据结构。接下来说一下七版本,下面哈西编码的不一样,直接七了啊,现在源码已经变了,说人话,其实质而言就是z list过渡到list pack。咱们看一眼,首先。先看一下object c对应的定义和实现一二,那么为什么分两步呢?我们同学们请看啊,我们这个C这有个创建哈希的对象。
08:01
然后呢,请大家看这有个,你看它这是不是还是用z list,就是原来那套版本的定义,只不过这变成了list pack new出了这么一个函数,然后下面呢,出来这么一个,请看red object这么一个对象,创建object,然后编码是什么,或者我们的常量定义是哈希的传了一个。ZL,当然这个就是一个指针,一个引用,然后告诉你这个对象里面的是吧,编码方式设置为list pack,然后返回我们这个哈希对象,那么现在大家应该清楚我们这个key结合里面的field的value是怎么一步一步来的了吧?好,那接下来的关键就是list pack new这一个方法,那么来同学们这些都是我从七里面这个抓图过来的啊,我就不再反复切换了。那接下来同学们请看list pack.c点开这看,首先这有list pack h.size多少是六,这是七的啊,然后结合刚才我们的派点C下面就会有。
09:13
List pack new这么一个东东,那么capacity初始化,它直接告诉你创建一个新的并且是空的list pack,好,这张代码呢,大概是这么一个意思,当我们要创建的时候,它先申请一个空的list派,那么空了以后呢,那不行啊,你得装东西啊,那么所以一开始分配的大小是这个的上面,上面是多少六听懂了吧,那么大家请看啊,Lp list pack h DR size,再加个Z,那么加这么一个字节是初始化的分配,而干的这个活呢,来判断一下,你给我的,你看它默认当时是不是一个零嘛,零大不大于这个,如果是三运算符大于的话就是这个,False的话是后面这个,OK,所以说我说的这个零是这个意思啊。
10:01
你看LP6是不是零能能理解了吧,下面是是是一个这个三个运算符,这这就不废话啊,那么所以说这种东西呢,是C语言里面的宏定义,那么再次跟大家说一下,不会逐行逐行的死扣里面那些C的东道啊,你大致了解就行了,毕竟我们是Java用red干活满足面试学到东西不是玩C好,那么这个时候呢,我们大家看默认六个字节,其中四个字节是记录这个list派总的字节数,两个字节式记录它的元素数量,此外最后一个记字节数要用什么?List pack end of fire,那么这个时候和list。Zip list列表项的结数标记一样,这货也就代表是什么255,就是0XF f16进制,那么这时候返回我们这个灯道,好返回了以后,那么大家请看我们这儿是不是返回了这么一个ZL了,那么好开始创建我们这个对象,相当于说这儿你要创建一个哈希对象之前,先要给它分配一个初始值作为默认大小的list派。哎,从这一点你就应该明白,真正真正RIGHT7以后,哈希对象底噪其实就是in respect紧凑列表,那么好,大家看一眼在这。
11:19
创建下来由这个对象,那么就是刚才我们所分配的,然后type编码指针引用,默认是不是只有一个人一在引用,然后这个判断这个max policy server定义的是否大于,然后怎么样最终L始终落克好,然后反馈我们这个对象,它的整体创建思路是这样一个流程。接下来红色面试题原题,明明已经有zip list压缩列表了,为什么要出现来一个list pack紧凑列表?那么自然而然一定是有压缩列表,有什么缺点在某些场景下面不OK,所以应运而生了更新的数据结构。那么下面我们一探究竟,先来复习一下,通过前面的讲解我们清楚,当我们任何一个zip list对吧?就在这假设是六的话,一个zip list它呢?
12:23
1234前三尾一是固定的,那么中间就是一个一个的N垂,那么每个N垂的结构前面我们已经详细说过,最重要的也就是这三个分别是是前一个节点的长度,以及本节点的编码大小,以及本节点的内容,那么好,N除以一,N除以二,N垂以三都这样,那么大家请看我这个是不是要记着前一个节点的长度,那么它这有个规矩压缩列表里面的每个节点中前置长度的属性都记录了前一个节点的长度,那么它呢,有一个对应的值,如果前一个节点的长度小于254,那么这个。
13:09
前置length的属性,只需要一个自己的空间就可以了,这样是不是最小占用?如果前一个节点的长度是大于254呢?那么这个是就让五个字节的空间来保持这个长度啊,这点是点小细节,但是不说这个呢,又讲不清,所以说给大家说人话的意思,就说前一个节点长度在每一个zip list里面的。属性里面不是保存一个字节,就是保存五个字节,好,有这个结论就行了,很关键,那么接下来继续,这个时候大家还记不记得?我在前面讲完课的时候,我们这儿说过一个问题。连锁更新现象导致zip list被紧凑列表所替换,那接下来同学们我们就来唠唠。
14:02
什么叫压缩列表的连锁更新问题?来同学们分这么几步帮助大家理解,压缩列表啊,它呢,新增或者是修改某个元素的时候,如果空间不够,那么压缩列表占用的内存空间就要重新分配,当新插入的一个元素比较大的时候,可能会导致后续的要记录前一个节点长度的占用空间会发生变化,从而引起连锁更新的问题,那么这就会导致每个元素的空间都要重新分配,造成访问压缩列表的性能下降。那说人话的意思啊,在六这我们这这个假设c name啊是W5,突然有一天杨哥呢,神经病。我这个W5呢,我就呜呜呜一大堆弟兄们,这个是不是就已经很长了,对吧?那么你这样一很长了以后,我这边是不是要从z list变成哈西table,也就是说我这有一个field的ID,有一个field c name,它们两个是底层是两个,分别是c entry,由于这个c name,你E这么干修改上是不是就相当于扩容了,那么我这个H以前你就玩五的时候,记得可能就是一个字节,但是随着你干就玩五,五越来越大了以后,那么我这个是不是也要。
15:30
变做修改,因为我后面第三个要记住前一个第二个的前置节点的长度,所以这就会导致这么一个情况,有一种极端情况,压缩列表每个节点正因为需要保存前一个节点的长度字段,就会导致连锁更新这样一个隐患啊,通过刚才的演示,我们再回到理论,假设一个压缩列表中有多个连续的长度在250~253之间的节点啊,比如说N除以一,N除以二,N除以N,反正啊,意思就是说没超过255够用,因为这些节点都小于254个字节也没有超过255,所以我一个字节来保存就OK了,很爽对吧?那么第二步这个时候,如果将一个长度大于等于250字节的新节点加入到压缩列表的表头,哎,或者是update修改操作,即新节点将成为N除一的前置节点,总之一句话就是不管是修改还是新建。
16:32
长度超过250字节的一个新的节点就出来了,那么来你晓得的,根据前面所讲,安一节点的前置长度属性一般是用一个字节大小表示,无法保存这么长的新节点的长度,那么这个就需要对压缩列表空间重新分配,将N除一这个节点的前置节点的长度属性从原来的一个字节扩大到五个字节,好,你加三进来了,我以前一个字节保存不够用了,现在要变成五个字节好吗?那么连续更新问题会出现,由于新插进来,这个影响到了N1。
17:13
扩容引发也对N除以二的扩展,因为这个大家基本上默认的够用的是不是都是写个一,那么你这变五了啊,都不好意思啊,前面的变五了,我后面是不是跟着,那么所以说就会导致一系列的扩张,尿导致一,一导致二,二导致三,三导致N,那么所以说这一系列扩张下去,直到最后一个节点全部扩容完成,N乘一的节点原本是在253以内,刚才一括N1的节点长度就大于254啊,那么原本N2的节点保存N1的节点,那么属性也将会从一个字节扩到五个字节,一扩了二就跟着扩,二扩了三跟着扩,三跟着扩了,四跟着扩,一直到N,一直到结尾,这种在特殊情况下连续多次扩展的操作就叫做连锁更新,明白吗?所以各位亲,得到这么一个结论,将会导致。
18:13
紧凑列表就是设计用来干掉替换掉压缩列表的数据结构,它通过每个节点记录自己的长度且放在节点的尾部来彻底解决z list连锁更新的问题。OK,所以这个就是为什么压缩列表被紧凑列表所替代。明白了替换原因以后,那么接下来我们重点转入list派,那么来吧,看看它。各自的组成分别是什么样?首先派的结构大家请看一般的结构,它告诉你了,我呢,由这四部分所组成,每一个节点分别是什么?那么均来自于官网,好,那这个官网的话呢,我这个gate呢,因为这个强的原因哈,哎,时好时坏,突然打不开了,但是呢。
19:08
好,那么现在大家请看啊,运气好啊,刚才死打都打不开,那他就直接告诉你现在list park它呢,是由这么一个动作所组成的,好,注意和我们之前的z list来进行对比,好吧,然后呢,简单一句话啊,在这块你要有兴趣,你可以去看一眼,他就告诉你以前的z list大概呢,是这么。一个形状对吧?三部分构成头、身子和尾,那么头呢,又用那三部分是不是大小啊,长度啊等等,那么中间身子呢,就是一个一个的z please entry,然后最后是zip end,基于此它呢做了一些修改,每一个list pack紧凑列表是这样,那么每一个紧凑列表里面的元素。ELEMENT1到element n又变成这样,有兴趣请参与官网,那么如果没有时间,请看杨哥一次性给你讲懂。首先我告诉大家资料来自于哪,第二个我们先来看,就两个东西,每一个紧凑列表,它的结构是这样的,每一个list派里面又有一个element,那么element又有三部分构成,那么说清楚这个,大致了解好派四部分构成分别是这样的,弟兄们1234请看首先是total bit。
20:39
那么也就是说,他的意思是。整个list派空间大小一般是占用四个字节,每个list pack最多这么多么多个字节,第二个number elements就是实际意义是为list派中元素个数,即N垂的个数,它一般呢是占用两个字节,第三一就是这么一个啊,第三一个就是ELEMENT1到element n每个具体的元素最后一个那么就是结束标志也还是那个0XF f255那么所以最终下来一张图给弟兄们说明白每一个list pack紧凑列表的结构分为。
21:23
整个total bits,第二个元素个数,第三个中间部分就是一个一个的list pack entry最终结尾标识。那么list pack entry又由什么构成呢?不放这呢,也就提前剧透,它主要也有三部分构成,分别是记录内容的类型和长度,然后呢,看实际的数据内容,最后是一个它们两个加起来的一个什么总长度也记这张图是不是要比你去看官网舒服多了?上面就是一般的list pack的总结构,就这条,那么对应着我们的笔记就这条,那么list pack里面要装一个一个的list pack ENT,那么每个entry又长什么样?那每个entry也就长这么个样,是不是告诉你including type元素的data和它们的total的长度,总长度就这么三个动作,OK,好,我们来,弟兄们接下来我们就会明白,那么the list介绍过了list pack新的开始,所以这个entry切记是新的东洞了。这个entry就是list pack每一个元素分别是什么?由三部分构成,分别是当前元素的编码类型。
22:43
元素的数据内容和编码类型,它们两个相加的两部分的长度,那么它在源码里面是在离派点H定义这来弟兄们请看三部分构成,这个里面叫list派N垂,OK和前面的压缩列表的那个N垂一回事,只不过存储的内容和结构发生了变化。好,那么最终下面弟兄们我们呢就来看一下这个list pack和the list相关的内存布局,给两种数据结构做一个对比。
我来说两句