京東一面：為什么 HashMap 是線程不安全的？
這是《Java 程序員進(jìn)階之路》專(zhuān)欄的第 58 篇，我們來(lái)聊聊為什么 HashMap 是線程不安全的。
為了便于大家更系統(tǒng)化地學(xué)習(xí) Java，二哥已經(jīng)將《Java 程序員進(jìn)階之路》專(zhuān)欄開(kāi)源到 GitHub 上了，大家只需輕輕地 star 一下，就可以和所有的小伙伴一起打怪升級(jí)了。
GitHub 地址：https://github.com/itwanger/toBeBetterJavaer
01、多線程下擴(kuò)容會(huì)死循環(huán)
眾所周知，HashMap 是通過(guò)拉鏈法來(lái)解決哈希沖突的，也就是當(dāng)哈希沖突時(shí)，會(huì)將相同哈希值的鍵值對(duì)通過(guò)鏈表的形式存放起來(lái)。
JDK 7 時(shí)，采用的是頭部插入的方式來(lái)存放鏈表的，也就是下一個(gè)沖突的鍵值對(duì)會(huì)放在上一個(gè)鍵值對(duì)的前面（同一位置上的新元素被放在鏈表的頭部）。擴(kuò)容的時(shí)候就有可能導(dǎo)致出現(xiàn)環(huán)形鏈表，造成死循環(huán)。
resize 方法的源碼：
// newCapacity為新的容量
void resize(int newCapacity) {
// 小數(shù)組，臨時(shí)過(guò)度下
Entry[] oldTable = table;
// 擴(kuò)容前的容量
int oldCapacity = oldTable.length;
// MAXIMUM_CAPACITY 為最大容量，2 的 30 次方 = 1<<30
if (oldCapacity == MAXIMUM_CAPACITY) {
// 容量調(diào)整為 Integer 的最大值 0x7fffffff（十六進(jìn)制）=2 的 31 次方-1
threshold = Integer.MAX_VALUE;
return;
}
// 初始化一個(gè)新的數(shù)組（大容量）
Entry[] newTable = new Entry[newCapacity];
// 把小數(shù)組的元素轉(zhuǎn)移到大數(shù)組中
transfer(newTable, initHashSeedAsNeeded(newCapacity));
// 引用新的大數(shù)組
table = newTable;
// 重新計(jì)算閾值
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
transfer 方法用來(lái)轉(zhuǎn)移，將小數(shù)組的元素拷貝到新的數(shù)組中。
void transfer(Entry[] newTable, boolean rehash) {
// 新的容量
int newCapacity = newTable.length;
// 遍歷小數(shù)組
for (Entry<K,V> e : table) {
while(null != e) {
// 拉鏈法，相同 key 上的不同值
Entry<K,V> next = e.next;
// 是否需要重新計(jì)算 hash
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
// 根據(jù)大數(shù)組的容量，和鍵的 hash 計(jì)算元素在數(shù)組中的下標(biāo)
int i = indexFor(e.hash, newCapacity);
// 同一位置上的新元素被放在鏈表的頭部
e.next = newTable[i];
// 放在新的數(shù)組上
newTable[i] = e;
// 鏈表上的下一個(gè)元素
e = next;
}
}
}
注意 e.next = newTable[i] 和 newTable[i] = e 這兩行代碼，就會(huì)將同一位置上的新元素被放在鏈表的頭部。
擴(kuò)容前的樣子假如是下面這樣子。
那么正常擴(kuò)容后就是下面這樣子。
假設(shè)現(xiàn)在有兩個(gè)線程同時(shí)進(jìn)行擴(kuò)容，線程 A 在執(zhí)行到 newTable[i] = e; 被掛起，此時(shí)線程 A 中：e=3、next=7、e.next=null
線程 B 開(kāi)始執(zhí)行，并且完成了數(shù)據(jù)轉(zhuǎn)移。
此時(shí)，7 的 next 為 3，3 的 next 為 null。
隨后線程A獲得CPU時(shí)間片繼續(xù)執(zhí)行 newTable[i] = e，將3放入新數(shù)組對(duì)應(yīng)的位置，執(zhí)行完此輪循環(huán)后線程A的情況如下：
執(zhí)行下一輪循環(huán)，此時(shí) e=7，原本線程 A 中 7 的 next 為 5，但由于 table 是線程 A 和線程 B 共享的，而線程 B 順利執(zhí)行完后，7 的 next 變成了 3，那么此時(shí)線程 A 中，7 的 next 也為 3 了。
采用頭部插入的方式，變成了下面這樣子：
好像也沒(méi)什么問(wèn)題，此時(shí) next = 3，e = 3。
進(jìn)行下一輪循環(huán)，但此時(shí)，由于線程 B 將 3 的 next 變?yōu)榱?null，所以此輪循環(huán)應(yīng)該是最后一輪了。
接下來(lái)當(dāng)執(zhí)行完 e.next=newTable[i] 即 3.next=7 后，3 和 7 之間就相互鏈接了，執(zhí)行完 newTable[i]=e 后，3 被頭插法重新插入到鏈表中，執(zhí)行結(jié)果如下圖所示：
套娃開(kāi)始，元素 5 也就成了棄嬰，慘~~~
不過(guò)，JDK 8 時(shí)已經(jīng)修復(fù)了這個(gè)問(wèn)題，擴(kuò)容時(shí)會(huì)保持鏈表原來(lái)的順序，參照HashMap 擴(kuò)容機(jī)制的這一篇。
02、多線程下 put 會(huì)導(dǎo)致元素丟失
正常情況下，當(dāng)發(fā)生哈希沖突時(shí)，HashMap 是這樣的：
但多線程同時(shí)執(zhí)行 put 操作時(shí)，如果計(jì)算出來(lái)的索引位置是相同的，那會(huì)造成前一個(gè) key 被后一個(gè) key 覆蓋，從而導(dǎo)致元素的丟失。
put 的源碼：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 步驟①：tab為空則創(chuàng)建
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 步驟②：計(jì)算index，并對(duì)null做處理
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 步驟③：節(jié)點(diǎn)key存在，直接覆蓋value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 步驟④：判斷該鏈為紅黑樹(shù)
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 步驟⑤：該鏈為鏈表
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//鏈表長(zhǎng)度大于8轉(zhuǎn)換為紅黑樹(shù)進(jìn)行處理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// key已經(jīng)存在直接覆蓋value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 步驟⑥、直接覆蓋
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 步驟⑦：超過(guò)最大容量 就擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
問(wèn)題發(fā)生在步驟 ② 這里：
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
兩個(gè)線程都執(zhí)行了 if 語(yǔ)句，假設(shè)線程 A 先執(zhí)行了 tab[i] = newNode(hash, key, value, null)，那 table 是這樣的：
接著，線程 B 執(zhí)行了 tab[i] = newNode(hash, key, value, null)，那 table 是這樣的：
3 被干掉了。
03、put 和 get 并發(fā)時(shí)會(huì)導(dǎo)致 get 到 null
線程 A 執(zhí)行put時(shí)，因?yàn)樵貍€(gè)數(shù)超出閾值而出現(xiàn)擴(kuò)容，線程B 此時(shí)執(zhí)行g(shù)et，有可能導(dǎo)致這個(gè)問(wèn)題。
注意來(lái)看 resize 源碼：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 超過(guò)最大值就不再擴(kuò)充了，就只好隨你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 沒(méi)超過(guò)最大值，就擴(kuò)充為原來(lái)的2倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 計(jì)算新的resize上限
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
}
線程 A 執(zhí)行完 table = newTab 之后，線程 B 中的 table 此時(shí)也發(fā)生了變化，此時(shí)去 get 的時(shí)候當(dāng)然會(huì) get 到 null 了，因?yàn)樵剡€沒(méi)有轉(zhuǎn)移。
點(diǎn)擊下方的名片，回復(fù)關(guān)鍵字「03」 就可以獲取《Java 程序員進(jìn)階之路》的 PDF 版了。
點(diǎn)擊閱讀原文也可以跳轉(zhuǎn)到在線閱讀地址，我們下期見(jiàn)（記得給二哥 star 哦）~
