JDK1.8 ConcurrentHashMap源碼閱讀

1.  帶著問題去閱讀

為什麼說ConcurrentHashMap是線程安全的？或者說 ConcurrentHashMap是如何防止併發的？

2.  欄位和常量

首先，來看一下ConcurrentHashMap中的一些欄位和常量，這些在接下來的操作中會用得到

2.1.  常量

從中，我們可以獲得以下信息：

1. 數組的預設容量是16，最大容量是1<<30
2. 當添加元素的時候，將列表轉成樹的閾值是8。也就是說，相同位置上多個元素是以鏈表的形式存儲的，而當鏈表的長度（元素的個數）超過8時，將其轉為樹
3. 在對數組擴容的時候，當樹中元素個數小於或等於6時，將樹轉成鏈表

2.2.  欄位

從這些欄位中，我們可以獲得以下信息：

1. 底層是一個數組，且數組的類型是Node，延遲初始化，更重要的是它被 volatile 修飾
2. sizeCtl是用於數組初始化和擴容的，當它是負數的時候，表示數組正在進行初始化或擴容，-1表示正在初始化，同時應該註意到它也被 volatile 修飾

2.3.  內部類

對比1.7裡面的HashMap不難發現：

1. Node繼承自Map.Entry
2. 其 value 和 next 都用 volatile 修飾

可以看到，TreeNode繼承自Node，主要用於樹形結構中。也就是說，TreeNode表示樹中的結點。

還有一個TreeBin也是繼承自Node

TreeBin表示整個樹，TreeNode表示樹中的結點

正常情況下，數組中某個位置的元素應該是Node，而Node是一個鏈表，它後面可能跟了多個Node。

但是，某個位置的節點個數超過閾值（預設8）時，將這個鏈表轉成紅黑樹，那麼此後數組中這個位置的元素就是TreeBin

也就是說，Node表示鏈表中的節點，TreeNode表示樹中的節點，TreeBin表示樹

3.  操作

3.1.  put

這裡，再多看一眼，剛纔的putTreeVal()方法

總的來說，是先插入，後調整

大致流程是這樣的：

1. 如果數組為空，則先初始化數組
2. 根據key計算哈希值，進而計算應該在數組的什麼位置
3. 取出該位置上的元素，如果為空，則直接構造一個Node，並將元素放置於此
4. 如果該位置上的元素不為空，則進一步判斷是鏈表還是樹（PS：Node還是TreeBin）
5. 如果是Node，則遍歷鏈表，如果發現有key相同的元素，則用新值替換舊值，否則構造Node，並將其插入到鏈表尾部
6. 如果是TreeBin，則遍歷樹，若發現相同key的節點，則用新值替換舊值，否則構造TreeNode，並將其插入到樹中
7. 插入完成以後，最後再看一下要不要轉成樹型結構
8. 如果舊值不為空，則返回舊值

3.2.  resize

在上一步的put操作中，如果數組正在擴容，則幫助擴容

下麵看一下擴容

我以前在理解上一直有一個誤區，以前我一直以為在數組相同位置上的元素的哈希值都相同，今天我恍然大悟，原來不是這樣的，這些元素之所以會在同一個位置是因為通過key的哈希值再結合數組長度計算得出該元素應該在這個位置上，而不同的哈希值可能經過計算也在同一個位置，所以，相同位置的元素的hash值不一定相同，或者說，鏈表上的元素的hash並不一定都相同，只是恰巧它們在數組的位置相同而已。

擴容是這樣的：

1. 新數組的長度是原來的2倍
2. 根據不同位置的元素的結構有不同的方式
3. 不管原來是鏈表結構還是樹型結構，擴容以後都變成兩部分，一部分是hash&n為0的，另一部分是hash&n不為0的，其中n為原數組的長度
4. 對於那些hash&n==0的結點，它們在新數組中的位置保持不變，也就是說它們原先在舊數組中是什麼位置，現在在新數組中還是什麼位置
5. 對於那些hash&n != 0的節點，它們在新數組中的位置相比於之前在舊數組中的位置是向後移動了n
6. 每個位置在遷移的時候都加鎖了
7. 擴容後，原來在舊數組中在相同位置的結點在新數組中未必還在相同的位置
8. 擴容後，鏈表沒有倒置
9. 由於遷移到新數組中時，會將原先一棵樹分成兩部分（跟鏈表一樣），所以分出來的樹中如果結點數小於或等於6，則轉成鏈表

下麵是一個示意圖，不必拘泥細節，重在意思

3.3.  get和remove

刪除和獲取相對比較簡單，不再贅述

至此，可以回答開頭我們提出的問題了

sychronized + volatile + CAS

插入、刪除、擴容的時候都對數組中相應位置的元素加鎖了，加鎖用的是synchronized

table數組、Node中的val和next、以及一些控制欄位都加了volatile

在更新一些關鍵變數的時候用到了sun.misc.Unsafe中的一些方法