【面試普通人VS高手系列】ConcurrentHashMap 底層具體實現知道嗎？實現原理是什麼？

之前分享過一期HashMap的面試題，然後有個小夥伴私信我說，他遇到了一個ConcurrentHashMap的問題不知道怎麼回答。
於是，就有了這一期的內容！！
我是Mic，一個工作了14年的Java程序員，今天我來分享關於」ConcurrentHashMap 底層實現原理「這個問題，
看看普通人和高手是如何回答的！

普通人：

嗯.. ConcurrentHashMap是用數組和鏈表的方式來實現的，嗯… 在JDK1.8裏面還引入了紅黑樹。然後鏈表和紅黑樹是解決hash衝突的。嗯……

高手：

這個問題我從這三個方面來回答：

ConcurrentHashMap的整體架構
ConcurrentHashMap的基本功能
ConcurrentHashMap在性能方面的優化

ConcurrentHashMap的整體架構

這個是ConcurrentHashMap在JDK1.8中的存儲結構，它是由數組、單向鏈表、紅黑樹組成。

當我們初始化一個ConcurrentHashMap實例時，默認會初始化一個長度為16的數組。由於ConcurrentHashMap它的核心仍然是hash表，所以必然會存在hash衝突問題。

ConcurrentHashMap採用鏈式尋址法來解決hash衝突。

當hash衝突比較多的時候，會造成鏈表長度較長，這種情況會使得ConcurrentHashMap中數據元素的查詢複雜度變成O(_n)。因此在JDK1.8中，引入了紅黑樹的機制。

當數組長度大於64並且鏈表長度大於等於8的時候，單項鏈表就會轉換為紅黑樹。

另外，隨着ConcurrentHashMap的動態擴容，一旦鏈表長度小於8，紅黑樹會退化成單向鏈表。
ConcurrentHashMap的基本功能

ConcurrentHashMap本質上是一個HashMap，因此功能和HashMap一樣，但是ConcurrentHashMap在HashMap的基礎上，提供了並發安全的實現。

並發安全的主要實現是通過對指定的Node節點加鎖，來保證數據更新的安全性。
ConcurrentHashMap在性能方面做的優化

如果在並發性能和數據安全性之間做好平衡，在很多地方都有類似的設計，比如cpu的三級緩存、mysql的buffer_pool、Synchronized的鎖升級等等。

ConcurrentHashMap也做了類似的優化，主要體現在以下幾個方面：
- 在JDK1.8中，ConcurrentHashMap鎖的粒度是數組中的某一個節點，而在JDK1.7，鎖定的是Segment，鎖的範圍要更大，因此性能上會更低。
- 引入紅黑樹，降低了數據查詢的時間複雜度，紅黑樹的時間複雜度是O(_logn)。
- 當數組長度不夠時，ConcurrentHashMap需要對數組進行擴容，在擴容的實現上，ConcurrentHashMap引入了多線程並發擴容的機制，簡單來說就是多個線程對原始數組進行分片後，每個線程負責一個分片的數據遷移，從而提升了擴容過程中數據遷移的效率。
- ConcurrentHashMap中有一個size()方法來獲取總的元素個數，而在多線程並發場景中，在保證原子性的前提下來實現元素個數的累加，性能是非常低的。ConcurrentHashMap在這個方面的優化主要體現在兩個點：
  - 當線程競爭不激烈時，直接採用CAS來實現元素個數的原子遞增。
  - 如果線程競爭激烈，使用一個數組來維護元素個數，如果要增加總的元素個數，則直接從數組中隨機選擇一個，再通過CAS實現原子遞增。它的核心思想是引入了數組來實現對並發更新的負載。