HashMap的死循环及数据覆盖问题

目录

一，HashMap 线程不安全的原因

二，HashMap 死循环问题

死循环发生的条件

死循环的具体过程

死循环执行步骤1

死循环执行步骤2

死循环执行步骤3 

三，HashMap 数据覆盖问题

数据覆盖执行流程1

数据覆盖执行流程2

数据覆盖执行流程3 

---

一，HashMap 线程不安全的原因

HashMap 不是线程安全的，原因主要体现在两个方面：

1. HashMap 在 JDK 1.7之前（包含 JDK 1.7）它不安全的原因体现在两个方面：
   • 环形链表，导致程序执行死循环；
   • 多线程并发执行，导致数据覆盖；
2. HashMap 在 JDK 1.8之后（包含 JDK 1.8）不再有死循环问题，但依旧存在数据覆盖问题。

二，HashMap 死循环问题

死循环发生的条件

1. 多线程并发执行
2. HashMap 发生扩容
3. 发生哈希冲突时采用的是头插法

死循环的具体过程

在 JDK 1.7中 HashMap 的底层的实现是数组+链表的方式，如下图所示：

而 HashMap 在数据添加时使用的时头插法，如下图所示：

HashMap 正常情况下的扩容实现如下图所示：

旧 HashMap 的节点会依次转移到新的 HashMap 中，旧 HashMap 转移顺序是A、B、C，而新 HashMap 使用的是头插法，所以最终在新 HashMap 中的顺序是C、B、A，也就是上图展示的那样。有了这些前置知识，我们来看一下死循环是如何诞生的？

死循环执行步骤1

死循环是因为并发 HashMap 扩容导致的，并发扩容的第一步，线程 T1 和线程 T2 要对 HashMap 进行扩容操作，此时 T1 和 T2 指向的是链表的头节点元素A，而 T1 和 T2的下一个节点，也就是 T1.next 和 T2.next指向的是B节点，如图所示：

死循环执行步骤2

死循环的第二步操作是，线程 T1 时间片用完休眠状态，而线程 T2 开始执行扩容操作，一直到线程 T1 扩容完成之后，线程 T2 才被唤醒，扩容完之后的场景如下图所示：

从上图可知线程 T1 执行完之后，因为是头插法，所以 HashMap 的顺序已经发生了变化，但线程 T2 对于发生的一切是不可知的，所以它的指向元素依然没有变，如上图展示的那样，T2 指向的是A元素，T2.next指向的节点是B元素。 

死循环执行步骤3 

当线程 T1 执行完，而线程 T2 恢复执行时，死循环就建立了，如下图所示：

因为 T1 执行完扩容之后B节点的下一个节点是A，而 T2  线程指向的首节点是A，第二个节点B，这个顺序刚好和 T1 扩完容之后的节点顺序是相反的，T1 执行完之后的顺序是B到A，而 T2 的顺序是A到B，这样A节点和B节点就形成死循环了，这就是 HashMap 死循环导致的原因。

三，HashMap 数据覆盖问题

数据覆盖问题发生在并发添加元素的场景下，它不止出现在 JDK 1.7版本中，其他版本也存在此问题，数据覆盖产生的流程如下：

1. 线程 T1 进行添加时，判断某个位置可以插入元素，但还没有真正的进行插入操作，自己时间片就用完了；
2. 线程 T2 也执行添加操作，并且 T2 产生的哈希值和 T1 相同，也就是 T2 即将要存储的位置和 T1 相同，因为此位置尚未插入值（T1 线程执行了一半），于是 T2 酒吧自己的值存入到当前位置了；
3. T1 恢复执行之后，因为非空判断已经执行完了，它感知不到此位置已经有值了，于是就把自己的值也插到了此位置，那么 T2 的值就被覆盖了。

数据覆盖执行流程1

线程 T1 准备将数据k1:v1插入到Null处，但还没有真正的执行，自己的时间片就用完了，进入休眠状态了，如下图所示：

数据覆盖执行流程2

线程 T2 准备将数据k2:v2插入到Null处，因为此处现在并未有值，如果此处有值的话，它会使用链式法将数据插入到下一个没值的位置上，但判断之后发现此处并未有值，那么就直接进行数据插入了，如下图所示：

数据覆盖执行流程3 

线程 T2 执行完成之后，线程 T1 恢复执行，因为线程 T1 之前已经判断过此位置没值了，所以会直接插入，此时线程 T2 插入的值就被覆盖了，如下图所示：