CurrentHashMap的整體系統介紹及Java內存模型(JVM)介紹

當我們提到ConurrentHashMap時，先想到的就是HashMap不是線程安全的：

在多個線程共同操作HashMap時，會出現一個數據不一致的問題。

ConcurrentHashMap是HashMap的線程安全版本。

它通過在相應的方法上加鎖，來保證多線程情況下的數據一致性。

hashmap導致數據不一致的原因？

數據不一致問題的表象有兩種情況:

1.寫-讀沖突:一個線程修改后，另一個線程讀到的不是最新的數據。

2.寫-寫沖突:兩個線程同時修改數據，發生數據覆蓋的情況。

原因是Java內存模型（JVM）的一些相關規定。

Java內存模型（JVM）

Java內存模型將內存分為兩種，主內存和工作內存。

并且規定，所有的變量都存儲在主內存中（不包括局部變量與方法參數)。

主內存中的變量是所有線程共享的。

每個線程都有自己的工作內存，存儲的是當前線程所使用到的變量值。即主內存變量中的一個副本數據。

線程對變量的所有操作都必須在工作內存中進行，而不能直接讀寫主內存中的變量。

不同線程間無法直接訪問對方工作內存中的變量。

線程間變量值的傳遞需要通過主內存實現。

這樣規定的原因：

是為了屏蔽各種硬件和操作系統的內存訪問差異，以實現讓Java程序在各種平臺下都能達到一致的內存訪問效果。

關于各種硬件間的內存訪問差異

CPU，內存，IO設備都在不斷迭代，不斷朝著更快的方向努力，但三者的速度是有差異的。

CPU最快，內存其次，IO設備（硬盤）最慢。

為了合理利用CPU的高性能，平衡三者間的速度差異，計算機體系結構，操作系統，編譯系統都做了貢獻，主要體現為:

CPU增加了緩存，以平衡與內存的速度差異，

這樣CPU運算時所需要的變量，優先會從緩存中讀取。

緩存沒有時，會從主內存中加載并緩存。如下圖所示：

事物都是有兩面性的，緩存提高了CPU的運算速度，也帶來了相應的問題：

當多個線程在不同的CPU上運行并訪問同一個變量時，由于緩存的存在，可能讀取不到做最新的值，也就是可見性問題。

可見性指的是一個線程對共享變量的修改，另一個線程能夠立刻看到，被稱為可見性。

操作系統增加了進程，線程，以時分復用CPU，進而均衡CPU與IO設備的速度差異

操作系統通過任務的一個切換來減少CPU的等待時間，從而提高效率。

任務切換的時間，可能是發生在任何一條CPU指令執行完之后。

但是我們平時使用的編程語言，如C，Java，Python等都是高級語言，高級語言轉換成CPU指令時，一條指令可能對應多條CPU指令。相當于1=n，這是違背我們直覺的地方。

所以問題來了，著名的count+=1問題就是這個原因。也就是原子性問題。

我們把一個或多個操作在CPU執行的過程中不被中斷的特性為原子性。（這里的操作是指我們高級語言中相應的一些操作）

編譯程序優化指令執行次序，使得緩存能夠得到更加合理的利用。

指令重排序可以提高了緩存的利用率，同樣也帶來了有序性問題。

也就是單例模式問題。

重排序提高緩存利用率的例子:

在平時寫代碼時，經常會在方法內部的開始位置，把這個方法用到的變量全部聲明了一遍。緩存的容量是有限的，聲明的變量多的時候前面的變量可能就會在緩存中失效。

接下來再寫業務時，用到了最先聲明的變量然后發現在緩存中已經失效了，需要重新的去主內存進行加載。

所以指令重排序可以看成編譯器對我們寫的代碼進行的一個優化。就類似于讓變量都能用上，不至于等到失效在使用。

所以要想實現在各種平臺都能達到一直的內存訪問效果，就需要解決硬件和操作系統之間產生的問題:

1.CPU增加緩存最后導致的可見性問題

2.操作系統增加了線程，進程之后出現的原子性問題

3.指令重排序導致的有序性問題

Java內存模型如何解決三個問題？

原子性問題解決方案

JVM定義了8種操作來完成主內存與工作內存之間的數據交互，虛擬機在實現時需要保證每一種操作都是原子的，不可再分的。

Java中基本數據類型的訪問、讀寫都是具備原子性的（long和Double除外），更大的原子性保證：Java提供了synchronized關鍵字（synchronized的字節碼指令monitorenter和monitorexit來隱式的使用了lock和unlock操作），在synchronized塊之間的操作也具備原子性。

八種操作： lock,unlock,read,load,assign,use,store,write

CAS（樂觀鎖），比較并替換，（Compare And Swap），CAS是一條CPU的原子指令（即cmpxchg指令），Java中的Unsafe類提供了相應的CAS方法，如（compareAndSwapXXX）底層實現即為CPU指令cmpxchg，從而保證操作的原子性。

可見性問題與有序性問題解決方案

JVM定義了Happens-Before原則來解決內存的不可見性與重排序的問題。

Happens-Before規則約束了編譯器的優化行為，雖允許編譯器優化，但是要求編譯器優化后要遵守Happens-Before規則。

Happens-Before規則：

對于兩個操作A和B，這兩個操作可以在不同的線程中執行，如果A Happens-Before B，那么可以保證，當A操作執行完后，A操作的執行結果對B操作時可見的。

8種Happens-Before規則

程序次序規則、鎖定規則、volatile變量規則、線程啟動規則、線程終止規則、線程中斷規則、對象終結原則、傳遞性原則。

volatile變量規則（重點）：對一個volatile變量的寫操作先行發生于后面的這個變量的讀操作。

hashmap導致數據不一致的解決方案

常規思路是加鎖，但是鎖的存在會大大影響性能，所以提升性能的關鍵就是減少鎖的粒度，以及找出哪些操作可以無鎖化。

對于寫操作：涉及到對數據的改動，需要加鎖，這只能盡量減少鎖的粒度。

對于讀操作：確保數據改動不會出錯之后，讀操作就相對好辦；主要考慮的能不能讀到另外一個線程對數據的一個改動（一致性）（等待寫操作的完成）

這時就有三種情況：

強一致性 ：讀寫都加鎖，類似于串行化，這樣可以保證讀到最新的數據，但性能過低
順序一致性 ：變量使用volatile關鍵字修飾
弱一致性 ：讀不加鎖

對應方案：

強一致性 使用synchronized 修飾方法或者代碼塊，來保證代碼塊或方法的一致性，可見性（串行，即有序性），性能較低
順序一致性 ：使用volatile關鍵字修飾變量，volatile 可以保證一個共享變量的可見性以及禁止指令的重排序
弱一致性：使用CAS，CAS操作可以保證一個共享變量的原子操作。

我們可以去讀一下ConcurrentHashMap的源碼，

可以發現代碼中一會使用CAS，一會使用synchronized，讓人摸不清，為什么呢？

這是因為在高級語言中一條語句往往需要多條CPU指令完成。

而Java中基本數據類型的訪問、讀寫都具備原子性（long和Double除外），其他大部分不是原子性操作，

就比如在new一個對象時，就不是一個原子性操作，它需要三步才能完成，分配內存，初始化對象，將對象賦值給變量。

所以在創建數組的時候，除了使用synchronized外，CAS是不能保證原子性的，CAS只是CPU的一條指令，他不能保證多個指令的原子性，但是我們可以參考AQS，使用CAS鎖一個基本類型的變量，其他線程進行自旋。

其次，synchronized鎖需要一個對象，當數組的元素為null時，是無法使用synchronized鎖的，所以此時使用的就是CAS操作來保證賦值的原子性。

以及底層的數組table已經被volatile修飾，但是數組元素的修改卻不能保證可見性。

明明volatile保證共享變量的可見性，為什么數組元素的修改卻不能保證可見性呢？

原因：

volatile保證共享變量的可見性，但是如果該變量是一個對象的引用，那么volatile此時指的就是對象引用的可見性。

而在Java中，數組也是一個對象，當使用volatile來修飾數組arr時，代表的是arr的引用具有可見性，即arr的引用地址修改了之后，其他線程是可見的，但是無法保證數組內的元素具有可見性。

HashTable與ConcurrentHashMap

Hashtable

前置知識：在JDK1.0時，加鎖只有synchronized一種方法，synchronized是重量級鎖（需要去CPU申請鎖）

底層結構：數組+鏈表鏈表使用頭插法定位數組下標使用取余操作

線程安全：使用synchronized來保證線程安全，在所有的方法上都加了synchronized關鍵字，即使用一把全局鎖來同步不同線程間的并發訪問（鎖住整個table結構），性能較低。

相關操作： put,get,remove,size方法體上都添加synchronized關鍵字，擴容邏輯在put方法內發生，也是線程安全的

優點：實現簡單

缺點：一個線程在插入數據時，其他線程不能讀寫，并發效率低下

ConcurrentHashMap（JDK1.5）

在JDK1.5時引入，此時Java內存模型已經成熟完善，在此基礎上開發了java.util.concurrent包，ConcurrentHashMap隨著JUC包一起引入JDK，同時引入了AQS，實現了ReentrantLock

底層結構：數組+鏈表鏈表使用頭插法定位下標使用&運算

線程安全：使用分段鎖的思想，其內部是一個Segment數組，Segment繼承了ReentrantLock（可重復鎖），即Segment自身就是一個鎖。

Segment內部有一個HashEntry數組（Segment有點類似HashTable），每個HashEntry是一個鏈表結構的元素，一把鎖只鎖住容器中的一部分數據，多線程訪問容器中里不同數據段的數據，就不會存在鎖競爭，提高并發訪問率

相關操作：調用put方法時，當前的segment會將自己鎖住，此時其他線程無法操作這個segment，但不會影響到其他segment的操作。

調用get方法時，使用unsafe.getObjectVolatile方法獲取節點；底層使用C++的volatile來實現Java中的volatile效果（保證共享變量的可見性（一個線程對共享變量的修改，另一個線程能夠立刻看到））

調用remove方法時，當前的segment會將自己鎖住。

put，get，remove操作都是在單個Segment上進行的，size操作是在多個segment進行的

size方法采用了一種比較巧妙的方式，來盡量避免對所有的Segment都加鎖。

每個Segment都有一個modCount 變量，代表的是對Segment中元素的數量造成影響的操作次數。這個值只增不減。

size 操作就是遍歷了兩次Segment，每次記錄Segment 的modCount值，然后將兩次的modCount進行比較，如果相同，則表示期間沒有發生過寫入操作，就將原先遍歷的結果返回。如果不相同，則把這個過程再重復做一次，如果再不同，則就需要將所有的Segment都鎖住，然后一個一個遍歷。

擴容操作，發生在put方法內部，跟put方法使用的是同一個鎖.

擴容不會增加Segment的數量，只會增加Segment中鏈表數組的容量大小。

這樣的好處是擴容過程不需要對整個ConcurrentHashMap做 rehash，只需要對Segment里面的元素做一個rehash即可。這樣就不會去影響其他的segment里面的元素。

優點：每次只鎖住一部分數據，訪問不同數據段的數據，不會存在鎖競爭。提高了并發訪問率；

擴容只針segment內部的HashEntry數組進行擴容，不影響其他segment內部的HashEntry數組。

缺點：定位一個元素，需要經過兩次hash操作。當某個segment很大時，類似Hashtable，性能會下降。

比較浪費內存空間（因為每個segment內部的HashEntry數組是不連續的）

拓展：

在JDK6中，針對synchronized做了大量的優化，引入了輕量級鎖和偏向鎖。性能與ReentrantLock已相差無幾，甚至synchronized的自動釋放鎖會更好用。

Java官方表示，在多線程環境下不建議使用HashMap。

隨著互聯網的快速發展，業務場景隨之更加復雜，很多人在使用多線程的情況下使用HashMap的時候，結果導致cpu100%的情況。

主要原因：HashMap的鏈表使用的是頭插法，在多線程的情況下觸發擴容，鏈表可能會形成一個死循環。

在JDK8中也做了相應的優化，將頭插法改為尾插法，引入了紅黑樹，來優化鏈表過長導致的查詢速度變慢。

連帶著ConcurrentHashMap也做了相應的修復，使得ConcurrentHashMap與HashMap的結構更加統一。

ConcurrentHashMap(JDK8之后)

由類圖可知，ConcurrentHashMap中有四種類型的節點，四種類型的節點的用途不同。

Node節點是ConcurrentHashMap中存儲數據的最基本結構，也是其他類型節點的父類，他可以用來構建鏈表。hash值>=0
TreeNode節點主要用來構造紅黑樹以及存儲數據。hash值>=0
TreeBin節點是紅黑樹的代理節點，不存儲數據，他的Hash值是一個固定值-2
ForWardingNode節點，表示的是底層數組table正在擴容，當前節點的數據已經遷移完畢，不存儲數據，hash值也是固定值-1

注意事項：TreeBin為什么是紅黑樹的代理節點？

因為在向紅黑樹添加數據或刪除數據時可能會觸發紅黑樹的自平衡，根節點可能會被子節點替代，如果此時有線程來紅黑樹讀取數據，可能會出現讀取不到數據的情況。

而紅黑樹的查找是從根節點開始遍歷的，當根節點變成子節點時，作為根節點的左子樹或者右子樹可能是不被遍歷的。

ConcurrentHashMap的get方法是沒有使用鎖的，不可能通過加鎖來保證強一致性，而紅黑樹的并發操作需要加上一層鎖來保證在紅黑樹自平衡時的讀操作沒有問題。這就是TreeBin的工作。

TreeBin重要屬性：

root：指向的是紅黑樹的根節點
first：指向的是雙向鏈表，也就是所有的TreeNode節點構成的一個雙向鏈表
lockState：用于實現基于CAS的讀寫鎖。

總結：對紅黑樹添加或刪除數據的整體操作：

首先在最外層加上synchronized同步鎖，然后再紅黑樹自平衡時加上lockState的寫鎖。

當由線程來讀紅黑樹的時候，會先判斷此時是否有線程持有寫鎖或者是否有線程在等待獲取寫鎖，如果有的話，讀線程直接讀取雙向鏈表，否則會加上lockState的讀鎖。然后讀取紅黑樹的數據，從而來保證讀操作不被阻塞以及它的正確性。

雙向鏈表的作用：

讀操作會來讀取鏈表上的數據。
在擴容時，會遍歷雙向鏈表，根據hash值判斷是放在新數組的高位還是低位。

底層結構：數組+鏈表+紅黑樹鏈表使用尾插法定位下標使用 & 運算

線程安全：消了分段鎖的設計，1取而代之的是通過 cas 操作和 synchronized 關鍵字來保證并發更新的安全。

Synchronized只是用于鎖住鏈表或者紅黑樹的第一個節點，只要沒有Hash沖突，就不存在并發問題，效率也就大大的提升。

相關操作：

put方法，使用cas + synchronized 來保證線程安全.

get方法，沒有使用加鎖，使用的是Unsafe.getObjectVolatile方法獲取數據。保證數據的可見性。

remove方法、使用synchronized 來保證線程安全。

size方法(難點)：主要是LongAdder的思想進行的累加計算。

擴容操作（難點）：擴容操作發生在數據添加成功之后，并且支持多個線程。

優點：鎖粒度更精細，性能更強

缺點:實現更加復雜。

希望對大家有所幫助！