HashMap1.7版本扩容时的死循环问题详解

HashMap1.7版本扩容时的死循环问题详解

HashMap是Java中非常重要的数据结构之一，在不同版本中针对多线程环境下的性能和安全性进行了多次优化。本文将通过代码分析和图解的方式，详细讲解HashMap1.7版本在多线程环境下扩容时使用头插法可能导致的死循环问题，并对比1.8版本中采用尾插法的改进。

1. 概述

在HashMap1.7版本中，扩容时采用的是头插法转移节点。在多线程并发的情况下，这种做法可能会导致链表死循环的问题。而在HashMap1.8版本中，这个问题通过改用尾插法得到了解决。

2. 问题分析

假设有两个线程，线程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在上述代码注释的地方暂停。此时的变量指针状态如下图所示：

线程2获得CPU资源并继续执行：

1. 线程2执行完第一轮循环后：

2. 线程2执行完第二轮循环后：

此时线程2暂停，轮到线程1继续执行。由于线程1中E变量指向a节点，next变量指向b节点，所以：

线程1继续执行被中断的代码：

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);
        }
    }
}  

执行完之后，链表结构变为：

此时，a节点的next指针指向了自己，形成了一个死循环。

3. 解决方案

在HashMap1.8版本中，通过改用尾插法解决了这个问题。尾插法确保了在多线程环境下，即使有线程切换，也不会导致链表结构的破坏。

总结

通过这个例子，我们可以看到HashMap在不同版本中的优化历程。虽然HashMap1.7版本的这个问题在当前版本中已经得到解决，但理解这些问题的根源有助于我们更好地掌握数据结构和多线程编程的原理。