一汹碱、CopyOnWriteArrayList

1. 類(lèi)型

Collection - List

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

動(dòng)態(tài)數(shù)組

3. 重要實(shí)現(xiàn)

a. 讀寫(xiě)分離

內(nèi)部使用“volatile數(shù)組”來(lái)存儲(chǔ)數(shù)據(jù)裁替。在“添加/修改/刪除”數(shù)據(jù)時(shí)，都會(huì)新建一個(gè)數(shù)組貌笨，并將更新后的數(shù)據(jù)拷貝到新建的數(shù)組中弱判，最后再將該數(shù)組賦值給“volatile數(shù)組”。由于在“添加/修改/刪除”數(shù)據(jù)時(shí)锥惋，都會(huì)新建數(shù)組昌腰，所以涉及到修改數(shù)據(jù)的操作，CopyOnWriteArrayList效率很低膀跌；但是單單只是進(jìn)行遍歷查找的話(huà)遭商，效率比較高。

b. 線(xiàn)程安全

通過(guò)volatile和互斥鎖來(lái)實(shí)現(xiàn)的捅伤。

• 通過(guò)volatile數(shù)組保存數(shù)據(jù)劫流。一個(gè)線(xiàn)程讀取volatile數(shù)組時(shí)，總能看到其它線(xiàn)程對(duì)該volatile變量最后的寫(xiě)入丛忆；就這樣祠汇，通過(guò)volatile提供了“讀取到的數(shù)據(jù)總是最新的”這個(gè)機(jī)制的保證。
• 通過(guò)互斥鎖來(lái)保護(hù)數(shù)據(jù)熄诡。在“添加/修改/刪除”數(shù)據(jù)時(shí)可很，會(huì)先“獲取互斥鎖”，再修改完畢之后凰浮，先將數(shù)據(jù)更新到“volatile數(shù)組”中我抠，然后再“釋放互斥鎖”苇本；這樣，就達(dá)到了保護(hù)數(shù)據(jù)的目的菜拓。

4. 特點(diǎn)

• 讀操作不需要加鎖等同步措施瓣窄，運(yùn)行速度快
• 修改操作需要新建一個(gè)數(shù)組并將原有數(shù)據(jù)拷貝到新數(shù)組中，效率較低尘惧。并且在數(shù)組元素較多的情況下需要占用的內(nèi)存空間較大

5. 適用場(chǎng)景

CopyOnWriteArrayList適合用在“讀多康栈，寫(xiě)少”的“并發(fā)”應(yīng)用中，換句話(huà)說(shuō)喷橙，它適合使用在讀操作遠(yuǎn)遠(yuǎn)大于寫(xiě)操作的場(chǎng)景里啥么。

二、CopyOnWriteArraySet

1. 類(lèi)型

Collection - Set

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

基于CopyOnWriteArrayList實(shí)現(xiàn)贰逾，即動(dòng)態(tài)數(shù)組

3.重要實(shí)現(xiàn)

基于CopyOnWriteArrayList實(shí)現(xiàn)悬荣，因此實(shí)現(xiàn)原理同CopyOnWriteArrayList。

a. 元素不重復(fù)

通過(guò)調(diào)用CopyOnWriteArrayList的addIfAbsent()和addAllAbsent()兩個(gè)方法疙剑，保證沒(méi)有重復(fù)元素氯迂。

4.特點(diǎn)

同CopyOnWriteArrayList，讀操作時(shí)運(yùn)行速度快言缤，“添加嚼蚀、刪除、修改”操作時(shí)效率低

5.適用場(chǎng)景

同CopyOnWriteArrayList

三管挟、ConcurrentHashMap

1. 類(lèi)型

Map

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

Segment是ConcurrentHashMap中的內(nèi)部類(lèi)轿曙，1個(gè)ConcurrentHashMap對(duì)象包含若干個(gè)Segment對(duì)象。

HashEntry是ConcurrentHashMap的內(nèi)部類(lèi)僻孝，是單向鏈表節(jié)點(diǎn)导帝，存儲(chǔ)著key-value鍵值對(duì)。Segment類(lèi)中存在“HashEntry數(shù)組”成員穿铆。

30215340-7346f15392ad4fb69e802749d56e0069.jpg

3. 重要實(shí)現(xiàn)

a. 線(xiàn)程安全實(shí)現(xiàn)原理

對(duì)于添加您单，刪除等操作，通過(guò)“鎖分段”實(shí)現(xiàn)荞雏。ConcurrentHashMap中包括了“Segment數(shù)組”虐秦，每個(gè)Segment就是一個(gè)哈希表，而且也是可重入的互斥鎖凤优。在操作開(kāi)始前羡疗，會(huì)先獲取Segment的互斥鎖；操作完畢之后别洪，才會(huì)釋放叨恨。

對(duì)于讀取操作，通過(guò)volatile去實(shí)現(xiàn)的挖垛。HashEntry數(shù)組是volatile類(lèi)型的痒钝，而volatile能保證“即對(duì)一個(gè)volatile變量的讀秉颗，總是能看到（任意線(xiàn)程）對(duì)這個(gè)volatile變量最后的寫(xiě)入”，即我們總能讀到其它線(xiàn)程寫(xiě)入HashEntry之后的值送矩。

以上這些方式蚕甥，就是ConcurrentHashMap線(xiàn)程安全的實(shí)現(xiàn)原理。

4. 特點(diǎn)

• 對(duì)于讀操作栋荸，不需要加鎖等操作菇怀，訪(fǎng)問(wèn)速度快
• 對(duì)于“添加、刪除晌块、修改”等操作爱沟，如果是不同segment，支持并發(fā)訪(fǎng)問(wèn)匆背，如果是同一segment呼伸，需要同步訪(fǎng)問(wèn)

5. 適用場(chǎng)景

ConcurrentHashMap對(duì)并發(fā)的控制較為細(xì)膩，適應(yīng)于高并發(fā)場(chǎng)景钝尸。

6. ConcurrentHashMap和HashTable的區(qū)別

Hashtable是線(xiàn)程安全的哈希表括享，通過(guò)synchronized來(lái)保證線(xiàn)程安全的；即珍促，多線(xiàn)程通過(guò)同一個(gè)“對(duì)象的同步鎖”來(lái)實(shí)現(xiàn)并發(fā)控制铃辖。Hashtable在線(xiàn)程競(jìng)爭(zhēng)激烈時(shí)，效率比較低猪叙，因?yàn)楫?dāng)一個(gè)線(xiàn)程訪(fǎng)問(wèn)Hashtable的同步方法時(shí)娇斩，其它線(xiàn)程就訪(fǎng)問(wèn)Hashtable的同步方法時(shí)，可能會(huì)進(jìn)入阻塞狀態(tài)沐悦。

ConcurrentHashMap是線(xiàn)程安全的哈希表，通過(guò)“鎖分段”來(lái)保證線(xiàn)程安全的五督。ConcurrentHashMap將哈希表分成許多片段(Segment)藏否，每一個(gè)片段除了保存哈希表之外，本質(zhì)上也是一個(gè)“可重入的互斥鎖”(ReentrantLock)充包。多線(xiàn)程對(duì)同一個(gè)片段的訪(fǎng)問(wèn)副签，是互斥的；但是基矮，對(duì)于不同片段的訪(fǎng)問(wèn)淆储，是可以并發(fā)進(jìn)行的。

四家浇、ConcurrentSkipListMap

1. 類(lèi)型

Map

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

跳表

跳表分為許多層(level)本砰，每一層都可以看作是數(shù)據(jù)的索引，這些索引的意義就是加快跳表查找數(shù)據(jù)速度钢悲。每一層的數(shù)據(jù)都是有序的点额，上一層數(shù)據(jù)是下一層數(shù)據(jù)的子集舔株，并且第一層(level 1)包含了全部的數(shù)據(jù)；層次越高还棱，跳躍性越大载慈，包含的數(shù)據(jù)越少。

30221944-21a18064c0114e65bffa68c5dadd4f0b.jpg

查找方式：

普通鏈表查找方式珍手，如下圖順序查找办铡，查找到“32”共需要4步。

30222059-f01604b1b24d429e940f7a002947c143.jpg

跳表包含一個(gè)表頭琳要，它查找數(shù)據(jù)時(shí)寡具，是從上往下，從左往右進(jìn)行查找焙蹭，如下圖晒杈，查找到“32”共需要2步（不包括垂直的跳躍）。

30222128-045c88b7e992443395a540ba2eb740f3.jpg

復(fù)雜度分析：

參考文檔：http://blog.sina.com.cn/s/blog_68f6d5370102uykh.html

每個(gè)跳表需要確定一個(gè)概率因子孔厉，表明對(duì)于每一層來(lái)說(shuō)每添加一個(gè)節(jié)點(diǎn)拯钻，把這個(gè)節(jié)點(diǎn)添加到上層的概率。概率因子一般用1/2或1/e 撰豺，下面使用P代替粪般。

空間復(fù)雜度：S = n + n/P + n/(P^2) + ... + n/(P^n) < n(1 + 1/P + 1/(P^2) + ... + 1/P∞) =2n，因此空間復(fù)雜度為 2n = O(n)

高度：對(duì)每層來(lái)說(shuō)污桦，它會(huì)向上增長(zhǎng)的概率為1/P亩歹，則第m層向上增長(zhǎng)的概率為1/(P^m)；n個(gè)元素凡橱，則在m層元素?cái)?shù)目的期待為Em = n/(P^m)小作；當(dāng)Em = 1，m = logp(n)即為層數(shù)的期待稼钩。故其高度期待為 Eh = O(logn)顾稀。

查詢(xún)復(fù)雜度：為高度／p，即O(logn)

插入／刪除復(fù)雜度： 插入和刪除都由查找和更新兩部分構(gòu)成坝撑。查找的時(shí)間復(fù)雜度為O(logn)静秆，更新部分的復(fù)雜度又與跳躍表的高度成正比，即也為O(logn)巡李。
所以抚笔，插入和刪除操作的時(shí)間復(fù)雜度都為O(logn) 。

3. 重要實(shí)現(xiàn)

線(xiàn)程安全實(shí)現(xiàn)原理

利用底層的插入侨拦、刪除的CAS原子性操作殊橙，通過(guò)死循環(huán)不斷獲取最新的結(jié)點(diǎn)指針來(lái)保證不會(huì)出現(xiàn)競(jìng)態(tài)條件。

4. ConcurrentSkipListMap和TreeMap的區(qū)別

• 線(xiàn)程安全性不同
• 實(shí)現(xiàn)有序的數(shù)據(jù)結(jié)構(gòu)不同，TreeMap使用紅黑樹(shù)實(shí)現(xiàn)蛀柴、ConcurrentSkipListMap使用跳表實(shí)現(xiàn)

五螃概、ConcurrentSkipListSet

1. 類(lèi)型

Collection - Set

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

基于ConcurrentSkipListMap實(shí)現(xiàn)

3.重要實(shí)現(xiàn)

基于CopyOnWriteArrayList實(shí)現(xiàn)，因此實(shí)現(xiàn)原理同CopyOnWriteArrayList鸽疾。

六吊洼、ArrayBlockingQueue

1. 類(lèi)型

Collection - Queue

2. 特點(diǎn)

數(shù)組實(shí)現(xiàn)的線(xiàn)程安全的有界的阻塞隊(duì)列

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

數(shù)組

4. 重要實(shí)現(xiàn)

a. 線(xiàn)程安全實(shí)現(xiàn)原理

使用“互斥鎖”ReentrantLock實(shí)現(xiàn)線(xiàn)程安全。在public方法中都使用ReentrantLock加鎖制肮，實(shí)現(xiàn)線(xiàn)程安全冒窍。

public void put(E e) throws InterruptedException {
    Objects.requireNonNull(e);
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        while (count == items.length)
            notFull.await();
        enqueue(e);
    } finally {
        lock.unlock();
    }
}

b. block實(shí)現(xiàn)原理

ReentrantLock兩個(gè)鎖，notEmpty用來(lái)表示是否為空列表豺鼻，notFull用來(lái)表示隊(duì)列是否已滿(mǎn)综液。

notEmpty = lock.newCondition();
notFull =  lock.newCondition();

ArrayBlockingQueue中put／take方法為阻塞方法。

put：若隊(duì)列已滿(mǎn)儒飒，notFull.await()谬莹，當(dāng)元素被消耗或者刪除時(shí)，notFull.signal()桩了。

public void put(E e) throws InterruptedException {
    Objects.requireNonNull(e);
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        while (count == items.length)
            notFull.await(); //如果隊(duì)列已滿(mǎn)附帽，則wait，并放棄目前得到鎖井誉。
        enqueue(e);
    } finally {
        lock.unlock();
    }
}

take：若隊(duì)列為空蕉扮，notEmpty.wait()，當(dāng)元素被添加時(shí)颗圣，notEmpty.signal()喳钟。

public E take() throws InterruptedException {
    final ReentrantLock lock = this.lock;
    lock.lockInterruptibly();
    try {
        while (count == 0)
            notEmpty.await(); //如果隊(duì)列為空，則wait在岂，并放棄目前得到鎖奔则。
        return dequeue();
    } finally {
        lock.unlock();
    }
}

5. 其他

take／put

阻塞方法

add／remove／element

非阻塞方法，當(dāng)隊(duì)列已滿(mǎn)或隊(duì)列為空導(dǎo)致執(zhí)行失敗時(shí)蔽午，拋出IIIegaISlabEepeplian／NoSuchElementException異常

offer／poll／peek

非阻塞方法易茬，當(dāng)隊(duì)列已滿(mǎn)或隊(duì)列為空導(dǎo)致執(zhí)行失敗時(shí)，返回false/null表示執(zhí)行失敗祠丝。

七疾呻、LinkedBlockingQueue

1. 類(lèi)型

Collection - Queue

2. 特點(diǎn)

單向鏈表實(shí)現(xiàn)的線(xiàn)程安全的無(wú)界的阻塞隊(duì)列

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

單向鏈表

4. 重要實(shí)現(xiàn)

a. 線(xiàn)程安全實(shí)現(xiàn)原理

使用“互斥鎖”ReentrantLock實(shí)現(xiàn)除嘹。由于鏈表的插入和刪除不會(huì)影響整個(gè)數(shù)據(jù)結(jié)構(gòu)（對(duì)于數(shù)組實(shí)現(xiàn)的ArrayBlockingQueue写半，插入和刪除都要修改整個(gè)數(shù)據(jù)結(jié)構(gòu)），因此使用takeLock和putLock兩個(gè)鎖尉咕，獲取數(shù)據(jù)時(shí)使用takeLock叠蝇，添加數(shù)據(jù)時(shí)使用putLock。

private final ReentrantLock takeLock = new ReentrantLock();
private final ReentrantLock putLock = new ReentrantLock();

5. 阻塞實(shí)現(xiàn)原理

兩個(gè)ReentrantLock年缎，兩個(gè)condition悔捶，notEmpty用來(lái)表示是否為空列表铃慷，notFull用來(lái)表示隊(duì)列是否已滿(mǎn)。

    -- 若某線(xiàn)程(線(xiàn)程A)要取出數(shù)據(jù)時(shí)蜕该，隊(duì)列正好為空犁柜，則該線(xiàn)程會(huì)執(zhí)行notEmpty.await()進(jìn)行等待；當(dāng)其它某個(gè)線(xiàn)程(線(xiàn)程B)向隊(duì)列中插入了數(shù)據(jù)之后堂淡，會(huì)調(diào)用notEmpty.signal()喚醒“notEmpty上的等待線(xiàn)程”馋缅。此時(shí)，線(xiàn)程A會(huì)被喚醒從而得以繼續(xù)運(yùn)行绢淀。 此外萤悴，線(xiàn)程A在執(zhí)行取操作前，會(huì)獲取takeLock皆的，在取操作執(zhí)行完畢再釋放takeLock覆履。
     -- 若某線(xiàn)程(線(xiàn)程H)要插入數(shù)據(jù)時(shí)，隊(duì)列已滿(mǎn)费薄，則該線(xiàn)程會(huì)它執(zhí)行notFull.await()進(jìn)行等待硝全；當(dāng)其它某個(gè)線(xiàn)程(線(xiàn)程I)取出數(shù)據(jù)之后，會(huì)調(diào)用notFull.signal()喚醒“notFull上的等待線(xiàn)程”义锥。此時(shí)柳沙，線(xiàn)程H就會(huì)被喚醒從而得以繼續(xù)運(yùn)行。 此外拌倍，線(xiàn)程H在執(zhí)行插入操作前赂鲤，會(huì)獲取putLock，在插入操作執(zhí)行完畢才釋放putLock柱恤。

take：

public E take() throws InterruptedException {
    E x;
    int c = -1;
    final AtomicInteger count = this.count;
    final ReentrantLock takeLock = this.takeLock;
    takeLock.lockInterruptibly();  //加鎖
    try {
        while (count.get() == 0) { //數(shù)量為0
            notEmpty.await();      //等待并釋放鎖
        }
        x = dequeue();   //put方法notEmpty.signal()数初，喚醒并獲取數(shù)據(jù)
        c = count.getAndDecrement(); //數(shù)量減1，此時(shí)拿到的c是減之前的數(shù)據(jù)
        if (c > 1) //c >= 2,表示拿完數(shù)據(jù)以后還有數(shù)據(jù)梗顺，繼續(xù)喚醒其他的消費(fèi)者
            notEmpty.signal();
    } finally {
        takeLock.unlock();
    }
    if (c == capacity) //原先的數(shù)量是滿(mǎn)的泡孩，此時(shí)消耗了一個(gè)，通知其他生產(chǎn)者可以生產(chǎn)了
        signalNotFull();
    return x;
}

put:

public void put(E e) throws InterruptedException {
    if (e == null) throw new NullPointerException();
    int c = -1;
    Node<E> node = new Node<E>(e);
    final ReentrantLock putLock = this.putLock;
    final AtomicInteger count = this.count;
    putLock.lockInterruptibly();
    try {
        while (count.get() == capacity) {
            notFull.await();  //等待并釋放鎖
        }
        enqueue(node); //添加到隊(duì)列里
        c = count.getAndIncrement();  //增加數(shù)量
        if (c + 1 < capacity) //還有容量寺谤，通知其他生產(chǎn)者繼續(xù)生產(chǎn)
            notFull.signal();
    } finally {
        putLock.unlock();
    }
    if (c == 0)  //從無(wú)變有仑鸥，通知消耗者可以消耗了
        signalNotEmpty();
}

八、LinkedBlockingDeque

1. 類(lèi)型

Collection - Queue - Deque

2. 特點(diǎn)

雙向鏈表實(shí)現(xiàn)的雙向并發(fā)阻塞隊(duì)列

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

雙向鏈表

4. 重要實(shí)現(xiàn)

包括一個(gè)“互斥鎖”和兩個(gè)“Condition”

final ReentrantLock lock = new ReentrantLock();
private final Condition notEmpty = lock.newCondition();
private final Condition notFull = lock.newCondition();

線(xiàn)程安全實(shí)現(xiàn)原理

所有public方法使用ReentrantLock包括变屁，保證其線(xiàn)程安全性眼俊。

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

使用notEmpty和notFull實(shí)現(xiàn)阻塞。

注意：

1. LinkedBlockingDeque使用單鎖粟关，getSize()時(shí)加鎖并返回count疮胖，count為普通int型，通過(guò)鎖保證數(shù)據(jù)正確性
2. LinkedBlockingQueue使用雙鎖，getSize()時(shí)直接返回count澎灸，count為AtomicInteger類(lèi)型院塞，通過(guò)自動(dòng)保證數(shù)據(jù)正確性

九、 ConcurrentLinkedQueue

1. 類(lèi)型

Collection - Queue - Deque

2. 特點(diǎn)

基于雙向鏈表的無(wú)界線(xiàn)程安全隊(duì)列性昭，按照 FIFO（先進(jìn)先出）原則對(duì)元素進(jìn)行排序拦止。隊(duì)列元素中不可以放置null元素（內(nèi)部實(shí)現(xiàn)的特殊節(jié)點(diǎn)除外）。

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

雙向鏈表

4. 重要實(shí)現(xiàn)

a. 線(xiàn)程安全

利用底層的插入糜颠、刪除的CAS原子性操作创泄，通過(guò)死循環(huán)不斷獲取最新的結(jié)點(diǎn)指針來(lái)保證不會(huì)出現(xiàn)競(jìng)態(tài)條件。

b. 并發(fā)優(yōu)化

入隊(duì)列

從源代碼角度來(lái)看整個(gè)入隊(duì)過(guò)程主要做二件事情括蝠。第一是定位出尾節(jié)點(diǎn)鞠抑，第二是使用CAS算法能將入隊(duì)節(jié)點(diǎn)設(shè)置成尾節(jié)點(diǎn)的next節(jié)點(diǎn)，如不成功則重試忌警。

hops的設(shè)計(jì)意圖搁拙。使用hops變量來(lái)控制并減少tail節(jié)點(diǎn)的更新頻率，并不是每次節(jié)點(diǎn)入隊(duì)后都將 tail節(jié)點(diǎn)更新成尾節(jié)點(diǎn)法绵，而是當(dāng) tail節(jié)點(diǎn)和尾節(jié)點(diǎn)的距離大于等于常量HOPS的值（默認(rèn)等于1）時(shí)才更新tail節(jié)點(diǎn)箕速，tail和尾節(jié)點(diǎn)的距離越長(zhǎng)使用CAS更新tail節(jié)點(diǎn)的次數(shù)就會(huì)越少，但是距離越長(zhǎng)帶來(lái)的負(fù)面效果就是每次入隊(duì)時(shí)定位尾節(jié)點(diǎn)的時(shí)間就越長(zhǎng)朋譬，因?yàn)檠h(huán)體需要多循環(huán)一次來(lái)定位出尾節(jié)點(diǎn)盐茎，但是這樣仍然能提高入隊(duì)的效率，因?yàn)閺谋举|(zhì)上來(lái)看它通過(guò)增加對(duì)volatile變量的讀操作來(lái)減少了對(duì)volatile變量的寫(xiě)操作徙赢，而對(duì)volatile變量的寫(xiě)操作開(kāi)銷(xiāo)要遠(yuǎn)遠(yuǎn)大于讀操作字柠，所以入隊(duì)效率會(huì)有所提升。

出隊(duì)列

并不是每次出隊(duì)時(shí)都更新head節(jié)點(diǎn)狡赐，當(dāng)head節(jié)點(diǎn)里有元素時(shí)窑业，直接彈出head節(jié)點(diǎn)里的元素，而不會(huì)更新head節(jié)點(diǎn)枕屉。只有當(dāng)head節(jié)點(diǎn)里沒(méi)有元素時(shí)常柄，出隊(duì)操作才會(huì)更新head節(jié)點(diǎn)。這種做法也是通過(guò)hops變量來(lái)減少使用CAS更新head節(jié)點(diǎn)的消耗搀擂，從而提高出隊(duì)效率西潘。

首先獲取頭節(jié)點(diǎn)的元素，然后判斷頭節(jié)點(diǎn)元素是否為空哨颂，如果為空喷市，表示另外一個(gè)線(xiàn)程已經(jīng)進(jìn)行了一次出隊(duì)操作將該節(jié)點(diǎn)的元素取走，如果不為空咆蒿，則使用CAS的方式將頭節(jié)點(diǎn)的引用設(shè)置成null东抹，如果CAS成功，則直接返回頭節(jié)點(diǎn)的元素沃测，如果不成功缭黔，表示另外一個(gè)線(xiàn)程已經(jīng)進(jìn)行了一次出隊(duì)操作更新了head節(jié)點(diǎn)，導(dǎo)致元素發(fā)生了變化蒂破，需要重新獲取頭節(jié)點(diǎn)馏谨。