JDK1.7
JDK1.7 及之前版本的 HashMap在多线程环境下，扩容操作可能存在死循环问题。
这是由于当一个桶位中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置。
从而形成一个环形链表，进而使得查询元素的操作，陷入死循环无法结束。
JDK1.8
为了解决这个问题，JDK1.8 版本的 HashMap 采用了尾插法，而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。
但是还是不建议在多线程下使用，因为多线程下使用HashMap， 还是会存在数据覆盖的问题。
并发环境下，推荐使用ConcurrentHashMap。
上面是结论，下面我们一起探讨下具体的原因。
原因分析
HashMap的内部实现：基于数组和链表和红黑树来实现的，红黑树是JDK1.8增加的。
如下图所示：
它使用哈希函数将键映射到数组索引，并将具有相同哈希码值的键值对存储在同一个链表（或红黑树）中，以解决哈希冲突。
如果数组桶尺寸很小，想放入更多的键值对，就会检查容量有没有超过设定的 threshold。
如果超过，需要增大 Hash 表的尺寸，这就需要扩容(rehash)，死循环就出在这里。
源码步骤，如下：
第一步：Put 一个 Key
public V put(K key, V value) {
......
// 计算 Hash 值
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);
//查看当前的 size 是否超过了设定的阈值 threshold，如果超过，需要 resize
if (size++ >= threshold)
resize(2 * table.length);
}
第三步：数据迁移
新建一个更大尺寸的 hash 表，然后把数据从老的 Hash 表中迁移到新的 Hash 表中。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
......
// 创建一个新的 Hash Table
Entry[] newTable = new Entry[newCapacity];
// 将 Old Hash Table 上的数据迁移到 New Hash Table 上
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
而这段代码中又调用了transfer()方法，重点来了：
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
//下面这段代码的意思是：
// 从OldTable里摘一个元素出来，然后放到NewTable中
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);
}
}
}
死循环问题 就是发生在这个方法里的，在进行元素转移时transfer()方法里会调用下面四行代码：
Entry<K,V> next = e.next; e.next = newTable[i]; newTable[i] = e; e = next;
该方法实现的机制就是：将每个链表转化到新链表，并且链表中的位置发生反转，而这在多线程情况下是很容易造成链表回路，从而发生 get() 死循环。
为了在多线程环境中使用哈希表而避免上述问题，可以使用以下替代方案：
1.使用Collections.synchronizedMap
这个方法可以将普通的HashMap包装成线程安全的同步Map，但是在高并发场景下性能较低。
2.使用ConcurrentHashMap
ConcurrentHashMap是专门为并发设计的哈希表，它采用了分段锁（在JDK 7及之前）或CAS操作（在JDK 8及之后），可以在高并发环境下提供更高的性能和线程安全性。
在多线程环境中，优先选择ConcurrentHashMap。
import java.util.concurrent.ConcurrentHashMap;
import java.util.Map;
public class ConcurrentHashMapExample {
public static void main(String[] args) {
final Map<Integer, String> map = new ConcurrentHashMap<>();
// 启动多个线程同时向ConcurrentHashMap中添加数据
for (int i = 0; i < 1000; i++) {
final int key = i;
new Thread(() -> map.put(key, "value" + key)).start();
}
// 读取数据
new Thread(() -> {
for (int i = 0; i < 1000; i++) {
System.out.println(map.get(i));
}
}).start();
}
}
关于mikechen
mikechen睿哥，10年+大厂架构经验，资深技术专家，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
关注「mikechen」公众号，获取更多技术干货！
