數據結構

jdk1．7

jdk1．8

如果頭節點是Node類型，其后就是一個普通的鏈表；如果頭節點是TreeNode類型，它的后面就是一顆紅黑樹，TreeNode是Node的子類。鏈表和紅黑樹之間可以相互轉換：初始的時候是鏈表，當鏈表中的元素超過某個閾值時，把鏈表轉換成紅黑樹；反之，當紅黑樹中的元素個數小于某個閾值時，再轉換為鏈表。

歷史版本對比

從JDK1．7版本的ReentrantLock＋Segment＋HashEntry，到JDK1．8版本中synchronized＋CAS＋HashEntry＋紅黑樹。代碼量從原來的1000多行變成了 6000多 行，實現上也和原來的分段式存儲有很大的區別。

1．數據結構

取消了Segment分段鎖的數據結構，取而代之的是數組＋鏈表＋紅黑樹的結構。使用紅黑樹，當一個槽里有很多元素時，查詢時間復雜度從原來的遍歷鏈表O（n），變成遍歷紅黑樹O（logN），Hash沖突的問題也會得到較好的解決

2．鎖的粒度：

JDK1．7采用segment的分段鎖機制實現線程安全，其中segment繼承自ReentrantLock。JDK1．8采用CAS＋Synchronized保證線程安全。原來是對需要進行數據操作的Segment加鎖，現調整為對每個頭節點分別加鎖，其并發度，就是Node數組的長度，初始長度為16，這降低了鎖的粒度。

3．并發的擴容：

在JDK 7中，一旦Segment的個數在初始化的時候確立，不能再更改，并發度被固定。之后只是在每個Segment內部擴容，這意味著每個Segment獨立擴容，互不影響，不存在并發擴容的問題。但在JDK 8中，相當于只有1個Segment，當一個線程要擴容Node數組的時候，其他線程還要讀寫，因此處理過會更復雜。

4．代碼實現上的區別：

sizeCtl：

多個線程的共享變量，是操作的控制標識符，它的作用不僅包括threshold的作用，在不同的地方有不同的值也有不同的用途。

－1代表正在初始化

－N 表示正在進行擴容操作。此時sizeCtl的高16位代表的是當前的容量（并不是數值等于容量大?。?低16位代表線程數 容量16的話計算rs ＝ 32795 也就是 1000 0000 0001 1011 可以看出不同的容量對應不同rs值， rs ＜＜ 16 的值為 11111111111111111111111111111111 10000000000110110000000000000000， 0－15位用于統計參與擴容的線程數， 16－31位用于代表擴容時容器的大小。

正數或0代表hash表還沒有被初始化，這個數值表示初始化或下一次進行擴容的大小，這一點類似于擴容閾值的概念。后面可以看到，它的值始終是當前ConcurrentHashMap容量的0．75倍，這與loadfactor是對應的。

MOVED，TREEBIN，RESERVED ：

MOVED，TREEBIN，RESERVED是用來表示特殊節點的哈希值。該類特殊節點均不含實際元素，且其哈希值被設置為負數和普通節點區分。

／／ ForwardingNode標記節點的hash值（表示正在擴容）

static final int MOVED ＝ －1； ／／ hash for forwarding nodes

／／ TreeBin節點的hash值，它是對應桶的根節點

static final int TREEBIN ＝ －2； ／／ hash for roots of trees

static final int RESERVED ＝ －3； ／／ hash for transient reservations