转载

一文看懂 HashMap 原理，从此哪个屯的面试官都不怕

人物画像

果哥：一线公司小码农，一直走在求职的路上。

一文看懂 HashMap 原理，从此哪个屯的面试官都不怕

果妹：一线公司美女面试官，一直和小码农们苦苦纠缠。

面试现场

一文看懂 HashMap 原理，从此哪个屯的面试官都不怕

果妹你上次不是要问我 HashMap 原来来着吗？

对哦，我记得你上次已经大概说了 HashMap 的基本结构了

漫画：HashSet 和 TreeSet 的实现与原理

那我问你点细节吧，你上次提到了 Hash，那么如果我想自定义一个 Class 作为 key，那么应该注意什么呢？

一文看懂 HashMap 原理，从此哪个屯的面试官都不怕

第一次遇到这么奇怪的问题，我想想啊……

我觉得应该是注意重写 hashCode 和 equals 方法。以 put 方法为例，因为在 HashMap 内部 hash 的时候需要用到 hashCode ，以此来判断两个 Class 实例的 hash 是否一致。equals 是用来在 hash 碰撞以后追加链表的时候比对看是否相同以便更新。

恩，那既然你提到了 hash 用到了 hashCode 方法，你来解释一下 HashMap 里面的 hash 具体怎么实现的呢？

一文看懂 HashMap 原理，从此哪个屯的面试官都不怕

好的，这个我还专门研究过，打开 HashMap 源码，从 put 说起吧。它最先调用的是 hash 函数，然后和当前的 n - 1 做与运算得到 bucket 的下标，关键代码如下：

(h = key.hashCode()) ^ (h >>> 16) // 338 行

tab[i = (n - 1) & hash] // 692 行

具体逻辑，先是获取 key 的 hashCode，然后把 hashCode 低位位移 16 位后和之前的 hashCode 做亦或运算得到最终的 hash 值， bucket 数量是有限的，所以需要和 n -1 与运算得到最终的下标，这么说可能比较晦涩，我简单画一个图吧。以 key 是 “果汁简历” 为例，n 默认为 16，下图是把十进制转换为二进制进行计算。

String value = "果汁简历";

int hashCode = value.hashCode(); //817810155

int lowBit = hashCode >>> 16; //12478

int hash = hashCode ^ lowBit; //817822293

int index = (n - 1) & hash; //5

一文看懂 HashMap 原理，从此哪个屯的面试官都不怕

如图，可以清楚的了解到 hash 的全过程，最后一步 (n -1) & hash 很好理解，就是为了把计算好的 hash 映射到所有的 bucket 槽位。那么 h ^ (h >>> 16) 是因为通常情况 bucket 的槽位很少，用于参与运算的只有 hashCode 低位，为了让高位也可以参与运算，尽可能的在不影响性能的情况下避免冲突，所以做了一下高位右移 16 位然后亦或运算。

接下来的流程就相对比较好理解了，获取到 index 以后没有碰撞直接放入 bucket，如果碰撞了就追加到链表尾部，JDK8以前是头部，JDK8是为了计算步长等于 8 的时候转换为红黑树，所以每次都是遍历链表插入到尾部。说到红黑树上次已经回答你漫画：HashSet 和 TreeSet 的实现与原理，最后如果 size 超过了 factor * capacity 就会 resize()。

恩，果哥你掌握的还不错嘛，那顺便和我说说你理解的 resize 吧？

一文看懂 HashMap 原理，从此哪个屯的面试官都不怕

resize 就是自动扩容，当 size 达到阈值以后会扩容到原来的 2 倍，关键代码 newCap = oldCap << 1 。但是这里有一个非常巧妙的解决方法，因为扩容是扩充的 2 倍， n-1 转换为二进制也就是高位变成了1，那么根据 (n - 1) & hash 计算，如果 hash 高位是 1 那么新的 index 位置就是 oldIndex + 16，如果hash 的高位是 0 ，那么 index 的位置就是原来的 oldIndex 的位置，这样直接判断高位就可以了，省去了重新计算hash。

一文看懂 HashMap 原理，从此哪个屯的面试官都不怕