Java

集合

Collection

List

ArrayList

實(shí)現(xiàn)原理：基于可變數(shù)組實(shí)現(xiàn)，默認(rèn)容量10，最大為Integer.MAX_VALUE

適用場景：非線程安全，支持隨機(jī)訪問，插入和刪除涉及到數(shù)組的拷貝，性能較低，適用于讀多寫少的場合。

LinkedList

實(shí)現(xiàn)原理：基于雙向鏈表實(shí)現(xiàn)，所占空間相比ArrayList要少，因?yàn)锳rrayList擴(kuò)容1.5倍，存在空間浪費(fèi)。

適用場景：非線程安全，不支持隨機(jī)訪問，實(shí)現(xiàn)了Queue接口，對頭部或尾部做插入或刪除操作效率很高，最多只影響一個(gè)節(jié)點(diǎn)。遍歷用迭代器效率最高。

Vector

ArrayList的線程安全版本，通過synchronized關(guān)鍵字實(shí)現(xiàn)。性能較低，不常用。

CopyOnWriteArrayList

實(shí)現(xiàn)原理：寫操作加鎖，讀操作不加鎖。不直接對當(dāng)前容器進(jìn)行寫操作，而是copy一個(gè)新容器，然后在新容器里寫。寫完后，將原容器的引用指向新容器。

適用場景：ArrayList線程安全版本，內(nèi)存占用較大，只能保證數(shù)據(jù)的最終一致性。適用于讀多寫少的場合。

Set

HashSet：基于HashhMap，HashSet里存儲(chǔ)的元素就是內(nèi)部HashMap的key。

TreeSet：基于TreeMap，TreeSet里存儲(chǔ)的元素就是內(nèi)部TreeMap的key。

CopyOnWriteArraySet：基于CopyOnWriteArrayList，只不過不能添加重復(fù)元素。

ConcurrentSkipListSet：基于ConcurrentSkipListMap。

Queue

ArrayBlockingQueue：數(shù)組實(shí)現(xiàn)的有界阻塞隊(duì)列，當(dāng)隊(duì)列滿時(shí)，生產(chǎn)的線程會(huì)被阻塞。當(dāng)隊(duì)列為空時(shí)消費(fèi)的線程被阻塞。基于ReentrantLock和Condition實(shí)現(xiàn)。

LinkedBlockingQueue：鏈表實(shí)現(xiàn)的有界阻塞隊(duì)列。

ConcurrentLinkedQueue：鏈表實(shí)現(xiàn)的無阻塞隊(duì)列，CAS+volatile保證線程安全。

PriorityQueue：基于堆實(shí)現(xiàn)。

DelayQueue:基于PriorityQueue實(shí)現(xiàn)的延遲隊(duì)列。

Map

HashMap

實(shí)現(xiàn)原理

1.7 基于數(shù)組和鏈表實(shí)現(xiàn)。put時(shí)，通過k的hashcode算出索引，然后將Entry放到該位置。如果該位置已存在元素，則比較hashcode和equals方法，判斷是否是同一個(gè)key，若相同則替換為新值并返回舊值。添加Entry節(jié)點(diǎn)前會(huì)判斷是否要做resize操作，resize在多線程下可能會(huì)導(dǎo)致鏈表成環(huán)，造成cpu100%。

1.8 相比于1.7，多了紅黑樹。當(dāng)鏈表長度超過8的時(shí)候，會(huì)變成紅黑樹。

LinkedHashMap

特點(diǎn)：繼承自HashMap，可以按插入順序或訪問順序(accessOrder為true時(shí))遍歷。

TreeMap

特點(diǎn)：紅黑樹實(shí)現(xiàn)，可按元素的順序或特定比較器進(jìn)行遍歷。

ConcurrentHashMap

實(shí)現(xiàn)原理

1.7 基于分段鎖，get不加鎖，put先計(jì)算要put到哪個(gè)segment，再通過segment加鎖put。

1.8 基于Node+CAS+synchronized

ConcurrentSkipListMap

特點(diǎn)：線程安全，基于跳躍表實(shí)現(xiàn)。

實(shí)現(xiàn)原理：插入和刪除操作只需要改變影響到的節(jié)點(diǎn)的右引用，而右引用是用volatile修飾的。

并發(fā)

synchronized

實(shí)現(xiàn)：基于編譯器時(shí)插入moniterenter和moniterexit指令，由JVM內(nèi)部實(shí)現(xiàn)。

優(yōu)點(diǎn)：不需要顯式釋放鎖

缺點(diǎn)：效率低，線程上下文切換較多。但jdk1.6做了優(yōu)化。偏向鎖，輕量級(jí)鎖，重量級(jí)鎖。

java.util.concurrent

實(shí)現(xiàn)：基于Java語言實(shí)現(xiàn)。

優(yōu)點(diǎn)：性能相對高，線程上下文切換較少。對鎖的可控性更強(qiáng)，共享獲取及超時(shí)獲取。

缺點(diǎn)：需要顯式釋放鎖。

AbstractQueuedSynchronizer

特點(diǎn)：其它并發(fā)工具的基礎(chǔ)，內(nèi)部封裝了同步狀態(tài)管理，線程的排隊(duì)、等待與喚醒等等底層操作。

ReentrantLock

特點(diǎn)：分為公平鎖和非公平鎖，非公平鎖是默認(rèn)實(shí)現(xiàn)。公平鎖對獲取鎖的條件更為苛刻，當(dāng)鎖沒有被線程持有，還要保證等待隊(duì)列為空，或者等待隊(duì)列中沒有其它線程在等待。（鎖的釋放到喚醒等待隊(duì)列的線程有一個(gè)延遲過程）

獲取鎖：都是先嘗試獲取鎖，沒有獲取到，則以當(dāng)前線程構(gòu)造一個(gè)節(jié)點(diǎn)加入到等待隊(duì)列尾。加入到等待隊(duì)列后，線程使用自旋的方式獲取鎖。如果前驅(qū)節(jié)點(diǎn)為頭節(jié)點(diǎn)則嘗試獲取鎖，否則進(jìn)入等待狀態(tài)。

釋放鎖：鎖的釋放就是將state-1直到為0。釋放完還要喚醒等待隊(duì)列的線程爭奪鎖。

ReentrantReadWriteLock

特點(diǎn)：讀寫鎖在同一時(shí)刻可以允許多個(gè)讀線程訪問，但是在寫線程訪問時(shí)，所有的讀線程和其它的寫線程均被阻塞。讀寫鎖比排它鎖有更好的并發(fā)性和吞吐量。

讀鎖

獲?。喝绻呀?jīng)有讀鎖或者當(dāng)前線程不是已經(jīng)獲取寫鎖的線程，則等待。如果獲取了寫鎖，則增加寫狀態(tài)。寫鎖被獲取，則其它讀寫線程被阻塞。

釋放：基本和ReentrantLock相同

寫鎖

獲?。喝绻呀?jīng)有其它線程獲取了寫鎖，則當(dāng)前獲取的線程被阻塞。

釋放：基本和ReentrantLock相同

CountDownLatch

特點(diǎn)：一個(gè)或多個(gè)線程等待其它線程完成某操作后，再繼續(xù)執(zhí)行。

實(shí)現(xiàn)：構(gòu)造方法初始化state變量的值。線程調(diào)用await方法，實(shí)際上是獲取鎖狀態(tài)等不等于0，等于0則繼續(xù)執(zhí)行，否則循環(huán)cas并判斷是否要進(jìn)入阻塞狀態(tài)。其它線程調(diào)用countDown方法，實(shí)際上就是釋放鎖的過程。當(dāng)釋放到0時(shí)，被阻塞線程則可以繼續(xù)執(zhí)行。

CyclicBarrier

特點(diǎn)：一組線程到達(dá)一個(gè)同步點(diǎn)后再一起往下執(zhí)行，任意一個(gè)線程沒到，則其它線程被阻塞。

實(shí)現(xiàn)：基于ReentrantLock和Condition。構(gòu)造方法初始化需要被等待的線程數(shù)。調(diào)用await方法將值減1，當(dāng)減到0時(shí)，喚醒被阻塞線程繼續(xù)執(zhí)行。否則該線程被阻塞。

Semaphore

特點(diǎn)：控制同時(shí)訪問某資源的最大線程數(shù)量。

實(shí)現(xiàn)：基于AQS。線程調(diào)用acquire獲取許可，release釋放許可。若許可數(shù)量小于1，則等待其它線程釋放許可。

StampedLock

特點(diǎn)：為控制讀寫訪問采用了三種模式。StampedLock鎖狀態(tài)包含一個(gè)版本號(hào)和模式。

寫：

讀：

樂觀讀：

LockSupport：阻塞或喚醒一個(gè)線程?；赨nsafe的native實(shí)現(xiàn)。