java8的ConcurrentHashMap為何放棄分段鎖

2019 年 10 月 5 日
筆記

今天突然被一個同事問到java8為何放棄分段鎖，於是花了點時間針對這個問題進行了小小的總結。

jdk1.7分段鎖的實現

和hashmap一樣，在jdk1.7中ConcurrentHashMap的底層數據結構是數組加鏈表。和hashmap不同的是ConcurrentHashMap中存放的數據是一段段的，即由多個Segment(段)組成的。每個Segment中都有著類似於數組加鏈表的結構。

關於Segment

ConcurrentHashMap有3個參數：

initialCapacity：初始總容量，默認16
loadFactor：載入因子，默認0.75
concurrencyLevel：並發級別，默認16

其中並發級別控制了Segment的個數，在一個ConcurrentHashMap創建後Segment的個數是不能變的，擴容過程過改變的是每個Segment的大小。

關於分段鎖

段Segment繼承了重入鎖ReentrantLock，有了鎖的功能，每個鎖控制的是一段，當每個Segment越來越大時，鎖的粒度就變得有些大了。

分段鎖的優勢在於保證在操作不同段 map 的時候可以並發執行，操作同段 map 的時候，進行鎖的競爭和等待。這相對於直接對整個map同步synchronized是有優勢的。
缺點在於分成很多段時會比較浪費記憶體空間(不連續，碎片化); 操作map時競爭同一個分段鎖的概率非常小時，分段鎖反而會造成更新等操作的長時間等待; 當某個段很大時，分段鎖的性能會下降。

jdk1.8的map實現

和hashmap一樣,jdk 1.8中ConcurrentHashmap採用的底層數據結構為數組+鏈表+紅黑樹的形式。數組可以擴容，鏈表可以轉化為紅黑樹。

什麼時候擴容？

當前容量超過閾值
當鏈表中元素個數超過默認設定（8個），當數組的大小還未超過64的時候，此時進行數組的擴容，如果超過則將鏈錶轉化成紅黑樹

什麼時候鏈錶轉化為紅黑樹？

當數組大小已經超過64並且鏈表中的元素個數超過默認設定（8個）時，將鏈錶轉化為紅黑樹

ConcurrentHashMap的put操作程式碼如下:

把數組中的每個元素看成一個桶。可以看到大部分都是CAS操作，加鎖的部分是對桶的頭節點進行加鎖，鎖粒度很小。

為什麼不用ReentrantLock而用synchronized ?

減少記憶體開銷:如果使用ReentrantLock則需要節點繼承AQS來獲得同步支援，增加記憶體開銷，而1.8中只有頭節點需要進行同步。
內部優化:synchronized則是JVM直接支援的，JVM能夠在運行時作出相應的優化措施：鎖粗化、鎖消除、鎖自旋等等。

參考

https://my.oschina.net/pingpangkuangmo/blog/817973
https://www.wanaright.com/2018/09/30/java10-concurrenthashmap-no-segment-lock/
https://blog.csdn.net/mian_csdn/article/details/70185104