问题引出

前一篇文章讲授了HashMap的实现道理，讲到了HashMap不是线程安详的。那么HashMap在多线程情况下又会有什么问题呢？

几个月前，公司项目标一个模块在线上运行的时候呈现了死轮回，死轮回的代码就卡在HashMap的get要领上。尽量最终发明不是因为HashMap导致的，但却让我重视了HashMap在多线程情况下会激发死轮回的这个问题，下面先用一段代码简朴模仿出HashMap的死轮回：

public class HashMapThread extends Thread
{
    private static AtomicInteger ai = new AtomicInteger(0);
    private static Map<Integer, Integer> map = new HashMap<Integer, Integer>(1);
    
    public void run()
    {
        while (ai.get() < 100000)
        {
            map.put(ai.get(), ai.get());
            ai.incrementAndGet();
        }
    }
}

这个线程的浸染很简朴，给AtomicInteger不绝自增并写入HashMap中，个中AtomicInteger和HashMap都是全局共享的，也就是说所有线程操纵的都是同一个AtomicInteger和HashMap。开5个线程操纵一下run要领中的代码：

public static void main(String[] args)
{
    HashMapThread hmt0 = new HashMapThread();
    HashMapThread hmt1 = new HashMapThread();
    HashMapThread hmt2 = new HashMapThread();
    HashMapThread hmt3 = new HashMapThread();
    HashMapThread hmt4 = new HashMapThread();
    hmt0.start();
    hmt1.start();
    hmt2.start();
    hmt3.start();
    hmt4.start();
}

多运行屡次之后死轮回就出来了，我或许运行了7次、8次的样子，个中有屡次是数组下标越界异常ArrayIndexOutOfBoundsException。这内里要提一点，多线程情况下代码会呈现问题并不料味着多线程情况下必然会呈现问题，可是只要呈现了问题，可能是死锁、可能是死轮回，那么你的项目除了重启就没有什么此外步伐了，所以代码的线程安详性在开拓、评审的时候必需要重点思量到。OK，看一下节制台：

赤色方框一直亮着，说明代码死轮回了。死轮回问题的定位一般都是通过jps+jstack查察仓库信息来定位的：

看到Thread-0处于RUNNABLE，而从仓库信息上应该可以看出，这次的死轮回是由于Thread-0对HashMap举办扩容而引起的。

所以，本文就解读一下，HashMap的扩容为什么会引起死轮回。

正常的扩容进程

先来看一下HashMap一次正常的扩容进程。简朴一点看吧，假设我有三个颠末尾最终rehash获得的数字，别离是5 7 3，图纸加密，HashMap的table也只有2，那么HashMap把这三个数字put进数据布局了之后应该是这么一个样子的：

这应该很好领略。然后看一下resize的代码，上面的仓库内里就有：

void addEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
    if (size++ >= threshold)
        resize(2 * table.length);
}

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }

    Entry[] newTable = new Entry[newCapacity];
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

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) {
            src[j] = null;
            do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            } while (e != null);
        }
    }
}

我总结一下这三段代码，HashMap一次扩容的进程应该是：

1、取当前table的2倍作为新table的巨细

2、按照算出的新table的巨细new出一个新的Entry数组来，名为newTable

3、轮询原table的每一个位置，将每个位置上毗连的Entry，算出在新table上的位置，并以链表形式毗连

4、原table上的所有Entry全部轮询完毕之后，意味着原table上面的所有Entry已经移到了新的table上，HashMap中的table指向newTable