原文出處: Hosee
參考:https://www.cnblogs.com/qingyunzong/p/9143249.html
HashMap的原理以及如何實現(xiàn)忱嘹,之前在JDK7與JDK8中HashMap的實現(xiàn)中已經說明了。
那么,為什么說HashMap是線程不安全的呢撤逢?它在多線程環(huán)境下,會發(fā)生什么情況呢?
1. resize死循環(huán)
我們都知道HashMap初始容量大小為16,一般來說,當有數(shù)據(jù)要插入時麻敌,都會檢查容量有沒有超過設定的thredhold,如果超過掂摔,需要增大Hash表的尺寸术羔,但是這樣一來,整個Hash表里的元素都需要被重算一遍乙漓。這叫rehash级历,這個成本相當?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:
- 對索引數(shù)組中的元素遍歷
- 對鏈表上的每一個節(jié)點遍歷:用 next 取得要轉移那個元素的下一個,將 e 轉移到新 Hash 表的頭部簇秒,使用頭插法插入節(jié)點鱼喉。
- 循環(huán)2,直到鏈表節(jié)點全部轉移
- 循環(huán)1趋观,直到所有索引數(shù)組全部轉移
經過這幾步,我們會發(fā)現(xiàn)轉移的時候是逆序的锋边。假如轉移前鏈表順序是1->2->3皱坛,那么轉移后就會變成3->2->1。這時候就有點頭緒了豆巨,死鎖問題不就是因為1->2的同時2->1造成的嗎剩辟?所以,HashMap 的死鎖問題就出在這個transfer()
函數(shù)上往扔。
1.1 單線程 rehash 詳細演示
單線程情況下贩猎,rehash 不會出現(xiàn)任何問題:
- 假設hash算法就是最簡單的 key mod table.length(也就是數(shù)組的長度)。
- 最上面的是old hash 表萍膛,其中的Hash表的 size = 2, 所以 key = 3, 7, 5吭服,在 mod 2以后碰撞發(fā)生在 table[1]
- 接下來的三個步驟是 Hash表 resize 到4,并將所有的
<key,value>
重新rehash到新 Hash 表的過程
如圖所示:
1.2 多線程 rehash 詳細演示
為了思路更清晰蝗罗,我們只將關鍵代碼展示出來
while(null != e) {
Entry<K,V> next = e.next;
e.next = newTable[i];
newTable[i] = e;
e = next;
}
- Entry<K,V> next = e.next;——因為是單鏈表艇棕,如果要轉移頭指針,一定要保存下一個結點串塑,不然轉移后鏈表就丟了
- e.next = newTable[i];——e 要插入到鏈表的頭部沼琉,所以要先用 e.next 指向新的 Hash 表第一個元素(為什么不加到新鏈表最后?因為復雜度是 O(N))
- newTable[i] = e;——現(xiàn)在新 Hash 表的頭指針仍然指向 e 沒轉移前的第一個元素桩匪,所以需要將新 Hash 表的頭指針指向 e
- e = next——轉移 e 的下一個結點
假設這里有兩個線程同時執(zhí)行了put()操作打瘪,并進入了transfer()環(huán)節(jié):
while(null != e) {
Entry<K,V> next = e.next; //線程1執(zhí)行到這里被調度掛起了
e.next = newTable[i];
newTable[i] = e;
e = next;
}
那么現(xiàn)在的狀態(tài)為:
從上面的圖我們可以看到,因為線程1的 e 指向了 key(3),而 next 指向了 key(7)闺骚,在線程2 rehash 后桃移,就指向了線程2 rehash 后的鏈表。
然后線程1被喚醒了:
- 執(zhí)行
e.next = newTable[i]
葛碧,于是 key(3)的 next 指向了線程1的新 Hash 表借杰,因為新 Hash 表為空,所以e.next = null
进泼, - 執(zhí)行
newTable[i] = e
蔗衡,所以線程1的新 Hash 表第一個元素指向了線程2新 Hash 表的 key(3)。好了乳绕,e 處理完畢绞惦。 - 執(zhí)行
e = next
,將 e 指向 next洋措,所以新的 e 是 key(7)
然后該執(zhí)行 key(3)的 next 節(jié)點 key(7)了:
- 現(xiàn)在的 e 節(jié)點是 key(7)济蝉,首先執(zhí)行
Entry<K,V> next = e.next
,那么 next 就是 key(3)了 - 執(zhí)行
e.next = newTable[i]
,于是key(7) 的 next 就成了 key(3) - 執(zhí)行
newTable[i] = e
菠发,那么線程1的新 Hash 表第一個元素變成了 key(7) - 執(zhí)行
e = next
王滤,將 e 指向 next,所以新的 e 是 key(3)
這時候的狀態(tài)圖為:
然后又該執(zhí)行 key(7)的 next 節(jié)點 key(3)了:
- 現(xiàn)在的 e 節(jié)點是 key(3)滓鸠,首先執(zhí)行
Entry<K,V> next = e.next
,那么 next 就是 null - 執(zhí)行
e.next = newTable[i]
雁乡,于是key(3) 的 next 就成了 key(7) - 執(zhí)行
newTable[i] = e
,那么線程1的新 Hash 表第一個元素變成了 key(3) - 執(zhí)行
e = next
糜俗,將 e 指向 next踱稍,所以新的 e 是 key(7)
這時候的狀態(tài)如圖所示:
很明顯,環(huán)形鏈表出現(xiàn)了S颇ā珠月!當然,現(xiàn)在還沒有事情楔敌,因為下一個節(jié)點是 null啤挎,所以transfer()
就完成了,等put()
的其余過程搞定后梁丘,HashMap 的底層實現(xiàn)就是線程1的新 Hash 表了侵浸。
2. fail-fast
如果在使用迭代器的過程中有其他線程修改了map,那么將拋出ConcurrentModificationException氛谜,這就是所謂fail-fast策略掏觉。
這個異常意在提醒開發(fā)者及早意識到線程安全問題,具體原因請查看ConcurrentModificationException的原因以及解決措施
順便再記錄一個HashMap的問題:
為什么String, Interger這樣的wrapper類適合作為鍵值漫? String, Interger這樣的wrapper類作為HashMap的鍵是再適合不過了澳腹,而且String最為常用。因為String是不可變的,也是final的酱塔,而且已經重寫了equals()和hashCode()方法了沥邻。其他的wrapper類也有這個特點。不可變性是必要的羊娃,因為為了要計算hashCode()唐全,就要防止鍵值改變,如果鍵值在放入時和獲取時返回不同的hashcode的話蕊玷,那么就不能從HashMap中找到你想要的對象邮利。不可變性還有其他的優(yōu)點如線程安全。如果你可以僅僅通過將某個field聲明成final就能保證hashCode是不變的垃帅,那么請這么做吧延届。因為獲取對象的時候要用到equals()和hashCode()方法,那么鍵對象正確的重寫這兩個方法是非常重要的贸诚。如果兩個不相等的對象返回不同的hashcode的話方庭,那么碰撞的幾率就會小些,這樣就能提高HashMap的性能酱固。