HashMap死循环分析

本篇博文以jdk1.7为例分析。

在put方法中如果需要插入一个新的元素(key不存在)，会调用addEntry(hash, key, value, i);方法。

 public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        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++;
        addEntry(hash, key, value, i);
        return null;
    }

其中在addEntry(hash, key, value, i);方法中，可能会进行扩容：

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

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

我们看一下resize方法：

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];
        boolean oldAltHashing = useAltHashing;
        useAltHashing |= sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash = oldAltHashing ^ useAltHashing;
        transfer(newTable, rehash);
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

其中transfer是将旧的table数据转到新的table：

//Transfers all entries from current table to newTable.
 void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        //循环遍历旧table中的元素
        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);
                }
                //找到新的索引位置
                int i = indexFor(e.hash, newCapacity);
                e.next = newTable[i];
                newTable[i] = e;
                e = next;
            }
        }
    }

下面开始具体分析循环是如何出现的。

假设HashMap初始化大小为4，插入个3节点，不巧的是，这3个节点都hash到同一个位置，如果按照默认的负载因子的话，插入第3个节点就会扩容。
HashMap死循环分析
插入第4个节点时，发生resize，假设现在有两个线程同时进行，线程1和线程2，两个线程都会新建新的数组(数组扩容为2倍)。

假设线程2 在执行到 Entry<K,V>next=e.next;之后，cpu时间片用完了，这时变量e指向节点a，变量next指向节点b。

线程1继续执行，很不巧，a、b、c节点rehash之后又是在同一个位置7，开始移动节点。

第一步，移动节点a(这里假设我们直接放链表中–为了图示说明)：
HashMap死循环分析
第二步，移动节点b(jdk1.7插入到链表头部，jdk1.8插入到链表尾部)：

第三步，继续移动节点c

这个时候线程1 的时间片用完，内部的table还没有设置成新的newTable，线程2 开始执行，这时内部的引用关系如下：
HashMap死循环分析
这时，在线程2 中(如上图所示)，变量e指向节点a，变量next指向节点b，开始执行循环体的剩余逻辑。

Entry<K,V> next = e.next;
if (rehash) {
    e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;

执行之后的引用关系如下图：
HashMap死循环分析
执行后，变量e指向节点b，因为e不是null，则继续执行循环体(如上图所示e.next此时为a)，执行后的引用关系图。

变量e又重新指回节点a，只能继续执行循环体，这里仔细分析下：
1、执行完 Entry<K,V>next=e.next;，目前节点a没有next，所以变量next指向null；
2、 e.next=newTable[i]; 其中 newTable[i] 指向节点b，那就是把a的next指向了节点b，这样a和b就相互引用了，形成了一个环；
3、 newTable[i]=e 把节点a放到了数组i位置；
4、 e=next; 把变量e赋值为null，因为第一步中变量next就是指向null；

所以最终的引用关系是这样的：
HashMap死循环分析
节点a和b互相引用，形成了一个环，当在数组该位置get寻找对应的key时，就发生了死循环。

另外，如果线程2把newTable设置成内部的table，节点c的数据就丢了，看来还有数据遗失的问题。

总之，千万不要在多线程写时使用HashMap，单写多读是没有问题的。

参考博文：
HashMap死循环分析的修正版

相关推荐