Java各個集合（Collection）的特性和用途

這篇文章總結(jié)了所有的Java集合（Collection）。主要介紹各個集合的特性和用途，以及在不同的集合類型之間轉(zhuǎn)換的方式。

Arrays

Array是Java特有的數(shù)組。在你知道所要處理數(shù)據(jù)元素個數(shù)的情況下非常好用。java.util.Arrays 包含了許多處理數(shù)據(jù)的實用方法：

• Arrays.asList：可以從 Array 轉(zhuǎn)換成 List。可以作為其他集合類型構(gòu)造器的參數(shù)。
• Arrays.binarySearch：在一個已排序的或者其中一段中快速查找。
• Arrays.copyOf：如果你想擴大數(shù)組容量又不想改變它的內(nèi)容的時候可以使用這個方法。
• Arrays.copyOfRange：可以復(fù)制整個數(shù)組或其中的一部分。
• Arrays.deepEquals、Arrays.deepHashCode：Arrays.equals/hashCode的高級版本，支持子數(shù)組的操作。
• Arrays.equals：如果你想要比較兩個數(shù)組是否相等，應(yīng)該調(diào)用這個方法而不是數(shù)組對象中的 equals方法（數(shù)組對象中沒有重寫equals()方法，所以這個方法之比較引用而不比較內(nèi)容）。這個方法集合了Java 5的自動裝箱和無參變量的特性，來實現(xiàn)將一個變量快速地傳給 equals() 方法——所以這個方法在比較了對象的類型之后是直接傳值進去比較的。
• Arrays.fill：用一個給定的值填充整個數(shù)組或其中的一部分。
• Arrays.hashCode：用來根據(jù)數(shù)組的內(nèi)容計算其哈希值（數(shù)組對象的hashCode()不可用）。這個方法集合了Java 5的自動裝箱和無參變量的特性，來實現(xiàn)將一個變量快速地傳給 Arrays.hashcode方法——只是傳值進去，不是對象。
• Arrays.sort：對整個數(shù)組或者數(shù)組的一部分進行排序。也可以使用此方法用給定的比較器對對象數(shù)組進行排序。
• Arrays.toString：打印數(shù)組的內(nèi)容。

如果想要復(fù)制整個數(shù)組或其中一部分到另一個數(shù)組，可以調(diào)用 System.arraycopy方法。此方法從源數(shù)組中指定的位置復(fù)制指定個數(shù)的元素到目標(biāo)數(shù)組里。這無疑是一個簡便的方法。（有時候用 ByteBuffer bulk復(fù)制會更快。可以參考這篇文章）.

最后，所有的集合都可以用T[] Collection.toArray( T[] a ) 這個方法復(fù)制到數(shù)組中。通常會用這樣的方式調(diào)用：

return coll.toArray( new T[ coll.size() ] );

這個方法會分配足夠大的數(shù)組來儲存所有的集合，這樣 toArray 在返回值時就不必再分配空間了。

單線程集合

這一部分介紹的是不支持多線程的集合。這些集合都在java.util包里。其中一些在Java 1.o的時候就有了（現(xiàn)在已經(jīng)棄用），其中大多數(shù)在Java 1.4中重新發(fā)布。枚舉集合在Java 1.5中重新發(fā)布，并且從這個版本之后所有的集合都支持泛型。PriorityQueue也在Java 1.5中加入。非線程安全的集合架構(gòu)的最后一個版本是ArrayDeque ，也在Java 1.6中重新發(fā)布了。

List

• ArrayList：最有用的List集合實現(xiàn)。由一個整形數(shù)字或數(shù)組存儲了集合的大�。〝�(shù)組中第一個沒有使用的元素）。像所有的List集合一樣，ArrayList可以在必要的時候擴展它的大小。ArrayList訪問元素的時間開銷固定。在尾部添加元素成本低（為常數(shù)復(fù)雜度），而在頭部添加元素成本很高（線性復(fù)雜度）。這是由ArrayList的實現(xiàn)原理——所有的元素的從角標(biāo)為0開始一個接著一個排列造成的。也就是說，從要插入的元素位置往后，每個元素都要向后移動一個位置。CPU緩存友好的集合是基于數(shù)組的。（其實也不是很友好，因為有時數(shù)組會包含對象，這樣存儲的只是指向?qū)嶋H對象的指針）。
• LinkedList：Deque實現(xiàn)：每一個節(jié)點都保存著上一個節(jié)點和下一個節(jié)點的指針。這就意味著數(shù)據(jù)的存取和更新具有線性復(fù)雜度（這也是一個最佳化的實現(xiàn)，每次操作都不會遍歷數(shù)組一半以上，操作成本最高的元素就是數(shù)組中間的那個）。如果想寫出高效的LinkedList代碼可以使用 ListIterators 。如果你想用一個Queue/Deque實現(xiàn)的話（你只需讀取第一個和最后一個元素就行了）——考慮用ArrayDeque代替。
• Vector：一個帶有線程同步方法的ArrayList版本。現(xiàn)在直接用ArrayList代替了。

Queues/deques

• ArrayDeque：Deque是基于有首尾指針的數(shù)組（環(huán)形緩沖區(qū)）實現(xiàn)的。和LinkedList不同，這個類沒有實現(xiàn)List接口。因此，如果沒有首尾元素的話就不能取出任何元素。這個類比LinkedList要好一些，因為它產(chǎn)生的垃圾數(shù)量較少（在擴展的時候舊的數(shù)組會被丟棄）。
• Stack：一種后進先出的隊列。不要在生產(chǎn)代碼中使用，使用別的Deque來代替（ArrayDeque比較好）。
• PriorityQueue：一個基于優(yōu)先級的隊列。使用自然順序或者制定的比較器來排序。他的主要屬性——poll/peek/remove/element會返回一個隊列的最小值。不僅如此，PriorityQueue還實現(xiàn)了Iterable接口，隊列迭代時不進行排序（或者其他順序）。在需要排序的集合中，使用這個隊列會比TreeSet等其他隊列要方便。

Maps

• HashMap：最常用的Map實現(xiàn)。只是將一個鍵和值相對應(yīng)，并沒有其他的功能。對于復(fù)雜的hashCode method，get/put方法有固定的復(fù)雜度。
• EnumMap：枚舉類型作為鍵值的Map。因為鍵的數(shù)量相對固定，所以在內(nèi)部用一個數(shù)組儲存對應(yīng)值。通常來說，效率要高于HashMap。
• HashTable：舊HashMap的同步版本，新的代碼中也使用了HashMap。
• IdentityHashMap：這是一個特殊的Map版本，它違背了一般Map的規(guī)則：它使用 “==” 來比較引用而不是調(diào)用Object.equals來判斷相等。這個特性使得此集合在遍歷圖表的算法中非常實用——可以方便地在IdentityHashMap中存儲處理過的節(jié)點以及相關(guān)的數(shù)據(jù)。
• LinkedHashMap ：HashMap和LinkedList的結(jié)合，所有元素的插入順序存儲在LinkedList中。這就是為什么迭代LinkedHashMap的條目（entry）、鍵和值的時候總是遵循插入的順序。在JDK中，這是每元素消耗內(nèi)存最大的集合。
• TreeMap：一種基于已排序且?guī)��?dǎo)向信息Map的紅黑樹。每次插入都會按照自然順序或者給定的比較器排序。這個Map需要實現(xiàn)equals方法和Comparable/Comparator。compareTo需要前后一致。這個類實現(xiàn)了一個NavigableMap接口：可以帶有與鍵數(shù)量不同的入口，可以得到鍵的上一個或者下一個入口，可以得到另一Map某一范圍的鍵（大致和SQL的BETWEEN運算符相同），以及其他的一些方法。
• WeakHashMap：這種Map通常用在數(shù)據(jù)緩存中。它將鍵存儲在WeakReference中，就是說，如果沒有強引用指向鍵對象的話，這些鍵就可以被垃圾回收線程回收。值被保存在強引用中。因此，你要確保沒有引用從值指向鍵或者將值也保存在弱引用中m.put(key, new WeakReference(value))。

Sets

• HashSet：一個基于HashMap的Set實現(xiàn)。其中，所有的值為“假值”（同一個Object對象具備和HashMap同樣的性能�；�于這個特性，這個數(shù)據(jù)結(jié)構(gòu)會消耗更多不必要的內(nèi)存。
• EnumSet：值為枚舉類型的Set。Java的每一個enum都映射成一個不同的int。這就允許使用BitSet——一個類似的集合結(jié)構(gòu)，其中每一比特都映射成不同的enum。EnumSet有兩種實現(xiàn)，RegularEnumSet——由一個單獨的long存儲（能夠存儲64個枚舉值，99.9%的情況下是夠用的），JumboEnumSet——由long[]存儲。
• BitSet：一個比特Set。需要時常考慮用BitSet處理一組密集的整數(shù)Set（比如從一個預(yù)先知道的數(shù)字開始的id集合）。這個類用 long[]來存儲bit。
• LinkedHashMap：與HashSet一樣，這個類基于LinkedHashMap實現(xiàn)。這是唯一一個保持了插入順序的Set。
• TreeSet：與HashSet類似。這個類是基于一個TreeMap實例的。這是在單線程部分唯一一個排序的Set。

java.util.Collections

就像有專門的java.util.Arrays來處理數(shù)組，Java中對集合也有java.util.Collections來處理。

第一組方法主要返回集合的各種數(shù)據(jù)：

• Collections.checkedCollection / checkedList / checkedMap / checkedSet / checkedSortedMap / checkedSortedSet：檢查要添加的元素的類型并返回結(jié)果。任何嘗試添加非法類型的變量都會拋出一個ClassCastException異常。這個功能可以防止在運行的時候出錯。//fixme
• Collections.emptyList / emptyMap / emptySet ：返回一個固定的空集合，不能添加任何元素。
• Collections.singleton / singletonList / singletonMap：返回一個只有一個入口的 set/list/map 集合。
• Collections.synchronizedCollection / synchronizedList / synchronizedMap / synchronizedSet / synchronizedSortedMap / synchronizedSortedSet：獲得集合的線程安全版本（多線程操作時開銷低但不高效，而且不支持類似put或update這樣的復(fù)合操作）
• Collections.unmodifiableCollection / unmodifiableList / unmodifiableMap / unmodifiableSet / unmodifiableSortedMap / unmodifiableSortedSet：返回一個不可變的集合。當(dāng)一個不可變對象中包含集合的時候，可以使用此方法。

第二組方法中，其中有一些方法因為某些原因沒有加入到集合中：

• Collections.addAll：添加一些元素或者一個數(shù)組的內(nèi)容到集合中。
• Collections.binarySearch：和數(shù)組的Arrays.binarySearch功能相同。
• Collections.disjoint：檢查兩個集合是不是沒有相同的元素。
• Collections.fill：用一個指定的值代替集合中的所有元素。
• Collections.frequency：集合中有多少元素是和給定元素相同的。
• Collections.indexOfSubList / lastIndexOfSubList：和String.indexOf(String) / lastIndexOf(String)方法類似——找出給定的List中第一個出現(xiàn)或者最后一個出現(xiàn)的子表。
• Collections.max / min：找出基于自然順序或者比較器排序的集合中，最大的或者最小的元素。
• Collections.replaceAll：將集合中的某一元素替換成另一個元素。
• Collections.reverse：顛倒排列元素在集合中的順序。如果你要在排序之后使用這個方法的話，在列表排序時，最好使用Collections.reverseOrder比較器。
• Collections.rotate：根據(jù)給定的距離旋轉(zhuǎn)元素。
• Collections.shuffle：隨機排放List集合中的節(jié)點，可以給定你自己的生成器——例如 java.util.Random / java.util.ThreadLocalRandom or java.security.SecureRandom。
• Collections.sort：將集合按照自然順序或者給定的順序排序。
• Collections.swap：交換集合中兩個元素的位置（多數(shù)開發(fā)者都是自己實現(xiàn)這個操作的）。

并發(fā)集合

這一部分將介紹java.util.concurrent包中線程安全的集合。這些集合的主要屬性是一個不可分割的必須執(zhí)行的方法。因為并發(fā)的操作，例如add或update或者check再update，都有一次以上的調(diào)用，必須同步。因為第一步從集合中組合操作查詢到的信息在開始第二步操作時可能變?yōu)闊o效數(shù)據(jù)。

多數(shù)的并發(fā)集合是在Java 1.5引入的。ConcurrentSkipListMap / ConcurrentSkipListSet 和 LinkedBlockingDeque是在Java 1.6新加入的。Java 1.7加入了最后的 ConcurrentLinkedDeque 和 LinkedTransferQueue

Lists

• CopyOnWriteArrayList：list的實現(xiàn)每一次更新都會產(chǎn)生一個新的隱含數(shù)組副本，所以這個操作成本很高。通常用在遍歷操作比更新操作多的集合，比如listeners/observers集合。

Queues/deques

• ArrayBlockingQueue：基于數(shù)組實現(xiàn)的一個有界阻塞隊，大小不能重新定義。所以當(dāng)你試圖向一個滿的隊列添加元素的時候，就會受到阻塞，直到另一個方法從隊列中取出元素。
• ConcurrentLinkedDeque / ConcurrentLinkedQueue：基于鏈表實現(xiàn)的無界隊列，添加元素不會堵塞。但是這就要求這個集合的消費者工作速度至少要和生產(chǎn)這一樣快，不然內(nèi)存就會耗盡。嚴(yán)重依賴于CAS(compare-and-set)操作。
• DelayQueue：無界的保存Delayed元素的集合。元素只有在延時已經(jīng)過期的時候才能被取出。隊列的第一個元素延期最�。ò�含負(fù)值——延時已經(jīng)過期）。當(dāng)你要實現(xiàn)一個延期任務(wù)的隊列的時候使用（不要自己手動實現(xiàn)——使用ScheduledThreadPoolExecutor）。
• LinkedBlockingDeque / LinkedBlockingQueue：可選擇有界或者無界基于鏈表的實現(xiàn)。在隊列為空或者滿的情況下使用ReentrantLock-s。
• LinkedTransferQueue：基于鏈表的無界隊列。除了通常的隊列操作，它還有一系列的transfer方法，可以讓生產(chǎn)者直接給等待的消費者傳遞信息，這樣就不用將元素存儲到隊列中了。這是一個基于CAS操作的無鎖集合。
• PriorityBlockingQueue：PriorityQueue的無界的版本。
• SynchronousQueue：一個有界隊列，其中沒有任何內(nèi)存容量。這就意味著任何插入操作必須等到響應(yīng)的取出操作才能執(zhí)行，反之亦反。如果不需要Queue接口的話，通過Exchanger類也能完成響應(yīng)的功能。

Maps

• ConcurrentHashMap：get操作全并發(fā)訪問，put操作可配置并發(fā)操作的哈希表。并發(fā)的級別可以通過構(gòu)造函數(shù)中concurrencyLevel參數(shù)設(shè)置（默認(rèn)級別16）。該參數(shù)會在Map內(nèi)部劃分一些分區(qū)。在put操作的時候只有只有更新的分區(qū)是鎖住的。這種Map不是代替HashMap的線程安全版本——任何 get-then-put的操作都需要在外部進行同步。
• ConcurrentSkipListMap：基于跳躍列表（Skip List）的ConcurrentNavigableMap實現(xiàn)。本質(zhì)上這種集合可以當(dāng)做一種TreeMap的線程安全版本來使用。

Sets

• ConcurrentSkipListSet：使用 ConcurrentSkipListMap來存儲的線程安全的Set。
• CopyOnWriteArraySet：使用CopyOnWriteArrayList來存儲的線程安全的Set。

相關(guān)閱讀

• Java 基本類型集合庫：Trove：Trove庫概述——存儲Java基本類型數(shù)據(jù)的集合庫（與大多數(shù)JDK中的Objects類不同）。
• Java常見數(shù)據(jù)類型內(nèi)存占用（1）：各種類的內(nèi)存占用會所名，包括enums、EnumMap、EnumSet、BitSet、ArrayList、LinkedList和ArrayDeque。
• Java常見數(shù)據(jù)類型內(nèi)存占用（2）：HashMap、HashSet、LinkedHashMap、LinkedHashSet、TreeMap、TreeSet和JDK 7 PriorityQueue內(nèi)存占用，以及對應(yīng)的Trove替代類說明。

推薦閱讀

如果想要了解更多關(guān)于Java集合的知識，推薦閱讀以下書籍：

• Cay S. Horstmann. Core Java Volume I–Fundamentals (9th Edition) (Core Series) ：第13章描述了Java集合.
• Naftalin, Wadler. Java Generics and Collections：書的第2部分（第10章至第17章）專門討論了Java集合。
• Goetz, Peierls, Bloch, Bowbeer, Holmes, Lea. Java Concurrency in Practice：最好的Java并發(fā)書籍。第5章討論了Java 1.5引入的并發(fā)集合。

總結(jié)