【面试知识点】一文带你深入了解HashMap

谁践踏了优雅 2023-03-04 05:26 126阅读 0赞

> ☞梦想进大厂的一只程序猿☜
> 
> ☞期望毕业前力扣刷够400题☜
> 
> ☞正在复习数据结构和算法☜

#  #

**目录**

HashMap的底层原理：

面试官：HashMap的存储原理：

面试官：在我们节点插入链表的时候，是怎么插入的？

面试官：为什么会被尾插法所替代呢？

面试官：HashMap的扩容机制

面试官：为什么要重新Hash呢，我直接赋值过去不行吗？

面试官：那是不是意味着Java中我们就可以吧HashMap用在多线程了呢？

面试官：HashMap的默认大小是多少？

面试官：那为啥是16呢？或者 Hash为什么不直接取模运算呢？

面试官：为啥我们重写equals方法的时候需要重写hashCode方法呢?

面试官：处理HashMap线程安全的场景？

面试官：HashMap的 hash(Obeject k)方法中为什么在调用 k.hashCode()方法获得hash值后，为什么不直接对这个hash进行取余，而是还要将hash值进行右移和异或运算？

面试官：jdk1.8引入红黑树后，如果单链表节点个数超过8个，是否一定会树化？

--------------------

# HashMap的底层原理： #

**1.7 数组+链表**

**1.8 数组+链表+红黑树**

# 面试官：HashMap的存储原理： #

在数组里面，我们存着Key-Value这样的实例

在java7中叫做Entry，在java8当中叫做Node

![20200801135326429.png][]

在插入的时候，他会根据key的hash去计算一个index(下标)，然后存储

每个节点(Ebtry、Node)，包括了hash值(通过hash计算出来的)、key的值、Value的值以及next(指向下一个节点)

![20200801135411288.png][]

#  #

# 面试官：在我们节点插入链表的时候，是怎么插入的？ #

在java8之前，我们使用的是头插法，如下图所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70][]

现在我们发生hash冲撞了，我们会将key:刘的的插入到key:黄的上面：如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 1][]

但这样的话，我们没办法进行查询呀，所以我们会再一次进行操作：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 2][]

在java8之后，这种头插法被尾插法所替代。

# 面试官：为什么会被尾插法所替代呢？ #

第一个是因为我们在java8中，引入了红黑树，我们当链表的长度大于8个时，开始转变红黑树而当红黑树的节点个数小于6个（默认值）以后，又开始使用链表。我们在进行尾插法的时候，还能够遍历一遍size()，来判断要不要进行树的转变

第二个就是：避免多线程死锁

# 面试官：HashMap的扩容机制 #

HashMap的扩容机制主要和负载因子和当前长度有关

![20200801135956578.png][]![20200801135957802.png][]

*  Capacity：HashMap当前长度。
 *  LoadFactor：负载因子，默认值0.75f

如果当前存储的数量 > 负载因子 \* 当前长度，就进行扩容，扩容是怎么样来扩的呢？

分为两步

*  扩容：创建一个新的Entry空数组，长度是原数组的2倍。
 *  ReHash：遍历原Entry数组，把所有的Entry重新Hash到新数组。

# 面试官：为什么要重新Hash呢，我直接赋值过去不行吗？ #

我们来看HashMap的Hash方法，Hash方法是：

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

扩容之前&8，扩容之后&16，肯定就不一样了

关于链表闭环这个问题：

为了避免链表成环的产生(这也是HashMap不支持多线程的原因)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 3][]

我们如果多个线程的话，第一个线程B---A

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 4][]

但是我们第二个线程才刚刚跑，A---->B的，这时候就会发生链表的成环（这里的叙述应该不太明确，可以请教一下面试官并顺便舔一波）

在Java8中，我们引进了红黑树，我们使用头插会改变链表上的顺序，但使用尾插法的话，不会改变我们的顺序

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

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

#  #

# 面试官：那是不是意味着Java中我们就可以吧HashMap用在多线程了呢？ #

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

（这里可能就会扯到多线程了，以及死锁、操作系统等）

#  #

# 面试官：HashMap的默认大小是多少？ #

在Java1.8中，默认大小为16， 而且还给我们特别注释了出来

#  #

# 面试官：那为啥是16呢？或者 Hash为什么不直接取模运算呢？ #

我们刚刚说到，在进行hash计算时：

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

重点在后面的（Length - 1)，我们可以想：我们进行Hash的意义是什么？

我们想让他映射到我们的数组下标对吧，我们取默认大小16的话，写成2进制减去1，看一下：0000 1111

我们回顾一下关于&的操作：只有都为1或者都为0，结果才为1

所以，我们可以看到，不论你的HashCode（Key）是什么，最后一定会在0000~1111之间的

# 面试官：为啥我们重写equals方法的时候需要重写hashCode方法呢? #

在Java中，所有的对象都是继承Object类的Ojbect类中有两个方法equals、hashCode，这两个方法都是用来比较两个对象是否相等的。在未重写equals方法我们是继承了object的equals方法，那里的 equals是比较两个对象的内存地址，显然我们new了2个对象内存地址肯定不一样

*  对于值对象，==比较的是两个对象的值
 *  对于引用对象，比较的是两个对象的地址

HashMap是通过key的hashCode去寻找index的，那index一样就形成链表了，index都可能是2，在一个链表上的。

我们去get的时候，他就是根据key去hash然后计算出index，找到了2，那我怎么找到具体的呢？

equals！是的，所以如果我们对equals方法进行了重写，建议一定要对hashCode方法重写，以保证相同的对象返回相同的hash值，不同的对象返回不同的hash值。

不然一个链表的对象，你哪里知道你要找的是哪个，到时候发现hashCode都一样，这不是完犊子嘛。

# 面试官：处理HashMap线程安全的场景？ #

面试官，在这样的场景，我们一般都会使用HashTable或者CurrentHashMap，但是因为前者的并发度的原因基本上没啥使用场景了，所以存在线程不安全的场景我们都使用的是CorruentHashMap。

HashTable我看过他的源码，很简单粗暴，直接在方法上锁，并发度很低，最多同时允许一个线程访问，currentHashMap就好很多了，1.7和1.8有较大的不同，不过并发度都比前者好太多了。

# 面试官：HashMap的 hash(Obeject k)方法中为什么在调用 k.hashCode()方法获得hash值后，为什么不直接对这个hash进行取余，而是还要将hash值进行右移和异或运算？ #

如果HashMap容量比较小而hash值比较大的时候，哈希冲突就容易变多。基于HashMap的indexFor底层设计，假设容量为16，那么就要对二进制0000 1111（即15）进行按位与操作，那么hash值的二进制的高28位无论是多少，都没意义，因为都会被0&，变成0。所以哈希冲突容易变多。那么hash(Obeject k)方法中在调用 k.hashCode()方法获得hash值后，进行的一步运算：h^=(h>>>20)^(h>>>12);有什么用呢？首先，h>>>20和h>>>12是将h的二进制中高位右移变成低位。其次异或运算是利用了特性：同0异1原则，尽可能的使得h>>>20和h>>>12在将来做取余（按位与操作方式）时都参与到运算中去。综上，简单来说，通过h^=(h>>>20)^(h>>>12);运算，可以使k.hashCode()方法获得的hash值的二进制中高位尽可能多地参与按位与操作，从而减少哈希冲突。

# 面试官：jdk1.8引入红黑树后，如果单链表节点个数超过8个，是否一定会树化？ #

不一定，它会先去判断是否需要扩容（即判断当前节点个数是否大于扩容的阈值），如果满足扩容条件，直接扩容，不会树化，

因为扩容不仅能增加容量，还能缩短单链表的节点数，一举两得。

[20200801135326429.png]: /images/20230208/5238bbad53674d2aa503ea78b8cde212.png
[20200801135411288.png]: /images/20230208/3e99630997fe4edaa61226d9fed39cad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70]: /images/20230208/62e741e8417e45f1896eaabef58d7dff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 1]: /images/20230208/d51144b2e79045539c406880a2119e3a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 2]: /images/20230208/6ec64338c7f74ac696979066ab68e21c.png
[20200801135956578.png]: https://img-blog.csdnimg.cn/20200801135956578.png
[20200801135957802.png]: /images/20230208/2e64616f925f42ec83c15024b0c374e1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 3]: /images/20230208/84b22eedfbc24f7fbb68520caeca5965.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwOTE1NDM5_size_16_color_FFFFFF_t_70 4]: /images/20230208/8599b0da9cb34651933dacc0996427d9.png