Java HashMap笔记之二:线程不安全原理
在上一篇《Java HashMap笔记之一:基本原理》中已经介绍了Java中HashMap的基本原理,包括初始大小、初始化时机、内部Entry数组大小为什么是2的幂、扩容的原因和时机等。本篇来介绍下HashMap为什么不是线程安全的。
HashMap线程不安全的根本原因-扩容
导致HashMap线程不安全的根本原因是扩容。扩容就是在put加入元素的个数超过capacity * loadFactor的时候就会将内部Entry数组大小扩大至原来的2倍,然后将数组元素按照新的数组大小重新计算索引,放在新的数组中,同时修改每个节点的链表关系(主要是next和节点在链表中的位置)。
在扩容的过程中,每个线程会申请扩容后大小的新数组,移动完成后将新数组复制到Entry数组中。如果多个线程同时进行扩容,由于线程的执行顺序的不确定性,导致多个线程操作节点的next值会发生不确定的变化,造成数据丢失,或者形成循环链表等问题,导致线程不安全。下面来看下具体的代码和例子。
HashMap扩容代码
扩容整个流程如下,整个代码以JDK 1.7为例:
put方法:判断key是否已经存在,如果已经存在则用value重新赋值,否则调用addEntry方法添加元素
addEntry方法:判断数组大小是否需要扩容,如果需要则进行扩容调用resize方法
resize方法:申请新的大小的Entry数组,调用transfer方法
resize方法:rehash方法一般为false(不需要重新计算hash值)。HashMap在JDK 1.7中的实现是数组+链表,所以移动节点过程是2层循环:第1层遍历所有的内部Entry数组table;第2层遍历table[i]下的每个节点。对每个节点的操作:
保存当前节点的next节点
计算当前节点在新数组中的索引
设置当前节点的next节点为新数组的头节点
设置新数组的头节点为当前节点(即当前节点为新的头节点,如果所有元素在新数组中的索引都相同,那么在新数组中的顺序和原数组的顺序相反)
将第1步中保存的next节点作为当前节点循环
线程安全的问题就在这5步中:第1步中保存的next节点,在执行到第5步的时候很有可能已经被其他线程修改,不是当前节点的next节点了,导致线程安全问题。下面用图来画出这种关系。
HashMap单线程扩容流程
为了简化描述,有如下假设:
Entry数组初始大小为2
当加入第3个元素的时候开始扩容(从2扩容到4)
hash = key % length
扩容前:hash(0) = hash(4) = hash(2) = 0
扩容后:hash(0) = hash(4) = 0; hash(2) = 2
index = hash & (length - 1)
扩容前:index(0) = index(4) = index(2) = 0
扩容后:index(0) = index(4) = 0; index(2) = 2
第1次移动元素,e指向key(0),next指向key(4),移动之后key(0)放在table[0]的头节点。
第2次移动元素,e指向key(4),next指向key(2),移动之后key(4)放在table[0]的头节点。注意key(4)和key(0)的相对顺序和初始状态相反。
第3次移动元素,e指向key(2),next指向null,移动之后key(2)放在table[2]的头节点。
正常扩容显然没有问题,那我们再来看一下2个线程同时执行的情况。
HashMap多线程扩容流程
多线程执行的顺序决定于CPU调度,对于每个线程在任意语句都可能被挂起,待其他线程执行执行若干语句后再被调度。
假设线程1执行到Entry<K,V> next = e.next;语句就结束,这样线程1中的e指向key(0),next指向key(4),此时线程1挂起。
线程2调度完成所有节点的移动,结果如下图所示,和单线程扩容结果一致。注意,此时节点的位置和顺序已经发生了变化。
线程1继续执行,将e指向的key(0)节点放在table[0]的头节点。注意线程1的next仍然指向key(4),虽然此时key(0)的next已经是null。
线程1的e指向了上一次循环的next,也就是key(4),此时key(4)的next已经是key(0)。将key(4)插入到table[0]的头节点,并且将key(4)的next设置为key(0)。此时仍然没有问题。
问题来了。线程1的e指向了上一次循环的next,也就是key(0),next是null。将key(0)插入到table[0]的头节点,并且将key(0)的next设置为key(4)。此时循环链表正式成立,并且因为next是null,线程1的所有移动操作结束。
问题已经比较明显,key(0)和key(4)形成了一个循环链表,同时线程1丢失了数据key(2),会导致如下问题:
get(2)会导致查不到数据
get(8)进入死循环,因为hash(8) = 8 % 4 = 0,index(8) = 0 & 3 = 0,查找会进入到table[0]的链表中从而形成死循环
小结
HashMap线程不安全的原因是多个线程可以同时操作同一个数据源,它并不是问题,而是JDK实现就设计如此,所以如果多线程环境需要使用HashMap可以使用ConcurrentHashMap,虽然HashTable也是线程安全的,但是因为HashTable在读写过程中都加入锁,所以性能会受到较大影响。