java集合的小抄 Java初學者必備

　在盡可能短的篇幅裡，將所有集合與並發集合的特徵，實現方式，性能捋一遍。適合所有"精通Java"其實還不那麼自信的人閱讀。

　List

　　ArrayList

　　以數組實作。節約空間，但數組有容量限制。超出限制時會增加50%容量，用System.arraycopy()複製到新的數組，因此最好能給出數組大小的預估值。預設第一次插入元素時建立大小為10的陣列。

　　按數組下標存取元素--get(i)/set(i,e) 的效能很高，這是數組的基本優勢。

　　直接在陣列結尾加入元素--add(e)的效能也高，但如果按下標插入、刪除元素--add(i,e), remove(i), remove(e)，則要用System.arraycopy()來移動部分受影響的元素，效能就變差了，這是基本劣勢。

　　LinkedList

　　以雙向鍊錶實作。鍊錶無容量限制，但雙向鍊錶本身使用了更多空間，也需要額外的鍊錶指標操作。

　　按下標訪問元素--get(i)/set(i,e) 要悲劇的遍歷鍊錶將指針移動到位(如果i>數組大小的一半，會從末尾移起)。

　　插入、刪除元素時修改前後節點的指標即可，但還是要遍歷部分鍊錶的指標才能移動到下標所指的位置，只有在鍊錶兩頭的操作--add(), addFirst(),removeLast ()或用iterator()上的remove()能省掉指標的移動。

　　CopyOnWriteArrayList

　　並發優化的ArrayList。用CopyOnWrite策略，在修改時先複製一個快照來修改，改完再讓內部指標指向新陣列。

　　因為對快照的修改對讀取操作來說不可見，所以只有寫鎖沒有讀鎖，加上複製的昂貴成本，典型的適合讀多寫少的場景。如果更新頻率較高，或數組較大時，還是Collections.synchronizedList(list)，對所有操作用同一把鎖來確保線程安全更好。

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

　　補充

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

　　沒有按元素值排序的SortedList，在線程安全類別中也沒有無鎖定演算法的ConcurrentLinkedList，湊合著用Set與Queue中的等價類別時，會缺少一些List特有的方法。

Map

　　HashMap

　　以Entry[]陣列實現的雜湊桶數組，以Key的雜湊值取模桶數組的大小可得到數組下標。

　　插入元素時，如果兩條Key落在同一個桶(比如哈希值1和17取模16後都屬於第一個哈希桶)，Entry用一個next屬性實現多個Entry以單向鍊錶存放，後入桶的Entry將next指向桶目前的Entry。

　　查找哈希值為17的key時，先定位到第一個哈希桶，然後以鍊錶遍歷桶裡所有元素，逐個比較其key值。

　　當Entry數量達到桶數量的75%時(很多文章說使用的桶數量達到了75%，但看代碼不是)，會成倍擴容桶數組，並重新分配所有原來的Entry，所以這裡也最好有個預估值。

　　取模用位運算(hash & (arrayLength-1))會比較快，所以數組的大小永遠是2的N次方， 你隨便給一個初始值比如17會轉為32。預設第一次放入元素時的初始值是16。

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

　　在JDK8裡，新增預設為8的閥值，當一個桶裡的Entry超過閥值，就不以單向鍊錶而以紅黑樹來存放以加快Key的查找速度。

　　LinkedHashMap

　　擴充HashMap增加雙向鍊錶的實現，號稱是最佔記憶體的資料結構。支援iterator()時會依照Entry的插入順序來排序(但是更新不算， 如果設定accessOrder屬性為true，則所有讀寫存取都算)。

　　實作上是在Entry上再增加屬性before/after指針，插入時把自己加到Header Entry的前面去。如果所有讀寫存取都要排序，也要把前後Entry的before/after拼接起來以在鍊錶中刪除掉自己。

　　TreeMap

　　以紅黑樹實現，篇幅所限詳見入門教學。支援iterator()時依Key值排序，可依實作了Comparable介面的Key的升序排序，或由傳入的Comparator控制。可想的，在樹上插入/刪除元素的代價一定比HashMap的大。

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

　　ConcurrentHashMap

　　並發優化的HashMap，預設16把寫鎖(可以設定更多)，有效分散了阻塞的機率，而且沒有讀鎖。

　　資料結構為Segment[]，Segment裡面才是哈希桶數組，每個Segment一把鎖。 Key先算出它在哪個Segment裡，再算出它在哪個哈希桶裡。

　　支援ConcurrentMap接口，如putIfAbsent(key，value)與相反的replace(key，value)與以及實現CAS的replace(key, oldValue, newValue)。

　　沒有讀鎖是因為put/remove動作是個原子動作(比如put是一個對數組元素/Entry 指針的賦值操作)，讀取操作不會看到一個更新動作的中間狀態。

　　ConcurrentSkipListMap

　　JDK6新增的並發優化的SortedMap，以SkipList實作。 SkipList是紅黑樹的簡化替代方案，是個流行的有序集合演算法，篇幅所限見入門教學。 Concurrent套件選用它是因為它支援基於CAS的無鎖演算法，而紅黑樹則沒有好的無鎖演算法。

　　很特殊的，它的size()不能隨便調，會遍歷來統計。

　　補充

　　關於null，HashMap和LinkedHashMap是隨意的，TreeMap沒有設定Comparator時key不能為null；ConcurrentHashMap在JDK7裡value不能為null(這是為什麼不能為null ；ConcurrentSkipListMap是所有JDK裡key與value都不能為null。

Set

　　Set幾乎都是內部用一個Map來實現, 因為Map裡的KeySet就是一個Set，而value是假值，全部使用同一個Object。 Set的特徵也繼承了那些內部Map實作的特徵。

　　HashSet：內部是HashMap。

　　LinkedHashSet：內部是LinkedHashMap。

　　TreeSet：內部是TreeMap的SortedSet。

　　ConcurrentSkipListSet：內部是ConcurrentSkipListMap的同時最佳化的SortedSet。

　　CopyOnWriteArraySet：內部是CopyOnWriteArrayList的並發優化的Set，利用其addIfAbsent()方法實現元素去重，如前所述該方法的性能很一般。

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

Queue

　　Queue是在兩端出入的List，所以也可以用陣列或鍊錶來實現。

　　--普通隊列--

　　LinkedList

　　是的，以雙向鍊錶實現的LinkedList既是List，也是Queue。它是唯一允許放入null的Queue。

　　ArrayDeque

　　以循環數組實現的雙向Queue。大小是2的倍數，預設是16。

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

　　PriorityQueue

　　用二叉堆實現的優先權隊列，詳見入門教程，不再是FIFO而是按元素實現的Comparable接口或傳入Comparator的比較結果來出隊，數值越小，優先級越高，越先出隊。但是注意其iterator()的回傳不會排序。

　　--線程安全的隊列--

　　ConcurrentLinkedQueue/ConcurrentLinkedDeque

　　無界的並發優化的Queue，基於鍊錶，實現了依賴於CAS的無鎖演算法。

　　ConcurrentLinkedQueue的結構是單向鍊錶和head/tail兩個指針，因為入隊時需要修改隊尾元素的next指針，以及修改tail指向新入隊的元素兩個CAS動作無法原子，所以需要的特殊的算法，篇幅所限見入門教學。

　　PriorityBlockingQueue

　　無界的並發優化的PriorityQueue，也是基於二叉堆。使用一把公共的讀寫鎖。雖然實作了BlockingQueue接口，其實沒有任何阻塞佇列的特徵，空間不夠時會自動擴容。

　　DelayQueue

　　內部包含一個PriorityQueue，同樣是無界的。元素需實現Delayed接口，每次調用時需返回當前離觸發時間還有多久，小於0表示該觸發了。
pull()時會用peek()查看隊頭的元素，檢查是否到達觸發時間。 ScheduledThreadPoolExecutor用了類似的結構。

　　--線程安全的阻塞隊列--

　　BlockingQueue的隊列長度受限，用以確保生產者與消費者的速度不會相差太遠，避免記憶體耗盡。隊列長度設定後不可改變。當入隊時隊列已滿，或出隊時隊列已空，不同函數的效果見下表：

可能報異常   返回布爾值   可能阻塞等待   可設定等待時間   

入隊 e)    put(e)    offer(e, timeout, unit)    

出隊   remove()    poll()    遠peek()    無   無   

　　ArrayBlockingQueue

　　定長的並發優化的BlockingQueue，基於循環數組實作。有一把公共的讀寫鎖與notFull、notEmpty兩個Condition管理佇列滿或空時的阻塞狀態。

　　LinkedBlockingQueue/LinkedBlockingDeque

　　可選定長的並發優化的BlockingQueue，基於鍊錶實現，所以可以把長度設為Integer.MAX_VALUE。利用鍊錶的特徵，分離了takeLock與putLock兩把鎖，繼續用notEmpty、notFull管理佇列滿或空時的阻塞狀態。

　　補充

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