本文分享自华为云社区《java中HashMap的设计精妙在哪？用图解和几个问题教你一次性搞定HashMap》，作者：breakDawn。

HashMap 核心原理

hashMap 完整的 put 过程

以下是对上图的详细解释：

1. 首先，要获取 key 的哈希值。

2. 如果为空，就统一是 0

3. 否则，调用对象的.hashCode()方法，接着再与自己的右移 16 位进行异或，以便充分利用高位信息。

4. 接着判断内部 node 数组是否为空，如果是，先进行初始化扩容。默认为 16。

5. 根据(n-1)&hash 值，获取哈希表索引位置。 （&的性能比取余要高,具体讨论见CPU取余原理）

6. 哈希表的 node 数组中，存放的是每组链表的头节点。

7. 先检查头节点是否和自己要存放的 key 完全匹配 （hash 值相同，key 值相同，先 hash 再 key，是因为 hash 的判断简单，key 的 equals 判断可能会复杂）

8. 如果匹配，得到需要替换的节点。

9. 头节点和自己要放的 key 不匹配，则判断一下这个头节点是否是红黑树节点，如果是，说明已经升级成红黑树了，调用 putTree 插入到红黑树中。

10. 如果不是红黑树， 那就是遍历链表，完全匹配就得到需要替换的节点。如果到尾部了，也没匹配的，则插入新节点。

11. 如果前面找到了要替换的节点，则判断一下是否可以替换（是否没要求 putIfAbsent，或者 value 为 null），是就替换，不是就结束

12. 如果前面是插入了新节点，非替换， 则要 modCount++（方便迭代器确认 map 是否更新）， 同时++size， 然后和扩容阈值做判断， 如果太大，就 resize 进行扩容

hashMap 的扩容过程，java7 和 8 扩容的区别

java7：

• 当 resize 时，新建一个数组 newTable

• 遍历原 table 中的每个链表和节点，重新 hash，找到新的位置放入

• 放入的方式是头插法，即始终插在链表的头节点。

java8:

• 不再每个点 rehash 放置，而是最高位是 0 则坐标不变，最高位是 1 则坐标变为“10000+原坐标”，即“原长度+原坐标. 避免了频繁的哈希计算和搬移过程。

• 使用尾插法在链表上插入节点

• 桶内元素超过 8 个，链表转成红黑树

为什么 java8 要改成尾插法？

多线程时，java7 的 map-put 可能造成死循环。

A 线程扩容到那一半， 还处在遍历链表做头插法搬移的过程时，存了 2 个局部变量，当前链点 now 指向 a， next 指向 b，正准备搬移（a->b->c 这样的链表，a 是头节点）B 线程则同时完成线程扩容，但是 map 里都是引用，浅拷贝，** 因为是头插法， 会导致顺序变化**， 原本 a->b->c 变成了 c->b->a。

因此 A 恢复时， 链点还是 a，next 还是 b， 于是往下走到了 b， 取 bbs 的 next 时，已经变成了 a， 于是发生了 a->b->a 的循环导致后续操作的 next 都是错误操作，引发环形指针。

java8 里改成尾插法，这样做 resize 时，a->b->c 如果仍然哈希到同一个节点， 顺序是不会发生变化的。

虽然解决了死循环问题， 但 java8 的 hashMap 仍然是线程不安全的，为什么？

因为缺乏同步，导致同节点发生哈希碰撞时，if 条件的判断都可能是有问题的，导致本该插在链表头节点后面的，结果直接作为链表头覆盖到数组上了。

具体到底满足什么情况，才会 resize 扩容呢？

HashMap 负载因子 LoadFactor，默认值为 0.75f。

衡量 HashMap 是否进行 Resize 的条件如下：

HashMap.Size >= Capacity * LoadFactor

另一种情况。JDK1.8 源码中，执行树形化之前，会先检查数组长度，如果长度小于 64，则对数组进行扩容，而不是进行树形化

扩容后，capacity 扩容多少倍呢？为什么

哈希表每次扩容是两倍。

初始长度为 2 的幂次方，随后以 2 倍扩容的方式扩容，元素在新表中的位置要么不动，要么有规律的出现在新表中（二的幂次方偏移量），这样会使扩容的效率大大提高。

另外，hashmap 采用二倍扩容还有另外一个好处：可以使元素均匀的散布 hashmap 中，减少 hash 碰撞。

点击关注，第一时间了解华为云新鲜技术~