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

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

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

1.HashMap的put和get操作

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

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

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

涉及到的幾個方法：

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é)點數(shù)據(jù)結(jié)構(gòu)，保存了四個字段，包括key，value，key對應的hash值以及鏈表的下一個節(jié)點：

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

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

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

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

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

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

這就需要在哈希表使用的過程中不斷的對table容量進行調(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大小的過程，默認是當前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];
 //初始化一個大小為oldTable容量兩倍的新數(shù)組newTable
 transfer(newTable);
 table = newTable;
 threshold = (int)(newCapacity * loadFactor);
}

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

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

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

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

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

看一下transfer的過程：

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

并發(fā)下的Rehash

1）假設我們有兩個線程。我用紅色和淺藍色標注了一下。

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

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

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

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

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

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

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

3）一切安好。

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

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

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

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

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

針對上面的分析模擬這個例子，

這里在run中執(zhí)行了一個自增操作，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ā)問題并不是一定會產(chǎn)生，可以多執(zhí)行幾次，

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

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

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

4.多線程put的時候可能導致元素丟失

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

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

導致兩個線程得到同樣的bucketIndex去存儲，就可能會出現(xiàn)覆蓋丟失的情況：

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

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

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

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

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

到此，關(guān)于“HashMap在多線程環(huán)境下的問題怎么避免”的學習就結(jié)束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續(xù)學習更多相關(guān)知識，請繼續(xù)關(guān)注億速云網(wǎng)站，小編會繼續(xù)努力為大家?guī)砀鄬嵱玫奈恼拢?/p>