HashMap在多線程環(huán)境下的問題怎么避免

這篇文章主要介紹“HashMap在多線程環(huán)境下的問題怎么避免”，在日常操作中，相信很多人在HashMap在多線程環(huán)境下的問題怎么避免問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”HashMap在多線程環(huán)境下的問題怎么避免”的疑惑有所幫助！接下來，請跟著小編一起來學(xué)習(xí)吧！

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個(gè)行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長期合作伙伴，公司提供的服務(wù)項(xiàng)目有：域名注冊、虛擬主機(jī)、營銷軟件、網(wǎng)站建設(shè)、贛縣網(wǎng)站維護(hù)、網(wǎng)站推廣。

在分析HashMap的并發(fā)問題前，先簡單了解HashMap的put和get基本操作是如何實(shí)現(xiàn)的。

1.HashMap的put和get操作

大家知道HashMap內(nèi)部實(shí)現(xiàn)是通過拉鏈法解決哈希沖突的，也就是通過鏈表的結(jié)構(gòu)保存散列到同一數(shù)組位置的兩個(gè)值，

put操作主要是判空，對key的hashcode執(zhí)行一次HashMap自己的哈希函數(shù)，得到bucketindex位置，還有對重復(fù)key的覆蓋操作。

對照源碼分析一下具體的put操作是如何完成的：

涉及到的幾個(gè)方法：

static int hash(int h) {
 h ^= (h >>> 20) ^ (h >>> 12);
 return h ^ (h >>> 7) ^ (h >>> 4);
}
static int indexFor(int h, int length) {
 return h & (length-1);
}

數(shù)據(jù)put完成以后，就是如何get，我們看一下get函數(shù)中的操作：

看一下鏈表的結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)，保存了四個(gè)字段，包括key，value，key對應(yīng)的hash值以及鏈表的下一個(gè)節(jié)點(diǎn)：

static class Entry<K,V> implements Map.Entry<K,V> {
 final K key;//Key-value結(jié)構(gòu)的key
 V value;//存儲(chǔ)值
 Entry<K,V> next;//指向下一個(gè)鏈表節(jié)點(diǎn)
 final int hash;//哈希值
 }

2.Rehash/再散列擴(kuò)展內(nèi)部數(shù)組長度

哈希表結(jié)構(gòu)是結(jié)合了數(shù)組和鏈表的優(yōu)點(diǎn)，在最好情況下，查找和插入都維持了一個(gè)較小的時(shí)間復(fù)雜度O(1)，

不過結(jié)合HashMap的實(shí)現(xiàn)，考慮下面的情況，如果內(nèi)部Entry[] tablet的容量很小，或者直接極端化為table長度為1的場景，那么全部的數(shù)據(jù)元素都會(huì)產(chǎn)生碰撞，

這時(shí)候的哈希表成為一條單鏈表，查找和添加的時(shí)間復(fù)雜度變?yōu)镺(N)，失去了哈希表的意義。

所以哈希表的操作中，內(nèi)部數(shù)組的大小非常重要，必須保持一個(gè)平衡的數(shù)字，使得哈希碰撞不會(huì)太頻繁，同時(shí)占用空間不會(huì)過大。

這就需要在哈希表使用的過程中不斷的對table容量進(jìn)行調(diào)整，看一下put操作中的addEntry()方法：

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);
 if (size++ >= threshold)
 resize(2 * table.length);
 }

這里面resize的過程，就是再散列調(diào)整table大小的過程，默認(rèn)是當(dāng)前table容量的兩倍。

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];
 //初始化一個(gè)大小為oldTable容量兩倍的新數(shù)組newTable
 transfer(newTable);
 table = newTable;
 threshold = (int)(newCapacity * loadFactor);
}

關(guān)鍵的一步操作是transfer(newTable)，這個(gè)操作會(huì)把當(dāng)前Entry[] table數(shù)組的全部元素轉(zhuǎn)移到新的table中，

這個(gè)transfer的過程在并發(fā)環(huán)境下會(huì)發(fā)生錯(cuò)誤，導(dǎo)致數(shù)組鏈表中的鏈表形成循環(huán)鏈表，在后面的get操作時(shí)e = e.next操作無限循環(huán)，Infinite Loop出現(xiàn)。

下面具體分析HashMap的并發(fā)問題的表現(xiàn)以及如何出現(xiàn)的。

3.HashMap在多線程put后可能導(dǎo)致get無限循環(huán)

HashMap在并發(fā)環(huán)境下多線程put后可能導(dǎo)致get死循環(huán)，具體表現(xiàn)為CPU使用率100%，

看一下transfer的過程：

這里引用酷殼陳皓的博文：

---

并發(fā)下的Rehash

1）假設(shè)我們有兩個(gè)線程。我用紅色和淺藍(lán)色標(biāo)注了一下。

我們再回頭看一下我們的 transfer代碼中的這個(gè)細(xì)節(jié)：

而我們的線程二執(zhí)行完成了。于是我們有下面的這個(gè)樣子。

注意，因?yàn)門hread1的 e 指向了key(3)，而next指向了key(7)，其在線程二rehash后，指向了線程二重組后的鏈表。我們可以看到鏈表的順序被反轉(zhuǎn)后。

2）線程一被調(diào)度回來執(zhí)行。

• 先是執(zhí)行 newTalbe[i] = e;

• 然后是e = next，導(dǎo)致了e指向了key(7)，

• 而下一次循環(huán)的next = e.next導(dǎo)致了next指向了key(3)

3）一切安好。

線程一接著工作。把key(7)摘下來，放到newTable[i]的第一個(gè)，然后把e和next往下移。

4）環(huán)形鏈接出現(xiàn)。

e.next = newTable[i] 導(dǎo)致 key(3).next 指向了 key(7)

注意：此時(shí)的key(7).next 已經(jīng)指向了key(3)， 環(huán)形鏈表就這樣出現(xiàn)了。

于是，當(dāng)我們的線程一調(diào)用到，HashTable.get(11)時(shí)，悲劇就出現(xiàn)了——Infinite Loop。

---

針對上面的分析模擬這個(gè)例子，

這里在run中執(zhí)行了一個(gè)自增操作，i++非原子操作，使用AtomicInteger避免可能出現(xiàn)的問題：

public static void main(String[] args){
 MapThread t0 = new MapThread();
 MapThread t1 = new MapThread();
 // 省略 t2-t9
 t0.start();
 t1.start();
 // 省略 t2-t9
}

注意并發(fā)問題并不是一定會(huì)產(chǎn)生，可以多執(zhí)行幾次，

我試驗(yàn)了上面的代碼很容易產(chǎn)生無限循環(huán)，控制臺(tái)不能終止，有線程始終在執(zhí)行中，

這是其中一個(gè)死循環(huán)的控制臺(tái)截圖，可以看到六個(gè)線程順利完成了put工作后銷毀，還有四個(gè)線程沒有輸出，卡在了put階段，感興趣的可以斷點(diǎn)進(jìn)去看一下：

上面的代碼，如果把注釋打開，換用ConcurrentHashMap就不會(huì)出現(xiàn)類似的問題。

4.多線程put的時(shí)候可能導(dǎo)致元素丟失

HashMap另外一個(gè)并發(fā)可能出現(xiàn)的問題是，可能產(chǎn)生元素丟失的現(xiàn)象。

考慮在多線程下put操作時(shí)，執(zhí)行addEntry(hash, key, value, i)，如果有產(chǎn)生哈希碰撞，

導(dǎo)致兩個(gè)線程得到同樣的bucketIndex去存儲(chǔ)，就可能會(huì)出現(xiàn)覆蓋丟失的情況：

5.使用線程安全的哈希表容器

那么如何使用線程安全的哈希表結(jié)構(gòu)呢，這里列出了幾條建議：

使用Hashtable 類，Hashtable 是線程安全的；

使用并發(fā)包下的java.util.concurrent.ConcurrentHashMap，ConcurrentHashMap實(shí)現(xiàn)了更高級(jí)的線程安全；

或者使用synchronizedMap() 同步方法包裝 HashMap object，得到線程安全的Map，并在此Map上進(jìn)行操作

到此，關(guān)于“HashMap在多線程環(huán)境下的問題怎么避免”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！

網(wǎng)站標(biāo)題：HashMap在多線程環(huán)境下的問題怎么避免
文章來源：http://bm7419.com/article38/ipdssp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站建設(shè)、定制網(wǎng)站、電子商務(wù)、關(guān)鍵詞優(yōu)化、域名注冊、外貿(mào)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)