HashMap在并發下可能出現的問題分析

我們都知道，hashmap在并發環境下使用可能出現問題，但是具體表現，以及為什麼出現并發問題，

可能并不是所有人都了解，這篇文章記錄一下hashmap在多線程環境下可能出現的問題以及如何避免。

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

大家知道hashmap内部實作是通過拉鍊法解決哈希沖突的，也就是通過連結清單的結構儲存散列到同一數組位置的兩個值，

put操作主要是判空，對key的hashcode執行一次hashmap自己的哈希函數，得到bucketindex位置，還有對重複key的覆寫操作。

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

<code>public</code> <code>v put(k key, v value) {</code>

<code> </code><code>return</code> <code>putfornullkey(value);</code>

<code> </code><code>//得到key的hashcode，同時再做一次hash操作</code>

<code> </code><code>int</code> <code>hash = hash(key.hashcode());</code>

<code> </code><code>//對數組長度取餘，決定下标位置</code>

<code> </code><code>int</code> <code>i = indexfor(hash, table.length);</code>

<code> </code><code>* 首先找到數組下标處的連結清單結點，</code>

<code> </code><code>* 判斷key對一個的hash值是否已經存在，如果存在将其替換為新的value</code>

<code> </code><code>for</code> <code>(entry<k,v> e = table[i]; e != </code><code>null</code><code>; e = e.next) {</code>

<code> </code><code>object k;</code>

<code> </code><code>if</code> <code>(e.hash == hash && ((k = e.key) == key || key.equals(k))) {</code>

<code> </code><code>v oldvalue = e.value;</code>

<code> </code><code>e.value = value;</code>

<code> </code><code>e.recordaccess(</code><code>this</code><code>);</code>

<code> </code><code>return</code> <code>oldvalue;</code>

<code> </code><code>modcount++;</code>

<code> </code><code>addentry(hash, key, value, i);</code>

<code> </code><code>return</code> <code>null</code><code>;</code>

涉及到的幾個方法：

<code>static</code> <code>int</code> <code>hash(</code><code>int</code> <code>h) {</code>

<code> </code><code>return</code> <code>h ^ (h >>> </code><code>7</code><code>) ^ (h >>> </code><code>4</code><code>);</code>

<code>static</code> <code>int</code> <code>indexfor(</code><code>int</code> <code>h, </code><code>int</code> <code>length) {</code>

<code> </code><code>return</code> <code>h & (length-</code><code>1</code><code>);</code>

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

<code>public</code> <code>v get(object key) {</code>

<code> </code><code>return</code> <code>getfornullkey();</code>

<code> </code><code>* 先定位到數組元素，再周遊該元素處的連結清單</code>

<code> </code><code>* 判斷的條件是key的hash值相同，并且連結清單的存儲的key值和傳入的key值相同</code>

<code> </code><code>for</code> <code>(entry<k,v> e = table[indexfor(hash, table.length)];e != </code><code>null</code><code>;e = e.next) {</code>

<code> </code><code>if</code> <code>(e.hash == hash && ((k = e.key) == key || key.equals(k)))</code>

<code> </code><code>return</code> <code>e.value;</code>

看一下連結清單的結點資料結構，儲存了四個字段，包括key，value，key對應的hash值以及連結清單的下一個節點：

<code>static</code> <code>class</code> <code>entry<k,v> </code><code>implements</code> <code>map.entry<k,v> {</code>

<code> </code><code>final</code> <code>k key;</code><code>//key-value結構的key</code>

<code> </code><code>v value;</code><code>//存儲值</code>

<code> </code><code>entry<k,v> next;</code><code>//指向下一個連結清單節點</code>

<code> </code><code>final</code> <code>int</code> <code>hash;</code><code>//哈希值</code>

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

不過結合hashmap的實作，考慮下面的情況，如果内部entry[] tablet的容量很小，或者直接極端化為table長度為1的場景，那麼全部的資料元素都會産生碰撞，

這時候的哈希表成為一條單連結清單，查找和添加的時間複雜度變為o(n)，失去了哈希表的意義。

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

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

<code>void</code> <code>addentry(</code><code>int</code> <code>hash, k key, v value, </code><code>int</code> <code>bucketindex) {</code>

<code> </code><code>entry<k,v> e = table[bucketindex];</code>

<code> </code><code>table[bucketindex] = </code><code>new</code> <code>entry<k,v>(hash, key, value, e);</code>

<code> </code><code>if</code> <code>(size++ >= threshold)</code>

<code> </code><code>resize(</code><code>2</code> <code>* table.length);</code>

這裡面resize的過程，就是再散列調整table大小的過程，預設是目前table容量的兩倍。

<code>void</code> <code>resize(</code><code>int</code> <code>newcapacity) {</code>

<code> </code><code>entry[] oldtable = table;</code>

<code> </code><code>int</code> <code>oldcapacity = oldtable.length;</code>

<code> </code><code>if</code> <code>(oldcapacity == maximum_capacity) {</code>

<code> </code><code>threshold = integer.max_value;</code>

<code> </code><code>return</code><code>;</code>

<code> </code><code>entry[] newtable = </code><code>new</code> <code>entry[newcapacity];</code>

<code> </code><code>//初始化一個大小為oldtable容量兩倍的新數組newtable</code>

<code> </code><code>transfer(newtable);</code>

<code> </code><code>table = newtable;</code>

<code> </code><code>threshold = (</code><code>int</code><code>)(newcapacity * loadfactor);</code>

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

這個transfer的過程在并發環境下會發生錯誤，導緻數組連結清單中的連結清單形成循環連結清單，在後面的get操作時e = e.next操作無限循環，infinite loop出現。

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

hashmap在并發環境下多線程put後可能導緻get死循環，具體表現為cpu使用率100%，

看一下transfer的過程：

<code>void</code> <code>transfer(entry[] newtable) {</code>

<code> </code><code>entry[] src = table;</code>

<code> </code><code>int</code> <code>newcapacity = newtable.length;</code>

<code> </code><code>entry<k,v> e = src[j];</code>

<code> </code><code>//假設第一個線程執行到這裡因為某種原因挂起</code>

<code> </code><code>entry<k,v> next = e.next;</code>

<code> </code><code>int</code> <code>i = indexfor(e.hash, newcapacity);</code>

<code> </code><code>e.next = newtable[i];</code>

<code> </code><code>newtable[i] = e;</code>

<code> </code><code>} </code><code>while</code> <code>(e != </code><code>null</code><code>);</code>

1）假設我們有兩個線程。我用紅色和淺藍色标注了一下。我們再回頭看一下我們的 transfer代碼中的這個細節： <code>do</code> <code>{</code> <code> </code><code>entry<k,v> next = e.next;</code><code>// <--假設線程一執行到這裡就被排程挂起了</code> <code> </code><code>int</code> <code>i = indexfor(e.hash, newcapacity);</code> <code> </code><code>e.next = newtable[i];</code> <code> </code><code>newtable[i] = e;</code> <code> </code><code>e = next;</code> <code>} </code><code>while</code> <code>(e != </code><code>null</code><code>);</code> 而我們的線程二執行完成了。于是我們有下面的這個樣子。

HashMap在并發下可能出現的問題分析
注意，因為thread1的 e 指向了key(3)，而next指向了key(7)，其線上程二rehash後，指向了線程二重組後的連結清單。我們可以看到連結清單的順序被反轉後。 2）線程一被排程回來執行。先是執行 newtalbe[i] = e; 然後是e = next，導緻了e指向了key(7)，而下一次循環的next = e.next導緻了next指向了key(3)

HashMap在并發下可能出現的問題分析
3）一切安好。線程一接着工作。把key(7)摘下來，放到newtable[i]的第一個，然後把e和next往下移。

HashMap在并發下可能出現的問題分析
4）環形連結出現。 e.next = newtable[i] 導緻 key(3).next 指向了 key(7) 注意：此時的key(7).next 已經指向了key(3)，環形連結清單就這樣出現了。

HashMap在并發下可能出現的問題分析
于是，當我們的線程一調用到，hashtable.get(11)時，悲劇就出現了——infinite loop。

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

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

<code>public</code> <code>class</code> <code>mapthread </code><code>extends</code> <code>thread{</code>

<code> </code><code>* 類的靜态變量是各個執行個體共享的，是以并發的執行此線程一直在操作這兩個變量</code>

<code> </code><code>* 選擇atomicinteger避免可能的int++并發問題</code>

<code> </code><code>private</code> <code>static</code> <code>atomicinteger ai = </code><code>new</code> <code>atomicinteger(</code><code>0</code><code>);</code>

<code> </code><code>//初始化一個table長度為1的哈希表</code>

<code> </code><code>private</code> <code>static</code> <code>hashmap<integer, integer> map = </code><code>new</code> <code>hashmap<integer, integer>(</code><code>1</code><code>);</code>

<code> </code><code>//如果使用concurrenthashmap，不會出現類似的問題</code>

<code>// private static concurrenthashmap<integer, integer> map = new concurrenthashmap<integer, integer>(1);</code>

<code> </code><code>public</code> <code>void</code> <code>run()</code>

<code> </code><code>while</code> <code>(ai.get() < </code><code>100000</code><code>)</code>

<code> </code><code>ai.incrementandget();</code>

<code> </code><code>system.out.println(thread.currentthread().getname()+</code><code>"線程即将結束"</code><code>);</code>

測試一下：

<code>public</code> <code>static</code> <code>void</code> <code>main(string[] args){</code>

<code> </code><code>mapthread t0 = </code><code>new</code> <code>mapthread();</code>

<code> </code><code>mapthread t1 = </code><code>new</code> <code>mapthread();</code>

<code> </code><code>mapthread t2 = </code><code>new</code> <code>mapthread();</code>

<code> </code><code>mapthread t3 = </code><code>new</code> <code>mapthread();</code>

<code> </code><code>mapthread t4 = </code><code>new</code> <code>mapthread();</code>

<code> </code><code>mapthread t5 = </code><code>new</code> <code>mapthread();</code>

<code> </code><code>mapthread t6 = </code><code>new</code> <code>mapthread();</code>

<code> </code><code>mapthread t7 = </code><code>new</code> <code>mapthread();</code>

<code> </code><code>mapthread t8 = </code><code>new</code> <code>mapthread();</code>

<code> </code><code>mapthread t9 = </code><code>new</code> <code>mapthread();</code>

<code> </code><code>t0.start();</code>

<code> </code><code>t1.start();</code>

<code> </code><code>t2.start();</code>

<code> </code><code>t3.start();</code>

<code> </code><code>t4.start();</code>

<code> </code><code>t5.start();</code>

<code> </code><code>t6.start();</code>

<code> </code><code>t7.start();</code>

<code> </code><code>t8.start();</code>

<code> </code><code>t9.start();</code>

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

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

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

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

hashmap另外一個并發可能出現的問題是，可能産生元素丢失的現象。

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

導緻兩個線程得到同樣的bucketindex去存儲，就可能會出現覆寫丢失的情況：

<code> </code><code>//多個線程操作數組的同一個位置</code>

<code> </code><code>entry<k,v> e = table[bucketindex];</code>

<code> </code><code>table[bucketindex] = </code><code>new</code> <code>entry<k,v>(hash, key, value, e);</code>

<code> </code><code>if</code> <code>(size++ >= threshold)</code>

<code> </code><code>resize(</code><code>2</code> <code>* table.length);</code>

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

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

使用并發包下的java.util.concurrent.concurrenthashmap，concurrenthashmap實作了更進階的線程安全；

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

HashMap在并發下可能出現的問題分析

繼續閱讀

【圖解HTTP】——確定Web安全的HTTPSHTTPS小結

網絡攻防技術（2021期末考試）

華為筆試軟體

軟體設計師筆記-----系統安全分析與設計五、系統安全分析與設計

軟考-軟體設計師筆記五（系統安全分析與設計）資訊系統安全屬性對稱加密技術非對稱加密技術資訊摘要數字簽名數字信封與PGP各個網絡層次的安全保障網絡威脅與攻擊防火牆技術

初談驗證碼與驗證碼設計

項目管理那些事兒

OS --written test1

OS-written test2

壓縮編碼M-JPEG、MPEG4、H.264

内網滲透1一、資訊收集二、一些概念三、提權四、擷取目前機器下各類密碼四、用到的工具

DOG（4）：解析器的部分實作細節先來說說parser一些可能迷惑的地方結果如何傳回?pcd其實是一回事最後的一點說明

Kali的安裝、配置和換國内源KALI的安裝、配置

轉詳解C#資料庫存取圖檔三大方式

BMP檔案結構及圖像每行位元組計算方法

磁盤結構及在Linux中的命名