1. 同步容器
在早期的JDK中，同步容器有兩種現(xiàn)成的實(shí)現(xiàn)，Vector和Hashtable，可以直接new對(duì)象獲取；在JDK1.2中，引入了同步封裝類，可以由Collections.synchronizedXxxx等方法創(chuàng)建；這兩種方式底層實(shí)現(xiàn)都是通過將狀態(tài)封裝起來，并對(duì)每個(gè)公有方法進(jìn)行同步，使得每次只有一個(gè)線程能訪問容器的狀態(tài)。
以Hashtable為例查看jdk源碼實(shí)現(xiàn)如下所示：
public synchronized V remove(Object key) {}
public synchronized V put(K key, V value) {}
public synchronized V get(Object key) {}
可以看到Hashtable與普通HashMap的區(qū)別就是相應(yīng)方法都添加了synchronized進(jìn)行同步，這個(gè)保證了容器操作的安全。但是，所有對(duì)容器狀態(tài)的訪問都串行化，這種代價(jià)就是嚴(yán)重降低了并發(fā)性，多個(gè)線程競(jìng)爭(zhēng)的時(shí)候，吞吐量嚴(yán)重降低。
2. 并發(fā)容器
前面敘述了同步容器使用的局限性，JDK5.0開始增加了ConcurrentHashMap等并發(fā)容器來代替同步容器提高多線程并發(fā)情況下的性能。下面就其中典型并發(fā)容器使用和實(shí)現(xiàn)進(jìn)行介紹：
2.1 ConcurrentHashMap
2.1.1ConcurrentHashMap設(shè)計(jì)
ConcurrentHashMap采用了分段鎖的設(shè)計(jì)，只有在同一個(gè)分段內(nèi)才存在競(jìng)態(tài)關(guān)系，不同的分段鎖之間沒有鎖競(jìng)爭(zhēng)。相比于對(duì)整個(gè)Map加鎖的設(shè)計(jì)，分段鎖大大的提高了高并發(fā)環(huán)境下的處理能力。
ConcurrentHashMap中主要實(shí)體類就是三個(gè)：ConcurrentHashMap（整個(gè)Hash表）,Segment（桶），HashEntry（節(jié)點(diǎn)），對(duì)應(yīng)下圖可以看出之間的關(guān)系：
從上面的結(jié)構(gòu)我們可以了解到，ConcurrentHashMap定位一個(gè)元素的過程需要進(jìn)行兩次Hash操作，第一次Hash定位到Segment，第二次Hash定位到元素所在的鏈表的頭部。由于不同的Segment有各自的鎖，理想情況下ConcurrentHashMap可以最高同時(shí)支持Segment數(shù)量大小的寫操作。
2.1.2ConcurrentHashMap常用方法分析
get操作
查看JDK源碼整個(gè)get操作過程不需要加鎖，主要分兩步第一步進(jìn)行再散列，并根據(jù)再散列值定位到Segment；第二步找到對(duì)應(yīng)HashEntry并遍歷鏈表找到具體對(duì)應(yīng)值。
put操作
查看JDK源碼put操作，為了線程安全，在操作共享變量時(shí)必須加鎖。put方法首先定位到Segment，然后在Segment里面進(jìn)行插入操作。插入操作需要進(jìn)行兩個(gè)步驟，第一步判斷是否需要對(duì)Segment里的HashEntry數(shù)組進(jìn)行擴(kuò)容，第二步定位添加元素的位置，然后將其放在HashEntry數(shù)組里。
size操作
前面兩個(gè)操作都是在單個(gè)segment中進(jìn)行的，但是size操作是在多個(gè)segment中進(jìn)行。ConcurrentHashMap的size操作也采用了一種比較巧的方式，來盡量避免對(duì)所有的Segment都加鎖。ConcurrentHashMap的做法是先嘗試2次通過不鎖住Segment的方式來統(tǒng)計(jì)各個(gè)Segment大小，如果統(tǒng)計(jì)過程中，容器count發(fā)生了變化，則采用加鎖的方式來統(tǒng)計(jì)所有Segment大小。這里ConcurrentHashMap通過判斷modCount是否變化來判斷容器在計(jì)算size過程中是否發(fā)生變化。
2.2 CopyOnWrite
CopyOnWrite即寫入時(shí)復(fù)制的容器，每次修改的時(shí)，都會(huì)創(chuàng)建并重新發(fā)布一個(gè)新的容器副本，然后新的容器副本里添加元素，添加完元素之后，再將原容器的引用指向新的容器。
CopyOnWrite容器也是一種讀寫分離的思想，讀和寫不同的容器，由于當(dāng)前容器不會(huì)被修改所以支持無鎖并發(fā)讀取。
2.2.1 CopyOnWriteArrayList的實(shí)現(xiàn)原理
作為CopyOnWrite思想具體實(shí)現(xiàn)類CopyOnWriteArrayList，首先看下源碼如何實(shí)現(xiàn)元素添加修改。可以發(fā)現(xiàn)在添加的時(shí)候是需要加鎖的，否則多線程寫的時(shí)候會(huì)Copy出N個(gè)副本出來。
同時(shí)，讀取元素操作非常簡(jiǎn)單不需要鎖如下圖所示：
2.2.2使用場(chǎng)景和注意點(diǎn)
CopyOnWrite并發(fā)容器用于讀多寫少的并發(fā)場(chǎng)景。比如白名單，黑名單，商品類目的訪問和更新的場(chǎng)景。
使用注意點(diǎn)：
- 使用批量添加。因?yàn)槊看翁砑?，容器每次都?huì)進(jìn)行復(fù)制，所以減少添加次數(shù)，可以減少容器的復(fù)制次數(shù)。
- 根據(jù)實(shí)際需求初始化容器大小，減少擴(kuò)容帶來的開銷。
- 該容器不適合存儲(chǔ)占據(jù)內(nèi)存大的大對(duì)象由于復(fù)制的原因容易引起FullGC
- CopyOnWrite容器只能保證數(shù)據(jù)的最終一致性，不能保證數(shù)據(jù)的實(shí)時(shí)一致性。所以如果你希望寫入的的數(shù)據(jù)，馬上能讀到，請(qǐng)不要使用CopyOnWrite容器。
2.3 并發(fā)隊(duì)列ConcurrentLinkedQueue
在并發(fā)編程中需要使用線程安全的隊(duì)列有兩種實(shí)現(xiàn)方式一種是使用阻塞算法，另一種是使用非阻塞算法。使用阻塞算法的隊(duì)列可以用一個(gè)鎖（入隊(duì)和出隊(duì)用同一把鎖）或兩個(gè)鎖（入隊(duì)和出隊(duì)用不同的鎖）等方式來實(shí)現(xiàn)，而非阻塞的實(shí)現(xiàn)方式則可以使用循環(huán)CAS的方式來實(shí)現(xiàn)。并發(fā)隊(duì)列ConcurrentLinkedQueue通過非阻塞方式實(shí)現(xiàn)。
2.3.1 ConcurrentLinkedQueue設(shè)計(jì)
ConcurrentLinkedQueue 的非阻塞算法實(shí)現(xiàn)主要可概括為下面幾點(diǎn)：
- 使用 CAS 原子指令來處理對(duì)數(shù)據(jù)的并發(fā)訪問，這是非阻塞算法得以實(shí)現(xiàn)的基礎(chǔ)。
- head/tail 并非總是指向隊(duì)列的頭 / 尾節(jié)點(diǎn)，也就是說允許隊(duì)列處于不一致狀態(tài)。 這個(gè)特性把入隊(duì) /出隊(duì)時(shí)，原本需要一起原子化執(zhí)行的兩個(gè)步驟分離開來，從而縮小了入隊(duì) /出隊(duì)時(shí)需要原子化更新值的范圍到唯一變量。這是非阻塞算法得以實(shí)現(xiàn)的關(guān)鍵。
- 以批處理方式來更新head/tail，從整體上減少入隊(duì) / 出隊(duì)操作的開銷。
ConcurrentLinkedQueue由head節(jié)點(diǎn)和tail節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)（Node）由節(jié)點(diǎn)元素（item）和指向下一個(gè)節(jié)點(diǎn)的引用(next)組成，節(jié)點(diǎn)與節(jié)點(diǎn)之間就是通過這個(gè)next關(guān)聯(lián)起來，從而組成一張鏈表結(jié)構(gòu)的隊(duì)列。默認(rèn)情況下head節(jié)點(diǎn)存儲(chǔ)的元素為空，tail節(jié)點(diǎn)等于head節(jié)點(diǎn)。
3. 阻塞隊(duì)列
阻塞隊(duì)列（BlockingQueue）與普通隊(duì)列的區(qū)別在于添加了兩個(gè)附加操作：當(dāng)隊(duì)列是空的時(shí)，從隊(duì)列中獲取元素的操作將會(huì)被阻塞；當(dāng)隊(duì)列是滿時(shí)，往隊(duì)列里添加元素的操作會(huì)被阻塞。
BlockingQueue最終會(huì)有四種狀況，拋出異常、返回特殊值、阻塞、超時(shí)，下表總結(jié)了這些方法：
- 拋出異常：是指當(dāng)阻塞隊(duì)列滿時(shí)候，再往隊(duì)列里插入元素，會(huì)拋出IllegalStateException("Queue full")異常。
- 返回特殊值：插入方法會(huì)返回是否成功，成功則返回true。移除方法，則是從隊(duì)列里拿出一個(gè)元素，如果沒有則返回null。
- 一直阻塞：當(dāng)阻塞隊(duì)列滿時(shí)，如果生產(chǎn)者線程往隊(duì)列里put元素，隊(duì)列會(huì)一直阻塞生產(chǎn)者線程，直到拿到數(shù)據(jù)，或者響應(yīng)中斷退出。當(dāng)隊(duì)列空時(shí)，消費(fèi)者線程試圖從隊(duì)列里take元素，隊(duì)列也會(huì)阻塞消費(fèi)者線程，直到隊(duì)列可用。
- 超時(shí)退出：當(dāng)阻塞隊(duì)列滿時(shí)，隊(duì)列會(huì)阻塞生產(chǎn)者線程一段時(shí)間，如果超過一定的時(shí)間，生產(chǎn)者線程就會(huì)退出。
3.1 JDK提供阻塞隊(duì)列
JDK7提供了7個(gè)阻塞隊(duì)列實(shí)現(xiàn)類，下面就其中常用類進(jìn)行分析：
- ArrayBlockQueue：一個(gè)由數(shù)組支持的有界阻塞隊(duì)列。此隊(duì)列按 FIFO（先進(jìn)先出）原則對(duì)元素進(jìn)行排序。創(chuàng)建其對(duì)象必須明確大小，像數(shù)組一樣。默認(rèn)情況下不保證訪問者公平的訪問隊(duì)列，即不會(huì)根據(jù)阻塞的先后順序來提供給訪問者。
- LinkedBlockQueue：一個(gè)可改變大小的阻塞隊(duì)列。此隊(duì)列按 FIFO（先進(jìn)先出）原則對(duì)元素進(jìn)行排序。創(chuàng)建其對(duì)象如果沒有明確大小，默認(rèn)值是Integer.MAX_VALUE。
- PriorityBlockingQueue：類似于LinkedBlockingQueue，但其所含對(duì)象的排序不是FIFO，而是依據(jù)對(duì)象的自然排序順序或者是構(gòu)造函數(shù)所帶的Comparator決定的順序。
- SynchronousQueue：同步隊(duì)列。同步隊(duì)列沒有任何容量，每個(gè)插入必須等待另一個(gè)線程移除，反之亦然。即每一個(gè)put操作必須等待一個(gè)take操作，否則不能繼續(xù)添加元素。SynchronousQueue可以看成是一個(gè)傳球手，負(fù)責(zé)把生產(chǎn)者線程處理的數(shù)據(jù)直接傳遞給消費(fèi)者線程。
- DelayQueue：一個(gè)支持延時(shí)獲取元素的無界阻塞隊(duì)列。隊(duì)列使用PriorityQueue來實(shí)現(xiàn)。隊(duì)列中的元素必須實(shí)現(xiàn)Delayed接口，在創(chuàng)建元素時(shí)可以指定多久才能從隊(duì)列中獲取當(dāng)前元素。只有在延遲期滿時(shí)才能從隊(duì)列中提取元素。
3.2 ArrayBlockQueue實(shí)現(xiàn)原理
以ArrayBlockingQueue為例我們查看下JDK源碼可以發(fā)現(xiàn)其主要使用Condition來實(shí)現(xiàn)通知?！?dāng)生產(chǎn)者往滿的隊(duì)列里添加元素時(shí)會(huì)阻塞住生產(chǎn)者，當(dāng)消費(fèi)者消費(fèi)了一個(gè)隊(duì)列中的元素后，會(huì)通知生產(chǎn)者當(dāng)前隊(duì)列可用。
生產(chǎn)者往滿的隊(duì)列里添加元素時(shí)會(huì)阻塞住生產(chǎn)者
消費(fèi)者消費(fèi)空隊(duì)列的時(shí)候會(huì)阻塞消費(fèi)者
3.3 阻塞隊(duì)列的應(yīng)用
阻塞隊(duì)列支持生產(chǎn)者——消費(fèi)者這種設(shè)計(jì)模式，當(dāng)數(shù)據(jù)產(chǎn)生時(shí)候，生產(chǎn)者把數(shù)據(jù)放到隊(duì)列當(dāng)中，而當(dāng)消費(fèi)者準(zhǔn)備處理數(shù)據(jù)時(shí)，將從隊(duì)列中獲取數(shù)據(jù)。生產(chǎn)者不需要知道消費(fèi)者的標(biāo)識(shí)或數(shù)量，只需要將數(shù)據(jù)放入隊(duì)列即可。同樣，消費(fèi)者也不需要知道生產(chǎn)者是誰。 阻塞隊(duì)列簡(jiǎn)化了生產(chǎn)者——消費(fèi)者設(shè)計(jì)的實(shí)現(xiàn)過程，支持任意數(shù)量的生產(chǎn)者和消費(fèi)者。
參考
http://www.cnblogs.com/dolphin0520/p/3932905.html
http://www.importnew.com/22007.html
http://ifeve.com/java-copy-on-write/
http://ifeve.com/java-blocking-queue/
http://blog.csdn.net/ghsau/article/details/8108292
