转载

为什么面试都喜欢问HashMap

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

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

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

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

HashMap底层由数组加链表结构实现。结构如下图：

数组用来存放元素位置，链表用来解决hash冲突。

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

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

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

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

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

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

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

往HashMap中put元素的时候，先根据key计算hashCode，然后找到在数组中的相应位置。那么，根据hashCode是如何找到在数组中的具体位置的呢？采用什么算法？
底层数组的初始长度是多少？为什么会设计成这个数呢？
扩容因子0.75，那么什么时候会触发扩容？是数组中元素占用位置数量还是HashMap总的元素数量超过扩容因子时会扩容？
扩容的时候，你说要重新计算hashCode，但是对于一个key而言，扩容时其hashCode的值是不变的，为什么要重新计算hashCode呢？直接从旧的数组中移到新的数组相应的位置不可以么？
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

 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的源码如下：

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