一、ConcurrentLinkedQueue/Deque

AQS內(nèi)部的阻塞隊(duì)列實(shí)現(xiàn)原理：基于雙向鏈表，通過對(duì)head/tail進(jìn)行CAS操作，實(shí)現(xiàn)入隊(duì)和出隊(duì)。

ConcurrentLinkedQueue 的實(shí)現(xiàn)原理和AQS 內(nèi)部的阻塞隊(duì)列類似：同樣是基于 CAS，同樣是通過 head/tail指針記錄隊(duì)列頭部和尾部，但還是有稍許差別。

其次，在AQS的阻塞隊(duì)列中，每次入隊(duì)后，tail一定后移一個(gè)位置；每次出隊(duì)，head一定后移一個(gè) 位置，以保證head指向隊(duì)列頭部，tail指向鏈表尾部。

但在ConcurrentLinkedQueue中，head/tail的更新可能落后于節(jié)點(diǎn)的入隊(duì)和出隊(duì)，因?yàn)樗皇侵?接對(duì) head/tail指針進(jìn)行 CAS操作的，而是對(duì) Node中的 item進(jìn)行操作。

二、ConcurrentHashMap

HashMap通常的實(shí)現(xiàn)方式是“數(shù)組+鏈表”，這種方式被稱為“拉鏈法”。ConcurrentHashMap在這個(gè) 基本原理之上進(jìn)行了各種優(yōu)化。

首先是所有數(shù)據(jù)都放在一個(gè)大的HashMap中；其次是引入了紅黑樹。

如果頭節(jié)點(diǎn)是Node類型，則尾隨它的就是一個(gè)普通的鏈表；如果頭節(jié)點(diǎn)是TreeNode類型，它的后 面就是一棵紅黑樹，TreeNode是Node的子類。

鏈表和紅黑樹之間可以相互轉(zhuǎn)換：初始的時(shí)候是鏈表，當(dāng)鏈表中的元素超過某個(gè)閾值時(shí)，把鏈表轉(zhuǎn) 換成紅黑樹；反之，當(dāng)紅黑樹中的元素個(gè)數(shù)小于某個(gè)閾值時(shí)，再轉(zhuǎn)換為鏈表。

那為什么要做這種設(shè)計(jì)呢？

1. 使用紅黑樹，當(dāng)一個(gè)槽里有很多元素時(shí)，其查詢和更新速度會(huì)比鏈表快很多，Hash沖突的問 題由此得到較好的解決。

2. 加鎖的粒度，并非整個(gè)ConcurrentHashMap，而是對(duì)每個(gè)頭節(jié)點(diǎn)分別加鎖，即并發(fā)度，就是 Node數(shù)組的長(zhǎng)度，初始長(zhǎng)度為16。

3. 并發(fā)擴(kuò)容，這是難度最大的。當(dāng)一個(gè)線程要擴(kuò)容Node數(shù)組的時(shí)候，其他線程還要讀寫，因此 處理過程很復(fù)雜，后面會(huì)詳細(xì)分析。

由上述對(duì)比可以總結(jié)出來：這種設(shè)計(jì)一方面降低了Hash沖突，另一方面也提升了并發(fā)度。

三、ConcurrentSkipListMap/Set

ConcurrentHashMap 是一種 key 無序的 HashMap，ConcurrentSkipListMap則是 key 有序的， 實(shí)現(xiàn)了NavigableMap接口，此接口又繼承了SortedMap接口。

1、ConcurrentSkipListMap

為什么要使用SkipList實(shí)現(xiàn)Map？

在Java的util包中，有一個(gè)非線程安全的HashMap，也就是TreeMap，是key有序的，基于紅黑樹實(shí) 現(xiàn)。 而在Concurrent包中，提供的key有序的HashMap，也就是ConcurrentSkipListMap，是基于 SkipList（跳查表）來實(shí)現(xiàn)的。

這里為什么不用紅黑樹，而用跳查表來實(shí)現(xiàn)呢？

也就是目前計(jì)算機(jī)領(lǐng)域還未找到一種高效的、作用在樹上的、無鎖的、增加和刪除節(jié)點(diǎn)的辦法。

2、ConcurrentSkipListSet

ConcurrentSkipListSet只是對(duì)ConcurrentSkipListMap的簡(jiǎn)單封裝。