在盡可能短的篇幅里，將所有集合與并發(fā)集合的特征，實(shí)現(xiàn)方式，性能捋一遍。適合所有"精通Java"其實(shí)還不那么自信的人閱讀。

　List

　　ArrayList

　　以數(shù)組實(shí)現(xiàn)。節(jié)約空間，但數(shù)組有容量限制。超出限制時(shí)會(huì)增加50%容量，用System.arraycopy()復(fù)制到新的數(shù)組，因此最好能給出數(shù)組大小的預(yù)估值。默認(rèn)第一次插入元素時(shí)創(chuàng)建大小為10的數(shù)組。

　　按數(shù)組下標(biāo)訪問元素--get(i)/set(i,e) 的性能很高，這是數(shù)組的基本優(yōu)勢。

　　直接在數(shù)組末尾加入元素--add(e)的性能也高，但如果按下標(biāo)插入、刪除元素--add(i,e), remove(i), remove(e)，則要用System.arraycopy()來移動(dòng)部分受影響的元素，性能就變差了，這是基本劣勢。

　　LinkedList

　　以雙向鏈表實(shí)現(xiàn)。鏈表無容量限制，但雙向鏈表本身使用了更多空間，也需要額外的鏈表指針操作。

　　按下標(biāo)訪問元素--get(i)/set(i,e) 要悲劇的遍歷鏈表將指針移動(dòng)到位(如果i>數(shù)組大小的一半，會(huì)從末尾移起)。

　　插入、刪除元素時(shí)修改前后節(jié)點(diǎn)的指針即可，但還是要遍歷部分鏈表的指針才能移動(dòng)到下標(biāo)所指的位置，只有在鏈表兩頭的操作--add(), addFirst(),removeLast()或用iterator()上的remove()能省掉指針的移動(dòng)。

　　CopyOnWriteArrayList

　　并發(fā)優(yōu)化的ArrayList。用CopyOnWrite策略，在修改時(shí)先復(fù)制一個(gè)快照來修改，改完再讓內(nèi)部指針指向新數(shù)組。

　　因?yàn)閷�快照的修改對讀操作來說不可見，所以只有寫鎖沒有讀鎖，加上復(fù)制的昂貴成本，典型的適合讀多寫少的場景。如果更新頻率較高，或數(shù)組較大時(shí)，還是Collections.synchronizedList(list)，對所有操作用同一把鎖來保證線程安全更好。

　　增加了addIfAbsent(e)方法，會(huì)遍歷數(shù)組來檢查元素是否已存在，性能可想像的不會(huì)太好。

　　補(bǔ)充

　　無論哪種實(shí)現(xiàn)，按值返回下標(biāo)--contains(e), indexOf(e), remove(e) 都需遍歷所有元素進(jìn)行比較，性能可想像的不會(huì)太好。

　　沒有按元素值排序的SortedList，在線程安全類中也沒有無鎖算法的ConcurrentLinkedList，湊合著用Set與Queue中的等價(jià)類時(shí)，會(huì)缺少一些List特有的方法。

　Map

　　HashMap

　　以Entry[]數(shù)組實(shí)現(xiàn)的哈希桶數(shù)組，用Key的哈希值取模桶數(shù)組的大小可得到數(shù)組下標(biāo)。

　　插入元素時(shí)，如果兩條Key落在同一個(gè)桶(比如哈希值1和17取模16后都屬于第一個(gè)哈希桶)，Entry用一個(gè)next屬性實(shí)現(xiàn)多個(gè)Entry以單向鏈表存放，后入桶的Entry將next指向桶當(dāng)前的Entry。

　　查找哈希值為17的key時(shí)，先定位到第一個(gè)哈希桶，然后以鏈表遍歷桶里所有元素，逐個(gè)比較其key值。

　　當(dāng)Entry數(shù)量達(dá)到桶數(shù)量的75%時(shí)(很多文章說使用的桶數(shù)量達(dá)到了75%，但看代碼不是)，會(huì)成倍擴(kuò)容桶數(shù)組，并重新分配所有原來的Entry，所以這里也最好有個(gè)預(yù)估值。

　　取模用位運(yùn)算(hash & (arrayLength-1))會(huì)比較快，所以數(shù)組的大小永遠(yuǎn)是2的N次方， 你隨便給一個(gè)初始值比如17會(huì)轉(zhuǎn)為32。默認(rèn)第一次放入元素時(shí)的初始值是16。

　　iterator()時(shí)順著哈希桶數(shù)組來遍歷，看起來是個(gè)亂序。

　　在JDK8里，新增默認(rèn)為8的閥值，當(dāng)一個(gè)桶里的Entry超過閥值，就不以單向鏈表而以紅黑樹來存放以加快Key的查找速度。

　　LinkedHashMap

　　擴(kuò)展HashMap增加雙向鏈表的實(shí)現(xiàn)，號(hào)稱是最占內(nèi)存的數(shù)據(jù)結(jié)構(gòu)。支持iterator()時(shí)按Entry的插入順序來排序(但是更新不算， 如果設(shè)置accessOrder屬性為true，則所有讀寫訪問都算)。

　　實(shí)現(xiàn)上是在Entry上再增加屬性before/after指針，插入時(shí)把自己加到Header Entry的前面去。如果所有讀寫訪問都要排序，還要把前后Entry的before/after拼接起來以在鏈表中刪除掉自己。

　　TreeMap

　　以紅黑樹實(shí)現(xiàn)，篇幅所限詳見入門教程。支持iterator()時(shí)按Key值排序，可按實(shí)現(xiàn)了Comparable接口的Key的升序排序，或由傳入的Comparator控制�？上胂蟮模�在樹上插入/刪除元素的代價(jià)一定比HashMap的大。

　　支持SortedMap接口，如firstKey()，lastKey()取得最大最小的key，或sub(fromKey, toKey), tailMap(fromKey)剪取Map的某一段。

　　ConcurrentHashMap

　　并發(fā)優(yōu)化的HashMap，默認(rèn)16把寫鎖(可以設(shè)置更多)，有效分散了阻塞的概率，而且沒有讀鎖。

　　數(shù)據(jù)結(jié)構(gòu)為Segment[]，Segment里面才是哈希桶數(shù)組，每個(gè)Segment一把鎖。Key先算出它在哪個(gè)Segment里，再算出它在哪個(gè)哈希桶里。

　　支持ConcurrentMap接口，如putIfAbsent(key，value)與相反的replace(key，value)與以及實(shí)現(xiàn)CAS的replace(key, oldValue, newValue)。

　　沒有讀鎖是因?yàn)閜ut/remove動(dòng)作是個(gè)原子動(dòng)作(比如put是一個(gè)對數(shù)組元素/Entry 指針的賦值操作)，讀操作不會(huì)看到一個(gè)更新動(dòng)作的中間狀態(tài)。

　　ConcurrentSkipListMap

　　JDK6新增的并發(fā)優(yōu)化的SortedMap，以SkipList實(shí)現(xiàn)。SkipList是紅黑樹的一種簡化替代方案，是個(gè)流行的有序集合算法，篇幅所限見入門教程。Concurrent包選用它是因?yàn)樗�支持基于CAS的無鎖算法，而紅黑樹則沒有好的無鎖算法。

　　很特殊的，它的size()不能隨便調(diào)，會(huì)遍歷來統(tǒng)計(jì)。

　　補(bǔ)充

　　關(guān)于null，HashMap和LinkedHashMap是隨意的，TreeMap沒有設(shè)置Comparator時(shí)key不能為null；ConcurrentHashMap在JDK7里value不能為null(這是為什么呢？)，JDK8里key與value都不能為null；ConcurrentSkipListMap是所有JDK里key與value都不能為null。

　Set

　　Set幾乎都是內(nèi)部用一個(gè)Map來實(shí)現(xiàn), 因?yàn)镸ap里的KeySet就是一個(gè)Set，而value是假值，全部使用同一個(gè)Object。Set的特征也繼承了那些內(nèi)部Map實(shí)現(xiàn)的特征。

　　HashSet：內(nèi)部是HashMap。

　　LinkedHashSet：內(nèi)部是LinkedHashMap。

　　TreeSet：內(nèi)部是TreeMap的SortedSet。

　　ConcurrentSkipListSet：內(nèi)部是ConcurrentSkipListMap的并發(fā)優(yōu)化的SortedSet。

　　CopyOnWriteArraySet：內(nèi)部是CopyOnWriteArrayList的并發(fā)優(yōu)化的Set，利用其addIfAbsent()方法實(shí)現(xiàn)元素去重，如前所述該方法的性能很一般。

　　補(bǔ)充：好像少了個(gè)ConcurrentHashSet，本來也該有一個(gè)內(nèi)部用ConcurrentHashMap的簡單實(shí)現(xiàn)，但JDK偏偏沒提供。Jetty就自己封了一個(gè)，Guava則直接用java.util.Collections.newSetFromMap(new ConcurrentHashMap()) 實(shí)現(xiàn)。

　Queue

　　Queue是在兩端出入的List，所以也可以用數(shù)組或鏈表來實(shí)現(xiàn)。

　　--普通隊(duì)列--

　　LinkedList

　　是的，以雙向鏈表實(shí)現(xiàn)的LinkedList既是List，也是Queue。它是唯一一個(gè)允許放入null的Queue。

　　ArrayDeque

　　以循環(huán)數(shù)組實(shí)現(xiàn)的雙向Queue。大小是2的倍數(shù)，默認(rèn)是16。

　　普通數(shù)組只能快速在末尾添加元素，為了支持FIFO，從數(shù)組頭快速取出元素，就需要使用循環(huán)數(shù)組：有隊(duì)頭隊(duì)尾兩個(gè)下標(biāo)：彈出元素時(shí)，隊(duì)頭下標(biāo)遞增；加入元素時(shí)，如果已到數(shù)組空間的末尾，則將元素循環(huán)賦值到數(shù)組[0](如果此時(shí)隊(duì)頭下標(biāo)大于0，說明隊(duì)頭彈出過元素，有空位)，同時(shí)隊(duì)尾下標(biāo)指向0，再插入下一個(gè)元素則賦值到數(shù)組[1]，隊(duì)尾下標(biāo)指向1。如果隊(duì)尾的下標(biāo)追上隊(duì)頭，說明數(shù)組所有空間已用完，進(jìn)行雙倍的數(shù)組擴(kuò)容。

　　PriorityQueue

　　用二叉堆實(shí)現(xiàn)的優(yōu)先級隊(duì)列，詳見入門教程，不再是FIFO而是按元素實(shí)現(xiàn)的Comparable接口或傳入Comparator的比較結(jié)果來出隊(duì)，數(shù)值越小，優(yōu)先級越高，越先出隊(duì)。但是注意其iterator()的返回不會(huì)排序。

　　--線程安全的隊(duì)列--

　　ConcurrentLinkedQueue/ConcurrentLinkedDeque

　　無有暗香盈袖界的并發(fā)優(yōu)化的Queue，基于鏈表，實(shí)現(xiàn)了依賴于CAS的無鎖算法。

　　ConcurrentLinkedQueue的結(jié)構(gòu)是單向鏈表和head/tail兩個(gè)指針，因?yàn)槿腙?duì)時(shí)需要修改隊(duì)尾元素的next指針，以及修改tail指向新入隊(duì)的元素兩個(gè)CAS動(dòng)作無法原子，所以需要的特殊的算法，篇幅所限見入門教程。

　　PriorityBlockingQueue

　　無有暗香盈袖界的并發(fā)優(yōu)化的PriorityQueue，也是基于二叉堆。使用一把公共的讀寫鎖。雖然實(shí)現(xiàn)了BlockingQueue接口，其實(shí)沒有任何阻塞隊(duì)列的特征，空間不夠時(shí)會(huì)自動(dòng)擴(kuò)容。

　　DelayQueue

　　內(nèi)部包含一個(gè)PriorityQueue，同樣是無有暗香盈袖界的。元素需實(shí)現(xiàn)Delayed接口，每次調(diào)用時(shí)需返回當(dāng)前離觸發(fā)時(shí)間還有多久，小于0表示該觸發(fā)了。
pull()時(shí)會(huì)用peek()查看隊(duì)頭的元素，檢查是否到達(dá)觸發(fā)時(shí)間。ScheduledThreadPoolExecutor用了類似的結(jié)構(gòu)。

　　--線程安全的阻塞隊(duì)列--

　　BlockingQueue的隊(duì)列長度受限，用以保證生產(chǎn)者與消費(fèi)者的速度不會(huì)相差太遠(yuǎn)，避免內(nèi)存耗盡。隊(duì)列長度設(shè)定后不可改變。當(dāng)入隊(duì)時(shí)隊(duì)列已滿，或出隊(duì)時(shí)隊(duì)列已空，不同函數(shù)的效果見下表：

	可能報(bào)異常	返回布爾值	可能阻塞等待	可設(shè)定等待時(shí)間
入隊(duì)	add(e)	offer(e)	put(e)	offer(e, timeout, unit)
出隊(duì)	remove()	poll()	take()	poll(timeout, unit)
查看	element()	peek()	無	無

　　ArrayBlockingQueue

　　定長的并發(fā)優(yōu)化的BlockingQueue，基于循環(huán)數(shù)組實(shí)現(xiàn)。有一把公共的讀寫鎖與notFull、notEmpty兩個(gè)Condition管理隊(duì)列滿或空時(shí)的阻塞狀態(tài)。

　　LinkedBlockingQueue/LinkedBlockingDeque

　　可選定長的并發(fā)優(yōu)化的BlockingQueue，基于鏈表實(shí)現(xiàn)，所以可以把長度設(shè)為Integer.MAX_VALUE。利用鏈表的特征，分離了takeLock與putLock兩把鎖，繼續(xù)用notEmpty、notFull管理隊(duì)列滿或空時(shí)的阻塞狀態(tài)。

　　補(bǔ)充

　　JDK7有個(gè)LinkedTransferQueue，transfer(e)方法保證Producer放入的元素，被Consumer取走了再返回，比SynchronousQueue更好，有空要學(xué)習(xí)下。

標(biāo)簽： isp 安全 代碼

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。