HashMap为什么线程不安全 - Sanarous的博客

HashMap为什么线程不安全

线程不安全的HashMap

HashMap 在日常开发中是十分常见的,也是我们使用 Map 存储键值对的首选类,关于 HashMap 的源码分析可以看这里。或者需要快速预览 HashMap 结构也可以看这里。由于从 JDK 1.8 开始对 HashMap 进行了优化,增加了红黑树这种数据结构,所以 JDK 1.8 的 HashMap 较为复杂,这里为了简化分析,采用 JDK 1.7 版本版本的 HashMap 进行举例说明。

HashMap 线程不安全主要体现在两个方面:

  1. 多线程环境下对键值对进行修改操作(put 和 remove)会出现丢失更新问题
  2. 多线程环境下进行 resize 扩容操作形成环形链表,导致 get 操作出现死循环,JDK 1.8 已经修复该问题

第一种情况下,我们可以先看一下 JDK 1.7 下 HashMap 的源码中的 put 操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
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;
}

在 put 操作中有一个 addEntry 方法,这是核心方法,其源码如下:

1
2
3
4
5
6
7
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);
}

现在假如 A 线程和 B 线程同时对同一个数组位置调用 addEntry,两个线程会同时得到现在的头结点,然后 A 写入新的头结点之后,B 也写入新的头结点,那 B 的写入操作就会覆盖 A 的写入操作造成 A 的写入操作丢失。

同理可以看一下 remove 操作:

1
2
3
4
public V remove(Object key) {
Entry<K,V> e = removeEntryForKey(key);
return (e == null ? null : e.value);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
final Entry<K,V> removeEntryForKey(Object key) {
int hash = (key == null) ? 0 : hash(key.hashCode());
int i = indexFor(hash, table.length);
Entry<K,V> prev = table[i];
Entry<K,V> e = prev;

while (e != null) {
Entry<K,V> next = e.next;
Object k;
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
modCount++;
size--;
if (prev == e)
table[i] = next;
else
prev.next = next;
e.recordRemoval(this);
return e;
}
prev = e;
e = next;
}

return e;
}

当多个线程同时操作同一个数组位置的时候,也都会先取得现在状态下该位置存储的头结点,然后各自去进行计算操作,之后再把结果写会到该数组位置去,其实写回的时候可能其他的线程已经就把这个位置给修改过了,就会覆盖其他线程的修改,也就是丢失修改问题。

第二种情况中,我们可以看一下 resize 操作的源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
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);
}

/**
* Transfers all entries from current table to newTable.
*/
// 关键在于这个transfer方法,这个方法的作用是将旧hash表中的元素rehash到新的hash表中
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) { // table变量即为旧hash表
while(null != e) {
// #1
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 用元素的hash值计算出这个元素在新hash表中的位置
int i = indexFor(e.hash, newCapacity);
// #2
e.next = newTable[I];
// #3
newTable[i] = e;
// #4
e = next;
}
}
}

假设线程 1 (t1)和线程 2 (t2)同时 resize,两个线程 resize 前,两个线程及 HashMap 的状态如下 :

堆内存中的 HashMap 对象中的 table 字段指向旧的 hash 表,其中 index 为 7 的位置有两个元素,我们以这两个元素的 rehash 为例,看看循环链表是如何形成的。

线程 1 和线程 2 分别 new 了一个 hash 表,用 newTable 字段表示。

Step1: t2 执行完 #1 代码后,CPU且走执行 t1,并且 t1 执行完成

这里可以根据上图推算一下,此时状态如下 :

用 t2.e 表示线程 2 中的局部变量 e,t2.next 同理。

Step2: t2 继续向下执行完本次循环

Step3: t2 继续执行下一次循环

Step4: t2继续下一次循环,循环链表出现

然后我们在这个时候进行一个 get 操作,get 方法源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public V get(Object key) {
if (key == null)
return getForNullKey();
Entry<K,V> entry = getEntry(key);

return null == entry ? null : entry.getValue();
}

final Entry<K,V> getEntry(Object key) {
if (size == 0) {
return null;
}

int hash = (key == null) ? 0 : hash(key);
// 遍历链表
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
// 假设这里条件一直不成立
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
}
return null;
}

由上图可知,for 循环中的 e = e.next永远不会为空,那么,如果 get 一个在这个链表中不存在的 key 时,就会出现死循环了。 更加具体的细节可以见参考文章[2]

实现线程安全

那么如何在多线程环境下使用线程安全的 HashMap 呢?

可以有一下解决方法:

  • 使用 Collections.synchronizedMap(Mao<K,V> m) 方法把 HashMap 变成一个线程安全的 Map
  • 使用 Hashtable、ConcurrentHashMap 这两个线程安全的 Map

参考文章

  1. HashMap为什么是线程不安全的?
  2. 不正确地使用HashMap引发死循环及元素丢失
如果这篇文章对您很有帮助,不妨
-------------    本文结束  感谢您的阅读    -------------
0%