HashMap的原理以及如何實(shí)現(xiàn)，之前在 JDK7與JDK8中HashMap的實(shí)現(xiàn) 中已經(jīng)說(shuō)明了。
那么，為什么說(shuō)HashMap是線程不安全的呢?它在多線程環(huán)境下，會(huì)發(fā)生什么情況呢?
1. resize死循環(huán)
我們都知道HashMap初始容量大小為16,一般來(lái)說(shuō)，當(dāng)有數(shù)據(jù)要插入時(shí)，都會(huì)檢查容量有沒(méi)有超過(guò)設(shè)定的thredhold，如果超過(guò)，需要增大Hash表的尺寸，但是這樣一來(lái)，整個(gè)Hash表里的元素都需要被重算一遍。這叫rehash，這個(gè)成本相當(dāng)?shù)拇蟆?/p>
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);
}
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<k,v> e : table) {
while(null != e) {
Entry<k,v> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
大概看下transfer：
對(duì)索引數(shù)組中的元素遍歷
對(duì)鏈表上的每一個(gè)節(jié)點(diǎn)遍歷：用 next 取得要轉(zhuǎn)移那個(gè)元素的下一個(gè)，將 e 轉(zhuǎn)移到新 Hash 表的頭部，使用頭插法插入節(jié)點(diǎn)。
循環(huán)2，直到鏈表節(jié)點(diǎn)全部轉(zhuǎn)移
循環(huán)1，直到所有索引數(shù)組全部轉(zhuǎn)移
經(jīng)過(guò)這幾步，我們會(huì)發(fā)現(xiàn)轉(zhuǎn)移的時(shí)候是逆序的。假如轉(zhuǎn)移前鏈表順序是1->2->3，那么轉(zhuǎn)移后就會(huì)變成3->2->1。這時(shí)候就有點(diǎn)頭緒了，死鎖問(wèn)題不就是因?yàn)?->2的同時(shí)2->1造成的嗎?所以，HashMap 的死鎖問(wèn)題就出在這個(gè) transfer() 函數(shù)上。
1.1 單線程 rehash 詳細(xì)演示
單線程情況下，rehash 不會(huì)出現(xiàn)任何問(wèn)題：
假設(shè)hash算法就是最簡(jiǎn)單的 key mod table.length(也就是數(shù)組的長(zhǎng)度)。
最上面的是old hash 表，其中的Hash表的 size = 2, 所以 key = 3, 7, 5，在 mod 2以后碰撞發(fā)生在 table[1]
接下來(lái)的三個(gè)步驟是 Hash表 resize 到4，并將所有的 <key,value>重新rehash到新 Hash 表的過(guò)程
如圖所示：
1.2 多線程 rehash 詳細(xì)演示
為了思路更清晰，我們只將關(guān)鍵代碼展示出來(lái)
while(null != e) {
Entry<k,v> next = e.next;
e.next = newTable[i];
newTable[i] = e;
e = next;
}
Entry<k,v> next = e.next; ——因?yàn)槭菃捂湵?，如果要轉(zhuǎn)移頭指針，一定要保存下一個(gè)結(jié)點(diǎn)，不然轉(zhuǎn)移后鏈表就丟了
e.next = newTable[i]; ——e 要插入到鏈表的頭部，所以要先用 e.next 指向新的 Hash 表第一個(gè)元素(為什么不加到新鏈表最后?因?yàn)閺?fù)雜度是 O(N))
newTable[i] = e; ——現(xiàn)在新 Hash 表的頭指針仍然指向 e 沒(méi)轉(zhuǎn)移前的第一個(gè)元素，所以需要將新 Hash 表的頭指針指向 e
e = next ——轉(zhuǎn)移 e 的下一個(gè)結(jié)點(diǎn)
假設(shè)這里有兩個(gè)線程同時(shí)執(zhí)行了 put() 操作，并進(jìn)入了 transfer() 環(huán)節(jié)
while(null != e) {
Entry<k,v> next = e.next; //線程1執(zhí)行到這里被調(diào)度掛起了
e.next = newTable[i];
newTable[i] = e;
e = next;
}
那么現(xiàn)在的狀態(tài)為：
從上面的圖我們可以看到，因?yàn)榫€程1的 e 指向了 key(3)，而 next 指向了 key(7)，在線程2 rehash 后，就指向了線程2 rehash 后的鏈表。
然后線程1被喚醒了：
執(zhí)行 e.next = newTable[i] ，于是 key(3)的 next 指向了線程1的新 Hash 表，因?yàn)樾?Hash 表為空，所以 e.next = null ，
執(zhí)行 newTable[i] = e ，所以線程1的新 Hash 表第一個(gè)元素指向了線程2新 Hash 表的 key(3)。好了，e 處理完畢。
執(zhí)行 e = next ，將 e 指向 next，所以新的 e 是 key(7)