众所周知,HashMap在多线程环境下是线程不安全的,
在jdk1.7中,主要有两个方面线程不安全,一是多线程扩容因为头插法容易造成死循环。二是put的时候容易造成数据覆盖。
在jdk1.8中,使用尾插法避免了resize时死循环,但是put的时候,多线程环境下仍然会出现数据覆盖的问题。
接下来逐个分析问题点:
HashMap在jdk1.7扩容时在多线程环境下会发生死循环问题,研究一下多线程环境下为什么会发生死循环,首先看一下扩容代码,扩容代码发生在put方法中:
public V put(K key, V value) {
if (table == EMPTY_TABLE) {
inflateTable(threshold);
}
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;
}
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
//扩容,将原来数组重新计算hash值,并且放到新的位置中
resize(2 * table.length);
hash = (null != key) ? hash(key) : 0;
bucketIndex = indexFor(hash, table.length);
}
createEntry(hash, key, value, bucketIndex);
}
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, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
发生死循环在transfer()方法中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
//1.将链表的下个节点放入新的对象next中
Entry<K,V> next = e.next;
//2.重新计算hash值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//3.重新计算当前e对象的hash值,并计算存储位置
int i = indexFor(e.hash, newCapacity);
//4.将新数组的i的位置的元素放到当前元素的后面,头插法
e.next = newTable[i];
//5.将新数组的i位置设置为当前e
newTable[i] = e;
//6.继续遍历next对象
e = next;
}
}
}
单线程环境下是这样扩容的:
(1) 原来的数组,假如2,4,6的hash值相同,都在old这个位置的链表上。
(2)现在新来一个元素(这个元素放在其他位置,这里就不画了),导致当前hashmap对象需要扩容。首先移动2
(3)移动4
(4) 移动6
使用头插法,将元素依次移动到新的链表位置。
在多线程环境下,发生多线程死循环的位置是当某个线程还未扩容完,另外一个线程竞争到锁,执行扩容,之后原来线程继续执行扩容时,对象的指针发生改变,导致后面的死循环。这里举一个例子,两个线程A和B,对hashmap对象进行扩容,发生死循环的过程
(1) 仍然使用上面的例子
(2)线程A竞争到锁,进行扩容
(2)当线程A执行到Entry<K,V> next = e.next;这步时,线程B竞争到了HashMap对象的锁,完成扩容。此时2已经移动到了i位置上
(3)线程A竞争到锁,继续执行没完成的任务,这里涉及到JVM的知识,我们再看一下transfer代码:
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
//1.将链表的下个节点放入新的对象next中,next为栈帧中的局部变量
Entry<K,V> next = e.next;
//2.重新计算hash值
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//3.重新计算当前e对象的hash值,并计算存储位置
int i = indexFor(e.hash, newCapacity);
//4.将新数组的i的位置的元素放到当前元素的后面,头插法
e.next = newTable[i];
//5.将新数组的i位置设置为当前e
newTable[i] = e;
//6.继续遍历next对象
e = next;
}
}
}
有两个重点需要了解一下:
Entry<K,V> next = e.next,next是局部变量,为线程A私有,因此next值不变,为4。
void transfer(Entry[] newTable, boolean rehash) {
···
for (Entry<K,V> e : table) {
···
}
//上面的for循环等价于
for(int j = 0; j < table.size(); j++){
Entry<K,V> e = table[j];//e指向table[j]的某个位置
}
}
接着说线程A的扩容,由于next和e都指向4,因此在while循环中,e的位置已经由old变为了i位置
(4)后面无论是线程A还是线程B扩容,e的指针都已经发生改变,执行这段代码的时候,next永远不为空,会循环放2和4,产生死循环
e.next = newTable[i];
//5.将新数组的i位置设置为当前e
newTable[i] = e;
(5)发生死循环
HashMap在jdk1.7中多线程会发生死循环的原因分析完成了。jdk1.8中HashMap去除了transfer方法,优化了链表插入方式,改为尾插法,避免了死循环。
jdk1.8中,HashMap在扩容的时候使用尾插法避免了死循环问题,但是put值覆盖的问题没有解决,接下来分析一下put为什么会造成值覆盖的问题。
原因resize扩容一样,当线程A执行完"if ((p = tab[i = (n - 1) & hash]) == null)"之后被线程B抢占资源继续执行,比如线程A定义的i=10,之后线程B执行完之后,i=10的位置已经有数据了,那么线程A继续执行的时候会将i=10的位置的数据覆盖,造成不安全的问题。接下来用代码演示一下put方法值覆盖的现象:
代码:
public class HashMapThreadDemo {
static HashMap<Integer, String> map = new HashMap<>();//存值
static ThreadLocal<Integer> count = new ThreadLocal<>();//计数器
static CountDownLatch countDownLatch = new CountDownLatch(2);//等待两个线程执行完主线程再继续执行
static Integer i = 0;//作为key自增
public static void main(String[] args) throws InterruptedException {
Thread t1 = new Thread(new HashMapThread(), "线程A");
Thread t2 = new Thread(new HashMapThread(), "线程B");
t1.start();
t2.start();
countDownLatch.await();
System.out.println("执行完成!map:" + map);
}
static class HashMapThread extends Thread {
@Override
public void run() {
if (count.get() == null) {
count.set(0);
}
//本地运行50次
while (count.get() < 50) {
String value = Thread.currentThread().getName() + "_" + i;
map.put(i, value);
System.out.println(Thread.currentThread().getName() + " key:" + i + " value:" + value + " 次数count:" + count.get());
count.set(count.get() + 1);
i++;
}
countDownLatch.countDown();
}
}
}
结果:
HashMap线程不安全的问题分析完成了。如果不太了解JVM里面的具体逻辑的话,直接看代码可能会云里雾里,不太了解JVM虚拟机的栈和堆各个对象存储以及运行机制的话,建议先了解一下JVM变量以及对象的存储相关知识,再回头看HashMap死循环的原因会理解的更加透彻!