Java基础：详解HashMap在多线程下不安全

今天想知道HashMap为什么在多线程下不安全，找了许多资料，终于理解了。

首先先了解一下HashMap:

HashMap实现的原理是：数组+链表

HashMap的size大于等于(容量*加载因子)的时候,会触发扩容的操作,这个是个代价不小的操作。

为什么要扩容呢?

HashMap默认的容量是16,随着元素不断添加到HashMap里,出现hash冲突的机率就更高,那每个桶对应的链表就会更长,

这样会影响查询的性能,因为每次都需要遍历链表,比较对象是否相等,一直到找到元素为止。

为了提升查询性能,只能扩容,减少hash冲突,让元素的key尽量均匀的分布。

在单线程中，HashMap是安全的，但是在高并发的环境下，会出现不安全，原因在于HashMap的扩容。

我们先看下HashMap扩容的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15


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]; 

           

        transfer(newTable);//可能导致环链 

           

        table = newTable; 

        threshold = (int)(newCapacity * loadFactor); 
} 

transfer方法就是进行HashMap的扩容的核心方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17


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); 

        } 

    } 
}

在并发情况下进行扩容，有一个线程执行到

1

Entry<K,V> next = e.next;

而另外一个线程已经执行完扩容，再等这个线程执行完就会出现环路，并且也会丢失一些节点。

我查看一下陈皓大神的文章，里面写的很详细：

https://coolshell.cn/articles/9606.html

正常的ReHash的过程

画了个图做了个演示。

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

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

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

Java基础：详解HashMap在多线程下不安全

并发下的Rehash

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

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

1
2
3
4
5
6
7


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);