Java的HashMap死循环问题

HashMap源码分析

Java的HashMap是线程不安全的，所以在jdk1.7中，多线程的HashMap扩容采用头插法会发生死循环问题。

正常扩容

当我们向HashMap中添加值的时候，调用的是Put()方法。

public V put(K key, V value) {
        //如果table数组为空数组{}，进行数组填充（为table分配实际内存空间），入参为threshold，
        //此时threshold为initialCapacity 默认是1<<4(24=16)
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
       //如果key为null，存储位置为table[0]或table[0]的冲突链上
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);//对key的hashcode进一步计算，确保散列均匀
        int i = indexFor(hash, table.length);//获取在table中的实际位置
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        //如果该对应数据已存在，执行覆盖操作。用新value替换旧value，并返回旧value
            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++;//保证并发访问时，若HashMap内部结构发生变化，快速响应失败
        addEntry(hash, key, value, i);//新增一个entry
        return null;
    }

put方法主要进行添加操作的是addEntry()方法。

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);//当size超过临界阈值threshold，并且即将发生哈希冲突时进行扩容
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }

addEntry方法中会对当前HashMap的容量进行判断。当个数大于等于阈值且当前要添加的数组下标位置已经存在元素了(准备添加时发生哈希冲突)的时候,就会调用扩容方法resize(2 * table.length)HashMap的容量扩大两倍

void resize(int newCapacity) {
    //旧Entry数组
    Entry[] oldTable = table;
    //旧Entry数组长度
    int oldCapacity = oldTable.length;
    if (oldCapacity == MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return;
    }
    //新Entry数组，长度为旧的两倍（2 * table.length）
    Entry[] newTable = new Entry[newCapacity];
    //将旧Entry数组中的值重新计算，添加到新Entry数组中
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    //指向新Entry数组
    table = newTable;
    //得到新的阈值（2*table.length*0.75=2*16*0.75=24）
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

resize创建了新的Entry数组，并通过transfer()方法中原来的数组添加到新的Entry数组中。

/**
 * Transfers all entries from current table to newTable.
 */
void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    //循环遍历table（旧Entry数组）
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> next = e.next;
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            //得到新Entry数组索引
            int i = indexFor(e.hash, newCapacity);
            e.next = newTable[i];
            newTable[i] = e;
            e = next;
        }
    }
}

这里就是发生死循环的地方了。首先我们假设出正常情况下的该方法图示。

• 我假设了我们的hash算法就是简单的用key mod 一下表的大小（也就是数组的长度）。

• 最上面的是old hash 表，其中的Hash表的size=2, 所以key = 3, 7, 5，在mod 2以后都冲突在table[1]这里了。

• 接下来的三个步骤是Hash表 resize成4，然后所有的<key,value> 重新rehash的过程

扩容之后rehash过程。

这就是单线程正常情况下的状况。

并发扩容

假设我们有两个线程。我用红色和浅蓝色标注了一下。

我们再回头看一下我们的 transfer代码中的这个细节：

//循环遍历table（旧Entry数组）
for (Entry<K,V> e : table) {
    while(null != e) {
        Entry<K,V> next = e.next; <--假设线程一执行到这里就被调度挂起了
        if (rehash) {
            e.hash = null == e.key ? 0 : hash(e.key);
        }
        //得到新Entry数组索引
        int i = indexFor(e.hash, newCapacity);
        e.next = newTable[i];
        newTable[i] = e;
        e = next;
    }
}

由于线程二的头插法，最开始的e和next所指的元素已经换掉了位置。接着线程一继续按照头插法操作。就会出现如下

e.next = newTable[i];
newTable[i] = e;
e = next;

此时就出现了循环。

参考文章https://coolshell.cn/articles/9606.html