本博客日IP超过2000，PV 3000 左右，急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包，请加博主新的微信号：xttblog2，之前的微信号好友位已满，备注：返现
受密码保护的文章请关注“业余草”公众号，回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽，请关注文末小程序
腾讯云】1核2G5M轻量应用服务器50元首年，高性价比，助您轻松上云
高并发环境下，HashMap可能出现的致命问题！注意：是在 jdk8 以下版本发生！
我们先来看看 Rehash 的概念。
Rehash 是 HashMap 在扩容时候的一个步骤。
HashMap 的容量是有限的。当经过多次元素插入，使得 HashMap 达到一定饱和度时，Key 映射位置发生冲突的几率会逐渐提高。
这时候，HashMap 需要扩展它的长度，也就是进行 Resize。
影响发生 Resize 的因素有两个：
- Capacity（HashMap 的当前长度–容量）
HashMap 的当前长度。上一期曾经说过，HashMap 的长度是 2 的幂。
- LoadFactor（负载因子）
HashMap 负载因子，默认值为 0.75f。
衡量 HashMap 是否进行 Resize 的条件如下：
HashMap.Size >= Capacity * LoadFactor （默认情况下是 == 原来长度 * 0.75）
HashMap 的 Resize 方法具体做了什么事情？
- 扩容
创建一个新的Entry空数组，长度是原数组的2倍。
- ReHash
遍历原 Entry 数组，把所有的 Entry 重新 Hash 到新数组。为什么要重新 Hash 呢？因为长度扩大以后，Hash 的规则也随之改变。
让我们回顾一下Hash公式：
index = HashCode（Key） & （Length - 1）
当原数组长度为 8 时，Hash 运算是和 111B（代表二进制的 7）做与运算；新数组长度为16，Hash 运算是和 1111B（代表二进制的 15）做与运算。Hash 结果显然不同
ReHash 的 Java 代码如下：
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}注意 HashMap 在多线程下的 Rehash 可能会出现什么样的问题呢？
现在假设一个 HashMap 已经到了 Resize 的临界点。此时有两个线程 A 和 B，在同一时刻对 HashMap 进行 Put 操作：
此时达到 Resize 条件，两个线程各自进行 Rezie 的第一步，也就是扩容。
这时候，两个线程都走到了 ReHash 的步骤。让我们回顾一下 ReHash 的代码：
假如此时线程 B 遍历到 Entry3 对象，刚执行完红框里的这行代码，线程就被挂起。
对于线程 B 来说：e = Entry3 next =Entry2 这时候线程 A 畅通无阻地进行着 Rehash，当 ReHash 完成后，结果如下（图中的 e 和 next，代表线程 B 的两个引用）：
直到这一步，看起来没什么毛病。接下来线程 B 恢复，继续执行属于它自己的 ReHash。
线程 B 刚才的状态是：e = Entry3 next = Entry2
当执行到上面这一行时，显然 i = 3，因为刚才线程 A 对于 Entry3 的 hash 结果也是3。
我们继续执行到这两行，Entry3 放入了线程 B 的数组下标为 3 的位置，并且 e 指向了 Entry2。
此时 e 和 next 的指向关系：e =Entry2 next = Entry2 整体情况如下图所示：
接着是新一轮循环，又执行到红框内的代码行：
e = Entry2
next = Entry3
整体情况如图所示：
接下来执行下面的三行，用头插法把 Entry2 插入到了线程 B 的数组的头结点：
整体情况如图所示：
第三次循环开始，又执行到红框的代码：
e = Entry3
next = Entry3.next = null
最后一步，当我们执行下面这一行的时候，见证奇迹的时刻来临了。
newTable[i] = Entry2
e = Entry3
Entry2.next = Entry3
Entry3.next = Entry2链表出现了环形！整体情况如图所示：
此时，问题还没有直接产生。当调用 Get 查找一个不存在的 Key，而这个 Key 的 Hash 结果恰好等于 3 的时候，由于位置 3 带有环形链表，所以程序将会进入死循环！
这种情况，不禁让人联想到一道经典的面试题：如何判断链表有环？
如何杜绝这种情况？
最后总结如下：
- Hashmap 在插入元素过多的时候需要进行 Resize。
Resize 的条件是 HashMap.Size >= Capacity * LoadFactor。
- Hashmap 的 Resize 包含扩容和 ReHash 两个步骤，ReHash 在并发的情况下可能会形成链表环。
链表头插法的会颠倒原来一个散列桶里面链表的顺序。在并发的时候原来的顺序被另外一个线程 a 颠倒了，而被挂起线程 b 恢复后拿扩容前的节点和顺序继续完成第一次循环后，又遵循 a 线程扩容后的链表顺序重新排列链表中的顺序，最终形成了环。
这也是为什么后来 HashMap 改为尾插法的原因之一。
最后，欢迎关注我的个人微信公众号：业余草（yyucao）！可加作者微信号：xttblog2。备注：“1”，添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注！后续有精彩内容会第一时间发给您！原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系！
本文原文出处：业余草： » 高并发环境下，HashMap可能出现的致命问题！