00:00
那这这个七呢,咱们就说到这儿了,下边我们来看一看这个GD8当中哈希map它的一个源码的一个剖析了啊,然后这块我们这样操作啊,咱们呢,七清楚以后呢,咱直接呢,就说一下这个八和七的这个区别是什么就可以了,然后呢,我们直接呢,呃d bug看一下这个源码这个情况好,那么GD8和GD7的这个不同之处啊,这块呢,我们可以总结成啊如下的这样的四个点啊,哪四个点呢,首先的话呢,就涉及到我们造对象的这样个行为。那我们在G7当中呢,通过这样的一个操作呢,我们创建了一个哈map的一个对象,然后呢,在GT8的时候,我们说呢,创建这个对象之后呢,底层并没有初始化长度为16的这样的一个数组。啊,这个我们写一下。第一个点啊,就是在JDK8中。啊,这个当是吧。我们创建了。啊,这个哈希map实力以后啊。说底层并没有。哎,并没有我们叫初始化啊,咱们这个table这样的一个数组。
01:03
OK啊,这个呢跟我们这位七呢是不一样的,这位七呢,一上来就长度为16的数组就创建好了啊这个没有初始化啊,啊这是我们说的这个第一个点,然后第二点啊,那么这时候就涉及到这个什么时候去初始化的啊,这个我们就提了啊说这个当哎首次诶这个我们把它呢就写到这吧。在这吧,是吧。这个当首次。啊,我们添加这个KY60。啊,咱们添加比如这个k value是吧。哎,KY60啊,这个进行判断。啊,这个如果发现。啊,当前的我们这个table呢,尚未初始化。哎,然后则哎,对我们这个数组来进行这个初始化,然后这个点的话呢,就有点类似于咱们讲的这个release,在GD7和GD8中的这个区别是一样的啊,就是相当于呢,我们延迟的这个数组的一个初始化的操作了。
02:03
这呢是我们说的第一个点,然后第二点这里边儿呢,其实我们在讲第一个点的时候呢,我可以避开了这个数组的类型啊,咱们在这个七当中呢,明确了这个数组类型呢,就是N垂类型,这个N垂的话呢,咱们刚才这个讲的源码的时候呢,这不也提到了它呢是诶。刚才我们回到了这儿来啊呃,点开这个吧,在讲这个N垂的时候呢,我们提到了在哈希map的这个呃内部,它定义了一个叫N垂类型的一个类,注意哈,这个类呢,它实现了mapb当中的entry这个接口。相当于我们当前呢,创建叫NT类型的数组,这个NT呢,指的是这个N。嗯,OK,然后在我们这个GD8当中啊,这个ner变了。对,这个呢,我们叫node了,而我们这个接口里边呢,还叫ENT啊,所以这块我们也提一下啊,这第二点说呢,在GD8当中。哎,说呢,我们用于存储这个数据的这个table呢,是一个node类型的啊,而不是我们叫entry类型啊。哎,说哈希map。
03:00
啊,底层哎定义了。啊,叫note。啊,这样的一个,呃,内部类啊。它呢,去替换GTA其中的。哎,中的这个我们叫N啊这样的一个内部类。哎,那就意味着。哎,我们创建的这个数组。哎,是这个,诶note类型的这样的一个数组了,这呢是一个比较大的一个变化啊,然后至于说呢,我们这个内部哈,说原来呢你叫entry,现在呢,改成叫note了,里边这个代码是不是一样呢,都一样。啊,只是说呢,我们这个名字呢,变了一下,但变完以后呢,其实也不影响我们平时的这样叫法哈,像这些漆的时候呢,我们说里边你放的是N垂,现在的话你要node了,我说里边放的还是N垂。其实也没问题,只不过这时候我们再说呢,里边放的还是ntri,你可以理解成呢,是从接口的角度来看的,因为你noe呢,你也实现这个接口了,我说放的是NT也没毛病啊。好,回过来,这是我们说的这个第二点的一个不同,好,第三个点。
04:00
然后呢,我们在JT7当中的时候呢,如果我们当前这个啊KY呢,添加成功了,我们是把这个元素呢放在这个数组的,如果数组的位置没有元素,我们就放这了啊,如果这个位置要有元素的话呢,我们要求是让这个元素呢,它得下来新的元素,这个呢指向这个旧的元素。呃,是这样的场景,而我们在GD8当中呢,就变了,G8呢,就是旧的元素呢,假设在这儿,然后呢,新的的元素呢,是放在我们当前这个元素的,呃,下边。哎,这个呢,我们叫头插法的话呢,这个就叫做尾插法。OK啊,这是我们这个第三个点的区别。哎,说呢,在JDK8当中。啊说哎,如果。哎,当前的啊,我们这个叫KY6啊。哎,如果当前这个KY6呢,说经过啊一系列。哎,判断之后。诶,一系列判断之后啊说呢,可以添加到当前的。
05:01
这个哎数组中,哎,那么此时哎或叫数组角标A中是吧。哎,那么如果,哎,此时这个叫角标或者叫索引。I位置上呢,有元素。啊有元素啊说呢,这个在JDK7中呢。哎,是将哎这个新的这个k value这个元素指向旧的元素啊。指向啊,这个已有的啊,旧的。这个元素啊,而。这个在啊JDK8种。啊,是我们说那叫旧的元素。指向新的这个K元素。哎,指向新的,哎,这叫KY6这个元素。诶OK啊,这呢就有一个这样的区别,然后这个呢,七的时候呢是呃,新的指向旧的啊,然后这个呢,我们称为呢,叫做头查法。
06:08
哎,这是他。诶,然后呢,我们在这八当这个情况呢,我们称它叫尾插法。嗯,指向新的这个,我把它换一下行吧。行啊,这呢有这样的一个区别啊,然后这个呢,呃,大家也可以用另外一个词呢去记一下,比如呢,我们这儿呢是个数组,这呢是原来的这个元素了啊,现在这个新的元素过来之后呢,你呢都往下放,然后七的是要放在这里边的,指向你这个旧的,然后八的话呢,是诶如果这块有元素了,然后我们现在呢,这个旧的呢是新的呢是往下放,所以这块你可以呢用一个词叫七上。巴西是吧?哎,正好呢,跟中国这个词呢,还对应哈。诶七上八下,诶这样记就可以了啊,可能有同学会问说,诶为什么这块还做一个修改呢,是吧,其实这块要一谈的话呢,就比较多了,诶但是你会发现呢,我讲这个h map呢,在咱们的课件当中哈,最后呢,我这还留了一些拓展的问题,这些问题的话呢,诶我就不去呢刻意的去讲了,有些问题呢,我们在这个后边的这个企业的笔试面试题当中有啊有一些呢,可能就没有了,这个呢,要一说的话呢,其实还挺多的啊。
07:15
然后呢,涉及到有一个问题呢,叫做诶,我们在1.7当中呢,可能会产生这个叫循环列表,循环列表其实就是一个死循环的意思了。啊,就是这个呢,我就不深入的去讲了哈,就是这个指向这个,这个指向这个,然后我们在扩容以后的话呢,在多线程的场景下呢,可能会出现了这个就反过来指的情况了。这样的话你就构成一个死循环了,这你找下个元素呢,永远出不来了,这时一下子这个CPU呢就标的相当高,出问题了。啊,这样,这是在多线程场景下会出现这个呢,其中的一个原因呢,就是跟他用这个头插法呢是相关的,啊怎么办呢,那就改成这个尾插法。哎,这样的一个情况去处理OK啊。好,诶这个事儿的话呢,我写到最后一个点了,但是这块我没有特意的展开说太多哈。啊,这个呢,就咱们就过过掉了啊,有兴趣的话呢,大家也可以查查相关的资料啊就可以了。
08:04
好,因为毕竟我们讲基础阶段啊,我们相关的一些点呢,得适可而止啊,无限的展开的话呢,东西就太多了啊,这个事儿呢,我们先去理解。这个完了以后啊,接着我们再看这个第四个问题啊,第四个问题的话呢,也是我们比较重要的一个点说呢,JDK7当中,哎,如果明确的说的话呢,就是数组加链表啊。这个列表呢,是单向列表。啊,而明确呢,我们在这个GT8当中。哎,那就是数组。哎,这个。哎,数组呢,加上啊单向链表,然后再加上一个叫非常重要的叫红黑数的一个结构。OK啊,这个红位数的话呢,我们说也是一个BST是吧。它属于一个bit bitt呢就是二叉排序数或叫二叉搜索数啊,这样一个场景就是它呢,对应的里边的元素呢,呃,相互之间呢,是有这个大小之说的啊哎,这不是红黑数嘛,是吧,我这块我就简单的都画这个叫黑的了啊,这个节点这个节点这个节点这个节点这个节点是吧?依次呢往下这样去排。
09:05
哎,排的时候呢,它这块呢,是有这个大小之说的,比较小的都在左边,比较大都在右边,每一个呢都是如此。但它是有序的这样的特征,咱们前面要讲这个吹side map呢,也提到了,都是红黑数啊好,那现在的话呢,我们要看一看说什么时候使用这个红黑数是吧。哎,这我们说一下啊,说呢它呢,首先它针对的是某一支上啊这个元素来讲的,所以呢,我们刚才呢,看到这个map里边,我们放这个图的时候啊,你看它具体在这一只上改成是个宏位数了。那这我们说一下啊,这个什么时候。啊,会使用这个诶红A数啊这样是这样的啊,说如果数组索引I位置上的这个元素的个数哈,达到这个八了。啊,其实呢,就是你添加是第九个元素的时候哈,呃,然后并且。这其实还有一个条件。这个条件呢,经常我们会忽略啊,就是并且呢,这个数组的这个长度呢,啊,也达到这个64了。
10:06
这个时候说呢。我们会将此。哎,这个索引I位置上的元素。哎,位置上的这个多个元素是吧。啊,此索引I位置上的。哎,多个元素。呃,然后呢叫改为呃,使用红黑树的结构呢进行存储啊。OK啊,这呢,我们说的这两个特征好,那这时候大家可能会问说,诶,为什么我们此时要把这个位置改成红一数呢?啊,为啥要改呢?对方便我们去查找啊,对,你像我们这一只的话呢,超过八了,它的定义呢,就是超过八呢,就比较长了,比较长的时候呢,你看我们如果呢,你要去put操作,这时候我们得一个个去比,看跟现有的是不是一样。
11:02
假设要不一样的话呢,那不就得都得走一遍嘛,然后呢,你要是get的时候呢,找这个元素空格可以找Y6是不是也得找到这一只也得一个找是吧,瑞木的时候是不是也得一样。所以说我们这块呢,做这些相关的操作时候都得需要呢,如果找到这支上元素太多,就得一个一个的这样去走,它的复杂度呢是O。N的吧。诶都得走一遍啊,而我们这块呢,首先左边呢比你小,右边比你的大。然后这会儿我们在找的时候呢,其实哎,这个元素一过来,小还是大,是不是就选一只。然后呢,这个每次呢,是不是都撇一半。当然这块我们不是说严格非得撇一半哈,诶这个不像我们说的这叫AV这个数啊,左支跟右支呢,它的高度差就差一个,这个呢,高度差呢,它可能超过一个了,但是呢,整个的这个复杂度呢,也是叫logn的。啊,你要说AV2呢,是log根很好理解,每次砍一半嘛,但是这块呢,虽虽然说呢,它左右不一定说差别是层级差别不一定是一了,其实相当于就它的基础上呢,成了个系数之类的。啊,你从这个阶成阶的这个角度来讲呢,还是这个跟log根呢是等阶的,这个细节的话呢,有个推动的公式,这个我就不在这儿讲了啊好,最终的目的的话呢,就是我们如果呢,做这个put get或幕操作的时候呢,它的复杂度会更低一些,所以呢,使得我们查询啊操作这个效率呢会更高一些。
12:15
啊,回过来。啊,在这呢,稍微说一下啊,这个叫为什么呃,修改呢,就是红黑树。是吧,我们呢,就进行这个诶put操作,或者你进行这个盖操作,或者这个操作是吧。哎,这样简单说一下啊。进行这个操作。哎,这个哎操作的这个哎时间复杂度为啊这个是O。这个小括号啊,还有这个log n的啊。这个log n呢,是以二为底的啊,是log n的,然后呢,比哎咱们这个叫单向链表的啊,这个时间复杂度。啊,这个O呢是烙N的啊ion的啊,它的这个呢要好是吧,哎,就意味着我们这个性能会更高啊。
13:07
好,这个呢我们就说清楚了,这个呢,就是什么时候会使用这个红位数,那其实这块呢,还多一个操作啊,就是这个呢,如果我们是叫生成红位数的话呢,下边这个呢,操作叫退化红霉素,就是如果我们这一支上呢,现在使用的是个红霉素,那我们可能会remove啊。人物就删呗,是吧,删删删删删,假如我删的元素呢,就在这个红霉素这一之上,删到一定程度的时候呢,它就又退化成是一个单向列表了。啊,这个我们也稍微提一下啊,就什么时候会啊,使用宏位数就意味着是单向列表转化为宏位数啊,这个我可以在单向链表变为啊红黑数啊这样的特点啊。往后再提一下。哎,这么着啊,然后下边呢,再哎反过来啊,说什么时候呢,是会把这个宏位数呢,再变为单向列表。诶,这呢,其实也会涉及到一个点。
14:01
什么点呢?哎,有同学说呢,诶这个宏位数不是挺好吗?那干脆你一上来直接数组加宏位数不得了吗?那干嘛,这块还要用一下单氧列表。对吧,你不是说红一树好吗?直接就输入加公因数五得了。嗯。哎,对,就是不是挺好吗?刚才我们说的这不都是好处嘛,是吧,对就是这是一个问题,包括呢跟这个呢,其实是一个问题啊,就是说我们用红叶树,这不都用着都好好的,你干嘛还退化呢,你化不得额外还得再做操作嘛,是吧。诶,这里边儿对,这里边儿你看这个点是啥呢?这个首先咱们先说清楚这个什么时候会退化吧,刚才提到说这个个数达到八了是吧,达到八以后呢,这个时候就变成宏位数了,那我们呢,就有可能呢,会对当前这一索引I位上元素呢不断的去删嘛,哎,那我们说呢,当。来使用啊,这个红黑数的这个索引I位置上的这个元素的这个个数是吧。
15:00
哎,个数啊,上面要达到这个我们叫低于六的时候啊,然后就会呢,将这个红黑数是吧。结构呢,叫退化为。哎,这个呢,叫单向链表了。哎,这个大家能。想象出来他为啥这样做,不。其实好像不太好说是吧。嗯。这个我就直接来解释了啊,这个呢,原因是啥呢,直接我们看一下它这个GT8的这个源码了啊。这个GD8源码这块我们还得稍微再调一下,针对我们当前这个module这个位置,我们改成是这个八啊,因为你看七呢,肯定看不到了,因为它也没混回数嘛,那这块也改一下也行啊,比如改成这八的了啊好回过来这是我们在CTRLN一下,咱们就直接再搜这个叫哈奇map了,然后看下这个八的源码。没在这儿。在这儿找?嗯,我看的是这一段吧,看这吧。在这呢,啊说呢because什么说这个吹not,就我们说的这个红位数里边这样一个元素了哈,说呢它大概呢是两倍的size,就是针对于我们普通的这个单链表里边这个node来讲啊,它呢占它的两倍的空间的大小。
16:12
所以呢,我们这时候呢,在必要的情况下呢,还要给他转回来,包括呢,我们为什么一开始就没有用红位数呢,你要都用红位数呢,这个占用的空间还是偏大一些。哎,从这个角度来考虑的啊,好这个呢,就我们说的这个GD8和GD7里边不同的这样的四个点,好这几个点说完之后,下边呢,咱们要看一下这个源码的一个执行情况了,咱们在这个map里边,我就直接右键了啊,新建一个class,诶我们称这叫map的。哎,它的一个test。首先呢,来一个哎,单人测试方法第一个啊。好,这我们就直接呢叫哈希map,这呢,比如叫string类型的。啊,这个呢叫类型。哎,这么着啊,然后map new一个,哎哈希map,哎这就可以了啊好map点。诶,我们去put一个元素啊,这个呢,假设就是AA啊,来个123行这就可以了,好,那么下边的话,我们来看一下它的一个底层源码的执行情况,这块的话呢,我就不像这个一点七一样,咱们跑一遍了,因为大家有这个七座底之后呢,我们再看八,哎要更舒服一点,主要呢,关注一下这个区别就可以了。
17:16
好,那这块呢,我们直接呢,就进行这个debug的一个操作了。啊,因为呢,我刚才啊,注意我在这个位置呢,已经改了咱们是这个八的了,所以我们现在看这源码呢,其实就是八里边的OK啊好,那首先呢,我们就进入到这个源码当中。啊,首先呢,它会加载咱们当前这个h map这个类哈,这里有个class loader这个咱们就跳出就行了,然后你再进去。啊,这块还是,诶这块就进来了啊好,这呢是我们1.8当中的这个哈信map,这呢是它的这个。轨道器啊,轨道器里边呢,我们看到它不会像七当中把这个table呢,做了一个初始化,它呢只是针对我们这个load featureer这样的一个属性啊,做了一个赋值,说白了就0.75呢给附上了。诶,比如我们往下呢,执行一行,再执行一行,诶当前你再看这个Z,比如我们当前哈ma的实例的时候呢,打开里边呢,针对这个load factor啊变成0.75了,其他的呢,都还是默认值。
18:06
好,那我们再往后执行,诶,那么这个构造器呢,就调完了,底层呢,就做了一个事儿,就是把我们里边那个0.75呢给附上了,好接下来的话呢,我们再调用那个叫put的方法,Put方法的话呢,我们进入源码去看一下啊,点进来。啊,因为呢,我们刚才那个Y6呢,是一个123,它有一个装箱的一个过程,对这个装箱呢,你看也调了一下啊,咱们回过来,然后我再去进入这个源码,这个呢,就是我们铺的方法。这普袜进来之后呢,大家会看啊,这是k value6,我们要添加这两个元素,它呢,诶直接呢,就把这个K呢,放到我们这个哈希的这个里边了,这个呢,就是我们在JT8当中的这个,咱们讲叫哈希值一变成哈希值二的这个哈希方法,哎,我们点下这源码,这就是这个哈希方法,这个方法呢,你会发现呢,比我们这个。刚才点过去了啊,比我们这个七里边那个是不是较简洁很多呀,七里边儿一顿猛操作是吧,哎,八里边呢,相对比较简洁,这呢叫哈一。
19:01
然后呢,做完以后的话呢,他再给他做一个U16位,然后求一个一或的运算了。啊,因为整个呢,我们是硬的形的一个值嘛,诶所以呢,整个它这个长度呢,是32位,32位的话呢,相当于中间截一半,把这一半呢再折叠过来,然后这样做一个一户的运算了。啊,就是跟小时候这个那家里边这个老人和面一样是吧,你把这个面呢,就是撑开之后呢,整个呢,就是北方人吃面条嘛,啊整个把这一边再折过去,然后再揉啊蒸馒头啥的是吧。诶,就这样一个思路哈,好这个呢,我们再点一下这个操作啊,这就回到我们当前这个第8UG的位置了,好这个哈希看完之后,然后这个呢,把你当前这个二次哈希值T6,后边还有相关这个属性啊,在某些判断的时候呢,它会用到这个啊,暂且我们先不管它,然后呢叫put v,我们点一下源码,这不就put v了。好,首先一过来之后呢,注意咱们此时的这个table啊,是不是还是个no啊。所以呢,把这个table呢,你给他这个tab,给他tab呢,Tab你看一下是不是no,那显然是no,这其实就个true,这个true的话呢,我们就进入到你这个衣服里边了。
20:04
这里边的话呢,它会调一个叫这两个方法,把这方法呢,再付给这个tab是我们现在关心的点,也就是在这个方法当中,咱们呢,因为是首次KY6的添加,所以呢在里边把这个数组给创建了,好呢,我们进入到源码里边看一下。啊,进来了啊,这块里边这个变量呢比较多,后续呢,我们如果要扩容的时候呢,用的也是这个方法,所以这里边逻辑呢,不光是最初的初始化,还包括后期的扩容啊好,这个reet进来之后呢,先把你现有的table呢,付给一个叫old tab啊,这都是no呗,然后tab是不是no,是no的话呢,给个零给他啊,这也是零,所以这块你看相应的这个值呢,我们都能看得见啊,然后TH后呢,这块呢叫临界值也没负过呢,所以呢,这块也给了个它,那这这大家都是这个零啊默认值啊这个情况好,首先呢,这个o type是不是大于0o type。零吧,所以这个衣服呢,没进去。又没进去呢,其实就直接蹦到。放到这块是吧,这块的话呢,其实也没进去,其实就碰到else这吧。
21:04
哎,是就跑这了啊,跑这以后的话呢,这块一个叫new cap,这个呢就是default initial capacity,这个呢就是16出现了,把16呢付给,哎,这里边一个叫new cap是16。好,然后这个位置呢,哎,这是加的因子0.75乘以这个16,这个呢叫new surprise后其实是吧,哎这个呢,值呢,12呢就也出现了。好出现了,好,首先判断你这个new这个是不是零,不是零不是零,就直接就走到这呗。就到这了啊好把你当前那个值给了threathol,哎,那么我这一行代码你看,如果你看这个this的话呢,这个hol这不还是零吗?这行代码一走,这不就变成12了。哎,就附上了,好附上以后,接下来大家看此时的话呢,我们不叫N垂类型的数组了,而是叫node类型数组。啊,这个node呢,就是我们说的底层这个替换的这个行为啊好,然后我这块new一个node,这个node呢,用的是new cap来进行赋值,New cap是不是16了。
22:01
诶,所以这个你看16的长度,这个node数组就创建好了,然后呢,你再把这个地址。哎,New tab这个地址给了我这个table。Table呢,首先这个new ta不就是这个数组,你看这个它的地址呢,是875啊,然后给了我们的table table不是你当前这个对象里边的这个table吗。这张代码我们一执行,你也就是875了。哎,所以这个数组呢,我们就给它创建了啊,然后下边问这个old ta是不是个no啊,把这个收起来,Oldb是一个no,所以这个if呢,没进去啊,一大段这块呢,就都不用管了,直接呢,我们往下一走是不就到这了。好,那么在刚才这个re这个方法的过程当中,主要的大家要看的就是这个数组呢被创建了。诶,我们再往回走一下,这不就到这儿了啊,那么他还把你当前的这个呃数组呢给返回给这个tab了,这个tab呢,其实就是咱们这个table。那你看我们这块往下再,哎,这个你收起来。这个吧,然后这个时候呢,它这个tab目前还是no呢,我们现在再一点,这不就给他负了值了,负值875不就是我们这里边这个数组吗。
23:07
哎,就过来了啊,好在这个数有了以后,然后他会判断一下,你看咱们前面呢,在这个期有一个叫index啊,在这儿的话呢,直接人家就写这了啊。诶,拿你当前的这个二次哈基,这个哈基值跟我这个N减一呢,做一个与的运算啊,直接呢,结果呢,不就零到15范围内的嘛,看一下你当前这个数组这个位置啊,有没有元素,先把这个元素取出来给了P,先看下P呢是不是no。P要是no,说明你这个位置就没有元素。是吧,诶我们这是第一次添加,显然是没有的啊,所以呢,我们就直接进去了,进去以后的话呢,不就是把我们当前这个哈基值2KY6啊这个NEX元素呢,因为你新添加的也没元素,下一个就是no哈,诶新有一个node,然后放到我们这个数组里边了。这个肉的呢,我们也搂一眼。啊,在这里边呢,实际上就用了一个node,这个node呢,就是我们相当于的这几个值,Node呢,我们再也看一眼,这不就是我们说的1.7呢,用的是叫entry 1.8呢,用的叫node,还是实现了这个map.entry接口里边这个东西呢,基本上都没变。
24:08
啊,基本上都没变啊,然后这块还是叫这个next的一个行为啊,这呢就做了一个初始化啊,这个我们再直接跳出去,哎,这不就new好了吗?New好以后的话呢,我们这时候呢在呃。执行一下是不是回到这儿了,相当于我们把这个元素呢,就放到了我们这个table I的这样一个位置了。啊,这个位置的话呢,我们,呃,这是if进去的,Else就不进去了,我得再往下。执行一步,他才给它赋值呢,是吧,诶你看目前我们这个里边这个table你看。全是闹吧?OK啊好,然后我再往下走一步,可以走到这儿了啊,这个时候你发现呢,我们A呢,恰好呢,它是放在这儿了。那这不就在这儿了啊,那这个变量不用管啊,但下边这个呢,说你这个加加size,哎,我现在这个S呢是零嘛啊,因为添加了个元素变成一了,说你是不是大于这个临界值,如果要大于的话呢,需要rees,这就扩容的问题了,咱们第一次呢,就不需要考虑扩容的这个事儿,所以整个这边就呃结束了。
25:03
诶回过来再走,是不是就执行到这儿就结束了。诶,刚才我们这个map里边,咱们再抬table这个位置的角标零的位置,把这个元素呢,就给它添加上了。好,这个呢,就是我们首次添加的时候呢,大家也看到底层呢,会进行数组的一个。啊创建是吧,好,那这块呢,我们要想看一看它这个呃,扩容的场景,包括呢,这个它变成一个树的一个场景,这块我们得添加好多的元素了,就不太好看了是吧,所以这块我就先就诶停下来了,咱们就下一步啊,直接咱们自己点进去呢看一下。是不是还是过来的啊,点那个葡萄V好这块呢,稍微有点绕了。哎,如果刚才呢,大家认为说这个事儿还行,那下边我们来看这个else的行为。刚才的话呢,我们只是分析了一下,对应的这个位置上呢,恰好没有元素。我们就直接添加了。那也有可能这个位置上是不是就有元素啊。有元素的话,那就不是no,不是no就进入F了。啊,那么此时的话呢,我们脑海当中啊,应该有这样的一个图。
26:04
啊,我们再去理解这个事儿呢,会更容易一些啊。好,放到这儿了。哎,现在注意啊,我们现在呢,对应的这个位置呢,有元素啊,你可能是这里边的任何一个叭,如这个绿色的这个场景有元素的话呢,哎,咱们走一下,这个脑袋要清醒。一步轻轻的就绕进去了啊嗯,首先呢,看一下你当前取出来的这个数组,这个位置上这个元素啊,它的哈希值跟我现在要添加的这个元素的哈希值呢,咱俩是不是一样的。咱们此时呢,先说这个事儿吧,咱们一个个来啊,先说一下呢,假设呢,咱们就以这一支为例,现在我找的这个位置上的元素呢,不是闹是吧,不是闹的,我们现在要比较一下,说你的跟我的哈希值,假设呢,咱们现在呢,就说一下这个添加二的这种成功的情况啊,就意味着我们这里边假设有多个,每一个哈希值都不一样。啊,这样的场景啊,好,那么首先呢,把你这个元素的含义值呢,取出来,跟我当前这个元素的要添加的含义值比一下,如果不一样。
27:02
不一样的,这个衣服就没进去。这个不用管,哎,当前的话,他也不是一个宏位数的一个结构,不是这样的啊,就是一个普通这样的,所以这个也没进去,数据走到这儿了。走到这儿的话呢,大家能想到我们下一步要干什么吗?是不是就接着往后比啊,所以这块呢,你看它有个for循环,哎,这个不断的去加加,接着取你这个P的next。这个P呢,给了EE,看你是不是no。就是如果要闹,说明就是到头了哈。哎,那到头了,如果要是呢,那接着是不是就你看P的next呢,去新旧一个,这不就我们说的叫尾插法吗。对,就是你旧的指向这个新的嘛,啊,那如果说你这个E呢,当前我们取过来之后呢,还不是个闹,假设呢,是第二个元素,不是闹的话呢,那就走到这儿了。看一下你这个E的哈义值跟我们当前的含义值一样不一样。如果还不一样,还不一样的话呢,这个就没进去。没进去呢,把这个E呢,再付给一个P,相当于我现在这个元素呢就叫P了。
28:00
然后呢,你这个else相当于执行完了。不对,不是不是小森,是这个执行完了以后呢,是这个操作完了,是不是又走到这儿了。然后这块呢,因为我把这个E呢,给它P掉,现在它是P哈,我再取这个P的next当做E,相当于呢,它的next就它了,它是E。对,它是E的话呢,再看一下它是不是no。哎,如果是nu说明到头了嘛,那就添加,如果不是nu呢,说明还有,然后再看看你这个元素的这个含蓄值,跟你现在要添加这个呢,是不是一样,如果不一样,不一样是不是接着再去找下一个。再找下一个呢,这块再看一下是不是no,还不是no,还不是no,再接着呢,看看你含义值是不是一样,如果还不一样,还不一样的话呢,这块再把这个E给这P,它是P了,他在next时候呢。是不是已经是闹了?哎,已经是闹了,已经闹了,那这块呢,那就添加一下呗。哎,这时候就把我们这个最后这个元素呢,现在就指向了一个你马上要添加的这个新的这个元素,这不就放这儿了吗。啊,放这儿啊好,那么放这儿以后。
29:02
放这以后他这块有个判断啊,其实我们在刚才这个不断的操作过程当中,这个有一个叫冰抗的这样一个变量啊,它不断的去加加。加加加加是吧,这个大家可以走一下这个细节啊,实际上你会发现呢,这个值这呢出现一个叫three hold,这不就八吗,八减一,这是七,这要大于等于这个操作啊,有同学说诶这块就大于等于七,其实这块呢,你看我们上面已经取了一些值了啊,包括一进来的时候这是零,然后呢,我们这块都已经比过了第二个元素了。然后呢,你回来才变成那个加一。所以这块你注意不是一上来说取缔一个元素,这个是一它不是的啊,它这块其实已经比了好几次,它才出现加加行为,所以实际情况呢,就是当我们超过,就是你添加这个元素是不是next已经添加过来了嘛,其实已经变成九了啊,九个元素的时候呢,我们就要是数形化一下。哎,舒心化呢,就是这里边儿这个具体操作。啊,就是具体操作行,呃,这个数形化呢,咱们等一会儿再说哈,刚才呢,我们说的场景是啥呢?是你这里边儿这个,哎,在比的时候这个哈一指你看都是叫什么不一样的这个情况啊,其实呢,实际情况就是哈,移值可能一样了,是不是有可能后边这个ECO次数不一样的。
30:11
总之的话呢,就是if呢都没满足,就是我们其实呢,说下一个下一个它的场景,包括呢还一直不一样,也包括呢还一直一样了,但是E次数不一样的情况。没问题是吧。这个OK吧。OK啊好,那是不是也有可能我们这个,呃,在比的过程当中一样了呀。那要一样的时候怎么办呢?如果你在这块出现时候一样的,是不是这块有个break呀。呢,叫做结束当前的循环是吧。理解吧,好,那他要结束当前循环的话,然后他这块呢,是不是就else就相当于执行完了。A,完的话呢,是不是就走到这儿了。哎,那我现在来判断当前这个元素,比如说就它吧,它跟我们现在要添加的这个元素呢,咱俩比的时候呢,说咱俩这个一样是吧,咱俩一样的话呢,现在你是E啊怎么办呢。
31:02
我把你的这个Y6值取出来。是吧,刚才我们看造这个呃,New哈奇map的时候,是不是有这样的变量啊。哎,那个值呢是个false,然后非呢,是不是就是个处。哎,那个默认情况下是吧,真的就是个出了,这要是true的话呢,哎,把我新的当前这个VALUE6呢,是不是切换到你原有的这个Y6的位置上,然把你这个O的呢给返回一下。这不就我们说的是一个奇幻行为吗?就是当咱俩呢,哈希值一样,E也一样,这时候呢,我新的Y6替换旧的Y6,返回旧的Y6,这就修改行为。啊,这不就看到了是吧。没问题啊行,然后这个位置的话呢,就是我们说的这个舒形化的这个行为了,哎,这块呢,出现了我们这个八,哎,当你要达到这个八了,现在我们要舒心化,在这个舒心化里边呢,它其实呢,也不一定马上进来就属形化,诶它还得加一个判断哈,首先呢,你当前这个tab也如我们这个table的一个长度,长度呢,我们假设就16了啊。哎,这个,哎,如果你刚开始是十六十六的话呢,是不是小于这还有一个值,这个呢,叫min吹fair的一个capacity,这个你往这一放,它是64。
32:05
啊,他其实想法是什么呢?呃,你现在这一只呢,已经达到八了。达到八的话呢,那其实呢,你现在要添加这个就算第九个了啊,你添加完以后呢,现在是有九个了,说是不是要数形化呢,人家看一看,说你这个数字现在多长啊,你说我是16。只有那不好意思,那你现在呢,先去扩容去。杨IG呢,就我认为呢,你现在这个达到一个都往这放的原因呢,是你这个速度长度呢,差点意思是吧,所以呢,就是能不舒心化呢,就先避开它,诶你呢是16嘛,那你先换成32 32的话呢,如果出现同样问题。你不是小于64吗?哎,那你再去。扩容是吧。诶就是你先呢考虑扩容啊,就是这个reset这个行为了啊,那如果说我们现在已经是这个64了,这时候呢,我们说你这个速度呢,已经算挺长了是吧,在挺常情况下呢,你发现大家都还往这一直上去放,那没办法了,那干脆咱们就抒形化一下吧。所以这个数化的有两个条件,一个呢就是达到八了,另外一个呢,就是它得超过64了是吧。
33:03
啊才可以啊,否则的话呢,我们还是做一个普通的扩容行为。啊,这个大家注意一下啊,然后呢,真正达到这个要变成数形化的时候呢,我们就开始用这个吹no呢,去整合咱们当前这一之上的这些元素,这个信息的话呢,诶,咱就不过多的去看了,有兴趣的同学呢,下边你可以去挖掘一下。啊,咱们就适可而止了啊就行啊好,那其实在这个不断的木的过程当中,大家你可以看蕊remove方法刚才减到这个六级以下的时候呢,它会有一个不断的缩减的这样一个过程。啊,有的人可能说诶12345678,诶这块怎么是个数呢?诶它其实在这个过程当中,你也可以理解成它,它缩减过是吧,只要呢,这个之上的话呢,它不能是低于六个的,低于六个的话呢,肯定就不能这样写了,它就一定又还原成是一个呃单向列表的一个结构了啊好,那这样的话呢,咱们就把这个八当中这个源码呢,也带着大家呢,就走了一下。啊,大家呢,就是自己捋一捋下来呢,也可以自己呢去走一下啊,然后在整个这个过程当中呢,它有一些相关的属性或者叫字段了啊这个咱们在讲七的时候呢,其实也提到过了这块,我就直接呢从我们课件里边把它拿过来,诶大家呢,整体上啊要去理解一下,因为有的时候在这个笔试当中啊,他可能会问啊说呢,我们这hand map里边都有哪些常见的字段啊,能说一说吗?
34:14
啊,有这样的一些啊,首先呢,就是我们这个初始化容量。哎,这有个它,然后呢,最大的一个容量。啊,这个呢,就是正常我们数组的一个最大容量了,然后呢,默认加载因子,然后呢,数形化的这个八,还有这个哎,相当于反数化啊,这有个六啊。然后这个位置还有我们刚才提到这个64哈,达到这个64呢,我们才会去做这个诶扩容哎,才会去做这个书画这个操作。哎,就我上边这块。在这写的是吧,这个64指的就是这个啊好,然后呢,整个我们这个数组呢,叫node类型的一个数组,然后里边存了几个这呢临界值,这个呢就是加载因子,哎,都是拿上面这个呢,可以做一个默认的赋值,OK啊行,这个呢我们就说完了。
我来说两句