为什么面试都喜欢问HashMap

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

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


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

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

HashMap底层由数组加链表结构实现。结构如下图:
hashmap
数组用来存放元素位置,链表用来解决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

1
2
3
4
 100011       35
& 1111 16-1=15
------- -------
000011 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的源码如下:

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

请注意第四行的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差不多,有兴趣的可以去看看。

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

线性探测法

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

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

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

总结

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

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

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

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