數(shù)據(jù)結(jié)構(gòu)

jdk1．7

jdk1．8

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

歷史版本對比

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

1．數(shù)據(jù)結(jié)構(gòu)

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

2．鎖的粒度：

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

3．并發(fā)的擴容：

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

4．代碼實現(xiàn)上的區(qū)別：

sizeCtl：

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

－1代表正在初始化

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

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

MOVED，TREEBIN，RESERVED ：

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

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

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

／／ TreeBin節(jié)點的hash值，它是對應(yīng)桶的根節(jié)點

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

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