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

行，那上午的话呢，我们把这个哈奇map它的底层实验原理的这个过程呢，给大家说清楚了，就这个过程呢，其实更重要一些，就大家能够把这个事儿呢表述清楚，这个呢是面试当中一个非常高频的问题啊，所有同学呢，其实都要掌握哎，你能把这个过程呢描述清楚，那么接下来呢，我们就开始来看一下这个底层的源码，那通过这个源码呢，我们去验证一下，咱们刚才说的这个过程呢，是对的啊，所以呢，先把这个事说清楚啊，下边呢，我们来看下这个源码，看源码的话呢，因为咱们说到了这个哈map呢，在七和八当中，它的这种实现呢，是稍有区别的，所以我们就先来看这个七，那七的话呢，我们就简单一点啊，直接呢啊，拿到这个七灯七当中的这个源码，这是这个K7啊，UPDATE7的这样一个小版本当中找一下Java YouTube啊，我们找一下这个叫哈希map。来哈map，然后CTRLC粘过来，放到咱们当前这个model下，不妨呢，我在下面呢，专门放一个包，放这个源码SRCOK啊CTRLV行就放到这了，放到这以后，我们下面来看一下这里边这个代码啊，它这个报错呢，也是正常的，涉及到一些这个负类的一些结构啊，或调一些其他接口啊，就没有了啊没有呢就报错了，但是不影响我们看这里边咱们想看的这些结构，首先我们先看一下这个构造器，CTRL一下找一下这个叫空单的构造器啊，空单构造器过来以后啊，这个大家呢，我们讲解过程当中也会涉及到几个，呃名词啊，这几个名词呢，大家也要关注一下，你看我在这个PPT当中呢，其实也说这个事儿了。

我看我放哪一页了啊，在这呢，哎这呢也是面试当中这个问到的一个题哈，说这个扩容机制，默认大小，附载因子，这个吞吐的临界值，哎，像这些概念的话呢，是什么意思啊，这呢就是面试当中被问到的一个问题，那我在上面呢，也提供了一页，就是来描述这里边儿的一些常量或者一些变量，它表示的是什么意思，在这也有写啊，下来呢，大家可以看一看，另外呢，咱们奖励源码呢，也会说到。

好，我们开始这个构造器，那么构造器一进来的时候，我们看到一个Z调用当前的重载的构造器，这里边儿呢，提到了两个，一看就是常量了，第一个叫默认的一个初始化的容量啊，点开就是16啊，这呢其实就影响着我们首先呢在底层创建的数组的长度，那么除了这个变量之外呢，呃，常量之外还有另外一个呢，叫默认的加载因子，这叫做加载因子叫0.75。那这个加载因子是干什么的？这个咱们等一下再说，那有了这个之后呢，我们点开看一下这个构造器，这呢是16，这个呢是0.75，好，首先这个是不是小于零不是，然后这个呢，诶是16了哈，是不是大于我们这个整数相当于一个，哎较大，这个大值是吧？Max哎，叫最大的一个值，这个也没超过，所以这个也不用管这个，这个加载因子呢，是不是小于等于零啊，也不是，所以直接呢就蹦到这来。这个in的一个capacity是一，然后那个一是不是小于我们的这个initial，呃，Capacity，嗯，这个initial capacity，咱们刚才呢，过来就是一个石六了啊，其实这块呢，咱们目前呢，其实也也用不着哈，呃，这个就涉及到后边呢，咱们造构造器的时候哈，如果大家呢，呃，去new一个哈希map，这个额外的说一句哈，大家呢，如果是一个这个哈希map，你这个位置写的是15，举个例子啊，那你以为底层创建数组的长度是15，其实不是15。

这其实呢，还是16。啊，你写的是15呢，你看你这个15就相当于是这不是刚才传就传到这了嘛，传到这儿的话呢，这个先有个一，一呢小于15，它就向左一一位啊相当于呢，这不就是变成二了啊，二呢又小于15，再移就变成四，再再移啊变成八，再移变成16，其实这个capacity派呢，决定了我们底层造的数组的长度啊，它一定是二的多少次幂啊，所以你你要是显示的掉某一个哈奇面的构造器写的这个数，它不一定就是我们底层数组的长度了。

小这额外插了一句，啊，那么还接着往下去说，这呢提到一个load factor，就是我们这个参数传过来的这个值，0.75就给了咱们当前对象的load factor。那么这个load factor我们就称作叫加载因子啊，这个加载因子就是0.75是默认值，那么在接下来mass当中，这个capacity capacity，咱们刚才这不是，呃，这这个问题当中，它本身这是16，然后移过来以后，其实还是16哈，那么16呢，去乘以这个0.75，得到的呢是12，哎，对，后边呢，有一个这个最大值，这个咱们刚开始呢，都涉及不到它这两个取最小，那就是这个了，这个呢叫thhold，这个呢，就我们所谓的叫临界值，临界值呢，哎，我们现在能看到它的值是16乘以0.75是12，那么这个12影响什么？影响的是我们扩容的那个时候。

哎，空中的时候，哎，那么什么意思呢？你看我们这个数组的长度是16。那么什么时候去扩容呢？哎，这个扩容的时候呢，不是说我们这个16乘不下，放第17个元素时候扩不对，因为你有有可能永远呢，不可能存码。因为咱知道有些呢，这个你放的元素是不是以链表的方式存了，哎，有些位置呢，这个数组当中它就永远空着，所以呢，你不能等把这个数组都填完的时候呢再扩。嗯，那这个时候呢，他就会提出在什么时候扩呢？啊，他不到16个时候呢，就开始扩了，这块呢，提到了一个值就叫做临界值，这个值就影响了我们扩容的时候的一个这个临临界情况啊，就是超过12个的时候呢，我们就开始扩容。哎，这个意思啊，回头呢，咱们再呃稍微提一下这个扩容的事情啊，那这呢叫临界值，那接下来我们去造了一个NT垂的数组，这个数组的长度capacity啊，这不就看到咱们这个剩下来的这是16啊，那这个16的话，我们就给了这个table，这个table呢，点开看一下，就是咱们当前这个哈希map当中的这样的一个底层结构，这也就是我们说哈希map呢，首先底层用的是一个数组，这个数组呢，就是entry类型的啊，叫table。

这是在我们JDK1.7当中啊，然后呢，再al左回来再回来啊到这这样的话呢，我们就造好这样的一个数组了，这呢是我们啊要看的话呢，大家就看到这就行，就是在我们一开始去new的时候啊，底层呢，造了一个长度为16的这样一个数组，OK，那么接下来呢，我们关心的就是往里去put数据的过程。好，再打开我们呢，Ctrl o一下，看一下这个put方法的调用，好在这现在呢，我们把一个key一个value呢，想放到我们当前的这个哈希ma克当中，看看怎么做的，首先他看一下这个K呢，是不是no，如果是no呢，它其实也往里放了，那么你能想到就是这个逻辑呢，在哈希table当中呢，哎，就不会这样的去设计了，哎哈，Table呢不能够放now汁。

哎，这个我们的哈西map能放是因为呢，它单独的就是关于是no的这个情况呢，给处理了一下啊，那这块呢，咱们就过掉了，那就是这考虑的就是它能够放no的key啊这样的情况，那么在接下来首先呢，我们先计算一下当前K的一个哈希值。啊，这个含义值怎么计算的，大家如果感兴趣呢，你可以点开稍微看一眼啊啊进来啊，这是个零啊这块呢，说它是不是一个string，这个值是多少呢？啊一开始它又是一个不这个这个false啊不用管，哎这个有同学问这个叫transcent，这个是关键字什么意思，这个咱们后边呢，讲到呃序列化的时候呢，再说啊嗯，那么现在的话呢，这个值呢，它其实个false啊，放在这块其实就进不来了，那就到这儿了，这儿呢，相当于是先拿到我们这个key，这个对象的一个哈扣的一个方法，调用的一个呃值得到，得到以后呢，又做了一个异货的操作。

那么我们讲的这个未运算符呢，在咱们这个集合的底层源码当中用的比较多，因为它的效率呢，会稍微高一些啊，哎，这样做完以后呢，又这样做了一个无符号右移啊，又做了一个异惑操作等等等等这块呢，大家细节的就不用看了啊，你可以理解为呢，整体啊，算出来一个这个哈希值，中间呢，也涉及到对我们重启的这个哈希code的方法的一个调用啊，不完全是由它决定的。行，那么再接下来，嗯，再回过去啊，再回过去，回过去呢，这得到这个哈希值了，这个哈希值并不是我们在数组中的存放位置，因为有可能这个数比较大，哎，我们在这个描述当中说了说经过某种特定的算法，然后得到在数组中的存这个存放位置，它掉的呢，就是这个index for这个方法，这呢是拿到这个哈希值，这有一个table的length，然后我们可以点一下，我们看到呢，它里边咱们当时讲说说，大家可以考虑用这个取模是吧。

哎，你看到它不是取的模，哎，它呢取的是这个，呃，余也是未运算符，这个效率呢，应该比咱里要高一些啊，你想要拿一个数这个取一下这个模，你去除呗，得是吧，来除一点点这样去算，那要是求这个与的话呢，这不直接你这是你这个哈值，然后这个LAS咱们当前是16减一，就是15 15保证就是你后边的。四位都是一是吧，哎，然后我们求这个与与负号的话呢，你像这些位置都是零啊，与的话呢，就是保证你上下都是一，结果才是一，所以你这个与完以后呢，这些不都是零嘛，哎，只有末位这四位呢是有数据的，对这四位有数据，它就不会超过16嘛。这个数啊，因为咱们现在要找你在数组当中的哪个索引位置啊，那肯定不能超过16了，哎，咱们数组目前呢，就零到15嘛，哎，就是哎，我们这用的是一个这个语运算啊，数个位运算符了，那么通过这个方法调用，咱们呢，就获取到在数组中的一个存放位置了。

啊，你始终想咱们上午讲的那样一个事儿啊，那么找到这个I位置以后，我们现在呢，就需要把咱们当前的这个KY6呢，哎，就放到我们这个I位置上，那现在关心的就是I位上本身有没有数据。所以首先呢，我们取出当前这个table当中的I位置上的这个数据，那么这个数据先看一下它是不是no，那如果说它不等于no，那就进去，如果它等于闹呢，说明这个位置上就没有元素，我们先考虑这个位置上没有元素，那就没有进去。那没有进去是不是呢？就直接把它加上就完了，哎，这个爱的一个entry，这是你当前这个K的这个哈希值了啊，那这是你自己的key value6，然后存放到就是Di这个位置上呗。啊，这个ad是不就进去预存了啊，哎，这块呢，其实有个判断，这个呢，就是刚开始第一次的话呢，这个size也都不会超的，当然也可能不是第一次啊，后边某一次填，只要你这个位置上没有元素就能够添加进来，这块咱们先呃不具体去往这看啊，先回过去先看一下这块这个逻辑。

啊，那么如果你这个位置上呢有值，那就意味着呢，你呢，不等于no。哎，你脑子里边大家可以浮现一种场景，就是你这个数组当中，这个位置上是有值的啊，那有值的话呢，也可能不止一个，对我在这个PPT当中，这个这不也画过啊，比如说你就在这一只上，它可能有好几个啊，这个这是八的啊，看七的吧，那有可能你这个位置上本身有好几个，那好几个的话呢，那就涉及到一个对比了，所以你看我这写的是一个for循环啊，那么你这个位置既然不是no，那行吧，那咱们就得去比较了，比较的话呢，首先进来看一下这个已经在这个位置上的这个值的哈希值，和你现在把我们要存的这个KY6这个含义值呢放一起看，你俩呢是不是，是不是等等。

等等是不是就你俩是还一直一样啊啊，那如果说这个位置要不等呢。不等，是不是后边这个就不用看了，那就意味着说，如果这个不满足，这要不满足，那就该是不是相当if没进去，是不是该这个next了，NEX的话呢，就取一个取一个还不知道啊，又判断又不等，假设呢，你跟已经存在的一个或多个都还一直不等，那这时候呢，咱们是不是又得结束for循环跑，这就艾了。哎，对，相当于呢，就是哈希值如果不一样呢，诶也能够添加成功，咱也说过了，那再接着哈，那如果呢，发现跟某一个哈希值呢，相等，哈希值相等了，那接下来还得再比。那比的话呢，其实本质上来讲是equals，但是呢，他之前有一个，呃，相当一个更便捷哈，Equals呢，毕竟得一个一个去比里边的内部的数据了，他先呢，看看你俩这个K啊是不是等等。有可能地址都一样啊，地址都一样呢，那就更省事了，省着去ES了啊，哎，但本质上来讲呢，就是看一下我们这个K它到底呢，是不是算是相等的了啊，算是不是算相等的了，那么呃，只有这个是这个也是处，它才能够进去，那如果说这个位置呢，不相等，相当于这个if呢，还是没进去。

衣服没进去又走啊，还是没进去又走，还是没进去，那yag呢，就是我们现在要存的这个啊，我们要存的这个K和V啊，这样判断的话，假设都是false哈，那相当于是不是我们就得又添加了。对吧。是这意思吧，哎，你跟现有的这些呢，哎，哈一值刚刚才说了不一样，不一样呢，直接就调查了，那哈一值呢，如果说一样，那这个呢，发现equals呢还是falses，那不还得蹦到母来调它吗？哎，那都是相当于叫所谓的我们叫添加成功，咱不是写了情况一情况二情况三吗？哎就都蹦到这了，那么有可能在这样补比的过程当中呢，哈希值一样这块判断的时候呢，返回处了。

它一直讲这块返回处了，相当于我们这个要填的这个KY6是不是真的就算是相同的了，那相同干什么事呢？你看哎这个E呢，呃，是咱们本身这个数组当中已经存在的已经添加的这个数据啊，我把已经添加的这个数据的这个value呢，当中一个叫old的value啊，把它返回，那同时的话呢，把我们新放进来的这个value呢，充当了你这个E的这个value。这就相当于是不是做了一个覆盖。对，就相当于或者叫修改，将我们新的这个哎key value放进去K呢，因为跟已有的某一个ENT垂东西K相同了，那我们就拿这个新的value呢，去替换原有的这个位置上的value啊，就是做这样一个事情。啊，这呢是一个修改操作，那咱们在刚才描述这个过程当中，是不是也说到这个替换的事情了，那么刚才这里提到情况一情况二，还有情况三，哎，这三个情况呢，是不是就都蹦到我们这个叫添加这个位置了。

啊不都崩这个位置了啊，那么咱们这个for循环呢，其实也就算呃结束了啊，就是这个，哎这个操作呢，整体能看得到的就是我们会把这个I位置上这个数组元素先找到它的第一个，然后通过那个的方式呢，相当于把这个列表呢，这几个就都走一遍，直到呢，你找找不到它的下边的元素了，只是这个链表这一支上的这些元素都变利的一个，哎，这个for循环啊。那么刚才我们看到了啊，在这个便利过程当中呢，有几种情况呢，是需要调用到这个I的entry这个方法的，相当于我们要把当前这个KY6呢添加过来，那么这个哈希呢，就是我们通过这个方法算出来它的这个叫哈希值啊叫哈希值，注意咱们这个前面这块写的这个哈希值哈。这个哈希值的话呢，不完全是调到这个方法，实际上呢，是这个方法呢，又参与到我们的这个方法当中，是这个计算出来这个哈希值啊，把它那叫一个哈希值。

嗯，那么嗯，爱的entry，爱的entry的话呢，我们此时呢就看一下，因为你现在呢，毕竟要把这个元素添加进来啊，我们就加进来这儿呢是我们要填的这个KY6，这呢是它要存放的位置，好看一看下边啊怎么加说呢，如果你这个size呢，大A等于我们的叫thhold。后咱们刚才看的叫12吧，哎，Size的话呢，就是我们已经存了几个了，那大于等于是不是假设已经存了12个了，等于包含，那我们现在要加的是不是就是第13个了，哎，如果呢，你这个位置假设这是处。假设这是处，这是处，这是个且且的话呢，是不是这也得看一下，那就是你我要放的这个位置呢，看看是不是确实也有元素。

啊，是不是也有元素啊，它这是什么意思呢？就是说咱们刚才说了，说长度大于12的时候呢，就要扩容，其实严格上来讲呢，还不是说呃，只要大于12就一定会扩容。他先看一下，比如我们现在已经存了12个了，你现在要存的这个元素，那就是第13个，它不是说呢，放这个元素就一定要扩容，他先看你要放的这个位置啊，空不空。你要是空空的话呢，其实那就干脆放着得了，我现在就懒得去扩容了。因为你放到这呢，其实也没有形成链表，因为行成链表呢，便利会稍微麻烦一点啊，你这个位置本身空着，那我就塞到你这个数组位置得了啊，这就是表示你就不你就是不空是吧，不空的时候这不是扩容，反之呢，就是说你要是空的话，我就不扩容了呗。这个意思啊，那么啊，这是我们刚才说的这个事儿啊，那什么时候会进去rees呢？就是你要么大于12了，并且呢，你这个位置发现还不空。啊，你要想形成新的列表，那就别生成列表了，Rees一下得了，就是我们所谓的扩容，扩容为多少？原来table的长度呢？乘以二，哎，那就是扩容为原来的二倍。

哎，这个回过来，我们下面呢，这不是提到这个，哎扩容的问题啊，扩容为原来的长度二倍，这呢我们又提说在什么情况下呢去扩容，哎，就是呢，我们要超过它的临界值啊，这个我们在这儿描述一下啊，不断的添加过程当中会涉及到这个扩容问题，那么当啊这个超出临界值时。其实这块要说也不对是吧，超出临界值呢，还得保证你要填的这个位置呢，它是一个非空的是吧，这其实要说的就就挺细了啊，超出临界值这我加个小括号吧啊且存要存放的位置且。哎，要存放的这个，呃，位置呢，这个非空时啊，那么就去扩容，哎默认呢，哎扩容为原来的二倍是不？我们就看到这个源码，它是这样写的，好，这呢就做了一个扩容啊扩容的话呢，这个是，哎我们还需要把原有的那些数据呢，得重新去计算一下，什么意思呢？就是原来呢，比如长度是16了，这里边呢，有几个元素呢，是这种指针的方式去存的，你现在呢，对它进行了扩容了，这这些位置呢，都重重新放啊重新放。

哎，复制过来的时候呢，还得重新去计算一下，他们在这个新的数字当中到底应该在哪个位置，那就有可能原来呢是列表，后来呢，计算完以后呢，是不是就不再是同一个位置放了，是有这种可能性的。啊，这是这样子的，所以这块呢，也相对来讲比较消耗这个内存啊行，这是这个事儿，那也有可能的话呢，我们不需要扩容，不需要扩容的话呢，那么直接就蹦到这儿了嘛。哎，我们去做一个create entry行还是呢，把我们这个哈一值key value和这个你要放的位置呢，放在这里边啊，调的叫create entry，所以上面这块逻辑呢，主要体现的是扩容的事儿啊，那如果不需要扩容，直接就做添加就进来怎么加，这是JDK7首先呢，把我们新的这个元素呢，直接放在我们这个数组的这个位置上，直接放在我们数组的位置上，那么我们就会想有可能人家这一只上本身是不是就有元素啊。

那有元素也不管，反正我这个新元素我就放在这个数组上，那么旧的元素怎么办呢？哎，这我你看我们就这个这个。嗯，先创建了一个塔哈，诶不是创建一个塔，这呢是先把这个原有的这个微商元素先取出来。是吧，哎，我们现在呢，要把这个KY6呢，这不是放在这个位置上嘛，我先把你本身这个数组当中这个微上元素先取出来，这是原来人家存的这个位置啊，然后呢，我们去拗一个新的一个entry，这个新的entry呢，就是我们现在要放的这个KY6，然后呢，你又写了个E，这个E呢，就是你原来这个位置上的E，嗯，你看我们这new这个entry这呢做什么事呢？这个构造器当中这个E啊，这个E相当于是付给这个N了哈，这个N呢，是作为咱们当前造的这个对象的next出现的。

是吧，这个N呢，这不是就咱们所说的这个数组，是一个N垂类型的数组啊，这个N垂类型就是我们对应的这个内部类，就这N垂，它有可能会以链表的方式去存，所以呢，我们会看到他这个源码，这不是在这会有一个next类型的一个声明嘛，单向链表。哎，单向链表，然后呢，咱们把用的当前这个KY6呢，是不是就通过这个构造器造的对象，把原来你这个数字上这个位置呢，作为我们当前造的这个对象的一个next出现了。哎，回过来。嗯，就是把你原来数组这个数组上的这个位置上元素放到这儿，作为我们新的这个KY6它的一个next出现，然后把我新到的这个呢，是不是放到你现在的一个数组的一个位置上啊，这呢就是我们所看到的这样一个情景啊啊这呢是人家可能已经放了这样的几个数据了，现在呢，你要新放一个，这个呢恰好就在这儿，咱们刚才第一行代码相当于把这个呢记录成一个E了，然后呢，咱们新造了一个，新造以后呢，哎把我的这个next我指向你了，但是你呢就别放这了，我把我呢我放这儿了，哎，我放一个蓝色啊，我放这了，然后呢，我的next呢就指向你，你呢还指向你原来的这些，哎，就成这么着了，这呢就是这几行代码所描述的一个状态。

好，那么就这样的一直去放，我们呢，就能看到在JDK7当中，首先呢是一个数组结构，其次的话呢，在这块我们会看到它是一个链表的一个结构，那你要是很多的都在这个位置上，那就以列表的方式一个一个往上去练就完了，这是我们GDK7当中的这个源码的一个分析啊，那么我们就说到这儿。