一、ConcurrentLinkedQueue/Deque

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

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

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

但在ConcurrentLinkedQueue中，head/tail的更新可能落后于節(jié)點的入隊和出隊，因為它不是直 接對 head/tail指針進行 CAS操作的，而是對 Node中的 item進行操作。

二、ConcurrentHashMap

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

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

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

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

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

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

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

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

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

三、ConcurrentSkipListMap/Set

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

1、ConcurrentSkipListMap

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

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

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

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

2、ConcurrentSkipListSet

ConcurrentSkipListSet只是對ConcurrentSkipListMap的簡單封裝。