作者：紅橙Darren
來源：https://www.jianshu.com/p/0b452a6e4f4e
- 五個線程同時往 HashMap 中 put 數據會發生什麼？
- ConcurrentHashMap 是怎麼保證線程安全的？
在分析 HashMap 源碼時還遺留這兩個問題，這次我們站在 Java 多線程內存模型和 synchronized 的實現原理，這兩個角度來徹底分析一下。至於 JDK 1.8 的紅黑樹不是本文探討的內容。
1. Java 多線程內存模型
五個線程同時往 HashMap 中 put 數據會出現兩種現象，大概率會出現數據丟失，小概率會出現死循環，我們不妨寫個測試代碼自己驗證一下。那為什麼會出現這兩種現象，我們先來回顧一下之前的Java 多線程內存模型。請看圖：
Java內存模型中規定了所有的變量都存儲在主內存中，每條線程還有自己的工作內存，線程的工作內存中保存了該線程使用到的變量到主內存副本拷貝，線程對變量的所有操作（讀取、賦值）都必須在工作內存中進行，而不能直接讀寫主內存中的變量。不同線程之間無法直接訪問對方工作內存中的變量，線程間變量值的傳遞均需要在主內存來完成，線程、主內存和工作內存的交互關係如上圖所示。
現在我們來想象一下，假設線程 1 把數據讀到了自己的工作內存中，在 tab 角標為 1 的鏈表頭插入了一條新的數據，倘若這時還沒來得及將新增的數據刷新到主內中。接著線程 2 就把數據讀到了自己的工作內存中，在 tab 角標為 1 的鏈表頭插入了一條新的數據。接著線程 1 把新增數據刷新到主內存中，線程 2 也把數據新增數據刷新到主內存中，那麼線程 2 就會覆蓋線程 1 的新增數據，從而導致數據丟失的情況。這裡需要注意的是，只有兩個線程都是操作 tab 的同一個 index 鏈表才會導致數據丟失的情況，如果不是同一個 index 鏈表就不會有覆蓋和丟失這一說。
2. synchronized 的底層實現原理
關於 HashMap 的線程不安全問題，Java 給我們提供了三種方案，第一種是 HashTable ，第二種是 Collections.synchronizedMap() ，第三種是 ConcurrentHashMap 。而第一種和第二種都是通過用 synchronized 同步方法來保證線程安全，性能上有所欠缺不推薦大家使用。ConcurrentHashMap 在 JDK 1.8 之前採用的是 Segment 分段鎖來實現的，而 JDK 1.8 之後則採用 synchronized 和 CAS 來實現。
HashTable 通過鎖住整個 put 和 get 方法來實現線程安全並不是很合理，因為一個線程在 put 的時候，另外一個線程不能再 put 和 get 必須進入等待狀態。同理一個線程在 get 的時候，另外一個線程也不能再 get 和 put 。上面通過分析只有兩個線程都是操作 tab 的同一個 index 鏈表才會導致數據丟失的情況，如果不是同一個 index 鏈表就不會有覆蓋和丟失這一說。因此也沒必要鎖住整個方法，只需要鎖住每個 tab 的 index 鏈即可。
ConcurrentHashMap 在 JDK 1.8 之前採用的是 Segment 繼承自 ReentrantLock 來鎖住 tab 的 index 鏈，而 JDK 1.8 之後則採用 synchronized 來實現，這兩者又有什麼區別？我們首先看下 synchronized 的底層是怎麼實現線程安全的。Java中的每一個對象都可以作為鎖。具體表現有以下3種形式。
我們可能會想鎖到底存在哪裡呢？鎖裡面會存儲什麼信息呢？其實 synchronized 同步的代碼塊，虛擬機在同步代碼塊開始前會插入一條 monitorenter 指令，在代碼塊的末尾會插入一條 monitorexit 指令。而每個對象的 Mark Word 頭信息裡都會存儲 Monitor 信息，也就是當前對象的鎖信息，當然 Mark Word 頭信息還包含對象的 hashCode 和 GC 的分代年齡，具體請看下錶：
Lock 的實現原理和 synchronized 有些類似，都是通過線程的原子性來保證線程同步，具體的實現的方式大家可以去看下 ReentrantLock 的源碼實現。那為什麼在 JDK 1.8 之後要採用 synchronized 和 CAS 來實現？在 JDK 1.6 為了減少獲得鎖和釋放鎖帶來的性能消耗，引入了“偏向鎖”和“輕量級鎖”，級別從低到高依次是：無鎖狀態、偏向鎖狀態、輕量級鎖狀態和重量級鎖狀態，這幾個狀態會隨著競爭情況逐漸升級。鎖可以升級但不能降級，意味著偏向鎖升級成輕量級鎖後不能降級成偏向鎖。這種鎖升級卻不能降級的策略，目的是為了提高獲得鎖和釋放鎖的效率。當線程 1 進入同步代碼塊遇到 monitorenter 指令，首先判斷鎖的狀態發現是 0 ，採用 CAS 將鎖的狀態設置為 1，偏向鎖設置為 1，鎖的標緻位設置為 1 ，繼續執行同步代碼塊裡面的指令。這是若線程 2 也來到了同步代碼塊，也會遇到 monitorenter 指令，首先判斷鎖的狀態發現是 1 進入等待中，等線程 1 執行完同步代碼塊遇到 monitorenter 指令，首先會清空鎖的狀態然後喚醒線程 2 。如此反覆即可保證線程安全。
偏向鎖
大多數情況下，鎖不僅不存在多線程競爭，而且總是由同一線程多次獲得，為了讓線程獲得鎖的代價更低而引入了偏向鎖。當一個線程訪問同步塊並獲取鎖時，會在對象頭和棧幀中的鎖記錄裡存儲鎖偏向的線程 ID，以後該線程在進入和退出同步塊時不需要進行 CAS 操作來加鎖和解鎖，只需簡單地測試一下對象頭的 Mark Word 裡是否存儲著指向當前線程的偏向鎖。如果測試成功，表示線程已經獲得了鎖。如果測試失敗，則需要再測試一下 Mark Word 中偏向鎖的標識是否設置成1（表示當前是偏向鎖）：如果沒有設置，則使用 CAS 競爭鎖；如果設置了，則嘗試使用CAS將對象頭的偏向鎖指向當前線程。
輕量級鎖
線程在執行同步塊之前，JVM 會先在當前線程的棧楨中創建用於存儲鎖記錄的空間，並將對象頭中的 Mark Word 複製到鎖記錄中。然後線程嘗試使用 CAS 將對象頭中的 Mark Word 替換為指向鎖記錄的針。如果成功，當前線程獲得鎖，如果失敗，表示其他線程競爭鎖，當前線程便嘗試使用自旋來獲取鎖。
重量級鎖
輕量級鎖採用自旋的方式不斷的嘗試獲取鎖，如果長時間獲取不到鎖勢必會不斷消耗 CPU 的資源。所以當線程競爭比較激烈或者線程遲遲獲取不到鎖，就會升級為重量級的鎖狀態，此時線程是阻塞的，且響應時間緩慢。
3. ConcurrentHashMap 源碼分析
最後值得一提的是 table 和 Node 對象中的 next 和 val 都是採用 volatile 來修飾的。
閱讀更多 Java面經 的文章
