00:00
好,同学们大家好,我们继续接下来接着给大家介绍red哈希数据结构的底层源码分析和案例演示。通过前面的介绍我们明白了red哈希结构分为RED7之前,RED7之后,随着它的底层的演变,分为了zip list,压缩列表变为了帕紧凑列表,所以我们本次案例为了给大家详细全面深入细致的讲解明白,我们必须要学两套,因为我不先和大家介绍z list是什么,它的优缺点,没有办法给大家讲清楚,为什么从z list被放弃了来到了派紧凑列表,哎,如果说从偷懒我可能会说啊,同学们现在呢,都是RED7这个版本,杨哥本次讲课就以七为主,六以前的不用学了,砍掉。但是呢,直接跟你讲这个你一定是懵逼的,所以呢,对不起,各位亲,只好是什么从严从难。基本功开始,万丈高楼平地起,一切承担靠地基,所以各位亲辛苦一下,不要嫌这些知识啰嗦,全面全部给我走下来,为什么从它到它了?好,首先六咱们先来学一下。
01:13
案例结构结论流程源码分析那杨哥你这个是原生的Linux上面按的REDX7,那六怎么办呢?再装一个,所以在这块呢,为了避免冲突,弟兄们你会想到什么?是不是RED68什么do OK,要不然我再骑一台机器太慢了,好吧,那么doer PS-N,我这个容器实力是6.0.8的镜像实力ID就这个,所以呢,Doer start启动我们的这个容器实力弟兄们没问题吧?那么大家请看。这个时候这边是六,这边是七,两边对比啊,一定要对比才能给大家讲清楚,那么do塔X1C-it干嘛?我是不是要进入到我这个容器实例里面,然后red-client一步到位,OK kiss心弟兄们没问题吧?所以说呢,这个时候这边是六,这边是原生的Linux机器上安装的真实的Rex实力REX7好了,咱们呢,就从六开始讲解,那么接下来仅仅把握着这个结论,RED6底层数据结构是由两种构成,压缩列表和哈希table。基于此,我们同学们请看config get,那么大家都清楚这个命令,这个config get的意思就是代表我们red con那个配置文件读取里面的TV建筑的配置啊,我们看到这儿同学们基于六这啊我们现在学的是哈希,那么具体是哪一个呢?我也不清楚啊,但是。
02:58
肯定是以哈希开头,同学们所以说哈希心以回车。这个时候兄弟们,我们就会看到一个东西,叫哈希最大的压缩列表的entry实体,512个最大的z list value的值是多少?64,听好,这是RE6的默认版本。
03:20
OK,好,讲完这个以后,不妨我们回到7CONIG get哈希心,注意啊,六的时候我们看哈希呢,只有一个z list z list默认值是512和64,至于说这个是什么东东,我们待会再聊,现在马上切换到七,我们还是执行同样的操作,同样的命令,一回车,同学们请看我们获得了什么?是不是除了z list以外,对于七而言还有list pack和list pack,一个是entr,一个是value,大家请看512 512 64 64值没有什么太大的变化,但是它的K是不是既有z list和又有list pack呀?那么下面我的问题是在七的话听谁的好?带着这么一个问题,弟兄们,我们来先回到六,那么接下来聚焦我们的目标,那么是不是就要给大家介绍?
04:20
Zip list压缩列表这种数据结构了,好,跟着来请大家看,这个基本上全部是抓图的啊,兄弟们我就不再废话了啊,待会儿我们来说,首先呢,这个z list是压缩列表保存哈希集合中的最大元素个数。啥意思啊,这个呢,是保存集合中元素的最大长度,听着杨哥你不是说它是有两个构成吗?哈希吗?那另外那个哈希table怎么没出来,它的原则是这样的。如果哈是类型的自动个数小于了这个啊。并且每个字段名和字段长度的值都小于这个,说白了就是在默认的512这个个数和长度大小六14以内,兄弟们,我们用什么,我们就用压缩列表来存储,该键也记啊,说人话就是假设你h set,比如说user,零五这个ID11C name假设叫张三这样很小很小的这么点东东。
05:25
对吧?它的个数就只有两个,ID和c name大小也不可能超过64的话,那么这个时候兄弟们它的默认值是多少?它的默认编码存储的方式什么?就是压缩列表,但是如果你超过了,请看前述条件任意一个不满足就会传转换成objectco HT哈希table的编码方式。哦,那杨哥我明白了,对于而言,哈希这种数据结构一底层对于六是压缩列表加哈希特表,如果说在512的个数和64的长度范围以内,那么它就用压缩列表来存储,如果这两个条件有任意一个被打破了,立刻变更为pass table讲完了,所以各位同学请看这个呢,是我们的默认配置,那么干脆啊,我们这个呢,RED7杨哥先把这个窗口关掉,我们现在呢,先从六开始来进行,我们对应的处理好,回到这儿看我们的案例。
06:26
前面所说默认是512个长度的值的话呢,是64,那么现在我故意把它缩小一点,三个字段长度是八,然后再来看给哈西三和八,OK,好,那接下来请大家看啊第一组H这个k name是张三,那么他的field。我们鉴定的上限是三,现在才几,它是一个,那么张三这个长度也没有超过八,所以这个时候我们object including兄弟们,它的编码类型是什么?Z please,好,第二个,我们现在呢,继续把这个name还是叫张三aaaaa字段值长度大于这个八了,对吧?那么编码格式将会由压缩列表切换为哈希table,所以这个时候同学们再来看此时我们是不是从z list切换为了has,再来看下面我们这个的多少个是三个,三个的时候同学们请看一眼是多少zip list,如果是。
07:30
Name age分数生热,大家请看是不是变成了四个字段,又变成什么哈希table,所以我们的结论就这么一句话,哈,是类型键的字段个数小于这个时候,并且每个字段名字段值的长度小于value的这个时候就会用z please,小范围,小尔美,用zip,如果超过了你的上限,最高的峰值立刻切换为has table。好,理论说完,那么同学们回到我们这RED6DO的这个版本啊,我们看这S首先。
08:09
来吧,我们的个数三,那么再来我们的value长度。现在呢,写个八,同学们看f get哈西大家请看默认的出厂的512和64是不是被我们改成了个数是三个,长度是八,好,那么为了避免误判,Delete user01好,删掉那么h set user01大家请看我们直接呢就是什么呢?ID11号这个没问题吧?好,那么接下来同学们请看看这个完了以后object,然后呢,USER01。答,此时我们现在的编码方式是多少?Zip list这一波没问题吧,好了,那假如说啊,我们再来。
09:10
二三四五六七八九十一十二够长了吧,直接过来超过了我们的这个八这个长度,弟兄们请看是不是变我们的哈希table了,OK,好,这个呢,是按照我们的长度这个值来进行了一种类型的转换和对应的匹配,那接下来set user02啊,ID12号c name,张三,然后age 22 OK,我们看这get哈西弟兄们都清楚几,是不是有三个IDC name age,好,我们来简单的看一下啊。同学们请看现在是什么,是不是还是z list好,那结果呢,我们现在还是这个动道,结果呢,我们来一个phone手机号,那么138OK,它的的字段值是不是达到了四个,我们再来看一下是不是马上从Z切换为了我们的哈希table啊,哎,跟我们的脑图笔记。
10:17
相关所讲的这个东道是一致的,一个是元素个数,一个是直的长度,OK,好,那么同学们我们得到结论,对于RE6,也就是七,以前这个版本哈希结构主要是z list,一个是个数长度,一个是它的直长度。结论默认哈希对象保存的间值对数数量是小于512个啊,当然啊,同学们你可以思考一下,如果你h set,比如说USER0,三这个T,你这个field的。干到500多个,那我个人认为也已经是个big k,这个就不是底层数据类型结构转换的问题,应该变成个大K的问题了,对吧?没有听说过哪个干到500多个的定义,所以这个呢,足够你用了,那么也就是说大部分情况下,它保证底层是z list,那么第二个所有的建制对的键和值的字符串长度都小于等于64个字节,OK,那么这个时候用z list,相反我们用has table,第二个小耳美用z list,如果超过了升级为哈table,这个从下往上升可以,但是反过来降级是不可以的,就说你已经升成哈table了,你别折腾,往下流的话留不下来。所以各位同学老爷一旦从压缩列表转换为哈希表,哈希类型就会一直用哈希表保存,而不会再转回回压缩列表啊,因为这种折腾翻箱倒柜的更加的。
11:50
影响程序的高效,所以在节省内存空间方面,哈希表就没有压缩列表高效,对吧?Z list1听说压缩肯定是节约空间嘛,但是以现在的语音,现在的内存,这个都不是个事儿,重要的是速度快,搞效OK,好,兄弟们,这个就是我们对应相关的案例。
12:10
接下来我们就需要把上面的案例结构和结论,一个小小的流程图的方式给大家做一个简单的总结和梳理。那么通过前面我们的讲解,我们也清楚无非就是这个字段有多少个,第二个它的值是否超过我们的上限对吧?N垂的数量,Value值的长度好,那么基于此大致如下,一开始对象变列,那么也就是说假设这个K啊,你有多少个F的个数上有没有超过这个实体要求数,然后这个Y6值的长度有没有超过我们规定的峰值啊,那么假如说啊,像这样遍历完了以后。现在我们这个value值。变相对立完了yes,发现它的编码格式就是z list啊,意思就是默认啊,就是最少和最小的时候默认第一步写使z list,也说value这边便利了,有点像这个RID实间我们就两位,对吧?便利了以后肯定不会超过这个八,那么接下来我们来看,那么这个条件达到们来看看这个哈希的长度,或者说它的个数有没有超过这个zip list entry,如果是超过了,那么对不起,Z list要转换成has table,那么也就是我们刚才实验所说的,假设ID从11变成这么多,那对不起,我一执行是不是会变成了好这一组分支,那假设啊,Value值很小,这个它的实体个数,这个z list ENT的个数没有超过我们的峰值,那么对不起,No,它是什么?就是z please,好,这是最大的两个分支啊,那么接下来如果。
13:52
对象变列,那是啥意思呢?也就说对不起这个field的个数。已经超过了ENT垂这个N垂这个个数已经很多,那么再看看这个对象字符串,这个value是不是也满足,那么如果是它这个分支走下来,那么z list也会转换成我们的哈,Table彻底结束,OK,一句话,也就是我们案例上。
14:18
把那张图稍微的总结一下,就是这么这句话我就不再重复啰嗦的读了。那么这顺便说一下这个流程图六跟七一样,唯一的区别就是把markx the interest和markx z value。这些字符上的长度和实体的个数,Field的个数从the list换成了list pack,仅此而已啊,后面我们就不画了。好,那么接下来我们来说一下这个源码分析,那么对应的我们大家都清楚,你在这写个set key field value field value field value对吧?那么对应的底层的C的源码是什么呢?首先咱们来明白,一开始这哥们一定是个z please啊,就是最小和最小的时候大部分都是它,因为默认值刚才我们看了,嗯,这个六的话是不是512个,其实64对吧?那么这个时候我们要清楚,但是如果超过这个风值啊,它会变成哈西,那么结合我们这h set,那么大家最熟悉的也是哈西,我们就从哈希入手,然后再来学习他的Z,请跟着我来首先。
15:31
在red当中,哈table就被称为字典dictionary,它是一个数组加链表啊,就是这个字典是数组加链表的这么一个结构,那么切记我们大家都清楚,如果说啊,我们最后OBG的话,超过那些上限和峰值了,它会变成哈table,那们来看一下这个编码分析,它呢是这样一个情况,最终兜底的是HT哈table这种编码方式才是真正的哈希表,或者称为字典结构OE的复杂度,那么在内部从哈希table类型到底层真正的散列表的数据结构是一层层嵌下去的,我们先把这个了解一下,首先我们在程序这边,我们就定义这个产量。
16:18
干嘛including htt啊,在这我一开始我这是不是写过一个东西叫including HT,就告诉你是哈table好,这是我们程序员层面上口语化的表达,这table,但是底层C这边他不懂,他只知道有一个东西叫dictionary字典,所以说在这啊,我们层层分析解套,宏观的就是我们程序员干活这个层面叫HT,编码底子对应下来叫字典,字典下面对应下来叫dictionary h table哈希table哈希表,哈希表下面一个一个的应该哈一个哈希表里面是不是有应该有一个个的哈希结构才叫dictionary entry哈希节点,OK,这个关系图很重要,这是从宏观到微观,这从微观到宏观,我把两个都给你罗列出来,这张表一定要搞懂。re,里面的哈希就是玩这张表,切记再啰嗦一遍,然。
17:19
哎,我们用哈希表design,对red底层资源而言就叫dictionary,那么dictionary里面按照你的KV建筑分类,我做成一个dictionary哈table HT,而每一个哈表里面,它会有一个真正正的哈希节点和N垂实体,所以在原代码d.H里面就定义了这套规矩。那么我呢,都给大家做好了抓图和笔记,我就不再翻源码,来回切换源代码在这dictionary.h2,那么来,同学们请看一眼首先啊。这是不是有我们的哈希节点,然后有哈希type?哎,能说杨哥dictionary,这没有dictionary type啊,别着急,请看这啊。
18:04
更进一步的,他在里面又做了一个细化,那么dictionary entry哈希条目,这是dictionary type,哎,你是什么类型的?搁到这儿,哈希表搁到这,大家请看是不是dictionary字典,所以具体落到实处,我们就是从HT到字典,到哈希HT,再到dictionary entry,这么层层嵌套,下面来有个字典类型和哈希表。TV好往上翻,那么dictionary哈希表就带着它的大小以及你的类型的指针。完了以后,Type是定义在这的一个结构体,最终我们对外暴露的是不是叫dictionary entry,它就是一个key和这一个value。OK,好,Dictionary,好,那么这个底层我们折腾明白,搞干净以后,那同学们我们在这儿啊,哈表呢,我们下面再说这个H命令,把这块内容放到下面,那么就记着每个建制,对,都会有一个dictionary en,这个就是哈希table和我们字典映射对应的这么一个最重要的结构,第一步先明白这第二个杨哥聊聊这个命令吧,H set来了,那么在这啊,几是六,所以打开我们的六两套源码都给大家呢,简单的解读一下,好,我们不用像Java里面啊,用idea里面de bug,一行一行逐行的C语言代码的解读,我们只要证明。
19:41
面试相关的red的哈希结构六这个版本是压缩列表加哈希table足以,那么来弟兄们找到我们的什么T哈希点C,那么来同学们这是不是有一这么一个动作,那么大家请看啊,在我们READY6这个版本下面五百三十五行这啊,大概我们一般在外面写的h set,实质而言底层就是调的h set command,这是我们的第一步,弟兄们没问题吧,所以各位亲,当我们在外面write client端写h set的时候,实质而言就是调的C元的h set command,那在这一块大家请看。
20:21
是不是任何一个都是一个right object,这个说过吧,好,各种判断和验证,如果这样的话就直接方法结束return,然后接下来哈,Type try conversion,是不是进行类型对应的编码判断和转换,意思就是说你到底是Z呢,还是h table还是table OK,好,那么接下来这个完活以后,同学们我们来看一眼这个啊,搞到这定义两个意符判断真真正正过来,这是哈西type,那么这个时候我们的编码就出来了。
21:01
查找一下,查找一下来,同学们请看,那么就是这段程序直接可以非常明确的给你肯定,那么检查这个对象的长度,去看看if we need to convert toa list,你看convert a z list toa real哈,这一段就决定了,默认小尔美就是在峰值以下的指z list,否则给我转换成哈希,那么弟兄们请看在这儿是不是会变成我们相关的,如果说啊大于这个,直接给我哈西Type Convert转换成objectco table,所以从z list转换成我们对应的哈希,那么得到我们的结论大家呢,都会清楚他们两个。就是哈希最终的一个根本的作用,好,这个先完成了我们的一半,哈希。我们用的set这个命令底层是怎么来进行这两个编码来进行映射、分析和转换的?OK,那么来在这块就是我们的转换和判断,那么接下来我们来唠唠,The please。
我来说两句