day24_集合/09-尚硅谷-Java语言高级-HashMap在JDK7中的底层实现原理

那下边呢，我们来说一下这个第三个事儿，也是咱们这里边的一个难点啊，就是哈希map的底层实现原理。哈奇map的底层实验原理，这呢是非常高频的道面试题，那我们要想说清楚，它需要呢，看这个源码啊，这块呢，我先不看源码，先给大家把这个事儿呢说清楚，大家呢把这个过程呢先能够理解了，理解以后的话呢，我们再通过源码做一个验证啊，要是一上来带大家看源码，回过来以后呢，你发现有点懵，那这里边这个代码呢，还是有一定难度的啊，我们把这个过程呢先说清楚，大家呢更多关注的就是这个事儿能够表达出来，然后通过源码验证，那么要想说清楚，又由于呢，我们在JDK7和八当中呢是不一样的，我们不妨呢先以JDK7来说明，然后呢我们再说一下八和七的区别，好，这个以JDK7为例说明，下边呢，我们就开始来说了啊嗯，开始来说的话呢，我们先怎么着呢，我们先说一下这个问题吧，哈希map map等于new一个哈希map通。

我们实际开发中这个操作来讲，此时呢，我们以这个空参的构造器为例，去创建一个哈希map的对象。那么这个时候呢，做了什么事，我们首先说底层，这是我们是JDK7啊，说在实例化以后，哎实例化以后，然后呢，底层创建了，哎长度是哎实六的一个哎数组，哎一位数组啊。底层创建了一个长度是16的，因为数组，这个数组呢，我们会关心关心它的类型，这个类型呢，就是N垂类型。这个数组的名呢，叫table。相当于我们这个哈希map中的数据，大家一会往里边put的数据呢，都是放在我们这个数组当中的。

哎，放在这个数组当中，那么entry也很好理解，因为你KY6呢，不都是哎构成一个entry嘛，我放了好多entry，那就是entry的数组呗。啊，长度为16的一个N垂数组，好，这呢是第一个过程完事啊，那么下一个过程呢，我们通过这个map呢，咱们去调它的一个铺的方法，我放一个呢，叫不妨我叫K1，叫VALUE61了，这呢是往里边添加数据，当然呢，在这个put的过程当中，咱们呢，为了更好的说明这个问题哈，就有可能我在前面呢，已经put了一些操作了。咱们想说的是某一个，呃特殊状态下啊，这个put方法的一个执行，呃不光是针对于第一种，第一次添加这个put啊，呃这个呢，我们说这个可能啊，已经啊执行过这个啊多次啊这个put了啊那这呢，我们就相当于说一个普通的一种这个put的一个情况，那现在呢，我们希望把这个K1V1放到我们的这个呃数组当中，呃对数组当中，那怎么去放这样的一个过程啊这呢我们去说明，嗯这个时候我们说呀说首先。

哎，首先呢，你要想往里放，我们呢，得知道放在这个数组中的哪个位置，怎么办呢？首先哎，这个计算这个K1啊它的一个哈希值，或者这样这样说吧，首先呢，我们调用啊这个K1它所在类的哈希扣的方法，哎然后呢，计算啊K1的一个哈希值，哎然后呢，此哈希值哎然后呢，经过。啊，经过某种算法计算以后。啊，计算以后，然后呢，得到在我们这个N垂数组中的存放位置。

它的一个存放位置，这个能看懂吧，跟咱们前面说的那个哈希map啊哈set呢，其实有点像啊，这个哈利值的话呢，可能它非常大，这个可能比如12345，你这个数的话呢，我们数组根本就没有这个角标，所以我们得处理一下，处理完以后的话呢，你看它到底是在哪个位置上啊，这个咱们当然也说过一个比较，呃，好理解的就是大家直接取膜，这个16啊，这个零到15就是看能角标了，但实际上它不是取的膜。哎，它不是情况，它其实用的是个与啊，咱们看原码的时候大家就知道了，那与的话呢，就与的实物啊，呃，那它呢，经过某种算法以后呢，得到在N垂数组当中的这个存放位置啊，那下边呢，我们就关心一下，它想往这个位置上放，那这个位置能不能放，那这时候呢，我们下边就分情况了，说如果啊，此位置上此位置，呃，这个这个上的这个数据为空。

那就意味着这个位置上没有数据，那就我们的K1V1呢，就直接添加成功啊，那此时的这个K1。啊，这个V1啊，它呢就添加成功。这个填到我们这个数组位置上，数据呢是N垂啊，大家注意，其实我们这呢，呃说叫双列数据一对一对，其实还是一个一个的，咱们比的都是这个N垂，只不过呢，是拿这个N垂中的K作为一个判断存在哪的一个标准而已啊，我这写的叫K1V1添加成功，实际上呢，是N1添加成功啊。啊，这呢就添加成功了，那么接下来说，如果此位置上的这个数据不为空。那就言外之意，我们这个位置上呢，已经有数据了啊，那不为空，这呢我们稍微多说一句啊，不为空的意思呢，就是意味着。

啊，此位置上存在一个或多个数据，它不一定就一个啊，那么如果是一个呢，那就直接放在这个数字里边，那要是多个的话呢，这个多个呢，还得是以链表形式存在的，这个已经是存在这样的一些结构了。啊，那还接着回过来说说，如果此位置上这个数据呢，不为空，不为空怎么办呢？我们就需要去比较啊，比较呢，我们当前的这个K1和我们这些数据的K1的哈希值，比较我们K1和啊已经存在的一个或多个数据的哈希值。啊，比较这个哈希值了，那下边呢，就得看这个哈希值了，说如果啊对，如果呢，我们的这个K1的这个哈希值与啊已经存在的数据这个哈希值都不相同，就是我的哈希值跟你们呢都不一样啊，那么此时呢，就用不着再调所谓的ES了啊此时呢，咱们这个K1啊，这个Y61相当于它对应的这个键值，对啊，就能够添加成功。

具体添加成功这个怎么往哪放这个咱们一会儿再说啊，这样呢，这时候添加成功了，那么还有一种情况呢，就是我们的这个呃K，它的哈希值和某一个数据的哈希值呢，相同了是吧。诶，哈希值和已经存在的某一个数据的哈希值相同。咱们俩的还一直相同了，接着干什么事呢？对接着呢，不能说还直一样，你俩呢，就ES了啊，你俩就一定一样了，不一定啊，那如果呢，它们还一是相同，那么继续比较啊，这个E的方法啊，继续比较，怎么比较呢？我们是哎调用这个K1所在内的异口的方法。

那杨一之呢，就是你跟谁相同，把相同的那个数据啊，他的那个K放到我们这个K1所在类的那个方法的行参啊，调用他的以后的方法，然后呢，比较。那比较的话呢，又可能会出现两种情况，那如果equals它呢返回先说返回的一个是处吧，哎，先说返回false吧，这个好说一点，那如果你返回false，意味咱俩呢，实际上是不一样的啊，那意味着我们此时的这个K1V1呢，它呢就添加成功了，好，那再接着，那如果。

呃，那么此时呢，它的这个E的方法呢，返回是true，返回是true呢，意味呢，就是咱俩的key呢，是一样的了啊，那咱们要求呢，说这个map中放的这个key呢，是不能一样的，那这时候呢，怎么处理呢。有的同学可能会认为，那么我们这个K1V1是不是就没气了，就进不去了，而事实上呢，不是，那如果此时返回是to首先呢K一样了，那我们怎么办呢？我们呢，就是将将谁呢，将我或者叫使用啊，我们这个Y61去替换啊，替换呢，咱们这个说叫呃相同这个K的啊，这个Y6值。我看这有没有说清楚啊，存在的某个数据，某个数据我这块呢，这样写一下吧，哎，我们写呢叫K2V2吧，Y62啊跟它一样了啊，调用它这个方法，这个呢，当于把这个K2呢放到这里边啊，那么使用Y61呢去替换，哎，我们这个相当于是Y62啊。

那相当于呢，我们此时的put方法，它具有叫修改的功能了，原来呢，比如说人家这块放了一个叫啊，比如叫K叫Tom哈，然后那个值呢，是23，可能表示的是这个年龄啊，现在呢，你又put一下，还叫Tom，显然呢，他俩的哈利值呢和一库托法都是处了，你这写了一个45，你调这个铺的方法，这也是一个铺的方法，调完以后大家如果去遍历，你会发现我们存的数据是to姆谁呀，对，是45，相当于我们这呢，45就把它给覆盖掉了，哎，此时的put方法还仍然表示，哎，还表示为一个修改功能，而不是一个简单的替换了。啊，保证呢，我们这里边儿放的数据呢，首先都不能够重复了啊，那你其实是个修改啊，这就做了一个替换操作，行这呢整个这个过程呢，我们就算是说完了，在这个过程当中，我们提到了几个位置啊，第一个呢，这呢叫天下成功哎，我们叫做情况一。

CTRLC，然后这呢也要填加成功，这个呢叫情况二，这个呢也要填写成功，这叫情况三，那情况一没什么可说的，这个数组的位置呢就空了，直接放到数组这块就OK了，那么关于这个情况二和情况三。哎，这呢相当于是一个补充了啊哎，关于情况二和这个情况三，这个在这个时候呢，添加成功，在这时候呢添加成功这个呢，基于的前提呢，是我们这个位置上都已经有数据了，那你都已经有数据了，我们呢还是想象这样的一个数组了啊那这个位置我想放这儿，这个位置已经有数据了，有数据的话呢，我们就只能是以列表的方式去存储了啊列表方式存储又涉及到一个到底谁指向谁的问题啊这是跟咱们说的哈利菜的对是一样的啊，就是如果呢是量值，这是你新元素，这是八啊七的话呢，是把这个呃新元素放这儿，然后呢，这个原来的旧元素呢，是往外放这样子啊呃，关于氢况二和氢况三，那我们说呢，呃，此时这个KEY1啊Y61，咱们先泛泛的说一下，它呢啊和原来的这个，呃，数据呢，以。

哎，链表的这个方式呢来存储，那么不同之处呢，就是哎七和八里边这个区别了啊哎，那暂时呢，咱们先把这个事呢先描述清楚，先不说这个啊不同，这呢以JDK7呢我就说完了，这呢我以七为例，把这个过程呢做了一个描述。啊，那再往后呢，其实呃，涉及到一个什么问题呢，就是扩容的问题呗。我现在说的主要是一个添加是吧，呃，添加然后扩容这块呢，我们也可以继续的去说明一下啊，就是说呃，在添加还不断的啊，添加过程中啊，那么会涉及到啊这个啊扩容问题啊，那么扩容问题呢，前面我们也见过像扩容string barber的扩容都讲过，那我们此时只需要大家关注它扩容的一个比例是吧？哎，那么我说默认的哎扩容方式，哎，我们说扩容为哎原来容量的二倍，哎扩容完以后呢，然后并将原有的数据呢，是不是复制过来。

来数据啊复制啊过来行，这呢就可以了，这呢是咱们JDK7当中哈希map的一个底层实验原理，哎，我把这个过程呢就描述清楚了。