ConcurrentHashMap為什麼比HashTable性能好
- 2019 年 11 月 24 日
- 筆記
ConcurrentHashMap：分段鎖 Segment+HashEntry
HashTable：競爭同一個鎖 Synchronized
Segment類繼承於ReentrantLock，主要是為了使用ReentrantLock的鎖，ReentrantLock的實現比 synchronized在多個執行緒爭用下的總體開銷小
既然ConcurrentHashMap使用分段鎖Segment來保護不同段的數據，那麼在插入和獲取元素的時候，必須先通過哈希演算法定位到Segment。可以看到ConcurrentHashMap會首先使用Wang/Jenkins hash的變種演算法對元素的hashCode進行一次再哈希。
再哈希，其目的是為了減少哈希衝突，使元素能夠均勻的分布在不同的Segment上，從而提高容器的存取效率。
整個操作是先定位到段，然後委託給段的remove操作。當多個刪除操作並發進行時，只要它們所在的段不相同，它們就可以同時進行。
由於put方法里需要對共享變數進行寫入操作，所以為了執行緒安全，在操作共享變數時必須得加鎖。Put方法首先定位到Segment，然後在Segment里進行插入操作。插入操作需要經歷兩個步驟，第一步判斷是否需要對Segment里的HashEntry數組進行擴容，第二步定位添加元素的位置然後放在HashEntry數組裡。
- 是否需要擴容。在插入元素前會先判斷Segment里的HashEntry數組是否超過容量（threshold），如果超過閥值，數組進行擴容。值得一提的是，Segment的擴容判斷比HashMap更恰當，因為HashMap是在插入元素後判斷元素是否已經到達容量的，如果到達了就進行擴容，但是很有可能擴容之後沒有新元素插入，這時HashMap就進行了一次無效的擴容。
- 如何擴容。擴容的時候首先會創建一個兩倍於原容量的數組，然後將原數組裡的元素進行再hash後插入到新的數組裡。為了高效ConcurrentHashMap不會對整個容器進行擴容，而只對某個segment進行擴容。
get操作不需要鎖
除非讀到的值是空的才會加鎖重讀，我們知道HashTable容器的get方法是需要加鎖的，那麼ConcurrentHashMap的get操作是如何做到不加鎖的呢？原因是它的get方法里將要使用的共享變數都定義成volatile。
size()操作
如果我們要統計整個ConcurrentHashMap里元素的大小，就必須統計所有Segment里元素的大小後求和。Segment里的全局變數count是一個volatile變數，那麼在多執行緒場景下，我們是不是直接把所有Segment的count相加就可以得到整個ConcurrentHashMap大小了呢？不是的，雖然相加時可以獲取每個Segment的count的最新值，但是拿到之後可能累加前使用的count發生了變化，那麼統計結果就不準了。所以最安全的做法，是在統計size的時候把所有Segment的put，remove和clean方法全部鎖住，但是這種做法顯然非常低效。
因為在累加count操作過程中，之前累加過的count發生變化的幾率非常小，所以ConcurrentHashMap的做法是先嘗試2次通過不鎖住Segment的方式來統計各個Segment大小，如果統計的過程中，容器的count發生了變化，則再採用加鎖的方式來統計所有Segment的大小。
那麼ConcurrentHashMap是如何判斷在統計的時候容器是否發生了變化呢？使用modCount變數，在put , remove和clean方法里操作元素前都會將變數modCount進行加1，那麼在統計size前後比較modCount是否發生變化，從而得知容器的大小是否發生變化。
