Java教程

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作为说明。

image-20210509213334307

多线程扩容

下面我们看下多线程场景的情况,我用两种颜色区分了两个线程。首先,假设线程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);

image-20210509215404369

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

image-20210509215621694

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

image-20210509215753105

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

image-20210509220147214

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

image-20210509220351336

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

总结

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

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