ConcurrentHashMap

ConcurrentHashMap

為什么要用ConcurrentHashMap

（1）線程不安全的HashMap

在多線程環境下，使用HashMap進行put操作會引起死循環，導致CPU利用率接近100%，所以在并發情況下不能使用HashMap。

HashMap在并發執行put操作時會引起死循環，是因為多線程會導致HashMap的Entry鏈表形成環形數據結構，一旦形成環形數據結構，Entry的next節點永遠不為空，就會產生死循環獲取Entry。

（2）效率低下的HashTable

HashTable容器使用synchronized來保證線程安全，但在線程競爭激烈的情況下HashTable的效率非常低下。因為當一個線程訪問HashTable的同步方法，其他線程也訪問HashTable的同步方法時，會進入阻塞或輪詢狀態。如線程1使用put進行元素添加，線程2不但不能使用put方法添加元素，也不能使用get方法來獲取元素，所以競爭越激烈效率越低。

（3）ConcurrentHashMap的鎖分段技術可有效提升并發訪問率

HashTable容器在競爭激烈的并發環境下表現出效率低下的原因是所有訪問HashTable的線程都必須競爭同一把鎖，假如容器里有多把鎖，每一把鎖用于鎖容器其中一部分數據，那么當多線程訪問容器里不同數據段的數據時，線程間就不會存在鎖競爭，從而可以有效提高并發訪問效率，這就是ConcurrentHashMap所使用的鎖分段技術。首先將數據分成一段一段地存儲，然后給每一段數據配一把鎖，當一個線程占用鎖訪問其中一個段數據的時候，其他段的數據也能被其他線程訪問。

ConcurrentHashMap的結構

ConcurrentHashMap是由Segment數組結構和HashEntry數組結構組成。Segment是一種可重入鎖（ReentrantLock），在ConcurrentHashMap里扮演鎖的角色；HashEntry則用于存儲鍵值對數據。

一個ConcurrentHashMap里包含一個Segment數組。Segment的結構和HashMap類似，是一種數組和鏈表結構。一個Segment里包含一個HashEntry數組，每個HashEntry是一個鏈表結構的元素，每個Segment守護著一個HashEntry數組里的元素，當對HashEntry數組的數據進行修改時，必須首先獲得與它對應的Segment鎖，

ConcurrentHashMap的初始化

ConcurrentHashMap初始化方法是通過initialCapacity、loadFactor和concurrencyLevel等幾個參數來初始化segment數組、段偏移量segmentShift、段掩碼segmentMask和每個segment里的HashEntry數組來實現的。

ConcurrentHashMap的操作

由于put方法里需要對共享變量進行寫入操作，所以為了線程安全，在操作共享變量時必須加鎖。put方法首先定位到Segment，然后在Segment里進行插入操作。插入操作需要經歷兩個步驟，第一步判斷是否需要對Segment里的HashEntry數組進行擴容，第二步定位添加元素的位

置，然后將其放在HashEntry數組里。

（1）是否需要擴容

在插入元素前會先判斷Segment里的HashEntry數組是否超過容量（threshold），如果超過閾值，則對數組進行擴容。值得一提的是，Segment的擴容判斷比HashMap更恰當，因為HashMap是在插入元素后判斷元素是否已經到達容量的，如果到達了就進行擴容，但是很有可能擴容

之后沒有新元素插入，這時HashMap就進行了一次無效的擴容。

（2）如何擴容

在擴容的時候，首先會創建一個容量是原來容量兩倍的數組，然后將原數組里的元素進行再散列后插入到新的數組里。為了高效，ConcurrentHashMap不會對整個容器進行擴容，而只對某個segment進行擴容。

先嘗試2次通過不鎖住Segment的方式來統計各個Segment大小，如果統計的過程中，容器的count發生了變化，則再采用加鎖的方式來統計所有Segment的大小。

那么ConcurrentHashMap是如何判斷在統計的時候容器是否發生了變化呢？使用modCount變量，在put、remove和clean方法里操作元素前都會將變量modCount進行加1，那么在統計size前后比較modCount是否發生變化，從而得知容器的大小是否發生變化。

HashMap Java 容器 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。