多線程（十四、ConcurrentHashMap原理（1）節點）

ConcurrentHashMap介紹

針對JDK1.8看ConcurrentHashMap是如何實現的

結構圖：

1、ConcurrentHashMap內部是一個Node節點的數組table，數組的每一個位置table[i]代表一個桶。根據鍵的hash值映射到不同的桶內。

transient volatile Node<K,V>[] table;

2、Node節點一共有5種類型

1、Node節點，是所有節點的父類，可以單獨放入桶內，也可以作為鏈表的頭放入桶內。
2、TreeNode節點，繼承自Node，是紅黑樹的節點，此節點不能直接放入桶內，只能是作為紅黑樹的節點。
3、TreeBin節點，TreeNode的代理節點，可以放入桶內，這個節點下面可以連接紅黑樹的根節點，所以叫做TreeNode的代理節點。
4、ForwardingNode節點，擴容節點，只是在擴容階段使用的節點，當前桶擴容完畢后，桶內會放入這個節點，此時查詢會跳轉到查詢擴容后的table，不存儲實際數據
5、ReservationNode節點，內部方法使用，暫時可以忽略。

2.1 Node節點

默認桶上的結點就是Node結點。
當出現hash沖突時，Node結點會首先以鏈表的形式鏈接到table上，當結點數量超過一定數目時，鏈表會轉化為紅黑樹。因為鏈表查找的平均時間復雜度為O(n)，而紅黑樹是一種平衡二叉樹，其平均時間復雜度為O(logn)。

Node只有一個next指針，是一個單鏈表，提供find方法實現鏈表查詢

2.2 TreeNode節點

TreeNode就是紅黑樹的結點，TreeNode不會直接鏈接到table[i]——桶上面，而是由TreeBin鏈接，TreeBin會指向紅黑樹的根結點。

提供了基于樹查找的findTreeNode方法。

2.3 TreeBin節點

TreeBin會直接鏈接到table[i]——桶上面，該結點提供了一系列紅黑樹相關的操作，以及加鎖、解鎖操作。

另外TreeBin提供了一系列的操作
1、TreeBin(TreeNode<K,V> b)，將以b為頭結點的鏈表轉換為紅黑樹.
2、lockRoot()，對紅黑樹的根結點加寫鎖
3、unlockRoot()，釋放寫鎖
4、find(int h, Object k)，從根結點開始遍歷查找，找到“相等”的結點就返回它，沒找到就返回null，當存在寫鎖時，以鏈表方式進行查找，不阻塞讀鎖。

5、removeTreeNode(TreeNode<K, V> p)，刪除紅黑樹的結點

a、紅黑樹規模太小時，返回true，然后進行 樹 -> 鏈表 的轉化
b、紅黑樹規模足夠時，不用變換成鏈表，但刪除結點時需要加寫鎖

6、紅黑樹的左旋，右旋等一系列算法。

2.4 ForwardingNode節點

1、ForwardingNode是一種臨時結點，在擴容進行中才會出現，hash值固定為-1，且不存儲實際數據。
2、如果舊table數組的一個hash桶中全部的結點都遷移到了新table中，則在這個桶中放置一個ForwardingNode。
3、讀操作碰到ForwardingNode時，將操作轉發到擴容后的新table數組上去執行；寫操作碰見它時，則嘗試幫助擴容，擴容是支持多線程一起擴容的。
4、提供了在新的數組nextTable上進行查找的方法find

2.5 ReservationNode節點

1、保留結點.
2、hash值固定為-3， 不保存實際數據
3、只在computeIfAbsent和compute這兩個函數式API中充當占位符加鎖使用