00:00
好,各位同学,接下来咱们案例验证来看一下我们的RED6、RED72代red对于list结构底层分别是什么?那么在开案例之前,记着杨哥总纲一句话,RED6和RED7它们底子既相同又不同,所谓的相同只有一种数据结构,就叫quick list,所谓的不同,RED6这个quick list里面装的是Z7里面这个quick list里面装的是list pack讲完了。如果粗分就一种结构,Quick克list,细分无非就是六装的是压缩的,细装的是紧凑的。讲解完毕,秒懂好兄弟们案例证明,大家请看can get list相关的得到了两个东东,这是几六好,我们会发现对应在六下的list结构还是和z list有关系,但是多了个东西叫comppress depress压缩深度,关键这个东西值是多少负二。
01:14
而这个是零,那么它们分别代表什么意思呢?我们从六开始一探究竟。下面请看这是六的案例说明。来第一个角list compress de pass压缩深度配置比,它的意思是表示在一个quickly list两端不被压缩的节点个数。这里的节点是指quick list双向链表的节点。那么什么叫quick list双向链表?首先明白个大概,List可以往left,可以往right两边加,一定是双向链表,也叫双端链表,而这个链表不是像Java里面的link list,而是新造了一种结构叫quick list。那么这个时候一定要明白这个节点代表的是quick list,而不是指list。
02:04
而不是指z list里面的数据项的个数,所以他们各个取值如下,第一个弟兄们请看默认值是几啊?在READY6里面是零特殊值表示都不压缩,这是ready默认值,建议大家用这个,OK,不用改,第二个,如果你是设置成了123,以此类推,如果是。一表示quick list两端各有一个节点不压缩,中间的节点压缩,如果是二表示两端各有两个节点不压缩,三有三个节点不压缩,以此类推,不再废话,用这个即可。那么第二个这个please size负二什么意思呢?那么同学们请看。这个是zip please里面的ENT,我们大家前面学过了,压缩列表里面其实值而言都是一个zip list ENT,一个实体啊,它负二的意思是当我们取正值的时候,表示按照数据项的个数来限定每个quick list的节点上的zip list的长度,比如配成五的时候,表示每个quick list的节点的zip list最多包含几个五个数据线,那么赋值的时候们表示按照占用字节数来限定每个quick list的节点上的z list的长度,这时它只能取负一到负五这五个值,每个值的含义如下来,负五,每个quick list节点上的z please的大小不能超过64KBOK,然后负四是这个,负三是这个,一句话负二就不要超过8KB,它好分配内存,好取值,就这么个简单。所以在这块你要清楚一个。
03:46
在六里面list结构是quick list,那么quick list里面说白了什么?装的是不是就是z list,听懂了吗?好,两个限定值,不用修改,OK,那么接下来我们会明白,在WRITE6版本前的list的只有一种编码list。
04:07
底噪就由quick list来存储,每个quick list是一个双向列表,那么每个列表的中间都是一个zip list节点。那么一句话说明白,一张图搞清楚,对于说LIST6DESIGN就叫quick list,每个quick list里面是不是要有一个quick list node,每个node里面放了一个zip list。讲完了了解这张图以后,接下来我们来说一下底层的细节和演变。在3.0之前,那杨哥你这儿不是到干到期了吗?对不起,从3.0开始,这个架构就已经固定了,3456都这样。都是采用replace压缩列表。加上我们的类似于Java link list的双端链表,因为它左边也可以进,右边也可以进,OK,但是呢,在高版本的专利子弹中,也就是从七开始啊,对不起。
05:04
我们呢,这个quick list发生点变化,上层都差不多。还是quick list,哎,还是叫quick list note,只不过下面装的被替换掉了,替换成什么啊,100%你也明白是不是叫list pack紧凑列表,所以说六到七都叫quick list,只不过里面装的从压缩列表变成了紧凑列表。OK,就这么点区别,好那么最后我们的结论,Quick list就是双向列表加压缩列表的组合啊,因为六是叫压缩列表,七是叫紧凑列表,OK,因为一个quick list就是一个列表,而链表中每一个元素又是一个压缩列表。好那么下面我们呢,来看一下较早的版本当中,List有两种底层实现。好。现在呢,当这个长度比较小的时候,它采用这个,当这个比较多的时候,它转向双端啊,这是什么较早版本你不用去了解了,但是呢,他们两者的优缺点需要了解。
06:16
这个紧凑效率高,缺点是更新效率低,数据量大的时候可能导致大量的内存复制,什么意思啊?我们前面说过,它的缺点是不是叫连锁更新,这货呢?Link list Java的同学都不陌生,它的优点是修改的效率高,但是额外的内存开销比较大,节点多的时候会产生大量的内存碎片。由于red呢,要兼顾内存的连连续性和紧凑性,尽量不要有太多内存碎片,所以结合两者的优点以后,3.2之后,List底层数据结构快速变为了quick list,这也就是为什么我们一再说red造它的思想是这样的,但是对外现在统一都叫list底子就叫quick克list,因为这两种都没有办法完完美的满足他,干脆新建了一种新的数据结构,就叫quick list,哎,它是这么来的,所以给同学们呢,说清楚这么点区别,好,那么这个就是我们RED6它。
07:16
怎么从双端链表压缩列表,最终结合两者的优点,整出来这个新的格式quick list,基于此,我们就会得到我们quick list。说白了就是。基于6.0的版本就是zip list和link list的结合体。下面一句话讲明白,Quick list是这两个混合,那么它将link list按段切分,每一段用zip list来存储,我们多个z list之间使用双向指针串起来。心造的这种数据结构怎么来的?说清楚了你就记着底层就叫quick list,双端head和T,每个quick list里面find的是一个quick list node,每个quick list note里面的又是个zip list,每个zip list里面前面讲过了吧,前三个和为中间是不是又叫zip list entry啊?这个就是我们quick list的来龙去脉。
我来说两句