Java中HashMap死循环分析

本文主要是介绍Java中HashMap死循环分析，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

JDK1.7中的HashMap在并发场景下，会出现死循环的情况。我面试的时候发现很多候选者都知道死循环的情况，但是很少有人能把这个情况说清楚。今天有空来详细分析下死循环是如何出现的。

HashMap的结构

首先，我们简单回顾下HashMap这个数据结构。在JDK1.7中HashMap是由数组加单链表组成的，当一个Key被加入HashMap的时候，首先会计算该Key的Hash值然后计算出应该被放入的数组下标。通过这样的方式来分散所有的Key，来提高查询效率。如果有两个Key同时分配到了同一个下边，这种情况叫Hash冲突或碰撞，这个时候会形成一个链表来解决冲突。

如果Key的数量很大的话，链表会很长，查询的时间复杂度会下降为O(n)。所以HashMap中设置了一个阈值，当Key的数量超过了这个阈值的时候，就会进行扩容，也就是rehash。rehash的过程就是，新建一个比原来大一倍的数组，然后将老数组中的元素移动到新数组中，再用新数组替换老数组。死循环出现的地方就是并发情况下的rehash中，下面我们会详细分析如何出现的死循环。

HashMap源码

我们先来看下HashMap的源码，下面是精简后的put值到HashMap的相关代码，重点关注transfer方法，死循环的关键点在这个方法里面。

public V put(K key, V value) {
    ......
    // 计算Hash值
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    // 如果key已经存在，则替换值
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    // key不存在，则新增节点
    addEntry(hash, key, value, i);
    return null;
}

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);
    // 查看size是否超过了阈值，超过了要进行resize
    if (size++ >= threshold)
        resize(2 * table.length);
}

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    ......
    // 创建一个新的Hash Table数组
    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中的元素数量超过了阈值，就会进行扩容。扩容的时候，是新建一个更大的数组，然后将老数组中的元素一个一个移动到新数组中，然后在用新数组替换老数组。这个里面关键的点在，数据转移的时候，采用的是头插法，也就是说，数据转移后顺序会颠倒。

单线程扩容

我们看下单线程正常的扩容流程，为了说明情况，这里只拿了两个key作为说明。

多线程扩容

下面我们看下多线程场景的情况，我用两种颜色区分了两个线程。首先，假设线程1执行到下面标记代码处被挂起了

do {
    // 线程1执行到该语句就被挂起了
    Entry<K,V> next = e.next;
    int i = indexFor(e.hash, newCapacity);
    e.next = newTable[i];
    newTable[i] = e;
    e = next;
} while (e != null);

此时，线程1的 e 指向了 key(3)，next 指向了 key(7)，这个时候线程1被挂起，然后线程2 执行扩容并且执行完了整个流程，这个时候情况如下图所示：

我们发现，线程1的 e 和 next 顺序颠倒了（因为头插法），然后CPU调度回来，轮到线程1 继续执行，线程1 首先将key(3)放入了新数组的头结点，然后执行e=next; next=e.next语句，得到如下情况：

代码继续执行，这个时候key(7)将会被移动到线程1的新数组中：

执行到这里，还是一切正常。在单线程的环境中，此时应该转移已经结束了，但是此时的 e 不等于 null， 而是指向了 key(3)，所以转移工作还会继续进行，再将 key 来一轮转移就变成了如下情况：

这个时候就出现了循环链表，当我们调用get()方法的时候，如果取到该数组下标，将会进入死循环。

总结

通过上面的分析，循环链表的形成其实还是很好理解的。造成死循环的核心是因为数组转移的时候采用了头插法，在多线程环境下，可能会颠倒某个线程的 e 和 next，进而造成某个key会被转移两次，从而形成循环链表。JDK1.8中将头插法改成了尾插法，避免了这个问题。但是在面试中，死循环的问题还是会经常被问到，希望这篇文章能给读者理解HashMap死循环问题带来一些帮助。

这篇关于Java中HashMap死循环分析的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！