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

jdk1．7

jdk1．8

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

歷史版本對(duì)比

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

1．?dāng)?shù)據(jù)結(jié)構(gòu)

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

2．鎖的粒度：

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

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

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

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

sizeCtl：

多個(gè)線程的共享變量，是操作的控制標(biāo)識(shí)符，它的作用不僅包括threshold的作用，在不同的地方有不同的值也有不同的用途。

－1代表正在初始化

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

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

MOVED，TREEBIN，RESERVED ：

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

／／ ForwardingNode標(biāo)記節(jié)點(diǎn)的hash值（表示正在擴(kuò)容）

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

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

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

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