HashMap在多線程環境下的問題怎么避免

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

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

1.HashMap的put和get操作

大家知道HashMap內部實現是通過拉鏈法解決哈希沖突的，也就是通過鏈表的結構保存散列到同一數組位置的兩個值，

put操作主要是判空，對key的hashcode執行一次HashMap自己的哈希函數，得到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);
}

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

看一下鏈表的結點數據結構，保存了四個字段，包括key，value，key對應的hash值以及鏈表的下一個節點：

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

2.Rehash/再散列擴展內部數組長度

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

不過結合HashMap的實現，考慮下面的情況，如果內部Entry[] tablet的容量很小，或者直接極端化為table長度為1的場景，那么全部的數據元素都會產生碰撞，

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

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

這就需要在哈希表使用的過程中不斷的對table容量進行調整，看一下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的過程，就是再散列調整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容量兩倍的新數組newTable
 transfer(newTable);
 table = newTable;
 threshold = (int)(newCapacity * loadFactor);
}

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

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

下面具體分析HashMap的并發問題的表現以及如何出現的。

3.HashMap在多線程put后可能導致get無限循環

HashMap在并發環境下多線程put后可能導致get死循環，具體表現為CPU使用率100%，

看一下transfer的過程：

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

并發下的Rehash

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

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

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

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

2）線程一被調度回來執行。

• 先是執行 newTalbe[i] = e;

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

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

3）一切安好。

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

4）環形鏈接出現。

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

注意：此時的key(7).next 已經指向了key(3)， 環形鏈表就這樣出現了。

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

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

這里在run中執行了一個自增操作，i++非原子操作，使用AtomicInteger避免可能出現的問題：

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

注意并發問題并不是一定會產生，可以多執行幾次，

我試驗了上面的代碼很容易產生無限循環，控制臺不能終止，有線程始終在執行中，

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

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

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

HashMap另外一個并發可能出現的問題是，可能產生元素丟失的現象。

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

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

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

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

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

使用并發包下的java.util.concurrent.ConcurrentHashMap，ConcurrentHashMap實現了更高級的線程安全；

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

到此，關于“HashMap在多線程環境下的問題怎么避免”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！