00:00
OK,咱们接着来讲这个第14章啊,主要呢,我们说两个事儿,第一个呢,就是数据结构啊,这呢我们剖析一下常见的数据结构的核心的这个代码,然后第二的话呢,我们来讲讲集合里边这个源码,源码这块呢,我们主要集中在两个接口下边,一个呢就是绿色接口,一个呢是map接口,这个我们已经说过了啊,因为这两个接口呢比较有代表性,然后呢,关于这个例子接口呢,咱们昨天的话呢,已经都讲完了。哎,这块有相应的一个结论启示是吧,诶这块呢,大家再熟悉熟悉啊,下来的话呢,自己呢,可以呢debug跑一跑啊,就是这块你要单独的去记这些内容的话呢,当然也行是吧,但多少呢,你自己看一看这源码呢,自己会更有感觉一些啊。好,那这块我们来看一看这个叫map的一个源码的剖析了啊,整个回过来我们看这里边的几个点,第一个呢,提到了说哈希map中元素的一个特点,那这块呢,其实我们在前面讲这个第12章的时候呢,已经说过这个事儿了,所以我这儿呢,就直接呢把它粘过来了啊这个特点的话呢,主要就是针对于咱们说的这个key value key value是吧?哎,它相关的比如说哎所有的key构成的是一个set。
01:04
啊,然后呢,所有的value,那我们说构成这个叫collection。然后呢,KPI呢,封装在一起,其实我们说map里边放的是键值,对键和值是作为一个N垂的对象的两个属性出现的,所以呢,我们也可以说呢,Map里边其实放的就是entry。其实也算是一个一个的元素,OK,好,那么NG的话呢,彼此之间呢,也是一种不可重复的无序的状态,所以呢,也是一个set集合。OK啊,这块呢,我们首先呢清楚这个事儿,这个完了以后。诶,下边我们来看看这个哈希map的一个源码分析啊,这个源码分析的话呢,咱们同样的呢,以不同的版本呢来进行一个说明,咱们这块讲的话呢,我先来讲JK7当中的源码,讲完这个之后的话呢,我们再来说一下这八,相当于从这个历史演变的过程来看,我们看看它都变了什么。通过这个变化的话呢,大家也去理解它,为什么要有这样的一个变化,其实呢,我们是能够理解的啊这个。
02:01
相关的这个企业真题当中呢,呃,有几个公司问这个问题了啊,就相当于呢,诶七跟八有什么不同,这是第一个问题是吧?呃,第二个问题的话,为什么会有这些不同,所以呢,我们通过时间线的这个顺序呢,理解呢会更好一些啊。当然了,如果大家呢,在这个笔试面试当中问到了哈希map的源码,而且这个频率呢,是极高的一道问题啊呃,问到这源码的时候呢,建议大家你说的时候呢,你就直接上来就说八就行,因为毕竟呢现在八呢是开发的,也算是一个主流,那说完现在十一十七不是陆续的也会是这个主要的版本嘛,是吧,尤其我们说这个JDK17呢,现在已经被啊像这个以Java为基础语言的相关的框架呢做了支持了,而且呢明确要支持说呢要倒成啊GDK10期为一个叫贝斯烂啊基础的一个基准线了啊,那GDK时期的市场份额呢,一定会上来,那目前我们看到呢,就GDK时期当中啊,真跟这个GDK8当中啊,其实没有实质性的变化了。所以呢,七跟八呢,其实相当于是个分水岭,OK,大家在这个呃,笔试面试当中的时候呢,其实你上来呢,就直接说这个八以后的这个版本就可以了,顺带呢,你可以补一补说七呢是什么样子的,所以这个立足点呢,要考虑清楚啊。
03:14
好,那这块的话呢,我们来看看在这个JDK7当中哈,Map呢,它的创建对象和添加数据的一个过程是什么样子的,其实这块呢,主要呢,我们就说两行代码就可以了,第一个啊,就是我们这个哈奇map,比如这块呢,我们给它这个键值呢,也指明它这个具体的泛型的类型啊,这个键的话呢,假设我们叫string,类型值的话呢,我们叫类型,那这儿我们来个map,实际呢去new一个。诶叫哈希map行这个代码的话呢,大家都比较清楚了啊,那么我们首先创建对象的时候,需要关注一下,说底层都干什么了啊,然后另外的话呢,我们通过这个map对象呢,去调一个铺的方法,比如说这个呢叫AA,诶传一个值呢,比如说叫A78,好我们看一看这个铺的操作呢,他都做了什么。
04:00
其实主要呢,就是做这个事儿OK啊。好,那么首先的话呢,我们说第一个这样的一个操作啊,这一块的话呢,我们相当于new了一个哈希map哈,Map呢咱们前面也都提到过了,它底层呢,哎,在上面写的哈,它使用的叫数组加单向链表加红黑数这样的一个结构,当然这个呢,结构说的时候呢,我们要明确出来是在GD8当中的七呢,就不是这样子了,七呢,没有这个红黑数啊,现在咱们讲的就是七嘛。哎,首先的话,我们提到这有一个数组的概念了,前面我们讲a release的时候。啊,底层用的也是数组,在这个七当中呢,哎,我们讲这个尔类斯。哎,往上翻一翻啊,哎,在这个漆当中呢,只要呢,你造对象了,底层这个数组呢就造好了。哎,那我们这个哈希map呢,也是同样的思路,因为他们都是1.7的啊,所以这个时候呢,当我们造好对象以后呢,底层这个数组呢,就也创建好了。啊是这样个场景啊,所以这块呢,我们说哎,创建完对象以后。啊,对,或者叫创建对象的过程中啊。
05:04
过程中。哎,我说呢,底层会啊,这个相当于初始化。哎,数组,这个数组的话呢,注意它是一个叫entry类型的,哎,这样一个数组,这个数组呢,叫做table。啊,这个table的话呢,相当于他就实打实的去扭了一个啊N垂类型的这样一个数组,这个数组这个长度呢是多少呢,是16。OK啊,相当于呢,在我们造完这个对象的时候呢,底层这个数组就已经创建好了。啊,初始化速度整个呢就长这样子,哎,大家呢,稍微关注一下这个名字叫table了啊,然后这个长度呢是16,这个16的话呢,是二的指定次幂是吧。40米是吧,诶就是16啊,这里边儿呢,其实有一个小的一个细节啊,就是包括呢,我们后期的话呢,还会出现这种扩容的情况啊,然后不管说你一开始的初始化的这个容量也好,还是说呢,后期扩容也好,我们会发现一个点,就是它底层对应的这个table的这个长度啊。
06:02
啊,它这个长度呢,永远都是二的整数次幂。啊,这个注意一下啊好,为什么这样呢,这个我们看源码的时候呢,可以找一下这个原因啊好,那这块的话呢,我们首先呢,就把这个数组呢,就创建出来了。啊,这个没问题了,那下一步的话呢,我们就要往里边去添加元素了,所以通过这儿呢,大家也能看到咱们说的key和value呢,封装在一起构成个entry,其实呢,就是作为N的两个属性出现的,我们呢,Put一个key put一个value,哎,首先呢,这块就提到了咱们这个所谓的这个key和value。啊,先明确这样一点啊,也就我们这里边AA和这个78,七八的话呢,其实它是先自动装箱变成一个了啊AA呢和78呢,其实呢,就封装到。哎,是不是一个叫N垂对象中啊。哎,然后呢,将此对象或者叫考虑吧,是吧,将此对象,然后呢,叫添加到咱们的table这个数组中。
07:01
诶,数组中是吧,这个呢,就是我们整体上的这样一个思路了啊好,那么这个put的操作呢,我说一下,它可能不是我们的第一个put的操作啊,为什么要这样讲呢?因为咱们现在要说一个通用的一个添加元素的一个过程是什么样子的,所以我就不拿说第一次添加为例来说了。好,这个呢,就是我们某一次添加的这样的一个行为,哎,下边我们来看看这个添加的一个过程。其实我这块叫添加呢,也不够准确,因为我这个put操作除了表示添加之外呢,它还有一个作用呢,是不是叫修改啊。对,所以呢,我们叫添加或者呢,是修改这样一个过程什么样子的。好,那这块呢,咱们先把这个事儿呢说清楚,说清楚以后咱们再看源码。也就是说呢,大家呢,呃,你源码呢,有可能自己看着感觉很吃力,但是最起码呢,你把这个过程先捋清楚,这个过程呢是一定要会说的啊,因为呢,这道面试题呢,是极其高频的一道面试题。啊,用了一个集齐的这个词是吧,所以所有同学都必须得会这个事儿啊,就是你可以呢,没有真正去看,当然呢,这个过程要弄清楚。
08:06
当然最好你看一看,这样你说起来的话呢,也比较有底气一些啊,就是通过源码我们证明的就是这样一个过程啊。好,那这个添加或修改过程啊,这呢我写的是A和78,那这呢我就抽象一点啊,那比如说呢,我们要将诶我这块写的啊叫K1Y61啊添加到。哎,当前的map中。OK,哎这呢,我们说这样的一个过程啊好,那这个过程是什么样的呢?哎,我们说呢,首先。哎,首先是吧,需要呢,哎这个叫什么。计算或者叫量啊,首先呢,我们要调用。啊,这个叫K1所在类的,叫哈西扣的这个方法。首先呢,要调用K1所在内的哈希构的方法,然后计算咱们这个K1,它所对应的叫哈希值。
09:01
没问题是吧,这个哈希值的话呢,我这块写一下计算K所对应的哈希值一。啊,你看我们为啥写了个一呢,因为下一步的话呢,他还要再去进行一个哈希的操作。呃,得到对应的这哈西值一啊,然后呢,此哈希值一说呢,就经过某种算法之后。哎,我们说呢,就要得到。叫哈希值二。啊,你看我这呢,提到了一个叫哈希值二,诶先呢,再来一个句号,这个某种算法是一个具体的方法,这个方法呢,就在咱们的哈希map当中,它定义的这个方法呢,一会儿我们也可以看一下啊,它其实呢就叫做哈希这样个方法,把我们的哈之一呢就扔进去。诶,扔进去之后的话呢,其实是把我们这个K给扔进去了啊,里边呢,只能说我们调用了一下它对应的那个哈希值一的这个数,我就这样写吧,经过某种算法之后呢,得到哈希值二。然后呢,这个接下来啊,说呢哈希值二说呢,他呢在经过。
10:07
嗯,某种算法之后。哎,就确定了其在数组咱们说叫table是吧,中的这个索引位置。哎,这个索引位置,比如说叫I。没问题了,好,这里边呢,你看我又提到说经过某种算法,这个肯定不是哈希了啊,这个呢,我们如果开始源码的话呢,它叫做index for。啊,这个咱们也能理解啊,你比如我们这块算出来这个哈,义值二呢,假设啊,就是1234这个数吧,1234,那这个数的话呢,我们要存在几定数组中,咱们说了数组默认呢,就是长度是16了,所以角标呢是从零到15的,那我们就需要呢,把这个数确定一下,所以你要放在我这个数组中,放在哪个索引位置啊哎,这个时候我们用的这个算法呢,叫index four。咱们前面呢,讲这个赛的时候呢,我稍微简单说了一下,说我们可以考虑呢,简单一点就是取模16。所以这样的话呢,你得到这个数呢,就是零到15范围内的。
11:01
OK啊,那实际上的话呢,底层呢,它用的不是这个取模操作,因为这个性能呢稍微的差一些。哎,那我们看看底层它用的是什么算法啊好,总之的话呢,它经过这个算法之后的话呢,它就确定了这个当前的我们的K1啊V1这个奇呢,准确的说呢,应该不光是说我们这个K了,应该是我们这叫。K1Y61是吧,在我们数组推部中的这个索引位置是L了,好,下边这块写1.1啊说如果此索引位置挨上。啊,这个就是我们这个数组上是吧,没有元素。啊,如果呢,呃此所以位置I上呢?呃,所以位置I在这个数组上是吧。我们说呢,没有元素,那就说明呢,我们的I位置呢是空的,哎,我们说则咱们这个叫K1Y61呢,就添加成功。杨癌针呢,就是这个位置呢,就是没有别人往这放,那我就认为呢,我就是跟其他的都不一样了,这个是我们叫添加成功的一种情况了,好,那我们再来个1.2,那下边就对你说,哎,如果此索引位置I的这个数组上是吧,有元素。
12:17
这个有元素的话呢,实际上呢,我们说这个元素呢,它有可能也不是一个啊,咱们就说一个比较,哎,基本的情况它就有一个吧。啊,有呢,这个元素叫K2呢,Y62。哎,那我们说呢,则需要继续比较K1和K2的啊情况是吧。啊,继续比较这个K1。啊和这个K2。哎,这样是吧,那具体来说的话呢,继续比较K1和K2的什么呀。啊,继续比较他俩的这个我们说呢,叫哈希值是吧。准确的说呢,就是哈希值二。啊,继续比较大的,还是之二好,那接着呢,往下再走,这个我就写个2.1了。
13:00
啊,继续比较它俩行一值二,那说如果叫K1的哈希值二。是吧,鱼。啊,这个我们叫K2的这个哈希值二。叫不相同是吧。现在呢,我们假设呢,这个位置只有这一个元素啊,这个元素就放在咱们这个数组的这个,呃,那个索引的这个位置上了,比如我们这个I就是这个位置是吧?现在这我们说呢,是相当于这有个K2,呃Y62就这个意思啊好,那现在这个位置就这一个元素,然后呢,我们比一下它们各自的哈希值二,看是不是相同,这个时候呢,它呀,哈希值二呢,不相同怎么着呀?则那就是不是意味着我们当前这个K1和这个Y61,我们认为呢,跟你现有的K2Y62就不一样了。哎,那就说呢,我们这个KY61呢,也添加成功。OK啊,诶这块大家稍微注意一下啊,我们这里边你发现了在现的,所以any位置上是不是已经有元素是吧?有元素的话呢,我们不能说哎冒似的,就认为说它们俩就是相同的了,还得需要做进一步的比较,那我们把这个位置呢,已经有元素的这种情况呢,呃,起个名这个呢叫哈希冲突。
14:12
哎,冲突什么意思呢?就是我们现在发现呢,他们俩放在同一个位置了是吧?哎,就这样的场景,但出现这种冲突之后呢,我们要做的事呢,就看一看你俩呢,是放在同一个位置了。那你俩的值,诶是不是它一值不一样呢?这种可能性是有的是吧,就像咱们说的,比如说一个数呢,取摸16,假设呢,这个数是15,那你取模16就是15,那这个数要是31的话呢。还是15是吧,就是你俩的这个索引位置一样,但是有可能你俩的哈移值呢是不一样的,所以我们先要比一下哈一值哈值要不一样,那说明咱俩呢就不一样,所以则添加成功,那对应的话我们还有这个2.2的情况,那就是说如果K1的话,一值二跟K2的话,一值二呢相同。相同了怎么办呀?哎,这个时候呢,相同呢,也不能认为他俩就是一样了。
15:02
注意啊,有可能说就是凑巧了是吧,你比如我们这个K1的话呢,咱们举个例子啊,咱们原来不是也说过这样的一个场景,呃,假设呢,我们这个对象的话呢,T啊。K这块呢,假设我们是一个呃,Person吧,Person有name和AGE2个属性啊,Name的话呢,假设叫小a age呢叫12,呃假设我们就非常简单的这个哈希方法呢,就是把它俩呢加了一下是吧,然后呢,另外呢叫小B啊,然后这个呢加上一个11。结果呢,你发现明明这两个呢。是不一样的,结果就是凑巧了,算出来这个数呢,是一样的了是吧。啊,有这种可能性哈,当然这块我举出来这个算上这个数一样呢,它其实对应的是我们这个哈希值一是一样的是吧。哈一都一样了,你经过这种同样的算法,你算出哈一值二是不是也得一样?对啊,所以说是有这种可能性啊。当然了,是不是还有一种可能性,就是说本身人家哈希值一不一样。结果你拿这个算法算完之后呢,还一直二一样。也有点这种概率是吧,这是有可能的哈,总之的话呢,我就诶不看那么细了啊,总之呢,就是你俩的还值二相同了,则需要继续比较咱们这个,哎,K1和。
16:11
啊,这个和我们这个K2他俩的ES的情况是吧。啊E口的情况,那现在的话呢,问题就是说到底是调谁的E口的方法。诶,这个要明确一下啊,则继续呢,比较他俩在这equals这个情况,那这时候呢,我们说要。嗯。诶,这个啊要调用。哎,对谁呢,注意是这个K1的啊,所在类的。啊,这个E口的方法。那就意味着我们需要呢,把这个K2呢,作为这个参数呢,传进去啊。哎,加K2。啊,作为参数啊传递。哎,进去。行这个呢,就我们说这个情况了,然后传进去以后呢,我们接着来一个啊3.1,那这时候呢,就有可能是吧,调用这一会方法的时候呢,返回是一个。
17:04
Force。比如说。哎,调用。S。方法,然后呢,返回false,返回false呢,就意味着它俩呢,我们认为是不宜cos的是吧。那怎么办?那是不是就意味着你这个K1跟我们这个K2呢,还是不一样的是吧,只不过恰好你俩算的哈一值一样了而已,所以呢,我们K1Y61仍是添加成功的。啊,这是这样的,好,然后呢,3.2呢,我们调用这个一会方法呢,返回是一个处。那就说明呢,你俩是不管还一直一样,E后词呢还真一样是吧。那就认为我们这个K1跟Y6 K1跟K2呢,就说明你俩是真一样了。是吧,我们这儿呢,就说哎则。啊,认为咱们的K1和K2呢,是相同的了。但是相同了,这时候我们其实这个默认情况下呢,是不是就是个修改行为了。
18:03
哎,我们说呢,诶默认情况下,咱们的这个叫Y62,不是Y62了,Y61是不是就替换原有的是不是叫Y62了。啊,相当于我们此时的这个铺的方法呢,就理解为是一个修改的行为了。而且呢,这个破的方法呢,它其实是有返回值的啊,就是我替换完以后呢,我把你原来的这个Y62呢,给你return一下。返回正常来讲呢,如果我们要是个添加的行为的话。哎,那你添加行为的话,这个返回值类型对于我们来讲其实没什么意义。所以如果呢,要是一种添加的这种行为。啊,像这的是吧,哎,它的返回值呢,是个nor。哎,要是修改的话呢,它的返回值呢,是原有的这个位置的Y6啊,这个注意一下,好,这就说完了啊,这个说完之后呢,我们在这儿呢,诶再做一个这个相当于补充的一个说明了啊,比如在这里边我们提到了,这叫添加成功,这也叫添加成功,这叫添加成功,他们呢,还是有点区别的,这个呢,我们称为呢叫情况一。
19:01
哎,把它CTRLC这个呢,我们叫情况二。这个呢叫情况三。好,那么这里边呢,我们去做一个,哎,补充的一个说明啊,这个情况一呢,我们说呢叫添加成功,它呢相当于把这个元素,因为对应的数组力位置上没有元素,所以我们就直接存放到了数组角标I的位置是吧。是吧,加。咱们的K1。哎,Y61啊,注意它俩呢,实际上是作为两个属性出现的啊,封装在一起其实有N垂对象了,正好我们这个数组呢,这不也是N垂类型的嘛,所以呢,就是将这个K1Y61呢,要存放到这个数组的索引I的位置。OK,这是这样的啊,然后呢,这里边儿还有一个呢,这个叫情况二和我们这个叫情况三。这个情况二和情况三呢,你注意现有的我们这个数组的位置啊,已经是放了元素了,那就意味着我们现在呢,在这个位置上。
20:02
啊,已经有一个叫K2Y62了,那现在的话呢,我们通过刚才这样一路判断哈,说你这个K1Y61啊,啊这个尤其是K了啊,K1和K2呢,它俩是不一样的了,不一样呢,我们说这个K1Y61呢,就能添加成功,那问题是现在往哪放。哎,这块呢,就不同的语言呢,处理方案就不一样了啊,比如像这个Python当中,处理方案呢,就如果呢,他要要往这放了,然后这个位置已经有元素了,然后有元素了,我们一判断发现新药方的元素跟它还不一样,不一样呢,他会选择往后边去找。就找这个I的位置的下个位置,下位如果要没有,我就放到下个位置。呃,如果下个位置有呢,再往下一个位置找。还有再往下一个位置找,然后这块找到末尾的时候呢,我再从头翻回来再找。是吧,总总找到一找到一个空的位置,我就放下了,如果你要没空的,那就该扩容就扩容了,是吧,这是这个思路哈,然后我们Java中这个思路呢,就是如果呢,这个位置呢,有元素了,而且发现不一样了,那这时候咱们就链表得了,这个链表上注意我现在说的是这个七啊七当中呢叫头插法。
21:05
头插法就是我们要放在头部,也就是说呢,你这个K2V2呢,你出来。是吧,我换个颜色啊。说你出来你放这儿,然后呢,我们这个位置呢,放K1V1是吧,然后它指向K2V2。哎,是这样一个特点。哎,在这这个七当中呢,也没有列,也没有这个红黑数之说,就是这个单向链表啊,所以呢,情况二啊,这个这个情况呢,我们就是哎,将。呃,首先的话呢,这个我们就简单来说的话呢,就是我们这个元素是吧。哎,它与我们现有的。啊,咱叫K2Y62啊,它呢就是构成了链表结构啊。诶,而且呢,这是一个单向链表结构。啊,这个再说一下呢,是我们这个叫K1啊Y61它呢指向。哎,咱们原有的这个旧的元素哈,叫K2V02,这个呢,我们都可以通过源码来来证明这个事儿。
22:05
行,这个呢,没什么问题了是吧,好,那么接下来的话呢,我们发现呢,随着我们不断的添加。啊,添加这个元素。随着我们不断的迁移元素,这个时候呢,我们这个数组中元素呢会越来越多,那下一个问题呢,是不是就该考虑扩容了。说呢,在满足要哎如下条件的情况下。哎,如下这个条件的这个情况下,哎会呢,哎,这叫什么考虑扩容。啊,那么这时候大家你猜一下啊,我们此时的默认的容量是16,你说我们大概什么时候会考虑扩容啊。诶,有同学说超过16,这个超过16呢,那得再继续追问一下,这个是指的是我们这个数组满的时候吗。
23:04
因为刚才说的要超过16,那意思超过16是不是那个概念,就是说满了,所以要扩容了,是这意思吗?他知道自己要买啊,那你意思就是还没到16呢是吧。好,那我刚才用那个词呢,叫做满啊。哎,这个呢,看大家能不能理解。哎,有没有同学会认为说这个买这个事儿呢就不靠谱。有可能永远也满不了。是吧,诶是这样的啊,所以这块呢,注意有个区别啊,咱们在前面讲这个a release的时候呢,咱们说呢,一开始长度是十,而且呢,它在添加,你看明确就是第11个元素的时候,那其实就是说你十个已经存满了,我们现在要放第11个了是吧,而对于我们这个map来讲呢,要注意啊,它可能就永远也满不了,因为呢,它有链表结构是吧。哎,所以说这块我们看到一个场景呢,可能是这样了啊,这个长度呢是16,然后呢,你第一个元素一过来,我们咔咔一顿算,算完以后呢,说你在这个缩引的这个位置上了,第二元素呢,结果一顿算了还在这个位置上是吧。
24:05
哎,那也有可能我们这个程序呢,就会出现了,假设我这放了几个元素,后续的话呢,他们有可能凑巧了。是吧,就是这样一个场景,你最后呢,已经放了16个了,有可能有好多位置呢,是不是始终是空的呀。所以说呢,对于我们这个N来讲,就哪怕说你数组这个位置都放上了,我们还可以再往下以列表方式再添加,所以它根本就没有满的概念。你可以一直不扩容,我说我在这个常规16这个数字中,我就添加1000个元素,你说可以吧。可以,那就练表呗。只不过链表太多的时候呢,你想如果它要特别长,几十个元素的话,我们要是想找某个元素,找到这个索引I的位置了,你下一步呢,是不是要接着去找这个链表了。所以导致呢,就是如果这个链表过长的话呢,我们这个查找的性能就会显得很差了。所以呢,我们要尽可能的让这个表当中少出现这个链表是吧。你包括呢,我们这块呢,说又得哈希值一下,其实它的这个不同的这个算法去计算,就是避免呢,尽可能的啊,咱们要是不ES的话呢,咱们的哈希值呢,尽量呢也别一样,尽量呢咱们就散略化一点,大家都均匀开。
25:14
啊,这样的话呢,我们每次查找的时候呢,如果都从数组里边就找到了,就省得你找链表性能肯定要好一些。啊,那一方面呢,我们去控制这个算法,另外一方面呢,那就是可以控制它的长度了。对吧,你像这个长度呢,我们都到1000个了,你还不扩容我这个算法,我再牛我也控制不住你这个列表太多。没法控制,所以呢,我们要想避免链码多呢,适当的时候呢,就要扩容了,那现在问题就是说什么时候扩。是吧,哎,这就一个这个条件了哈,哎,那这个扩的话呢,你也可以呢,是大于16的时候。啊,也可以是小于16的时候,因为要大于16的话呢。肯定是就有。肯定是不是我说诶,比如说我这里存了17个元素,我说肯定有链表对吗。肯定的是吧,因为你大不了就16个都放了,剩下那个肯定是得链表了是吧,就是你要是17个的时候肯定有链表,那如果说我们就不希望尽量的少出现列表,那你可以考虑的是不是少于16个时候就扩容是吧。
26:12
对的啊好,那到底什么时候扩呢,咱们稍微的可以这时候看一眼这个源码啊,我呢就输入一个叫哈希map了。啊,这个没有咱们七的是吧,这块咱们要看七的,所以呢,正好一会儿咱们也要看这源码了,所以我就先把咱们当前这个Mo哈,我把这个改成是1.7的了。嗯,这块呢,改不改其实倒都还行啊。好改完以后的话呢,我这会再CTRL一下阿信大,那我们就能看到这1.7的了啊啊进来这个我就先快速的,诶让大家呢去看一眼啊,我就找一下这个铺这个操作了点进来。然后呢,他在下边添加的时候,然后在这有一个叫。哎,我要找什么找的时候是吧。什么时候要进行一个,诶前面的这儿是吧。在这个条件呢,如果是处的时候呢,它不就执行rees吗?而且你还看到了库容原来的。
27:02
二倍是吧,哎,好,回过来啊,这个我们还是收起来好说呢,在满足如下的条件上,会考虑扩容,诶,往这一站。哎,这个我加上括号也行啊,大家看一下这个条件是什么呢?它提到一个size size就是我们现有已经存了几个元素了,这个呢叫stresshold,这个thhold呢叫做临界值的意思。就是当这个塞呢,大于等这个临界值的时候呢,我们就要扩容,当然了还有一个补充条件啊,就是你现在要放在这个I的这个位置,它就是我们这个元素I的位置啊,I的位置上呢,还不是一个no。其实主要的条件呢,咱们就考虑前边啊,就是会考虑扩容怎么着,我们解读为呢,就是当啊这个元素的个数啊达到咱们说呢叫临界值时。啊,临界值时,哎,然后呢,就考虑扩容,呃,然后这个临界值是多少呢?这个呢,我就先写到这儿了啊这个临界值呢,它等于。啊,我用个箭头来说吧,等于呢,我们叫数组的长度乘以一个叫加载因子。
28:10
啊,加载因子啊好,然后呢,咱们现在这个数组长度是不是16啊,这个加载因子实际上呢,就决定了我们到底什么时候来扩容了,哎,这个加载因子呢,咱们说默认呢是0.75。哎,3/4,所以一乘的话呢,就是12是吧,哎,言而之呢,就是当我们这个达到这个12的时候了,啊,大于等于12了是吧,然后这个时候呢,我们就要考虑扩容了,当然了这块大家会发现人家其实还有个条件,只有这个条件也满足的时候才扩容。这个他想表达什么意思呢?就是你现在要添加的这个元素呢,其实呢。哎,这个位置呢,是空的啊。就是相当于我现在要添加的元素呢,不会导致我链表增加。你看是吧。你看啊,现有这块呢,我们是不是已经出现啊,这样咱们说这个还不如直接我这里边儿有个图啊。
29:02
诶,找我们这个map了。嗯,Map在这啊。咱就看这个吧,这个呢是GD8呢啊,八大中有这个红黑数了,你就假设现在没有这个红位数呢,或者你看这个位置这个这个也行啊,这不都是N垂嘛,好,现在的话呢,我们要考虑这个扩容了,发现这个size呢已经达到这个12了,那我现在要添加的这个元素,说这时候呢,你先别着急添加了,就一定要扩容吗?也不一定,假设我这个元素呢,我就要放在这个位置了。因为你要放在这个位置的话呢,根本没有导致我们的列表会增多呀。你没有导致我增多,那要不就先忍一忍?是吧,先放这儿,你如果再放第,呃是这个是这个再往后放,再往后放的时候呢,你发现你要放这个位置了,这个位置也没有链表。或者也没有元素,所以你放这儿完全不会导致这个链表增加是吧,那就再忍一忍。哎,直到呢,就是我们现在已经超过12了,结果你发现呢,要放的位置呢,出现这个列表了。这个时候呢,我们才一定要扩容是吧,所以它这里边儿这儿呢,算是一个小的细节啊,大方向来讲的话呢,就达到这个临界值的时候,我们就考虑扩容。
30:03
OK啊,那么哎默认的,哎这个我们说呢,叫临界值。啊,是多少呢?就是我们这个数组的长度16呢,去乘以0.75,啊这呢,我们就得到了叫12是吧。哎,默认的临界值呢,就12,就是相当于你要达到这个12了,我们要考虑扩容这个事儿了。好,那么。刚才我们也看到这个底层源码了哈,说呢默认呢,扩容为。哎,原来的,哎这个两倍是吧。OK啊。好像这个空间的话呢,我们就扩了一倍,扩了一倍呢,就相当于我们从这个16呢,就变成了这个32哈,32的话呢,也是二的五次方,每次呢,我们都扩容两倍啊,原来是二的四次幂,每次再扩容的话,你发现呢,乘以二最后得到的是不是都是二的整数次幂是吧。那这样一个特征啊,行,那这里边儿的话呢,大家会发现这个加载因子呢,还是蛮重要的,因为呢,我说呀,它直接决定了我们这个数组的一个系数度。
31:02
或者我们整个这个链表可能出现了一个概率的问题。你想想啊,如果我们这个加点因子要是比较大,当然呢,完全也有可能超过一是吧,这个数要比较大的话呢,意味我们这个临界值出现的就比较晚。那就意味着我们当年这个数组呢,你用的机会呢,就比较久是吧,这就意味着我们这里边添加的元素就比较多。这个逻辑呢,能推动是吧,那比较多的话呢,就意味着我们出现链表的概率呢。就要大很多。但是它的好处是什么呢?缺点呢,就是链表可能会很多是吧,好处呢,就是说我们现在是不是节省内存空间了,因为你每次一扩容,然后再把它再呃复制过去,这个呢要花时间花精力啊是吧?所以呢,我们要是加载因子比较大的话呢,我们能够节省内存空间。哎,但是的话呢,你这个链表过多,导致我们后期呢,查找啊的一些行为,包括删除一些行为都会很差。所以这块呢,我们这个家的因子呢,不能太大,那你说这加的因要特别小吧。
32:04
也不行是吧,别人整个0.1。那16呢?乘以0.11.6,这一节省一了,添加第二元素就扩容了。就是对,这时候呢,你空太多东西了是吧,没有必要呢,你说你为了担心有链表,然后呢,贴俩俩仨元素,你就开始扩容了,就空的也太多了,有点浪费了是吧?所以这时候呢,我们就要找到一个平衡,既呢让他这个链表不能太多,也不要过多的去浪费这个空间,最后呢,可以理解成从统计上来讲。啊,我们这块呢,选了一个直角0.75是比较合适的。啊好,那这个值呢,一般咱们都不会动它。当然呢,我们通过相关的构造器呢,你也可以不用它哈,但是我们一般的话呢,都选择0.75啊,就不要去改了啊好,这样的话呢,咱们就把这个1.7当中这个源码呢,我就说清楚了,为啥我亲自要去写呢?啊,我完全可以一粘粘过来说一下就得了,是吧,亲自写的目的呢,是大家呢,根据我刚才说的这个事儿,我一边说大家应该一边理解一边记。
33:03
这个过程呢,要能用自己的语言给它表达出来,下边的话呢,我们来证明是不是这样一个过程啊。行,这个清楚以后呢,再证明这个事儿呢,看源码,这个大家会更清楚一点,如果上来咱们看源码呢,可能就有点懵了哈,这个为了比较好的去说明这个事儿呢,哎,这个咱们换一种思路,我就1.7的,我就不提bug了,咱们直接呢把代码粘出来,咱们就一点点看啊,这样呢给大家留一个笔记。这边呢,我这我写一个啊啊JDK7中的。哎,中的这个,诶,我们叫哈希map,它的一个源码啊,啊CTRLS,哎,我现在就把它保存在这个桌面上吧。哎,刚才的话呢,我们主要呢,说其中的啊,两行代码啊,第一个呢,就是我们去new一个哈希map。这样的一个操作啊,CTRLC。哎,我我呢把它粘过来了,好,它呢我们说哎,对应的这个叫源码是吧,好下边我们就来把它这个源码呢粘过来啊。
34:04
好,回过来这时候呢,哎,我们这个其实就是哈,我说你确定一下,我们现在用的是1.7的哈,点进来好CTRL f12,我们现在找这个构造器哈,构造器的话呢,首先我们看到这个构造器。哎,我就先把它粘过来了啊。先占到这好,这呢,它又调用了本类当中重载的另外一个构造器了。啊,这块我们就接着回过来点一下这个Z啊,从这。啊,一直到这儿是吧,CTRLCL一下。这个呢,我们就把它呢也拿过来。来CTRLV啊行,这块我们再往前移一下,好,这块我们就先说这个构造器的事儿,哎这呢,我们去拗一下这个哈信map用的空间构造器,它掉了这个Z了,这里边呢,你发现它出现了两个常量啊,这个呢叫默认的initial capacity,这默认的一个叫load factor,哎这呢,我们也关心一下,说这两个值它到底是多少。诶,CTRL f12一下还回到这个位置,然后把它那点一下,这个值呢是16。
35:04
啊,这呢,我们在这写上啊说这个其中是吧。哎,这个值呢是16,然后还有一个呢,叫啊default load factor啊再回过来。哎,这不,Default load factor。0.75出现了。好,这让我们把它也粘过来好,那压一呢,我们现在呢,把这个16呢跟这个0.75呢,就传过来了,这个是16~0.75,哎,这判断是不是小于零啊,这个这样啊,其实一开始的时候这个事呢全都进不去,我这呢就写了个略了啊。哎,咱们只留一下这个最核心的这个代码。哎,这个就咱们这个,呃,省略的就是它有一定的判断,这些判断其实都没进去啊。好对了,然后接下来诶,我们这呢,看在内部呢,定义了一个局部变量叫capacity是一,然后呢,说这一呢,小于是16嘛。E小于16,然后呢,它就向左移一位,然后一顿直行,其实这个capacity你发现它决定了我们最终是不是创建的这个数组的一个长度了。
36:04
哎,这个capacity是,而不是说我们拿着这个16呢,直接就把它塞到这个N垂这块当长度了。不是这样子的啊,好,这个是一,好咱们看一下一小于16。左翼一位。变成二了。二小于16左一位是不是变成四了?四小于16左一位八了。八小于16左一位16了吧,16小于16不满足了吧,所以这个capacity呢,经过这样一顿直行之后,它是。16吧。刘,这费这个劲呢。啊,你看,因为你有可能是不是掉这个构造器啊。咱们刚才调的是空三的,它这传来是16,那它这个你也空能是不是直接就调这个构造器。我要直接调这个构造器,注意看啊,我要是传了个15。那我问底层那个数组长度是多少?还是15吗?不是了是吧,他并没有直接拿着这个值,是不是跟我们这个NT呢去赋值是吧,哎,他呢,是不是又得经过刚才说的这样一个过程啊。
37:03
说你这个,咱们刚才比如说到八了哈,八小于15满足了,往左一是不是变成16了,16小于15不满足了,结束了,但你写的是15的时候呢,是不是这还是16。所以呢,它保证这个数组是不是始终是二的整数倍呀,因为你每次都乘二乘二乘二嘛。哎,就这样个逻辑啊,所以这块呢,我们的哎目的是什么呢?就是通过哎此循环是吧,我们说呢,要得到这个可拍的最终值。哎,最终值,而此最终值就决定了我们这个N垂数组的一个长度。这个没问题啊,因为直接在这负的值,而且这个capacity派呢,我们通过这样的循环也发现哈,说此时的这个capacity派D呢,它一定是二的整数倍啊。诶,这就相当于我们在设计的时候都是这样子的压这哈,大家顺便也看到了,如果我们去new一个哈希map的时候呢,这块你写了一个容量啊,这个容量你注意它可不是数组的长度,有的时候这个比试题他会问啊,说我用这个构造器,我这写的15,数组长度是15吗?注意不是因为它有个这样的一个判断啊。
38:12
注意好,那这时候问题可能就多一个,说为什么得是二的整数倍呢?这个我们稍微往后一会再说啊。前期的一个准备,那么接下来这个呢,你看拿着这个load factor啊,然后呢,我们就给当前这个对象里边这个属性叫load factor。所以这里边儿其实就涉及到咱们当年类里边呢,还有别的这个属性的load factor呢,属于其中之一是吧,回过来我们F12一下啊。找到我们这个构造器的,哎,刚才我们是先这个是吧,这个到这儿过来,这不有一个,哎,Load factor这个呢,就是咱们当前这个类里边的一个属性哈。啊,这个我们就称为呢,就是叫加载因子了。就是我们最后的扩容,实际上呢,是由它决定的,但是它呢,在这个位置我们发现呢,是拿这个来赋的值,这个呢,不就我们刚才传的0.75吗。
39:02
哎,所以这块呢,我们就是诶要确定了加点因子的值。哎,这个就给到了啊好,下边这个呢,我们取了一个min,呃,这个呢叫capacity派乘以这个,这不就是capacity派,刚才16嘛,16乘以0.75,这得到不就12了嘛,这个最大的capacity派这个数相当大啊,哎,所以它俩取个最小值呢,这个得到一个它就是临界值是吧?这个临界值呢,刚才看到不就是12吗?这个我们就叫确定了。那叫林。介质啊好,这个threat后的话呢,也是咱们当前类里边的一个属性是吧。哎,这叫临界值啊。哎,这个连接人你看他为啥不是final呢。呃,因为你扩容之后的话呢,我们还得变的是吧,嗯,OK啊好这呢就完事了,然后下边这个table的话呢,毫无疑问是我们当前这个类里边呢,非常重要的一个一个属性了。
40:02
哎,就是当年我们这个N的这个数组呗。啊。他呢,就是实打实的来存储我们数据的啊。哎,这个数组好,那这时候我们就确定了,相当于呢,叫初始化的数组。啊,然后呢,长度为就我们这个capacity啊。这么找一下好,下面这个没有用,这个包括这个阴利的这个方法呢,其实它里边啥也没做啊,你看CTRL f12我们还回到这个位置啊,这个掉它了,然后这个不是有个阴的方一点开,你看啥也没有是吧。啊,OK行,那这块我们回过来,相当于后续这个代码呢,咱就不多关心了啊,这个我们再写个叫略。诶这样就行,好,那通过我们刚才这样一个构造器,诶大家呢,你关心一下,哎,我们这里边主要做的你看是什么事,必要的一些结构呢,已经做了初始化了,主要呢是它啊好这呢是我们叫创建对象的这样一个过程。我在这写一下啊。这个呢叫实例化啊。
41:03
哎,它的一个过程。好,接着我们回到下边这个位置啊。这个我们来个第二个,这个呢,我们就是添加元素,哎,或者叫put操作的一个过程啊。K value。哎,这样个过程,好这块我们就直接呢,就来找它这个源码了啊回过来CTRL f12这个找我们这个put的方法,诶进来,哎,就找到这儿了啊找到这儿的话呢,我们就把当前这个操作CTRLC粘过来。诶好,我们现在就来分析啊,里边需要用到什么方法呢?我们再去给大家去粘啊。好这块的话呢,你发现一上来说这个K呢,如果是no,我们就这么着,这个呢,相当于咱们哈希map,当初咱们在讲这个第12章的时候呢,提到过它呢,是可以允许K或者是Y6都为no的是吧。所以呢,他专门针对这个K呢,是闹的时候呢,专门判断了一下,为啥这样呢?因为你后边呢,如果调这个key的哈西扣的方法,你是个no,一调哈西扣不就控制人了吗。
42:00
所以他上来先把这个特殊情况呢,先给你抛出去啊,然后这块呢,大家也完全可以打开这个源码,你看一下我在这呢,我就特意说一下了啊,诶就是看源码以后得到结论是什么呢?就是如果那首先呢,我们说明呢,就是这个哈希map呢,是允许添加尿值的。哎,Happy map说允许添加,哎,No的这个K是吧。或者叫添加K为no的值。哎,这是一个情况啊,然后第二情况的话呢,就是你看它已经是no了,你再拿着它去算哈希值也没什么意义,也算不了,那这时候呢,它会有个默认的规定,规定什么呢?就是K为no的这种情况呢,这个KY6啊,放哪呢?就放到我们整个这个数组角标零的位置。啊将此啊,这个我们说呢,叫KY6啊。叫存放到。哎,这个我们说呢叫黑。哎,索引,哎,零的位置。
43:03
这个事儿呢,要证明呢,那非常简单啊,或者说呢,这个不能叫证明了,准确的说呢,应该就是看了人家写的咱们回过来说的这句话啊,你看我一进来这块呢,不就直接问说你角标零的位置有没有元素吗?如果角标零的位置呢,根本就没有元素,那就直接添加呗,就放到角标零呗。哎,如果这个位置有元素了,有元素我看你是不是闹啊。你要不是闹,你要不是闹的话呢,我就你看,如果你要不是闹,我是闹,你不是闹,咱俩肯定不一样嘛,那就接着next呗。如果呢,你要是这个角标零的位置,万一有个直视no,你是no,我也是no。那我就替换呗。是吧,诶非常直接的啊,行,所以这个呢,细节这个咱就不多关注了,这个代码不算难,大家你看一眼都可以啊好,我们再跳回来。这块呢,我们就不管了啊,这个说的就是这种特殊的这种情况,咱们呢关心的是这种一般的场景,一般场景来我们看到一个操作叫哈希方法。刚才我说了啊,哎,我们需要呢,拿着这个K的一次哈希值,然后呢,经过这样方法之后呢,得到一个二次哈希值。
44:02
那这时候我们比较关心的就是这个哈棋方法怎么做的啊,这个我们写一个叫其中啊。好,那这块我们回来点一下这个哈希啊,把这个代码呢,从这往这一粘,CTRLC一下粘过来,这个方法的话呢,大家不用去细研究啊。你拿着这个key过来之后呢?这是不是叫伊斯哈希?呃,然后呢,有一个易货的这样操作是吧,呃,然后呢,再到你这个H上,H呢,又一顿猛操作是吧。这个你看还挺整的,挺复杂是吧?啊,总之呢,就给你各种混淆啊,混完以后的话呢,得到一个返回的值,这个返回的值就是我刚才上面讲的,咱们得到叫哈希值二。啊,这个注意,哎,所以这里边儿呢,我们说哎将哎K。哎,传入啊,这个哈希这个方法是吧,然后内部呢,哎,使用了这个key的。哎,我们叫哈希值一是吧,然后呢,这个此方法返回。
45:03
那此方法执行结束后,哎,我们叫返回叫哈希值二。行,那这个哈值二呢,就得到了,那这个哈二呢,就决定了我们到底应该放在数组的哪个位置,它这有个方法呢,叫index for。好回过来我们这块呢,再回复去这个源码啊,这不是有index for嘛,把它呢CTRLC咱们前面呢提到了,说咱们取模一下就可以了,你会发现呢,它用的呢不是取模操作。哎,你看他怎么做的呢。啊,比如这个值啊,咱们就随便来个数哈,就1234了,然后我想判断一下它在数组中存在哪个位置,索引范围呢,是零从零到15嘛。是吧,那怎么找呢,它这块呢,叫LA4减一。啊叫L4减一,咱列L不是16吗?16减一就15是吧,我让他跟15呢,求一个这个与的操作。啊,这个结果呢,我说它一定是这个零到蓝色减一这个范围内的。
46:02
这个呢,就是我们的一个微运算符了啊。啊,有同学说,诶,这个符号到底是未运算符啊,还是逻辑运算符啊。你看前后是不是数,要是数肯定是位运算符是吧?这要是一个布尔类型的,那就是逻辑呗。对,这显然是数了哈,好,你看这个呢,大家要理解啊。什么样一个思路呢?咱们来一个这个in特性的值吧,就是你随便呢写一个十进制。这呢就是得到我们这个所谓的汉一值二是吧,我不管这个数是几啊,然后呢,你对应的这个二进制。这个二进制呢,这就我们下边写的这个了,我让他呢跟这个15求个与15呢,你会发现它就是四个一。哎,就是四个一啊,那求一个与操作呢,与就是你上边原来这个数是几,我们得到这个结果就是几是吧。我这都是一了,你上面一结果就是一,你要上面零结果还是零。这个我这个数整的有点特别了。上面四个零了是吧,哎,恰好我们这个结果呢,是不是就四个零。
47:01
对,那四个零对应的就是索引零的位置。哎,你最多的话呢,你是不是就四个一啊。上面四个一,得到结果还是四个一,这阵不就是15吗?所以我们现在得到这个结果就一定是零到15范围内的。他这个为什么不用取模。这个L呢?对,人家这个快呀,你这个要取摸这个LS的话呢,你上边这些数是不是都要参与。哎,去除除除得到个结果,我这儿呢,我直接就取你最低的这四位。都方便。哎,那么他怎么去保证这个,你看这叫LA4减一,这就十五四个一,我要是回头变成32呢。32减一是不是就31啊,31我前面是不是再补一个一就行。所以为什么是二的整数次幂呢?每次我这样呢,去计算这个索引的时候很方便呀。啊,这呢,就解释咱们为什么上面提到了这个事儿吗。这个是吧。他每次计算这个索引的时候呢,很方便啊。好,那接着我们回过来在这儿啊,所以呢,非常简单的一个语运算,它就能够搞定啊,在整个我们这个数组当中存放的位置啊。
48:03
确定这个我们的当前。哎,当年这个key。Y6是吧,在数组中的这个,哎,存放位置啊,哎,好这个I呢,就找到了I这个位置,找到以后呢,下边这个事呢,我们是不是要看一下I这个位置上有没有元素了是吧。所以他这块看有个for循环啊,首先呢,我找到你这个table I的这个位置。找到这个位置以后呢,如果这个位置呢,就是闹哈。就是我们刚才提到这个添加成功的第一种情况就是这个位置上根本就没元素是吧,相当于E呢,不等于no不满足吧。整个for循环是不是没进去?哎,这块坚持住啊,这个就没进去,没进去相当于你直接是不是就走到下边了。这个事的话呢,咱就不关心了啊,哎,这个我就。对这个呢,我们以后呢,提到了关于这个修改啊,什么时候会失败啊是吧?诶这个时我们再说啊,现在把它就过滤掉了,直接呢,我们就看这个操作了,相当于呢,我们直接这个位置上就是空的,那我们就直接添加就行了。
49:03
所以它就直接就掉了一个叫ADD entry这样的一个方法啊好,这个方法呢,我们还得再看一眼。啊,点一下有这个。还挺多是吧,以为说到头了呢,就还有啊。啊。坚持一下啊,好把这个代码呢,我们拿过来。走到这儿了啊,现在呢,你要调这个添加的操作了啊,添加操作注意它这个添加的时候呢,你看这个哈希哈,这个哈希呢,是这个哈希。也就是我们这个哈希值二吧。他把这哈一直二和你当前的key value,还有你要放的位置都放在这里边了。然后呢,就放到我们这个里边,哎,看看怎么着啊,我要添加了,我得先看看用不用扩容。啊,这个呢,其实就是我们,哎扩容的一个条件啊。哎,咱们那会儿呢,不已经说这个事儿了吗。啊,然后呢,诶怎么扩容这呢是它的一个比例。这个我们叫,诶默认呢,扩容为。
50:00
原有容量的二倍是吧,行,那这个呢,就多说一句啊,如果你要是扩容的话呢,然后它下边还得再重新的,你发现啊,你这个K还不是no,它重新的就再算一下你这个哈希值。就本来这个哈希值我已经都算完了是吧,他呢又给你重新算了一遍啊,就把这个又给扔进去计算了一次,这个大家了解一下就行啊好,这个呢,我们这块呢,假设要不需要扩容的话。直接添加是吧,直接添加的话呢,又掉了一个方法啊。点他。And dress it。啊,又掉了这个方法。诶,就是大家你看这个代码的时候呢,凡是出现方法了,我基本上都在下边都写了啊好第二列方法,然后把你这个啊一开始的这个哈,之二呢传进去,KY6和你要放的位置传进去,好我们这块呢,就首先呢,找到现有的这个K的这个位置上的这个元素。也就说诶我们这个刚才不是说了氢压,说这个位置没元素吗?那这个就是闹呗。
51:02
啊,这就no好,然后呢,我在这块呢,我new了一个entry。这个N里边呢,有几个属性哈,首先啊,咱们就直接呢点进来啊,是不是就N垂的构造器了,这呢,其实就是我们核心的这个说底层呢是N垂数族,这就是这个N垂的它的一个主要的一个结构哈。哎,我们在这儿明确说一下啊,说这个。嗯,给我写成是一个。哎,三吧。哎,这个就是我们这个N翠,哎,它的一个定义啊如下。哎,他那是比较重要的结果,我就直接呢,给他单独的拿出来了啊。啊,这么着一下,好,你看这个NT啊,这个NT里边它有个K,有个value,有个ne,它有个哈希,就是它把你这个二次哈希这个值呢,还作为一个属性呢,给它固定下来了啊。我们现在扭了1N把,你还一值KY6和这个EE,注意是我们原来这个数组位置上元素。啊,然后把这个元素呢,作为我们这里边儿,你看叫next出现的,相当于我们新的元素。
52:00
是不是指向这个旧的元素。对,这就是我们构成了一个头插法的这样的一个,诶。一个一个证明是吧,好了,然后呢,这块呢,我们这个位置因为没有元素嘛,那你所以这块呢,其实就no相当于我们现在这个数组,我要放在这个位置,它指向的实际上是个空呗,就是吧,哎,行,这个size再加加一下好至此的话呢,咱们这个位置如果要是没有元素的话。啊,咱们回到这儿啊,没有元素的话呢,不就直接添加成功了吗。啊,就这样逻辑啊,在这儿我们写下说将咱们这个AKY6啊添加到。或者叫封装为一个NT垂对象啊。然后呢,并将此对象哎保存在。哎,这个索引I的这个位置。诶,这个稍微大家注意一下呢,就是我们这个所谓的哈希值呢,他也没有说每次都临时算一个,它呢,也作为我们N垂中的一个属性给固定下来了。这个呢,我们在这里写啊。相当于呢,就是使用是吧,咱们这个K得到的这个叫哈希值二啊进行赋值啊。
53:08
诶。进行这个诶复制操作行,把它就给固定下来了啊。嗯,固定下来什么意思呢,就是如果我们回头这个K呢,里边的某一个属性给变过啊。啊,比如我们那K是个person类型,里边呢有name有age,我把age给改了,所以你会发现呢,我们这个哈呢,它还是用的原来的那个哈,是吧。哎,这个注意一下啊,他没改,他不是每次都临时算啊,他就给按你最初存的时候的那个含义质量给固定下来了。然后的话呢,我们再回过去说到哪儿了呢?说到这儿了,咱们刚才呢,只演示了一下啊,对应过来源码里边呢,叫添加成功一嘛。这个位置本来就没元素,但是现量呢,这个位置有元素了。那你这块还得看下边这个情况是吧,好回过来。假设呢,这个位置呢有元素,那就E呢,就不是闹了。不是闹了下边。咱俩哈西纸一样吗?是不是判断这个事儿啊,那如果还一直要不一样。
54:02
就没进去是吧,你看这是个且的关系,这个要不是出了是不是就不用在看到后边了,所以好咱俩还一直不一样,不一样的话那行。接着再取你下一个元素,你下个元素看看是不是no,不是no,说明你这个是不是有列表。呃,也就是说我们目前这个场景呢,我们要看的话呢,它线上这个位置啊,它有东西哈。咱们这个是JDK,我这是八了,咱们你要是把它考虑七七的话呢,你就别想这块就行了,你就想象它有这个结构是吧。好,这个我们拿它来说哈。回过来啊,就是现在呢,假设我们找的这一支呢,假设就是这一支的啊呃,一开始找这位置有元素,然后我们这块,哎,就是先看一下你跟我们现要添加这个呢,你看K是不是一样还是不一样,还一要不一样不一样,那我接着再next就取这个了,这个呢,再看咱俩还一样不一样不一样不一样再取这个,再取这个,直到呢取到呢,就是你在next的时候呢,已经是no了。闹了就退出了,说明呢,我就跟你这一支上的所有的元素都含一日不一样,不一样,是不是就添加成功了。
55:02
这个对应的就咱们说的这个添加成功二是吧。哎,添加成功,然后呢,这块咱们不是也说了,诶怎么添加成功呢,他把这个索引I位置上这个元素呢,是不是现有的这个位置元素先取出来。这不是在这儿吗?先取出来是吧,现有这个I的未知元素取出来,那不就是这个元素吗。这个原子取出来之后呢,我又新用了一个数组。新旧这个,呃,新旧这个ENT,就我当心要添加这元素,然后把你现在取出来这元素呢作为我的next出现,然后把我呢放在这个数组的位置。这不就是就我们说这叫头插法吧,就是你这一只是吧。你怎么着啊,你往下移。对,你你往下走,然后呢,我当天要添加的元素放在这儿,然后我指向你。是不是就头插法每次都在头部这块是吧。就这个思路啊,好,这个咱们就说过了这儿了啊,那我们还回到刚才说的这这个呢,刚才我就把这个第二种添加成功的情况就说了啊,那么有可能的话呢,我们就在这个诶找这个链支的时候过程当中哈,一直呢,突然发现跟某个元素一样了。
56:09
一样啦。那不能证明咱俩就一四,是不是还得继续后边这个。后边这个呢,其实本质上来讲呢,就是判断咱俩是不是ES了啊,但是的话呢,先多判断一步,说你现有这个位置的key啊,你看咱俩地址一样。然地址要一样了,是不是都不用ES了?是吧,哎,这就相当于一个快速的判断机制啊,那地址要不一样,咱俩再实打实的看看咱俩属性啊,是吧,重启的一个方法怎么写的呀,你看我这块呢,是不是咱们当天要添加的这个元素,作为我们这个。K1它呢,调他自己所在类的一个方法,把你现有这个位置的元素的这个K值是不是放进去。现在这个K不就是这个吗。现有的这个位置上的这个元素的K值放进去,所以它作为形参出现的啊,好,那如果说这一块呢,不满足。这要不满足它是false了,那就说明咱俩哈一直一样,但是不是ES的。
57:00
那也没有进一是不是接着在next。下一个。就像我们说的,哎,你这个呢,就是哈一直不一样了,这叫添加成功了,你要是哈一直一样呢,Equals也不一样,是不是接着再找下一个。啊,都不一样,都不一样,都不一样,那是不是就是添加乘三的情况了。对的啊好,那现在如果说这个是处,这个是处,那说明咱俩真一样。咱俩要真一样的话呢,先把你一样的这个位置的Y轴呢,取出来把你返回。然后呢,我现有的这个呢,Y6呢,充当你现有位置的这个Y6。是不是就这意思啊?哎,就这样就行了,哎,你看我们刚才讲的,如果添加成功的场景是不是return是no。然后呢,你要是替换的行为呢,它返回的是你原来的这个value是吧。哎,就是在这个位置呢,我们体现啊说呢,如果put呢是叫修改操作啊,然后呢,会返回原有这个啊叫。啊,原有咱就直接说吧,叫旧的这个Y流值。
58:00
啊,如果你要是一个添加行为呢,我们反过来是个闹是吧。哎,添加。操作啊会。返回一个闹,因为你添加嘛,这个你也不需要呢,返回啥了哈,好这个呢,就咱们刚才分析的这样的一个过程,然后呢,呃,简单的话呢,这块不有一个二倍的一个扩容问题,这个我就不展开去看这个事了。诶,我们在这个1.8当中呢,这个reet方法我们需要呢去看一下啊行,那这个呢,就关于我们这1.7呢,诶这不就说清楚了啊,我觉得这样呢,写写笔记呢,大家可能会看的更清晰一些啊,然后把这个呢笔记呢,我CTRLC一下,诶咱们也可以呢CTRLV啊我就直接粘到咱们的。哎,这个idea里边了啊,粘过来之后呢,大家这块呢,就能直接看了,他这块呢,有三个图啊,这呢就是呃,写的这个操作跟这个展示的操作,这个呢,就是纯写的操作,你就点最后这个啊。是不是就在这儿也能看了?哎,这样就可以啊好,这个呢是1.7的源码,1.8的话呢,我就不这样来了,1.8咱们就直接抵bug啊。好,那这呢1.7大家需要记住,1.8呢,我们就直接说一下跟1.7的区别是什么,然后呢,我们看一下源码。
我来说两句