果哥：一线公司小码农，一直走在求职的路上。
果妹：一线公司美女面试官，一直和小码农们苦苦纠缠。
面试现场
果妹你上次不是要问我 HashMap 原来来着吗？
对哦，我记得你上次已经大概说了 HashMap 的基本结构了
那我问你点细节吧，你上次提到了 Hash，那么如果我想自定义一个 Class 作为 key，那么应该注意什么呢？
第一次遇到这么奇怪的问题，我想想啊……
我觉得应该是注意重写 hashCode 和 equals 方法。以 put 方法为例，因为在 HashMap 内部 hash 的时候需要用到hashCode，以此来判断两个 Class 实例的 hash 是否一致。equals 是用来在 hash 碰撞以后追加链表的时候比对看是否相同以便更新。
恩，那既然你提到了 hash 用到了 hashCode 方法，你来解释一下 HashMap 里面的 hash 具体怎么实现的呢？
好的，这个我还专门研究过，打开 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
如图，可以清楚的了解到 hash 的全过程，最后一步 (n -1) & hash很好理解，就是为了把计算好的 hash 映射到所有的 bucket 槽位。那么 h ^ (h >>> 16) 是因为通常情况 bucket 的槽位很少，用于参与运算的只有 hashCode 低位，为了让高位也可以参与运算，尽可能的在不影响性能的情况下避免冲突，所以做了一下高位右移 16 位然后亦或运算。
接下来的流程就相对比较好理解了，获取到 index 以后没有碰撞直接放入 bucket，如果碰撞了就追加到链表尾部，JDK8以前是头部，JDK8是为了计算步长等于 8 的时候转换为红黑树，所以每次都是遍历链表插入到尾部。说到红黑树上次已经回答你漫画：HashSet 和 TreeSet 的实现与原理，最后如果 size 超过了 factor * capacity 就会 resize()。
恩，果哥你掌握的还不错嘛，那顺便和我说说你理解的 resize 吧？
resize 就是自动扩容，当 size 达到阈值以后会扩容到原来的 2 倍，关键代码 newCap = oldCap << 1。但是这里有一个非常巧妙的解决方法，因为扩容是扩充的 2 倍，n-1 转换为二进制也就是高位变成了1，那么根据(n - 1) & hash 计算，如果 hash 高位是 1 那么新的 index 位置就是 oldIndex + 16，如果hash 的高位 是 0 ，那么 index 的位置就是原来的 oldIndex 的位置，这样直接判断高位就可以了，省去了重新计算hash。
通过 HashMap 源码我们也可以清楚的看到，714-743 行：
恩恩，掌握的还不错嘛，对了，说了这么多 HashMap 终究不是线程安全的，那么怎么样把它变成线程安全的你知道吗？
我记得有一个工具方法，java.util.Collections#synchronizedMap(Map<K,V> map)，这个方法通过 synchronized 关键字使得 map 的每一个操作都变成了同步，这样就可以做到线程安全了。
ConcurrentHashMap 有听过吗？是不是线程安全的呢？给我讲讲这个吧。
哎呀，这个我还不太清楚诶，要不然我回去研究下，明天找你再考考我？
觉得文章不错就给小老弟点个关注吧，更多内容陆续奉上。
最后，分享一份面试宝典《Java核心知识点整理.pdf》，覆盖了JVM、锁、高并发、反射、Spring原理、微服务、Zookeeper、数据库、数据结构等等。加入我的个人粉丝群（Java架构技术栈：644872653）获取免费领取方式。
网友评论