00:00
好,这个呢,我们关于这个哈,Map的这个底层源码呢,我们就说完了啊,然后呢,我们这块呢,呃,给大家留的是七的这个笔记,然后八这块呢,我们就直接debug的啊,大家呢,主要关注的就是这个七跟八这个区别就行了啊,除了这个区别之外呢,剩下呢,其实都是一样的,什么叫剩下一样呢?你比如说我们在七的时候呢,已经讲过了,什么时候需要考虑扩容这个事儿了啊,那我们在这个八当中呢,大家同样的道理啊,这块的话呢,你相应的达到这个临界值了,哎,这个呢,就需要呢去扩容了。当然了,这个扩容行为呢,我们刚才在这吧里边还看到有一个特殊的场景啊,就是当我们这块呢,要做这个数形化的时候是吧。呃,就是它还有一种扩容的场景呢,就是说呃,我们当前这块呢,假设呢,这个长度是16,其实呢,我们现在还没有达到这个临界值呢,但是呢,由于我们这一支上啊。是不是这个链表存储的这个元素有点多了是吧,已经达到这个八了哈,达到八的时候呢,这时候呢,我们按说呢,哎,那就属形化吧,哎,它里边呢,判断了一下,所以你这个长度比较有点短哈,这个你也先扩容,所以这呢也算是一个我们扩容的一种场景。当然正常情况下呢,都是达到临界值的时候呢,我们去扩容这个事儿啊。
01:03
诶包括呢,我们也看到这个哈,Map呢,它底层使用的这个结构呢,确实也变了CTRL f12下,它呢,使用的是这个node类型的这样的一个数组。啊,在这儿呢是吧,看的都比较清楚一点啊行这呢是我们这个呃,JD1.7.8里边这个map这样一个码,然后接下来啊,我们带呢,再提一下呃,相关的一些map中的这个结构啊,比如这个呢叫link的哈map,那我们在前面讲这个link哈map的时候呢,提到过它是哈西map的一个类是吧。哎,首先呢,我们提到这个事啊,哎,另map它呢是。诶,我们这个叫诶哈希map它的一个子类啊,然后这个子类呢,体现具体的话呢,我们说这个link的哈希map,它呢,在我们这个哈希map使用的这个数据结构的基础之上,又增加了一对双向链表是吧。啊在哈map使用的,诶,咱们叫数组加,哎,单向链表。哎加这个叫哎红黑数的基础上,哎又增加了哎一对叫双向链表。
02:12
哎,双向链表啊,那么它增加这个双向链表的目的是什么呢。或者用来干什么呢?诶,是不是记录一下我们添加的这个KY的一个先后顺序啊。啊,记录添加的。哎,咱们这个叫哎小花啊。Value啊,它的一个先后顺序。哎,就是前一个元素呢,我就指向了后一个,我添加这样的元素,然后呢,便于是吧,我们去便利吧。啊,便利我们这个所有的这个KY6啊。诶OK啊行,那就意味着如果我们有频繁的这种便利的一个需求的话呢,推荐呢,我们就使用这叫link还map了啊,那这个我们就得看一看啊说怎么体现呢,它增加了一对双元列表,这个呢在哪能看得见。
03:02
啊,那很显然的话呢,我们这个在添加这个元素的时候呢,我们呢,就需要呢,把这个列表呢给它用上了,所以应该是在添加这个操作里边,是不是能看到这样的一个行为啊。好,那这块我们可能想到说,那我就看一下这个添加行为了,哎,那这块呢,我们这样啊,我CTRLC一下,咱们把它呢再粘过来,然后呢,这个我们叫二这个位置呢,这个位置其实改不改无所谓,关键这个位置是不是一定要写成叫link的哈,Map。哎,左边呢,没改是因为这是多肽了。对的啊好,我这块呢,我就打一个断点了,这时候我们就直接呢叫debug,相当于我们就看new一些link哈,Ma它的一个行为是吧,诶首先的话呢,这块进来我们进一下源码啊,这就进到这儿了啊,你发现它这块啊,这个呢就不用关心了,主要看这个啊super。它一虚的话呢,是不是就找到我们哈map了。其实里边也没干啥是吧,就把这个临界值呢给哎,不是临界值,我们这个加载因子0.75呢,给确定了一下,所以呢,基本上没什么作为啊啊这块我们就直接出来了。
04:01
啊,接下来的话呢,我们看一下这个put方法的调用,现在我们比较关心的呢,也是这个put的行为,好进着这个源码,首先呢,是这个Y6这个值的一个装箱啊,就要调这个Y6OF5了,这个我们再直接跳出来,我们再进到这个源码里边,好就进到这儿了,然后进到这儿了,大家注意看一下哈,我这个辅导方法是谁的。看这儿。对,相当于呢,我们现在呢,我们是通过啊,咱现在回到这个代码层面啊,咱是通过这个link的哈希map调到put,你发现这个put呢,调的仍然是哈希map里边的。啊,有人说,诶我这块我点一下,我点那哈尼map这个其实不太准,因为我恰好这块我写成是个多肽了是吧。而且要多态的话呢,我们按住CTRL键,是不是认为你是左边的是吧。诶当然呢,你现在真正我们执行的时候,你发现呢,这个我们点一下这儿啊,他确实执行的时候呢,是谁那就是谁发现他还真是哈金。OK啊,那这个put VR呢,我们进入源码呢,你发现还是这个哈希map。诶,这个先是哈希了哈,哎,我们出来一下,然后再点,诶这边呢,就我们这个put VR还是哈希map里的。
05:05
诶,这这块还是哈希map啊,它总得有一个位置不是吧。因为你签押的时候呢,你是不是得记录天下的先后顺序了啊,所以你总得有个位置不是,哎,那么大家你猜一下,你看我们在哪不是呢。不用考虑了,肯定是是吧。肯定还是哈奇map里的哈,再往后走。哎,这块呢,是不是真的要添加了。诶这块呢,就我们现在关心的点,你这有个new node了啊,添加的话呢,你应该跟哈map就不一样了,我们再进一下这个源码。再看。确实不一样了。所以说呢,就是我们在这个啊,整个咱们从这来看哈,我们通过这个link哈map去添加元素的时候呢,它一开始用的都是哈信mapb里边的,当我们真正要添加的时候。说白了就是你现在呢,我们怎么算能加呀,先一次哈希二次哈希,然后呢,一个一个比这个值,像这些呢,跟哈希map都一样啊。当我们真正要加的时候呢,说你有一个双向链表了,那就按照你自己的逻辑来加,诶所以呢,才回到我们这个位置的。
06:04
好,那么这块的话呢,我们就看到了一个非常重要的一个方法,回过来我把它呢就写到这儿了,啊说呢,这个link的哈希map它重写了。哎,咱们这个哈希map的如下方法。好,这个方法呢,我们就直接呢,就粘过来啊,咱们往前来这样整一下啊。这块大家你看一下这个不好看,就把它再拽到这儿啊,所在我们另一个的map,它点一个N垂哟。他自己内部有个恩水啊。他这个nri的话呢,是你有这个link哈,Map的一个nri,那现在我们其实感兴趣这个nri长什么样是吧,好把这个N呢,我们点一下啊长这样。好,CTRLC一下直接回过来啊,底层的一个结构啊,这个我们就站到这儿。来这呢,就说一下另的哈希map内部呢,定义了一个ENT。他这块呢,又叫ENT了哈,这个ENT的话呢,继承了哈希map的node,哈希map这个no里边呢,它本身呢,是不是有一个有一个哈西有个key,有个value,还有一个那个next是吧。
07:08
哎,这就是单向列表这样一个结构,它在它的基础之上呢,你看。是不是多了一组,就是你前一个后一个是谁这呢,我们其实就能证明这个双向链表,不就是看这吗。哎,就发现了啊,所以这块你看我们用了一个它之后,然后呢跟诶你把这个呢,再放到我们这个链里边,其实这块呢,就是记录一下前一个后一个,哎这呢就是专门的给他去连接先后顺序啊,添加记录一下这个添加的先后顺序的这样的一个指针了。这个细节呢,咱们就不用去看了啊,基本上这事呢,我们看的也比较清楚了,就看到这儿了,这就我们增加了一对双向列表啊。哎,双向这个,哎链表啊OK好,那么关于另一个含义麦吧,那咱们就说到这就可以了。哎,这呢,我们就做了个证明啊,OK,行,那这个说清楚之后呢,诶,我整个这个断点呢,我就结束了啊接着的话呢,我们稍微的再提一下,这叫哈西set和这个link的哈希set啊,前面呢,我们也提到了,它长得呢就跟我们说的ma有点像,这个哈西set它的底层使用的就是。
08:11
对,咱们说那叫哈西map啊,而这个link的哈西底层使用的就是link哈西map。使用的是。诶link,诶哈希map,所以说呢,在这个比视面尔当中,为什么没有人去问你哈希set和link哈set呢,首先呢,就是这两个结构我们开发中用的比较少,所以呢也不不爱问你啊,再者来讲的话呢,就是问你呢也没啥意思,因为真要问你的话呢,其实你就直接呢,你说底层使用的是哈map,那下边呢,我给你讲讲哈map。所以完全这个题目呢,就变成哈希map了,那还不如直接就问你哈希map了。那就这样啊好,那这个证明的话呢,其实也很简单啊,直接我们CTRL一下,咱就来一个叫哈希set。啊,这块我们点一下这all places啊,比如以1.8为例进来,好这块我们首先呢去使用这个构造器,我们new一个哈希set啊里里边呢就帮我们扭了一个哈希map了,然后呢,我们通过这个哈呢,我们去调一个爱的方法。
09:10
这个时候的话呢,其实呢,它就底层掉了一个map的这个put方法了,把你这个元素咱们set里边放的是一个一个的元素,其实呢,我们就相当于是放的是个K。啊,然后呢,在这个set中,你说放在哪儿呢?其实这块呢,主要取决于你map当中啊,这里边儿呢,就是针对你当前这个T算你放在哪而已。啊,其实呢,放在就是map里边,然后封装成呢,其实也是一个entry或者是一个node了,只不过呢,哎,它呢Y6值是一个常量。全局常量,然后呢,是new了一个object啊,前面我们稍微也提到过一下啊,你说他为什么这样处理呢。对,它相当于就是这样个场景哈,如果我们从一个map的角度来看的话呢,这呢叫key级,这呢叫Y6级,呃,你要从一个set角来讲呢,就是这块呢,我们只考虑key,这就是个set,然后呢,它把数据呢都放到map里了,大家都指向了此static,也就是说只有唯一的一个。
10:06
啊,一个值,这个值的话呢,它是new的一个,就是它呢没有整合now啊整闹的话呢,万一你要是调相关value的一些方法,是不是就控制人了是吧,它呢避免你控制人,然后这块呢,我们就拗一个东西,那拗谁呀,拗的其实也没有实大实的意义了,干脆就拗一个object得了。哎,所以这块呢,你看AVE其实也没有什么实打实的这个意义了啊,哎,就new了个它了,保证呢,你这个Y不空就行,然后此时我们关键点呢,只是key,所以它就是个set。哎,所以整个这put行为就不用再往里去细看了啊好,那么再对应的我们CTRL呢,叫a link的,哎,叫哈希set。好link的还下,然后呢,我们也是啊CTRL f12一下,诶先纳去,哎提供这样的一个。构造器是吧,中国这个构造器呢,我们又调虚荷了,这个虚荷呢,是不是就到了我们哈西set了。诶,我们点一下就到这儿了是吧,这块的话呢,你发现呢,是不是你有了一个叫link的哈希map。
11:03
那既然如此,所以呢,你再通过这个link哈set去调at方法,那就是调map的这个at的方法,哎,Map的put方法。Put方法的时候呢,你实打实的用的是它,那其实就按照我们这个link的map的特点往里边去put它了。所以呢,我们另用了哈,为什么也能添加记录添加的顺序呢?因为你里边是拿着它put的,他呢能记住,所以你也能记住。哎,到此为止是吧,我们就都说清楚了。好,那这样的话呢,我们就把其他的这些结构呢,这个底层源码呢,基于哈map啊,我们要弄清楚之后呢,相关联的一些结构呢,就都清楚了。好,那么这个内容呢,我们讲完之后呢,咱们课后这块呢,有两个小的题目,诶这两小的题目呢,让大家呢再找找感觉啊,第一个的话呢,这是个练习,这个练习呢,你看是这样写的啊,刚才我扭了一个哈奇map往里边铺的啊,31 31 47 45啊这样的几个元素的这个过程。哎,这个过程的话呢,我们稍微的可以通过这个。哎,断点方式我们去做一个查看啊,这呢我们就做一个debug了。
12:04
啊,没问题啊好,那么此时的话呢,我们就执行第一行代码,第一行代码呢,这块咱们其实也不用去看它的源码了啊,我们就直接的就把它就过掉了,诶那么这一行执行完以后啊,咱们其实呢,这不就有一个map的对象了,哎,如果呢,我现在使用的是JK1.8的话及以上的版本的话,这时候其实底层的这个table啊。是不是并没有创建?对的啊好,所以呢,我们再往下执行一行,诶,你首次添加完以后,我们这个推步呢,就实打实的给创建了。好创建好以后呢,我们打开呃,这时候呢,其实一共是有15个呃角标到十五十六个元素,然后呢,我们刚才这个31和张三呢,这个31呢,我们得计算它,哎现在自动装箱成一个in了,然后呢,按照in特这哈库的方法计算哈一是吧,然后再哈二。然后再确定它的底层存储位置啊,最终确定的话呢,它是在这个位置。好大家看啊,这个位置的话呢,就是我们实打实的这个叫node了吧。因为这个数组是个node数组是吧,好,这个node型的这个数组里边呢,咱们说过是不是有这样的几个属性啊。
13:05
还记得吧?好,那这几个属性里边的这个哈希是不是二次哈希值啊。对的啊,所以说我们这个31的话呢,你可能算完以后呢,就是31这个答为什么还是31,这个你就不用研究了哈,总之它是31,它为什么在这个角标15的位置呢。诶,这个你看我们来一个计算器哈。这个呢,咱们找一下这个十进制的双字节,这儿呢,来一个31,但是你看这个31的这个后四位。是不是就四个一啊。好,这四个一呢,我们跟15求个与,是不是还是四个一,所以呢,它不就放在角标15的位置了吗。啊,那这块呢,还一直31KEY呢,就是我们这个啊一嘛,31YY6呢,就是张三嘛,这样好,你看下边我又来个31,这时候呢,是不是会发生Y6的一个替换了。对啊,我们再往下走一步,你看这个时候呢,还是就这一个元素啊,此时的我们这个Y6值呢,变成李四了。所以此时的put方法呢,体现为就是修改的行为。
14:00
啊,没问题啊好,然后下边来个47,这个47呢,你看我们也把它呢,执行一下47,诶你发现呢,它跟我们当前的这个呢,就都放在一起了。诶这个呢,47呢,如果算下它的这个二次哈义值还是47,然后我们在这块呢,啊,你看清一下47,你看巧了。诶,它的最后这四位呢,还是四个一,所以这块呢,我们得到呢,就还是15,所以它也要放这,它也要放这呢,咱俩去比一下汉一值。是不一样啊。I值不一样了,就没有必要再去比这个E方法了啊,所以直接就放过来,因为呢,我们用的是GT1.8及以上的版本,所以呢是旧的元素指向新的元素。所以呢,这时候我这是47啊,这是K,这是Y6啊,这呢是一个no。啊,没问题是吧,好下边这个45啊,再往下呢,添加一下45的话呢,算完以后呢,它就不在这儿了。哎,45你看它这个哈,值呢,是45这块你也清一下啊,45这是1101。呃,这个呢,是八加四加一嘛,13那不就是13吗。
15:02
哎,所以呢,它就放在这儿了。在这儿,这儿这儿。比较清楚吧。那OK哈,行这个再执行,这就结束了。好,通过这个呢,我们再去体会一下这样一个过程啊,然后呢,在这个诶课件这块呢,我稍微的把这个图啊,我也放到这儿了。图呢?在这啊打开,诶这里有一个这个PPT哈。诶,这个呢,我放在就咱们刚才说的这样的一个题目,这里边呢,想让大家体会的点呢,就是说我们在这个node里边哈,它其实有好几个属性,一个呢是封装了key和value了,另外呢,因为是单列,所以你会记录一个,另外呢,还有一个就是会把这个哈希值也作为一个属性给固定。啊,这个大家细节要注意一下,所以呢,下边这个过程是不是就刚才说的这个事儿啊,这个31张三不就放在这儿了,然后后来的话呢,这个李四呢,跟他一个位置啊,这个而且K都一样,就替换成李四了,然后再来了一个这个,哎47王五,哎这不就得这样了吗。
16:00
然后再来一个45兆六啊,他这也就在这儿了。诶这样个情况,好这块呢,大家稍微的记录一下啊好,那这块呢,为啥我要强调说这个哈,一值呢,没有没有变是吧,它相当于呢,把这个noe这个值呢,就给固定下来了,哎大家回忆一下,咱们当初呢,讲前面这个。诶,哈希set的时候,哎,当时呢,让大家呢,做过一道题,就这道题。两个person是吧,添加进来了,然后呢,对其中的一个属性呢,是不是改了,然后有啊又怎么着的是吧?这个题呢,当时呢,大家做着可能会有点迷糊,那现在我们讲了哈希map的底层源码之后呢,诶咱们再来看一下这个题,你会更清晰一些。好,我进来了啊,针对于我们当前呢,是把这个person对象呢,放在咱们的哈西里,虽然是哈,其实里边就是map了。啊,那这个person的话呢,咱们相应的这里边儿ES和呢都不少都重写过了啊,诶这个就自动生成的了,好回过来这时候我们再把这个过程呢,咱们跑一下啊好断点一打,然后呢1DE bug。
17:02
好过来了,诶这呢,我就直接呢,就下一步了啊,这个执行完以后的话呢,那么底层对这个赛来讲,Map呢,是不是就创建好了。哎,Map注意此时呢,咱们还没有添加数据呢,所以它里边的table呢,就是闹嘛。诶,OK啊,下边呢,我们就先造了俩对象,这个不用多说,现在把其中的第一个对象添加到我们的set里边,这个添加的话呢,诶添加完以后,我们这个推步就有了。黑呢,这不是15个长度就有了。然后这时候呢,去计算一下,我们P1调用它所在类的哈数的方法叫哈值一,然后在二次哈希一下,总之最后得到结果呢,就是当前这个。注意啊,是我们这个P拿着1001和AA算出来的这个哈希值呢,是33111。哎,这个呢,Node是不是已经就像我们刚才看PPT一样,这个node这个对象造好了,这个哈希这个属性值就是33111。然后你的就是我们的这个person的这个P呢,就是我们这里边这个A了是吧,没问题啊,诶是不是点开一下啊,这个就看不到了啊,这其实是A了啊。
18:05
哎,不是A。说错了哈,这个呢,不是A啊,是咱们整个这块呢,是当key的是吧,我们放到side里边那个Y6是不是那个new object。是我这的吗?对吧,OK啊行,然后这个next没有,然后我现在再去艾特一下,然后一走。好注意看啊,这是我们这个P2呢,计算了一下,哎,我把这个收起来,你发现这个P2呢,是在这儿的啊,它的这个哈一值呢,算的是这个数。啊,如果大家你要感兴趣的话呢,你就这块你再算一下呗,听一下,比如说就拿它来说33174。33174,你看一下他的这个。这个是四加二是吧,C2是不是六啊,哎,所以就放这呗,然后这个值的话我就不算了啊,这个你算一下之后呢,肯定是七。所以他就放在七,它放在六,这没毛病是吧?这个呢比较简单啊,好,接着我往下走,此时的话呢,我把这个P的这个name呢改成CC了,嗯,现在呢,你看它是1001AA的哈,然后往下走一步,这不就改完了吗?不就改成CC了吗?
19:06
啊,改好了啊好改好以后呢,现在我们去一下这个P。APE,注意我们前面呢,光讲过这个添加的一个操作木的整个的过程呢,跟我们添加呢,其实是类似的。那拿着这PE呢,你对应的这两个属性值。啊,就是先一次哈希,二次哈希,是不是看一下你这个元素到底应该在哪儿是吧。哎,在哪儿,我们这时候呢,你注意咱们是拿着1001CC。是不是算的它的一次哈希和二次哈希的值?然后呢,为什么我们这块木之后呢,你发现呢,根本没有删掉呢。你看都走到这儿没删掉。对,因为我是拿着1001CC的二次哈希值吧。二是那个哈移值的话呢,呃,就是有可能是在这儿,也可能不在这儿,我不管你那个位置到底是在哪儿,假设你哪怕就在这儿了,咱们俩的哈移值也不一样。因为这个含义值是不是1001AA算出来的。
20:00
对,你RC算的数跟我这肯定不一样,不一样,咱俩就认为不同了,那你肯定删不了我呀。对吧,没问题哈,好,然后接下来我再去艾特一个叫1001CC了,我就添加是1001CC啦,然后我们走一下,巧了。也在这儿。还真就在这儿了。啊,这个题目设计的就很巧是吧。啊好,你看啊,我们拿着1001CC,我算的这个哈希值,结果呢,它的哈希值呢是33175。哎,这个3175呢,你这块你也可以看看啊,33175,这是八加。不是四加二加一。七嘛是吧,哎,这不就在这儿嘛,这个3311呢,其实也是啊,所以呢,就是他俩的这个,诶都是在这个索引期的位置的。而且你看还真是都1001CC啊,这很巧,哎,那这时候你看这个过程咱们俩呢,我也放到这儿了,咱俩先哈希一下吧,一哈希不一样吧。
21:00
对不一样,那是不是就直接进来了。所以呢,你看看似那两个一样的,根本就没有机会去ES,因为哈希都不一样了。所以就进来了,好这块呢,所以就有三个元素啊,那接下来我们再添加一个元素。这个呢叫new一个PERSON100AA,诶这个呢先算哈值,很显然它的哈值其算完以后也是33111。那这时候呢,怎么办呢?对,我一上来的话呢,这块呢,要添加发现呢,也要添加到这儿,然后呢,这个331要跟你一样了,跟你一样了,然后咱俩就E一下呗。你是1001CC,我是101A,咱俩不一样。所以呢,这个就接着比下一个吧,下一个跟他比的时候呢,你是他,我是33111,咱俩还一直不一样。所以呢,是不是我就跟你俩都不一样了,所以呢,你看我们这时候再执行一步,这样直接不就加到这儿了吗。呃,因为它就是33111,它虽然跟这个一样,但是他俩的这个值当初我们改过哈。所以呢,就看这几个元素就全都加进来了。
22:01
这样呢,我们再去理解前面我们讲的这道题,大家应该就会更清晰一些啊好,那通过这个题目呢,Debug大家下来也可以走走,然后彻底的话,把我们这个map底层这样一个结构呢,给大家弄清楚,OK。
我来说两句