您好,登錄后才能下訂單哦!
本篇內(nèi)容主要講解“Java中為什么HashMap線程不安全”,感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷,實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“Java中為什么HashMap線程不安全”吧!
眾所周知,HashMap 是通過拉鏈法來解決哈希沖突的,也就是當(dāng)哈希沖突時(shí),會(huì)將相同哈希值的鍵值對(duì)通過鏈表的形式存放起來。
JDK 7 時(shí),采用的是頭部插入的方式來存放鏈表的,也就是下一個(gè)沖突的鍵值對(duì)會(huì)放在上一個(gè)鍵值對(duì)的前面(同一位置上的新元素被放在鏈表的頭部)。擴(kuò)容的時(shí)候就有可能導(dǎo)致出現(xiàn)環(huán)形鏈表,造成死循環(huán)。
resize 方法的源碼:
// newCapacity為新的容量 void resize(int newCapacity) { // 小數(shù)組,臨時(shí)過度下 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 方法用來轉(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 開始執(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 了。
采用頭部插入的方式,變成了下面這樣子:
好像也沒什么問題,此時(shí) next = 3,e = 3。
進(jìn)行下一輪循環(huán),但此時(shí),由于線程 B 將 3 的 next 變?yōu)榱?null,所以此輪循環(huán)應(yīng)該是最后一輪了。
接下來當(dāng)執(zhí)行完 e.next=newTable[i]
即 3.next=7 后,3 和 7 之間就相互鏈接了,執(zhí)行完 newTable[i]=e
后,3 被頭插法重新插入到鏈表中,執(zhí)行結(jié)果如下圖所示:
套娃開始,元素 5 也就成了棄嬰,慘~~~
不過,JDK 8 時(shí)已經(jīng)修復(fù)了這個(gè)問題,擴(kuò)容時(shí)會(huì)保持鏈表原來的順序,參照HashMap 擴(kuò)容機(jī)制的這一篇。
正常情況下,當(dāng)發(fā)生哈希沖突時(shí),HashMap 是這樣的:
但多線程同時(shí)執(zhí)行 put 操作時(shí),如果計(jì)算出來的索引位置是相同的,那會(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; // 步驟④:判斷該鏈為紅黑樹 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); //鏈表長度大于8轉(zhuǎn)換為紅黑樹進(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; // 步驟⑦:超過最大容量 就擴(kuò)容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
問題發(fā)生在步驟 ② 這里:
if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null);
兩個(gè)線程都執(zhí)行了 if 語句,假設(shè)線程 A 先執(zhí)行了 tab[i] = newNode(hash, key, value, null)
,那 table 是這樣的:
接著,線程 B 執(zhí)行了 tab[i] = newNode(hash, key, value, null)
,那 table 是這樣的:
3 被干掉了。
線程 A 執(zhí)行put時(shí),因?yàn)樵貍€(gè)數(shù)超出閾值而出現(xiàn)擴(kuò)容,線程B 此時(shí)執(zhí)行g(shù)et,有可能導(dǎo)致這個(gè)問題。
注意來看 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) { // 超過最大值就不再擴(kuò)充了,就只好隨你碰撞去吧 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 沒超過最大值,就擴(kuò)充為原來的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)樵剡€沒有轉(zhuǎn)移。
到此,相信大家對(duì)“Java中為什么HashMap線程不安全”有了更深的了解,不妨來實(shí)際操作一番吧!這里是億速云網(wǎng)站,更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢,關(guān)注我們,繼續(xù)學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。