HashMap1.7 头插法造成死循环的原因

r囧r小猫 2022-10-21 14:00 193阅读 0赞

# 一：概述 #

HashMap1.7当中，扩容的时候，采用的是头插法转移结点，在多线程并发的情况下会造成链表死循环的问题。

# 二：图解 #

假设有两个线程，线程1和线程2，两个线程进行hashMap的put操作，触发了扩容。

下面是扩容的时候结点转移的关键代码

void transfer(Entry[] newTable) {
          Entry[] src = table; 
          int newCapacity = newTable.length;
          for (int j = 0; j < src.length; j++) { 
              Entry<K,V> e = src[j];           
              if (e != null) {//两个线程都先进入if
                  src[j] = null; 
                  do { 
                      Entry<K,V> next = e.next; 
                     int i = indexFor(e.hash, newCapacity);
                     e.next = newTable[i]; //线程1 这里还没执行 停下
                     newTable[i] = e;  
                     e = next;             
                 } while (e != null);
             }
         }
     }

线程1和线程2 都进入if，然后线程1没有拿到cpu的资源在上面代码注释的地方停下了。此时的变量指针如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdzZW5saW4zNDE_size_16_color_FFFFFF_t_70]

记住 线程1中 E变量指向a结点，next变量指向b结点。

下面是线程2 拿到cpu的资源，执行结点转移

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdzZW5saW4zNDE_size_16_color_FFFFFF_t_70 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdzZW5saW4zNDE_size_16_color_FFFFFF_t_70 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdzZW5saW4zNDE_size_16_color_FFFFFF_t_70 3]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdzZW5saW4zNDE_size_16_color_FFFFFF_t_70 4]

线程2停下，轮到线程1

因为之前线程1中E变量指向的是a结点，next变量指向的是b结点，所以如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdzZW5saW4zNDE_size_16_color_FFFFFF_t_70 5]

再来看看 刚才线程是在e.next = newTable\[i\] 这句代码还没执行的时候停下的，那么现在就要执行这一句代码

void transfer(Entry[] newTable) {
          Entry[] src = table; 
          int newCapacity = newTable.length;
          for (int j = 0; j < src.length; j++) { 
              Entry<K,V> e = src[j];           
              if (e != null) {//两个线程都先进入if
                  src[j] = null; 
                  do { 
                      Entry<K,V> next = e.next; 
                     int i = indexFor(e.hash, newCapacity);
                     e.next = newTable[i]; //线程1刚才在这里停下，所以现在从这一句代码开始执行
                     newTable[i] = e;  
                     e = next;             
                 } while (e != null);
             }
         }
     }

此时线程1 执行代码之后，就造成了链表的死循环，结果如下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdzZW5saW4zNDE_size_16_color_FFFFFF_t_70 6]

[参考博客][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdzZW5saW4zNDE_size_16_color_FFFFFF_t_70]: /images/20221021/d656fa2c0096437aacec37ca80547946.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdzZW5saW4zNDE_size_16_color_FFFFFF_t_70 1]: /images/20221021/e7ac7eca9dfc42d0a8534ea64fdfecc3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdzZW5saW4zNDE_size_16_color_FFFFFF_t_70 2]: /images/20221021/5f751c84e52e45db8e5ffd76f976c389.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdzZW5saW4zNDE_size_16_color_FFFFFF_t_70 3]: /images/20221021/7b978896f74b45ed86d2c812751a15fd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdzZW5saW4zNDE_size_16_color_FFFFFF_t_70 4]: /images/20221021/7b5bee1c981244cc8cd5321bbbe074f5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdzZW5saW4zNDE_size_16_color_FFFFFF_t_70 5]: /images/20221021/47717ad5518e4278a8437e7a44ec91b3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dvbmdzZW5saW4zNDE_size_16_color_FFFFFF_t_70 6]: /images/20221021/0d72358127de47bfb18e385fbd9ff3e6.png
[Link 1]: https://blog.csdn.net/gongsenlin341/article/details/112582217