關于Java集合的小抄

在盡可能短的篇幅里，將所有List、Map、Set、Queue的特征與實現方式捋一遍。適合所有"精通Java"其實還不那么自信的人閱讀。

List

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

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

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

按下標訪問元素--get(i)/set(i,e) 要悲劇的遍歷鏈表將指針移動到位(如果i > size/2)會從末尾移起。
在任何地方插入、刪除元素時修改前后節點的指針即可，但還是要遍歷部分鏈表的指針才能移動到下標所指的位置，只有在鏈表兩頭的操作--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%時，會成倍擴容桶數組，并重新分配所有原來的Entry，所以這里也需要一個合理的預估值。

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

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

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

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 指針的賦值操作；remove是一個對 entry.next 的賦值操作，rehash是一個對數組引用的賦值操作)，因此read不會看到一個更新動作的中間狀態。

ConcurrentSkipListMap
JDK6新增的并發優化的SortedMap，以SkipList實現。SkipList是紅黑樹的一種簡化替代方案，是個很流行的有序集合算法，見入門教程。Concurrent包中選用它是因為它支持無鎖算法，而紅黑樹則沒有好的無鎖算法。

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

Set

Set幾乎都是內部用一個Map來實現, 因為Map里的KeySet就是一個Set，而value全部使用同一個Object。

HashSet：內部是HashMap。
LinkedHashSet：內部是LinkedHashMap。
TreeSet：內部是TreeMap。
ConcurrentSkipListSet：內部用ConcurrentSkipListMap的并發優化的SortedSet。

CopyOnWriteArraySet：內部用CopyOnWriteArrayList 實現的并發優化的Set，利用其addIfAbsent()方法實現元素去重，如前所述該方法的性能很一般，同時繼承CopyOnWriteArrayList的其他優缺點。

補充：好像少了個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
不限長的并發優化的Queue，基于鏈表，也是很棒的實現了無鎖算法，見入門教程，由head與tail兩個變量管理鏈表的兩端。

PriorityBlockingQueue
不限長的并發優化的PriorityQueue，也是基于二分堆。使用一把公共的讀寫鎖。雖然實現了BlockingQueue接口，其實沒有任何阻塞隊列的特征，空間不夠時會自動擴容。

DelayQueue
內部包含一個PriorityQueue，元素需實現Delayed接口，每次調用時需返回當前離觸發時間還有多久，小于0表示已到點。
pull()時會用peek()查看隊頭的元素，檢查其是否到達觸發時間。Java的定時任務Scheduler用了類似的結構。

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

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

LinkedBlockingQueue
可選定長的并發優化的BlockingQueue，基于鏈表實現，將capacity設為某值，也可以設為Integer.MAX_VALUE，有takeLock，putLock兩把鎖及notFull，notEmpty兩個Condition精細復雜的管理阻塞狀態。

ArrayBlockingQueue
定長的并發優化的BlockingQueue，基于循環數組實現。也由一把公共讀寫鎖與notFull，notEmpty兩個Condition管理阻塞狀態。

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