day24_集合/12-尚硅谷-Java语言高级-HashMap在JDK8中的源码分析

好，那刚才呢，我们把这个J这个七当中哈奇map的这个源码呢，我们就带着大家呢串了一下，大家呢下来呢，也可以自己呢走一走这个过程，这个源码呢，其实你看它代码量不是说特别多，但是呢，这个逻辑思维呢是非常严密的，哎，大家呢，你看一看这个源码，而且呢自己也能完全看得懂，其实是很有成就感的啊，而且以后呢，你看别的代码呢，其实凡是涉及到数据结构这种层面的，其实是有难度的，你要看一些只是调方法呢，其实难度没这么大啊，你把这个能力提升上来以后呢，再看一些不如它这种复杂的代码呢，会更简单一些，就相当于能力就提升上来了啊把这呢我CTRL一下，我先都注释掉啊。不看了，那么接下来呢，我们看看这个这个八当中这个情况，看看这个八里边呢，是不是像我们下边输的这样一种状态啊，诶ctrl shift呃，T一下我们呢输入叫哈西啊map，呃，我们看到是咱们八里边的这里的啊来点开好，那这个八呢，看起来比七呢就会更痛苦一些啊，因为呢有红黑数了嘛，毕竟啊，当然有一些呢是一样的，刚才也讲过了，一样的这块呢，大家可能就诶稍微轻松一些啊先ctrl o，我们呢先去看一下它这个构造器啊。

构造器呢，我们看到一进来的时候呢，它并没有像刚才这个七当中一样，把我们底层去造完这个数组，它没有，它呢里边就写了一个非常简单的一个属性的赋值，把当前这个啊造的哈希map对象的一个属性叫啊加载因子负了，负值位呢叫0.75。哎，负值位呢叫0.75，好，复完值以后呢，没干别的，所以说呢，我们在这个八当中看到底层呢，并没有创建长度为16的这个数组啊，并没有看到这个数组啊，好，那么接下来的话呢，我们就往里边去放数据了，这我写了一个，它这个呢先看一下也行，一会呢我们添加的时候你也能看到啊，哎，我这呢写的说在八当中我们底层数组叫node，不叫entry了，这个非常容易证明啊，你就往上找就完了。

啊，这是咱们注释掉的啊，这个就关了，咱们看一下这个哈希map，哎，这边是这个巴黎的帮找。大家看看这咱们在这个哈尼map在七当中的时候呢，你看到它是个entry类型的啊，在咱们这儿呢，相当于叫node类型，其实本质上没有太大区别，换了个名啊，里边呢，该有的几个属性都有，咱们刚才那个七当中的entri呢，有哈有哈希，有key，有value next，它这一样还是这么几个事儿，而且呢，它还是实现了Mac里的ntri。啊，就是本质上其实还是一个N垂啊好，那么咱们下边呢，看谁呢，咱们ctrl o看一下这个put的方法。看破的方法，我们现在呢，需要将一个k value6呢放到咱们哈奇map里边了，呃，首先呢，它里边去return调了一个这个方法，这呢跟咱们之前一样，算出它的一个哈希值，对哈希值里边呢，只不是还是用了一下我们现有的这个K的哈希值，但是它呢，不是作为咱们说的这个哈希值啊，哎，还稍微呢去做了一些处理啊，把这个呢，我们也叫做这个哈希值了，哎，拿到它的哈希值，它的key，它的value啊，这两个呢是一个是for一个处啊，这个咱们不用过多的去关注啊，哎，我现在呢需要put进去，这呢是哈义值，这是当前要存的这个KY6。

好，往下走，这是咱们首次啊，首次啊，这块呢，会稍微的痛苦一点，大家得坚持一下啊，首先我声明一个tap是not类型啊，No它两个变量不用管了，咱们当前的这个table，我们在构造器当中没有对它进行初始化，所以呢，它是no，它付给它判断它是不是no，是no，这是个true，那true后边不用管了，往下看，你要是个处。啊，我们现在要干什么事，就这个tab呢，我给你reces一下，Reces呢，就是去扩容了，我如果我们是首次调用，那确实呢，这个是处，它就蹦到这来了，所以我们就要看一下reces reces咱们知道是干什么事了啊，底层帮我们把这个数组造好了，造好数组这个事其实就在这个方法里边做的好看一下这块呢，稍微有点。

有点这个思维量啊，首先当前这个table呢，是一个闹，这相当于是个闹好首先你这个呢，等等于闹处吗？是处是处呢，把零负给他，这是零，然后surprise后的当前那个临界值，临界值呢，也没付临界值负过吧，临界值没有负，那会负的是加的因子是吧？哎，构造器里的，所以这个值也是零啊，这个零给了它了，好下边的定义俩变量，这俩变量都是零，下边old的cap是不是刚才说这是零嘛，所以这个不进去啊，然后呢，你这个old，它old它这不也是零嘛，这个也不进去，所以呢，就进到这了，进到这啊叫default initial capacity16出现啊，16给了它，然后呢，诶，这个是0.75乘以这个16，哎，这个12出现，好这两个出现了，出现以后再往下这个它等于零嘛，这不刚才算它是12嘛，所以这个呢不进去好把这个12。

付给咱们的code啊，出现了一个临界值的负值，这个就有值了，然后再往下，嗯，我去扭了一个node，好，这个数组出现了，又了一个node，这个node是new cap new cap往上推，哎，对是在哪呢，它是零，嗯，咱们刚才是走的这没进去是吧？啊这在这是吧，哎，这是16，所以这呢，我们就把这个数组呢就造好了。啊，数组造好了，然后把造好这个数组给了咱们当前的table。哎，那就相当于咱们在首次put的时候呢，帮我们把这个底层的N，哎不叫N垂类型no的类型的数组呢，就造好了，哎下边这逻辑呢，大家就可以先不用看了啊返回了，哎就是这个返回的，这不恰好就是我们这个新的这个呃，底层这个数组了，现在啊好这个呢，我们就再往回走啊，点这个alt左就往回了啊。

诶回过来，那再总结一下这块就是说呢，我们当前这个table呢，看看你是不是闹，你要是闹的话呢，我们帮你造好，那那就是相当于你首次的时候，它才会进入这个recess，如果呢，你当前这个table已经是有具体的一个数组了，所以它呢就是个false了，哎然后呢，这个诶这块它呢，这不就我们底层数组那个数组长度呢，是不是零不是零嘛，哎不是零的话呢，这个呢，它其实就进不去了，也就是说你要不是首次添加这个逻辑呢，就不用考虑了，好接着往下下边呢，我们这个tab啊这个tab呢，不就是我们底层这个数组嘛，嗯，底层这个数组先呢，这就我们说的啊，判断一下我们在这个新的数组当中的哪个位置，所谓的我们说叫通过某种算法，其实就是这个一个做了与运算啊，找到呢，我们在当前这个数组当中存放的一个位置，把这个位置上的这个值呢给了P啊，那就首先看一下当前我要存。

KY6的这个位置啊，就是这个I了，这个位置上呢，是不是no，如果是no。那是最理想的状态，直接呢，是不是就把它存这就完了，哎直接存这你有个node还一直当前你这个KY6你的下一个没有啊，这呢就是最容易理解的一个事儿，叫添加成功啊添加成功这不是就对应着咱们说的啊，这个呢叫添加成功，第一种情况是吧，然后呢，我们有可能它不是一个no啊，不是一个no呢，那就蹦到这个else里了，好，下边呢，这个又是一段这个代码。

这个那不是no，不是no呢，说明你这个位置上就有值，这就是我们现有的这个位置上的这个值，呃，这个N垂啊，相当于不是叫en垂了，这叫node了，那么先看一下你现在有的这个啊元素，它的哈希值跟咱们现在要要传进来的这个KY6这个哈希值呢，看是不是相等，这块逻辑呢，跟咱们刚才哎那会看到那个七当中呢是类似的，那就是说如果呢，他们的哈希值。啊，如果要是不等这块已经是false了，后边不用管这个相当于就不进去了。这个不进去的话呢，嗯，就是咱们先考虑这个不等啊，不等就相当于是让他要添加成功的，这个呢，先不考虑先不进去，他不进去，然后呢，这个呢是考虑是不是一个吹no的，这个咱们先暂时不管，或者呢，暂时我们这个P呢，先假设它就不是一个以红黑树的方式存的啊，那压G呢，它也不是一个吹no的啊，咱们直接就蹦到这来了，注意这时候呢，是咱们说明这个哈希值不相等啊，哈希值要不相等。

它是只是咱们第一个这个P的这个哈希值不相等是吧，第一个这个P的哈希值要不相等，你看这又整了一个for循环。咱们这个说的事是什么，咱们在七当中看断是直接写了个for啊，他这是先判断一下，然后再写这个for什么意思，就是咱们这呢，底层这个数组当中，我这呢，哎有元素，这个咱们说也可能不止一个元素，假设呢，这有三个我现在要放的元素是它，咱们首先呢，拿它的含义值跟它比了一下说明，哎看到了说他俩的不等，他俩不等那就能马上存吗？不能，因为你有可能你俩不等，是不是咱俩等啊，哎，所以呢，我们下边你要你俩要不等的话呢，咱们是不是跟下边都得。比一下是吧，啊，那要多比一下，这个事可能还比较多，那咱们就先说一下简单的吧，假设他俩等了。咱先说他俩，等了吧。

它俩要是等了，那相当于这个呢就满足了是吧，满足以后呢，我们再看下是是又看这个Y6了，哎，不是Y6又看看这个K呢，它俩是不是到底真正的是ES的啊，当然你俩要是地址都一样，那就懒得去离S了，肯定你这就算是一样的了啊，你要是一样。你看我们做了一个替换。哎，不是剃瓜。啊，就是如果呢，你要是一样一样的话呢，我们把当前这个数组当中这个E呢，我P呢，我把它呢，就存到这个E里了。还没有说这个去替换了啊，我只是把它放在这个E里了，对吧，那这块呢，没有替换啊，没有替换，因为咱们这个KY0还在上边呢，这个E呢，哎，这块假设一开始也不是一个红黑数啊，是不是就相当于他们就都蹦到这块来了。啊对，它就不进这块了哈，哎，这不是负完值，咱们刚才考虑是进去的是吧，进去以后呢，这个假设不，这个也不用看了哈，这个不用看，这个不用看，应该是把这都过了啊，是不是就走到这了，嗯，走到这哈，你这个E的话呢，现在不是no，那不是no啊，你把这个P不是付给他了吗？付给他以后，咱们把这个E就是相当于你现在数组当中这个E其实就是P啊，把它的Y6呢，看成是个旧的啊，旧的话呢，把返回旧的啊，下边这块呢，其实把这个咱们要放的这个Y6呢，替换成你原有这个位置上value，这其实就是个替换的逻辑。

对吧，啊这就相当于是如果呢，你发现啊，你现在呢，要放的这个呢，跟已有的这个呢，哈希值呢是一样的，呃，然后呢，这里边呢，发现value，呃K呢通过E的判断也一样啊那这块呢，相当于是做了一个替换，替换呢value在这这个逻辑呢，啊行，那么呢，每走到这儿没走进去。啊没走进去呢，呃，有两种情况，一种呢，就是你俩的哈希值呢不一样，还有一种呢，就是哈希值一样，但是呢，咱俩这个判断ecos的时候呢，不一样了啊，那这时候呢，也会走到下边啊就是这块媒体，那当然先看到这个，先看这个了啊这个呢，咱们先暂时考虑它不是一个吹no的啊啊没有宏位数，那这时候我们就直接到这个else里了啊，那ya AG呢，就是我们现在这这个数组，我现在这是一个P，现在我们要存的这个元素，跟这个P做对比，发现呢，咱俩呢要么哈希质不一样。

嗯，哈希值不一样，要么呢，就是哈希值一样，但是咱俩ecos的时候也不一样，那仅从这个去判断我这个能不能添加还有点仓促，你还得需要判断它下边可能还会有其他的，所以这就蹦到咱们这个for里边了，哎，蹦到这里边啊，这呢有一个count值是零，没有这个循环的终止条件进来，那么我们先取出P的next。因为你跟P已经比了，那我们接着就比这个P的next，先看P的next呢，是不是个no，如果P的next是no，说明呢，你这个位置就一个元素，就是这个P啊，就这一个元素，那是闹，咱们就进去了，进去以后啊，相当于你看我们这会就新造了一个node，新造了1NODE呢，就是你要放的这个KY6，你就这一个元素跟P刚才也比过了，说明不一样，那咱们就新造一个，新造一个完以后呢，把这个新造的就是你新要添加的KY6作为我们P的next。

这就我们所说的七上八下的下对吧？哎，新的元素呢，方程这个原有元素的下一个，哎，你新的元素呢，下一个不就没有了吗？哎，这是这样一个情况啊，那再往下这个判断呢，这就涉及到说嗯，什么情况下呢，去变成一个红黑数了，这个咱们暂时呢先先不看它啊行，这呢就相当于是添加进来了，这呢是咱们考虑说呃，你呢，下一个没有啊，那如果说你P的next有元素哈，它不是nu不是nu呢，不就蹦到这来了吗？哎，这个始终别别晕了啊，也就跟他比呢，咱们这不是说这个肯定跟他比呢，哈利值要么不一样，要么就ESK的时候呢也不一样，那不一样的话呢，咱们蹦到这个else里，Else呢下边担心呢，就是你下边可能会有好几个啊，咱们呢，这个衣服呢，就判断一看，诶下边没有了啊，没有你这块就直接加成了，那下边还有还有那不就蹦到这了啊还有呢，我们把这个P的next的原有人家这里边的这个列表的这个元素的哈希值算一下，跟咱们现有的哈希值呢比一下，其实又是同样的一个逻辑，相当于就是比P的next的这个元素哈义值，你俩一样不啊，你们的这个K的这个E后方法，嗯，怎么着呢，这不又是这个逻辑吗？这个逻辑呢，是处的时候呢，就能进去处呢，就意味着说你俩的哈希值一样。

你俩的哈希值一样，你俩的E时候呢，也是一样的，行了，你就别再在这放循环了，Break掉相当于呢，找到一个K真的是相同的了，Break完了以后呢，下边呢，是不是又做了一个替换。

这个替换呢，是这个意思啊P，然后本身呢，它下边有这个ne，可能下边还有现在呢，我们是拿着这元素，刚才跟它比呢是不相同的，但是你跟下边这个比的时候发现相同了，相同了，这不就走到这个break这了，然后呢就停了，不要比了啊，后边可能还有不要比了，然后你呢，把你的Y6呢替换了，这个的Y6就跑到这来了。啊，那这个呢，可能不是，那可能下边的是。啊，那就相当于你当前这个呃没有进去，没进去的话呢，我们把这个呃，当初你这个P的next给了E了，然后呢，呃比了你这个E以后，把这个E呢，再给他P，咱们再翻回去，翻回一这V进来，再接着考虑下一个元素。刚才这是P，然后呢，我们它的next这个叫E，现在我把这E呢当成是P，然后我们再看看P的next，不就是又考虑下一个元素了吗？啊，那么一四这样去判断啊，依次这样去判断，就是看一下这个，只要你找到是no了，哎，然后跟现有的这个都没break瑞进去过，那就是哎做一个添加了。

那如果说你要是进去过呢，呃，这个说明呢，就是跟这个以链表存在的某个元素是相同的了，那相同的话呢，就break，然后呢，就做一个替换。啊，这是这个逻辑行，那基本上这块呢，就看清楚了，这里边儿这个，呃，问题是什么呢？就我们看到这样一个结构啊说呢，我们把这个P的next就添加进来了，它这里边多了一个逻辑，多在这个逻辑呢，这提到一个叫啊tree five s hold这个呢是个八，这就是我们所谓的当我们这个链表上的这个数据啊，你往下这个走啊，走走走走走，现在还想添加了，当这个长度呢，超过八的时候呢，哎，超过八的时候呢，它就要把你变成是一个tree的结构了。啊，就重新整合一下，哎，这呢就是这个吹，刚才呢，我们看到那个值叫八啊，那么当超过八就一定要这个变成一个红黑树吗？我们进来以后，你会看到这块的这样一个逻辑，当年这个table呢，不是no啊很显然。

然后嗯，这个再回过去哈，这不咱们就把当前这个数组底层的这个数组传进来的哈，当年的不是no，嗯，这是一个或或的关系哈，嗯，当这是等于no是吧？哎，这个等于no的时候呢，它就能进来，这个呢，咱们不是no，所以不用管它，再看后边这个把当前这个数度的长度给了NN呢，如果要是小于。这呢叫64啊，然后这种情况下呢，它叫re size reces呢，就是不是变成属性结构，是做了一个扩容。什么意思呢，就是我们呢，现在呢，这个底层往下走走走，哎，现在呢，咱们通过刚才那个判断啊，现在我们要再添加的话呢，这个就超过八了。超过八的话呢，这个我们就调到这个方法了，调这个方法进来以后说什么呢？说呢，你要是想走这个方法，这个咱们当前它不是no啊，所以这个不用管了，关键就看它是不是出，如果它要是出呢，就是rees，它是出就意味着当前啊，就现在呢，按说你想变成数了，但是它没有马上变，他说你当年这个数组你的长度是多少啊，长度是N，说你这个长度NN呢跟64比一下，看你跟64比谁大谁小，如果呢，你要这个N小于64。

你要N小于64啊，不要改成数，你去呢扩容。啊，你去扩容只有呢，你要是大于这个，哎64了，这个咱们走下边这个就相当于把我们现有的这一只呢，就改成一个树形结构。他其实想表达的事呢，就是说嗯，你这个一开始这个数组比较短啊，你可能这个设计的有点问题啊，导致这个里边呢，这个都在这一串上了，这个只要呢，我们扩下容，你这个呢，树形结构呢就会减少啊，就是你这个长度本身不太长，这个尽可能的我们也避开用树形结构，毕竟稍微复杂一点啊，但是如果呢，你这个数组长度已经挺长了哈，都超过64了，这个时候的话呢，哎，都在这一只上，那那就用树形结构得了。

啊，是这样一个逻辑啊，这能看到这个值它是64，所以回过来咱们就写的这个逻辑啊说呢，当我们某一个索引位置上的元素以列表形式存在，个数大于八，并且呢，当前速度长度呢，啊还都比较长了，这个时候呢，你再改成回约数，你要是小于64呢，这时候呢，你去扩容去。啊，你去扩容啊，是这样一个逻辑，行，那咱们把这个八呢，基本上就都说清楚了啊在这里边儿呢，咱们会涉及到几个概念啊，啊第一个呢，叫默认的，其实其实就这里边是吧。这里边我写的这个啊，默认的一个初始化容量啊，这是咱们这个大家需要关心的一个事儿啊，一个它还有呢，提到一个加载因子。

哎，这个default漏的factor叫加载因子，这个加载因子它是多少，0.75对，还有一个呢，叫临界值是吧。S后的诶，CTRLC，诶这个临界值，这个临接值呢，就是咱们诶默认的就是16乘以这个0.75啊16，哎，这个啊，这个等于的这样写吧，12其实是啊，那那么在咱们这个J8当中，这不还多了一个叫呃，Tree fair righthold，所以这个时候呢，就转化成红位数，这个咱们看到它是。八。哎，这是这个八，哎，然后呢，看到的这个这个叫mean fair capacity是吧，这个呗。对，这是64。

哎，大家呢，关注一下这里边这样几个量啊，那这几个量里边有一个呢，我们多说几句，就是关于这个量0.75，哎，我们会看到这个map，它不像咱们前面讲的a release a release呢，说底层一开始的容量是多少十，那咱们是不是存前十个元素的时候都不会扩容啊，当咱们放第11个元素的时候呢，才扩容啊，因为不够了，所以得扩，那这块呢，我们发现这个哈希map呢，它底层一开始长度是16，它可不是说当不够16个，第17个的时候扩容的。不是啊，那么问为什么他要提前扩容？为什么不等满的时候再过呢？那就得反问一句话，它一定会满吗？什么叫满呢？是吧，这个就很难说了啊，因为咱们本身往里边放，是不是也不是一个挨一个放的，对，它是通过这个哈希值啊，然后呢，再调了一下那个index form嘛，是吧？哎，说你要放到这第二个元素呢，可能要放这第三呢，可能要放这第四个呢，发现诶开始形成链表了，第五个发现，哎呀，还是链表啊，你放了可能16个，甚至说你放了更多的，有一些位置可能它始终就是空的。

是吧，哎，那么为什么他要提前去扩呢。他得尽可能让你这里边出现这种链表的情况呢，还是要少一些的，还是要少一些，那这呢就有个技术活了啊，那么我们你要是希望它这个链表少，就咱们可以让这个加载因子呢，尽可能的小一些，比如说你要写成一个0.38，那16乘以0.3啊4.8 4.8呢就是400，那相当于超过四个呢，我们就要扩容，那你这时候呢，这个数组的利用率是不是有点低啊啊，这个你要小了不太好，利用率太低了，你要是太大呢，0.9呢，可能链表就有点多了，有啊，那这呢，你得找个相对比较稳定的一个值，就是既兼顾到这个呃数组的利用率，同时呢又尽可能。

这个让这个这个这个链表的结构稍微少一点，哎，通过大量的这个测试啊，你可以说是统计学上的一些这个测试啊，最后呢说哎达到这样一个平衡呢，哎基本上就应该是处在0.7~0.75之间啊，哎这呢就用的这个0.75啊，用它呢来代表这个默认的加载因子。OK啊行，那么咱们把这个底层这个结构呢，就说清楚了。