为什么面试都喜欢问HashMap

系统管理员 2023-07-04 08:38 2阅读 0赞

# 为什么面试都喜欢问HashMap #

现在Java面试，好像大家都喜欢问HashMap的实现原理。有的人可能会问，HashMap有什么可聊的呢，网上随便找一篇关于HashMap博文，看一下不就可以了嘛？能考察出什么来呢？我在我们公司招聘过程中，也会问候选人关于HashMap这个问题，这个问题真的是网上找一篇文章看看，就能蒙混过关么？HashMap到底问的什么呢？它能考察出候选人哪些方面的技能呢？

我来试着从我作为面试官的角度来分析一下这个问题。

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

我一般的问题会是这样的：你能简述一下Java里面HashMap的实现原理吗？

很多候选人给的回答大致是这样的：

> HashMap底层由数组加链表结构实现。结构如下图：  
> [![hashmap][]][hashmap 1]  
> 数组用来存放元素位置，链表用来解决hash冲突。
> 
> 1.  当往HashMap中添加对象时，先计算key的hashCode，然后根据hashCode计算出元素应该放到数组的哪个位置。找到对应的位置，判断该位置是否已存在该键值对，如果已存在，那么覆盖掉原来的value，如果不存在，那么放到该位置。链表的存在就是为了解决不同key出现hash冲突的问题。一般元素会放到链表头，这样做减少操作。
> 2.  HashMap有一个扩容因子0.75，当元素数量大于数组长度乘以扩容因子时，会触发扩容操作。扩容时，将数组长度变为原来2倍，然后将元素重新计算hashCode放到相应的位置。

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

这个回答，乍一看，也没什么问题，逻辑也都ok，说明候选人对HashMap有基本的了解。但是说实话，像上面这些，基本如开头所说，网上随便一篇文章，都能说出上面的答案，在面试前一天看看也基本能掌握。

可是，面试的时候，真的是想看你在面试前上网准备的这些么？其实不是的，面试的时候，抛出一个问题，其实是想从一个点，打开一个面，从各方面了解候选人对技术的掌握程度，由点及面，了解知识的宽度。

为什么这么说呢？我慢慢解释一下我在和候选人聊HashMap时我的一个想法与思路，我想从这个问题了解候选人哪些方面。

我先说一下我在面试时，遇到这样的回答，我会这么继续问：你看过jdk的源码么？

这么问，是想从候选人的角度去再问不同的问题。看过，是一种问法，没看过，又是另外一种问法。

一般我都会追加如下几个问题：

1.  往HashMap中put元素的时候，先根据key计算hashCode，然后找到在数组中的相应位置。那么，根据hashCode是如何找到在数组中的具体位置的呢？采用什么算法？
2.  底层数组的初始长度是多少？为什么会设计成这个数呢？
3.  扩容因子0.75， 那么什么时候会触发扩容？是数组中元素占用位置数量还是HashMap总的元素数量超过扩容因子时会扩容？
4.  扩容的时候，你说要重新计算hashCode，但是对于一个key而言，扩容时其hashCode的值是不变的，为什么要重新计算hashCode呢？直接从旧的数组中移到新的数组相应的位置不可以么？
5.  HashMap其实是数据结构中哈希表的一个具体实现，那么，你还知道的哈希表的其他实现方式么？

我追加的这几个问题，好像也没什么，上网找关于HashMap的文章，好像也能找到相应的答案，那么我问的理由是什么，我又想从这些问题中了解候选人哪些东西呢？

其实这些问题基本都是递进的关系，我的意图是通过这种慢慢深入的方式，了解候选人对于HashMap这个数据结构的一些认识，当然，这里面其实还蕴含这一些计算机的基本知识，我会慢慢说来。

### 根据hashCode如何找到在数组中的具体位置 ###

首先，第一个问题，怎么根据hashCode找到元素在数组的位置呢？一般有点数理逻辑的人都能说出来，只要用hashCode对数组长度取模即可。如果候选人看过源码，可能会说使用位运算，`hashCode&(length-1)`。

这个时候，我会继续追问，这个位运算和取模运算的结果是一样的吗，jdk的源码里为什么这么实现，而没有使用取模运算呢？

首先，在jdk的实现里，使用的`hashCode&(length-1)`位运算的结果和`hashCode%length`的结果是一致的，之所以使用位运算是因为位运算比取模运算要快。

但是请注意，使用的`hashCode&(length-1)`位运算的结果和`hashCode%length`的结果是一致的，这是有一个前提条件，即底层数组的长度都是2的n次幂，其结果才一样。这也是为什么HashMap数组的初始默认长度是16的原因。

这是为什么呢？这个前提条件很重要么？对的，很重要，如果数组的长度不是2的n次幂，那么`hashCode&(length-1)`的结果和`hashCode%length`是不一致的。这里的原因得从计算机的存储方式说起。

计算机内部，都是用二进制存储的，对于一个数字 35 ，其二进制表示为：`100011`，我们分别计算这两种方式的结果看看：  
35 % 16 == 3

其结果是一样的，这是巧合么？不是巧合，这是必然的结果。我们看上面位运算的过程，对于一个lenth是2的n次幂的整数，其二进制表示形式是 `10000...0`这种形式，也就是最高位是1，其余全是0，那么length-1的二进制表示形式就是，将其最高位置为0，其余全变为1，这样再和任意一个整数hashCode进行位运算&时，相当于把hashCode的高于length最高位的位全置为0，低位全保留，这个逻辑其实就是hashCode对length取模的逻辑。

所以说，jdk源码中采用`hashCode&(length-1)`位运算的前提就是，数组的长度是2的n次幂，且每次扩容都是长度乘以2，还是2的n次幂，用这样的方式来加快计算速度，其数理逻辑还是**hashCode对数组长度length取模**。

jdk的源码如下：

<table> 
 <tbody> 
  <tr> 
   <td> <pre>1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
</pre> </td> 
   <td> <pre>final Node&lt;K,V&gt; getNode(int hash, Object key) {
    Node&lt;K,V&gt;[] tab; Node&lt;K,V&gt; first, e; int n; K k;
    if ((tab = table) != null &amp;&amp; (n = tab.length) &gt; 0 &amp;&amp;
        (first = tab[(n - 1) &amp; hash]) != null) {
        if (first.hash == hash &amp;&amp; // always check first node
            ((k = first.key) == key || (key != null &amp;&amp; key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            if (first instanceof TreeNode)
                return ((TreeNode&lt;K,V&gt;)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &amp;&amp;
                    ((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}
</pre> </td> 
  </tr> 
 </tbody> 
</table>

请注意第四行的`first=tab[(n-1)&lash]`，这里就是使用位运算&来计算的hash在数组中具体的某一个位置。

### 底层数组的默认长度是多少 ###

上面分析过了，底层数组默认长度是16， 每次扩容乘以2，都保证长度length是2的n次幂。原因就是这样可以使用位运算来加快计算在数组中的位置。

### 什么时候会触发扩容？ ###

很多人在这个问题上会掉进陷阱里。我会这样问，是数组中占用位置个数大于扩容因子的时候还是HashMap元素总数大于扩容因子的时候需要扩容？

如果对HashMap理解不透彻，这里很容易就答错了。这里**HashMap中元素总个数达到阈值时就会扩容**。很多人可能会疑问，为什么是总个数，而不是数组占用个数呢？

想象一下这个情况：假设有12个元素都落到了数组的同一个位置（当然现实情况这种机率非常非常小，几乎没有），数组只占用了一个位置，那么为什么要扩容呢，还有那么多位置没用呢？其实这里之所以要扩容，是有一个隐含的逻辑，如果元素总个数大于阈值，而数组占用位置没达到阈值，说明这些元素在当前长度下，分布是“不均匀”的，扩容是为了让其分布“更均匀”。

### 扩容时，直接将数据从原数组平移到新数组可以吗 ###

这也是一个陷阱，很多人都知道扩容时要重新计算hash，重新放置元素，却不知道为何这样做。

有些候选人不是很清晰HashMap的实现，可能就直接掉进来了，说可以。

当然，更多的候选人看过文章，看过源码，可能说不可以，要重新计算。我会继续追问，为什么要重新计算呢，对于一个key而言，扩容与否，其hashCode都是不变的，平移过来岂不是效率更高？

其实，这是不可以的，如果可以，源码实现上也就不重新计算，重新放置了。虽然key的hashCode不会变，但是数组长度变了，在根据hashCode计算数组位置时，得出的索引值肯定是不同的，如果平移过来，会直接导致扩容前添加到HashMap中的数据无法被get()到。因为在数组中索引变了，找不到了。

### Hash表的其他实现 ###

这个就是从纯数据结构层面考察了，对于一个知识点，我们要知其然，知其所以然。  
比如数据结构中，哈希表的使用场景，以及其实现方式。

说其实现方式，其实就是在遇到哈希冲突时，不同的解决哈希冲突的方式。

Java中HashMap解决冲突的方式是采用拉链法，就是如果冲突了，直接以链表的形式追加在后面，形成一条链表。除了Java中HashMap，redis中的字典也是这种方式，而且其整个实现过程和HashMap差不多，有兴趣的可以去看看。

除了拉链法，解决哈希冲突还有开发寻址法，具体怎么个过程呢，比如下图：

[![线性探测法][format_png]][format_png 1]

如图所示，假设数组长度为8，当要添加元素的hash值为18时，由于(18%8)=2，但是第二个位置已经放入了元素10，那么就继续往后探测位置3是否有元素，这里位置3也放入了元素11，再继续往后探测位置4，哎，位置4现在还没元素，好了，18这个元素就放到位置4了。

那这种方式怎么查找元素呢，还是要先计算索引，比如还是上面的18，计算出索引为2，那么会比较位置2元素是否和当前查找的元素一致，不一致，继续往后探测位置3，再比较，以此类推，直到找到元素或遍历完数组未找到返回空。

这种方式受限于数组中元素个数，当个数越来越多时，冲突越来越大，效率也越来越低，所以，很少有使用这种方式去实现哈希表的。

### 总结 ###

好了，现在我只是从最基本的HashMap的实现上，就问出了这么多细节的问题，这些问题包含的面很广，有基础的数理逻辑问题，计算机基础的二进制存储方面，二进制位运算方面的知识，更有数据结构方面哈希表这个结构的一些实现与原理。

这还没有关多线程的问题，有的面试官可能还会继续问，HashMap是不是线程安全的呀，为什么不是线程安全的呀，在什么情况下会发生死锁呀，哪个结构是线程安全的呀等等问题，这就涉及到操作系统层面线程，死锁的考察了。

所以说，虽然是一个小小的HashMap的结构，能考察的知识面却是很广的，这也是为什么在面试时HashMap会被经常问道。仅仅上网搜一下，看别人写的文章，如果不好好理解，还真的很难把这个问题答完美。

面试，都是由点及面，从一个点去考察候选人知识面，而不是简单的考你这个点记住没，对于基础的这些知识，还是应该好好理解才好。

[hashmap]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcwMDEtMTAwNDI5NzEuY29zLmFwLXNoYW5naGFpLm15cWNsb3VkLmNvbS9ibG9nL2Njc2l0ZS9oYXNobWFwL2hhc2htYXAucG5n?x-oss-process=image/format,png
[hashmap 1]: https://img001-10042971.cos.ap-shanghai.myqcloud.com/blog/ccsite/hashmap/hashmap.png
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9pbWcwMDEtMTAwNDI5NzEuY29zLmFwLXNoYW5naGFpLm15cWNsb3VkLmNvbS9ibG9nL2Njc2l0ZS9oYXNobWFwL2hhc2gucG5n?x-oss-process=image/format,png
[format_png 1]: https://img001-10042971.cos.ap-shanghai.myqcloud.com/blog/ccsite/hashmap/hash.png