面试必问HashMap知识点（附源码）

我会带着你远行 2023-03-02 05:29 26阅读 0赞

文章部分摘于：[点击查看原文][Link 1]

在Java中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。（**详见上一篇文章浅谈数组和链表**）HashMap就是将**数组和链表**组合在一起，发挥了两者的优势，我们可以将其理解为链表的数组。jdk1.8之后，又加入了红黑树的结构，就变成了**数组和链表加红黑树**的组合。

### ** 我们先了解一下Map的体系结构：** ###

![20200728094222138.png][]

由体系继续图我们可以知道，HashMap是继承了AbstractMap，下图是源码图：

![20200728094612296.png][]

然后我们继续往上看，AbstractMap实现了Map，下图是源码图：

![20200728094723469.png][]

### HashMap的结构解析 ###

HashMap底层存储结构

![20200728115619575.png][]

数组里面每个地方都存了Key-Value这样的实例，在Java7叫Entry在Java8中叫Node。默认的Key与Value都是null。

**每一个节点都会保存自身的hash、key、value、以及下个节点，下图是Node源码。**

![20200728102018475.png][]

**当HashMap的结构是数组的结构图：**

![20200728100933541.png][]

**HashMap是比如put插入新的元素的：**

因为他本身所有的位置都为null，在put插入的时候会根据key的**hash**去计算一个index值，**Hash的公式：index = HashCode（Key） & （Length - 1）**

就比如我put（”小明“，18），我插入了为”小明“的元素，这个时候我们会通过哈希函数计算出插入的位置，计算出来index是2那结果如下。hash（“小明”）= 2。

**HashMap是比如put插入新的元素后的结构图：**

![20200728101227944.png][]

**HashMap的结构为什么需要链表？**

数组长度是有限的，在有限的长度里面我们使用哈希，哈希本身就存在概率性，就像”小明“和”明小“我们都去hash有一定的概率会一样，就像上面的情况我再次哈希”小明“极端情况也会hash到一个值上，那就形成了链表。

**当HashMap的结构是数组+链表的结构图：**

![20200728101820183.png][]

**新的Entry节点在插入链表的时候，是怎么插入的？**

**java8之前是头插法**，新来的值会取代原有的值的位置，原有的值就顺推到链表中去，就像上面的例子一样，因为写这个代码的作者认为后来的值被查找的可能性更大一点，提升查找的效率。**在java8之后，改为尾插法。**

**在java8之后，为啥改为尾插法？**

数组容量是有限的，数据多次插入的，到达一定的数量就会进行扩容，也就是resize，**在多线程的情况下对该HashMap进行插入，**因为resize的赋值方式，也就是使用了**单链表的头插入方式，同一位置上新元素总会被放在链表的头部位置**，在旧数组中同一条Entry链上的元素，通过重新计算索引位置后，有可能被放到了新数组的不同位置上。

我们可以看到链表的指向A->B->C

**Tip：A的下一个指针是指向B的**

![20200728103327161.png][]

因为容量的问题我们扩容了一个新的HashMap，这时候就需要将旧HashMap中的元素全部放到新的HashMap中，通过**重新计算索引位置后**，有可能被放到了新数组的不同位置上。

就可能出现下面的情况，大家发现问题没有？

**B的下一个指针指向了A**

![20200728104051954.png][]

一旦几个线程都调整完成，就可能出现**环形链表**

![20200728104127897.png][]

如果这个时候去取值，悲剧就出现了——Infinite Loop。

**什么时候resize呢？**

有两个因素：

**Capacity：HashMap当前长度，默认的长度是16。**下图是源码图：

![20200728110613585.png][]

**1<<4 **这里使用位运算，**位与运算比算数计算的效率高了很多**，之所以选择16，位运算(&)效率要比代替取模运算(%)高很多，主要原因是**位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。**

那么，为什么可以使用位运算(&)来实现取模运算(%)呢？这实现的原理如下：

X % 2^n = X & (2^n – 1)

假设n为3，则2^3 = 8，表示成2进制就是1000。2^3 -1 = 7 ，即0111。

此时X & (2^3 – 1) 就相当于取X的2进制的最后三位数。

从2进制角度来看，X / 8相当于 X >> 3，即把X右移3位，此时得到了X / 8的商，而被移掉的部分(后三位)，则是X % 8，也就是余数。

上面的解释不知道你有没有看懂，没看懂的话其实也没关系，你只需要记住这个技巧就可以了。或者你可以找几个例子试一下。

6 % 8 = 6 ，6 & 7 = 6  
  
10 & 8 = 2 ，10 & 7 = 2

运算过程如下如：

![format_png][]

所以，return h & (length-1);只要保证length的长度是2^n 的话，就可以实现取模运算了。

**因为位运算直接对内存数据进行操作，不需要转成十进制，所以位运算要比取模运算的效率更高，所以HashMap在计算元素要存放在数组中的index的时候，使用位运算代替了取模运算。之所以可以做等价代替，前提是要求HashMap的容量一定要是2^n 。**

**既然是2^n ，为啥一定要是16呢？为什么不能是4、8或者32呢？**

既然一定要设置一个默认的2^n 作为初始值，那么就需要在效率和内存使用上做一个权衡。这个值既不能太小，也不能太大。

**太小了就有可能频繁发生扩容，影响效率。太大了又浪费空间，不划算。**所以，16就作为一个经验值被采用了。

因为在使用不是2的幂的数字的时候，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的**HashCode本身分布均匀，Hash算法的结果就是均匀的**。这是为了**实现均匀分布**。

LoadFactor：负载因子，默认值0.75f。下图是源码图：

![20200728110633364.png][]

怎么理解呢，就比如当前的容量大小为100，当你存进第76个的时候，判断发现需要进行resize了，那就进行扩容，但是HashMap的扩容也不是简单的扩大点容量这么简单的。

**扩容分为两步：**

第一扩容：创建一个新的Entry空数组，**长度是原数组的2倍。**

第二ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。

**为什么要重新Hash呢，为什么不复制过去?**

是因为长度扩大以后，Hash的规则也随之改变。

Hash的公式： index = HashCode（Key） & （Length - 1）

原来长度（Length）是8你位运算出来的值是2 ，新的长度是16你位运算出来的值明显不一样了。所以放的位置也不会相同。

**1.8的尾插是怎么样的呢?**

因为**java8之后链表有红黑树**的部分，大家可以看到代码已经多了很多if else的逻辑判断了，红黑树的引入巧妙的将原本O(n)的时间复杂度降低到了O(logn)。红黑树的知识点(可以看我写的另外一篇文章[Mysql数据库索引数据结构学习篇][Mysql])

**使用头插**会改变链表的上的顺序，但是如果**使用尾插**，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。

就是说原本是A->B，在扩容后那个链表还是A->B

![20200728113946888.png][]

Java7在多线程操作HashMap时可能引起死循环，原因是**扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。**

Java8在同样的前提下并不会引起死循环，原因是**扩容转移后前后链表顺序不变，保持之前节点的引用关系**。

**Java8就可以把HashMap用在多线程中呢？**

即使不会出现死循环，但是通过源码看到put/get方法都没有加同步锁，多线程情况最容易出现的就是：无法保证上一秒put的值，下一秒get的时候还是原值，所以线程安全还是无法保证。下图源码图：

![20200728120851990.png][]

![20200728121208932.png][]

**为啥我们重写equals方法的时候需要重写hashCode方法呢？**

因为在java中，所有的对象都是继承于Object类。Ojbect类中有两个方法equals、hashCode，这两个方法都是用来比较两个对象是否相等的。在未重写equals方法我们是继承了object的equals方法，**那里的 equals是比较两个对象的内存地址**，显然我们new了2个对象内存地址肯定不一样。HashMap中的链表结构，它的inex是相同的，如果链表下有多个元素，我们怎么知道其中的那个是我们想要的那个元素呢，这时候就需要**equals**！是的，所以如果我们对equals方法进行了重写，建议一定要对hashCode方法重写，以保证相同的对象返回相同的hash值，不同的对象返回不同的hash值。

**链表与红黑树之间是如何让转换的？**

默认情况下，当链表的长度大于8且整个hash桶中的元素大于64的时候就会转为红黑树（两者条件都必须同时符合）。下图是源码图：

![20200728120339796.png][]

![20200728120351491.png][]

当红黑树中的元素小于6的时候将转换为链表。下图是源码图：

![20200728120414296.png][]

[Link 1]: https://www.processon.com/;jsessionid=013E07E0613AED7A10E1E6E87ACE212F.jvm1
[20200728094222138.png]: /images/20230208/a7b653b75beb4fb2bd75b6f7914cc7f7.png
[20200728094612296.png]: /images/20230208/0963dbbf673b468b824830db79400c97.png
[20200728094723469.png]: /images/20230208/c2a584a914344184bc2cae5a9955cd00.png
[20200728115619575.png]: /images/20230208/e7aa68ba636046a4a440ccd88029f340.png
[20200728102018475.png]: /images/20230208/9047082c9d3d44a6ad0c46ef542b239e.png
[20200728100933541.png]: /images/20230208/3c4a216265a141aba1700960faeac54b.png
[20200728101227944.png]: /images/20230208/f3565207fb694e92aa9a8b521e1801ac.png
[20200728101820183.png]: /images/20230208/d542151aa6f04dc1ad1dfebcab79967a.png
[20200728103327161.png]: /images/20230208/69dace310ab442b2a588a63c0844a214.png
[20200728104051954.png]: /images/20230208/98ebe44abc3f452690cec63f18a361e9.png
[20200728104127897.png]: /images/20230208/0edc89b5f8464b6093055717d91d18ee.png
[20200728110613585.png]: /images/20230208/0d2c7b7c93e14e58a9e42040fbe1341b.png
[format_png]: /images/20230208/d6f8ddaac7a8492f95b84ed75737d574.png
[20200728110633364.png]: /images/20230208/415caa4c6967408a86c57ba939d7cbac.png
[Mysql]: https://blog.csdn.net/weixin_38007185/article/details/107369086
[20200728113946888.png]: /images/20230208/81e2757cc4c24c18bf53da696fdbd0f3.png
[20200728120851990.png]: /images/20230208/41f8899318854d6e9bb8e9573d93e2ef.png
[20200728121208932.png]: /images/20230208/302dbea196d240a2aa93389466f7e1a3.png
[20200728120339796.png]: /images/20230208/3f2ebcdcef4e49fd83d07c1717ef31bc.png
[20200728120351491.png]: https://img-blog.csdnimg.cn/20200728120351491.png
[20200728120414296.png]: https://img-blog.csdnimg.cn/20200728120414296.png