HashMap并发下扩容的死循环通俗易懂的解释

今天和朋友讨论了下HashMap并发扩容下产生的死循环问题，发现用语言把它说清楚有点难，遂开博客锻炼下自己语言组织能力。


public V put(K key, V value) {
    ......
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    // 如果key存在 更新旧的value
    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);
  //超过阈值扩容
    if (size++ >= threshold)
        resize(2 * table.length);
}

void resize(int newCapacity) {
    Entry[] oldTable = table;
    int oldCapacity = oldTable.length;
    Entry[] newTable = new Entry[newCapacity];
    //链表节点迁移函数
    transfer(newTable);
    table = newTable;
    threshold = (int)(newCapacity * loadFactor);
}

重点来了造成死循环问题的函数

void transfer(Entry[] newTable) {
   //源数组
    Entry[] src = table;
    int newCapacity = newTable.length;
    //取出源数组的每个Node插入新数组中
    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);
        }
    }
}

接下来上图

1.

线程A执行 next = e.next
先mark一下 e指向3的节点 next指向7的节点一会要用到很重要

1.png

2.

进程换到B线程 B线程执行完扩容全过程
扩容完节点是头插的所以节点的顺序与未扩容时相反

2.png

3.

进程A被选中继续执行
刚才在1中 e指向3 next指向7

e.next = newTable[i];   //e.next = null
newTable[i] = e;  //newTable[i] = 3;
e = next;  //e=7;

屏幕快照 2019-12-24 下午10.50.33.png

4.

e != null 继续循环

上一步中 e=7 e.next = 3

Entry<K,V> next = e.next;   //next = 3
e.next = newTable[i];   
newTable[i] = e; 
e = next;  //e=3;

屏幕快照 2019-12-24 下午10.53.02.png

5.

上一步中 e=3

Entry<K,V> next = e.next;   //next = null
e.next = newTable[i];   //出现循环
newTable[i] = e; 
e = next;

屏幕快照 2019-12-24 下午10.58.00.png

最后编辑于：2019.12.24 22:58:31