为什么面试都喜欢问HashMap

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

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

---

我一般的问题会是这样的：你能简述一下 Java 里面 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

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

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

这也是一个陷阱，很多人都知道扩容时要重新计算 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 会被经常问道。仅仅上网搜一下，看别人写的文章，如果不好好理解，还真的很难把这个问题答完美。

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