为什么面试都喜欢问hashmap

柔情只为你懂 2023-06-18 14:54 58阅读 0赞

HashMap的工作原理是目前java面试问的较为常见的问题之一，这里面主要会包含是否用过Hashmap，hashMap的hash碰撞的机制是什么，hashMap是如何扩容的，hashMap的底层数据结构是什么，jdk1.8中对hash算法和寻址算法是如何优化的等问题，那么我们现在就针对这些问题做个简要的分析和解答。

1.为什么在java面试中一定会深入考察HashMap？

hashMap作为一个键值对(key-value)的常见集合，在整个java的使用过程中都起着举足轻重的作用，比如从DB中取值、数据的加工、数据回传给前端、数据转换为json等都可能使用到hashMap，且hashMap作为一个可以允许空键值对的集合，也能实现自动的扩容，扩容的参数值为0.75，达到后自动扩容一倍，这样给一些处理未知数据量大小的数据来说，是很方便的。虽然hashMap是线程不安全的，主要体现在1.7和1.8上，1.7的hashMap在扩容的时候回形成循环链，导致死循环而报错，或者数据的丢失情况，在1.8上，虽然对这方面做了改进，但是仍然是线程不安全的，主要是体现在，若多线程操作数据，如线程A  B同时进行数据的put操作，在put操作前，会进行key的hash碰撞，但是线程A  B有可能同时碰撞且碰撞的值相同，那么就会发生线程A先插入到了碰撞的地方值，然后B也随后插入到同样的地方，导致线程B会覆盖线程A所插入的值，导致数据丢失。所以，在面试的时候，都很喜欢问hashMap。

2.hashMap的底层数据结构

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTE2MTY1NjAw_size_16_color_FFFFFF_t_70][]

hashMap是一个用于存储Key-Value键值对的集合，每一个键值对也叫Entry，这些个键值对（Entry）分散存储在一个数组之中，这个数组就是hashMap的主干，HashMap数组每一个元素的初始值都是null，

![20191203094254955.png][]

hashmap最常用的两个方法就是get和put方法。

我们一般使用put(key,value)的方法存储对象到Hashmap中，使用get(key)方法从hashMap中获取对象，当我们给put()方法传递键值对时，先对键对调用hashCode()方法进行hash碰撞，返回的hashcode用于找到bucket位置来存储Entitry对象，关键点就在于HashMap是在bucket中存储键对象和值对象的，最为Map.Entitry。这一点有有助于理解获取对象的逻辑。若是这样回答，显示出面试者确实知道hashing和hashmap的工作原理。下一个问题接下来就会问hashmap中的碰撞检测(collision detection)以及碰撞的解决方案了：

“当两个对象的hashcode相同时会发生什么？”从这里开始，困惑就开始了，一些面试者会回答因为hashCode相同，所以两个对象是相等的，HashMap会抛出异常，或者不会存储。然后面试者就会提醒有equals(）和hashCode两个方法，并告诉他们两个对象就算是hashCode相同，但是也不一定相等。有些面试者会回答“因为hashCode相同，所以他们的bucket位置相同，碰撞会发生。”因为HashMap使用LinkedList存储对象，这个Entry（包含有键值对的Map.Entry对象）会存储在LinkedList中，这个答案非常合理，虽然有和多种处理彭祖航的方法，这种方法是最简单的，也正是hashMap的处理方法。

“当两个键的hashCode相同，你如何获取对象？”面试者会回答：当调用get()方法，hashMap会使用键值对象的hashCode找到对应的bucket位置，然后获取值对象面试官提醒他如果两个值对象存储在同一个bucket上，他给出的答案：将会遍历LinkedList直到找到值对象，面试官会问因为你并没有值对象去比较，你说如何确定找到了值对象的？除非面值这直到HashMap在linkedList中存储的是键值对，否则他们是不可能回答出这一题的。其中一些记得这个重要知识点的面试者会说，找到了bucket位置后，会调用key,equals()方法找到LinkedList中正确的节点，最终找到了值对象，完美答案。

许多情况下，面试者会在这个环节出错，因为混淆了hashCode()和equals()方法。因为在此之前hashCode()屡屡出现而equals()方法仅仅在获取值对象的时候才会出现，一些优秀的开发者会指出使用不可变的，神明为final的对象，并且采用合适的equals()和hashcode(）方法的话，会减少碰撞发生，提高效率，不可变性使得能够缓存不同键的hashcode，这将提高整个获取对象的速度，使用String Integer这样的wrapper类作为非常的选择。

如果你认为到这里已经完结了，那么听到下面这个问题的时候，你会大吃一惊。**“如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？”**除非你真正知道HashMap的工作原理，否则你将回答不出这道题。默认的负载因子大小为0.75，也就是说，当一个map填满了75%的bucket时候，和其它集合类(如ArrayList等)一样，将会创建原来HashMap大小的两倍的bucket数组，来重新调整map的大小，并将原来的对象放入新的bucket数组中。这个过程叫作rehashing，因为它调用hash方法找到新的bucket位置。

如果你能够回答这道问题，下面的问题来了：**“你了解重新调整HashMap大小存在什么问题吗？”**你可能回答不上来，这时面试官会提醒你当多线程的情况下，可能产生条件竞争(race condition)。

当重新调整HashMap大小的时候，确实存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在LinkedList中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在LinkedList的尾部，而是放在头部，这是为了避免尾部遍历(tail traversing)。如果条件竞争发生了，那么就死循环了。这个时候，你可以质问面试官，为什么这么奇怪，要在多线程的环境下使用HashMap呢？：）

总结：

HashMap的工作原理：

HashMap是基于hashing原理，通过通过put(）和get()方法存储和获取对象。让我们把键值对传递给put(）方法时，它将调用对象的hashcode()方法来计算hashcode，然后找到在bucket的位置来存储Entity对象。当获取对象时，通过键对象的equals()方法来找到正确的键值对，然后返回值对象。HashMap使用LinkedList来解决碰撞问题，当发生碰撞了，对象将会存储在LinkedList的下一个节点中。HashMap在每个LinkedList节点中存储的是键值对对象Entity。当两个不同的键对象的hashCode相同时，它们会存储在统一规格bucket位置的LinkedList中，键对象的equals()方法用来区分和找到具体的键值对。因为HashMap的好处非常多，可以用来做缓存，出于性能考虑，会使用hashMap和concurrentHashMap

原理：

HashMap是用来存储key-value键值对的一种集合，这个键值对也叫Entity,而每个Entity都是存储在数组当中，因此这个数组就是HhashMap的主干，HasmMap数组中的每一个元素的初始值都输null

1.put方法的实现原理：

HashMap的一种重要的方法put(）方法，当我们调用put()方法时，比如hashmap.put("test',"test")，此时我们要插入一个key值为test元素，这时首先需要一个Hash函数来确定这个Entity的插入位置，设为index，即index=hash(test"),假设求出index的值为2，那么这个Entity就会插入到数组索引为2的位置。当插入的entity越来越多时，不同的key值就通过hash函数算出来的index的值肯定会有很多冲突，此时就可以利用linkedList来解决  其实hashmap的数组的每一个元素不止一个Entry对象，也是一个链表的头结点，每一个Entry对象通过next指针指向下一个Entry对象，这样当新的Entry的hash值与之前的冲突时，只需要插入到对应链表即可。需要注意的是，新来的Entry节点采用的是头插法，而不是直接插入在链表的尾端，这是因为hashMap的发明者认为，新插入的节点被查询的可能性较大。

2.get方法的实现原理

get()方法用来依据key值来查询对应的value,当调用get()方法时，比如hashmap.get（“apple”）,这是同样要对key值做一次hash映射，算出来其对应的index值，即index = hash("apple")。前面说过可能存在hash冲突，同一个位置可能存在多个Entry，这时就要从对应LinkedList的头开始，一个一个的向下查询，直到找到对应的key值为止，这样就获取到了所要查询的键值对。例如找apple

第一步：算出key值 apple  的hash值，假如为2

第二步：在数组中查询bucket的index为2的地区，此时找到头结点为Entry6，Entry的key为banana，不是我们要的值

第三步：查找Entry6的next节点，这时为Entry1，key为apple 是我们要的值，这样就找到了对应的键值对，结束。

面所说的就是HashMap的基本原理，可以总结出HashMap的3个要素为：hash函数、数组、链表，如下图：

![format_png][]

接下来对于HaspMap还有很多深入的问题，比如：  
1.HashMap默认的初始长度是多少？为什么这么规定？  
2.高并发情况下，HashMap会出现死锁吗？  
3.Java8中，HashMap有怎样的优化？  
下面开始说明这几个问题：

HashMap的长度

HaspMap的默认初始长度是16，并且每次扩展长度或者手动初始化时，长度必须是2的次幂。之所以是16，是为了服务于从Key值映射到index的hash算法。前面说到了，从Key值映射到数组中所对应的位置需要用到一个hash函数：index = hash("Java");

那么为了实现一个尽量分布均匀的hash函数，利用的是Key值的HashCode来做某种运算。因此问题来了，如何进行计算，才能让这个hash函数尽量分布均匀呢？

一种简单的方法是将Key值的HashCode值与HashMap的长度进行取模运算，即 index = HashCode(Key) % hashMap.length，但是，但是！这种取模方式运算固然简单，然而它的效率是很低的， 而且，如果使用了取模%， 那么HashMap在容量变为2倍时， 需要再次rehash确定每个链表元素的位置，浪费了性能。  
因此为了实现高效的hash函数算法，HashMap的发明者采用了位运算的方式。那么如何进行位运算呢？可以按照下面的公式：index = HashCode(Key) & (hashMap.length - 1);

接下来我们以Key值为“apple”的例子来演示这个过程：

1.  计算“apple”的hashcode，结果为十进制的3029737，二进制的101110001110101110 1001。
2.  HashMap默认初始长度是16，计算hashMap.Length-1的结果为十进制的15，二进制的1111。
3.  把以上两个结果做 与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以 index=9。

可以看出来，hash算法得到的index值完全取决与Key的HashCode的最后几位。这样做不但效果上等同于取模运算，而且大大提高了效率。

那么回到最初的问题，初始长度为什么是16或者2的次幂？如果不是会怎么样？

我们假设HaspMap的初始长度为10，重复前面的运算步骤：

![format_png 1][]

单独看这个结果，表面上并没有问题。我们再来尝试一个新的HashCode 101110001110101110 1011 ：

![format_png 2][]

然后我们再换一个HashCode 101110001110101110 1111 试试 ：

![format_png 3][]

这样我们可以看到，虽然HashCode的倒数第二第三位从0变成了1，但是运算的结果都是1001。也就是说，当HashMap长度为10的时候，有些index结果的出现几率会更大，而有些index结果永远不会出现（比如0111）！

所以这样显然不符合Hash算法均匀分布的原则。

而长度是16或者其他2的次幂，Length - 1的值的所有二进制位全为1（如15的二进制是1111，31的二进制为11111），这种情况下，index的结果就等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。这也是HashMap设计的玄妙之处。

2.HashMap的死锁

我们知道HashMap是非线程安全的，那么原因是什么呢？

由于HashMap的容量是有限的，如果HashMap中的数组的容量很小，假如只有2个，那么如果要放进10个keys的话，碰撞就会非常频繁，此时一个O(1)的查找算法，就变成了链表遍历，性能变成了O(n)，这是Hash表的缺陷。

为了解决这个问题,HashMap设计了一个阈值，其值为容量的0.75，当HashMap所用容量超过了阈值后，就会自动扩充其容量。

在多线程的情况下，当重新调整HashMap大小的时候，就会存在条件竞争，因为如果两个线程都发现HashMap需要重新调整大小了，它们会同时试着调整大小。在调整大小的过程中，存储在链表中的元素的次序会反过来，因为移动到新的bucket位置的时候，HashMap并不会将元素放在链表的尾部，而是放在头部，这是为了避免尾部遍历。如果条件竞争发生了，那么就会产生死循环了。

具体发生死锁的过程可以参考这篇文章：[疫苗：JAVA HASHMAP的死循环][JAVA HASHMAP]

3.HashMap的优化

关于Java8中对于HashMap的优化，可以参考下面两篇文章：  
[Java 8系列之重新认识HashMap][Java 8_HashMap]

[HashMap源码分析（JDK1.8）][HashMap_JDK1.8]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTE2MTY1NjAw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191203093646952.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxMTE2MTY1NjAw,size_16,color_FFFFFF,t_70
[20191203094254955.png]: https://img-blog.csdnimg.cn/20191203094254955.png
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy83MzQ3MzkzLTgwYmZkZmQyMzE3NDE5ZDkucG5n?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy83MzQ3MzkzLWE5OTYyYzVmYjkyZWI5NTgucG5n?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy83MzQ3MzkzLTVhNGI2YzBhMmZjNGVlZjAucG5n?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy83MzQ3MzkzLWUzN2Y5ZDVhOTQzODIzYjEucG5n?x-oss-process=image/format,png
[JAVA HASHMAP]: https://link.jianshu.com/?t=https%3A%2F%2Fcoolshell.cn%2Farticles%2F9606.html
[Java 8_HashMap]: https://link.jianshu.com/?t=https%3A%2F%2Ftech.meituan.com%2Fjava-hashmap.html
[HashMap_JDK1.8]: https://link.jianshu.com/?t=https%3A%2F%2Fblog.csdn.net%2Fbrycegao321%2Farticle%2Fdetails%2F52527236