摘要：單線程集合本部分將重點介紹非線程安全集合。非線程安全集合框架的最新成員是自起推出的。這是標準的單線程陣營中唯一的有序集合。該功能能有效防止運行時造型。檢查個集合之間不存在共同的元素?；谧匀慌判蚧蛘页黾现械淖畲蠡蜃钚≡亍?/p>

【編者按】本文作者為擁有十年金融軟件開發經驗的 Mikhail Vorontsov，文章主要概覽了所有標準 Java 集合類型。文章系國內 ITOM 管理平臺 OneAPM 編譯呈現，以下為正文：

本文將概覽所有標準的 Java 集合類型。我們將按照它們可區分的屬性與主要用例進行分類。除此之外，我們還將窮舉在不同集合類型之間進行數據轉換的方法。

數組是 Java 語言內置的唯一集合類型，尤其擅長處理預先知道數量上限的元素集。java.util.Arrays 包含了許多用于處理數組的方法，列舉如下：

Arrays.asList ——將 array(數組) 轉變為 List(列表)，后者可以傳值給其他標準的集合構造函數。

Arrays.binarySearch ——對有序數組或其分段進行快速查找。

Arrays.copyOf ——如果想在擴展數組的同時保存其內容，可調用該方法。

Arrays.copyOfRange ——如果需要拷貝整個數組或其分段，可調用該方法。

Arrays.deepEquals, Arrays.deepHashCode ——支持嵌套子數組的 Arrays.equals 或 Arrays.hashCode 版本。

Arrays.equals ——如果需要比較兩個數組是否相等，可調用此方法（不可調用數組自身的 equals 方法，array.equals 方法未被重寫，因此只會比較對數組的引用，而非其內容。）此方法可以與 Java 5 中的 boxing(裝箱)與 varargs(可變參數)特性并用，以編寫類 equals 方法的簡單實現——在比較對象類型之后，將所有類字段都傳給 Arrays.equals 即可。

Arrays.fill ——將整個數組或其分段賦值為給定的值。

Arrays.hashCode ——計算數組內容的 hashcode 值（數組自身的 hashcode 方法無法實現此功能。）此方法可以與 Java 5 中的 boxing(裝箱)與 varargs(可變參數)特性并用，以編寫類 hashcode 方法的簡單實現——將所有類字段都傳給 Arrays.hashcode 即可。

Arrays.sort ——根據自然排序(natural ordering)規則，對整個數組或其分段進行排序。若要利用已知的 Comparator 對 Object[] 進行排序，也有一對 Arrays.sort 方法。

Arrays.toString ——打印數組的具體內容。

如果需要將部分數組（或整個數組）拷貝到另一個已有數組，你需要調用 System.arraycopy 方法，后者會將源數組中指定位置的給定數量的元素拷貝到目的數組的指定位置。通常，這是在 Java 中拷貝數組內容的最快方式（不過，在某些情況下，你也可以檢查一下 ByteBuffer 批量拷貝的速度是否更快）。

最后，還有一點，任何 Collection(集合) 都可以使用 T[] Collection.toArray( T[] a ) 方法拷貝到數組中。此方法調用的常見模式如下：

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

此方法調用會分配足夠大的數組以存儲整個集合，因此 toArray 不必要分配很大的數組用于返回。

本部分將重點介紹非線程安全][6集合。這些集合全都存儲于 java.util 包中。其中一些集合類型從 Java 1.0 開始就有了，現在已經不再建議使用(deprecated)，但大多數集合類型從 Java 1.4 開始啟用。枚舉集合(Enum collections)自 Java 1.5 開始出現，同時具備所有集合類的泛型支持。PriorityQueue 也是從 Java 1.5 開始啟用的。非線程安全集合框架的最新成員是自 Java 1.6 起推出的 ArrayDeque。

ArrayList ——用處最大的 List 實現。包含一個數組與一個 int 類型，后者代表了數組中首個未使用元素所在的位置。與其他 List 一樣，ArrayList 可以在需要的時候進行擴展。此外，元素讀取時間固定，在列表尾部更新時成本很?。◤碗s度是固定的），而在頭部更新時成本很高（復雜度是線性增長的），這是因為 ArrayList 不變量——所有元素在底層數組中從索引(index)為0處開始，這意味著在插入元素時，插入位置右邊的所有元素都要往右移；在移除元素時，移除位置右邊的所有元素都要往左移。由于包含數組，該集合類型易于 CPU 緩存。（不過，也不是特別容易。因為其包含 Objects，而后者其實是指向實際對象的指針）。

LinkedList ——Deque 實現，每個 Node(結點)由一個值，以及 prev 與 next 指針構成。這意味著，元素讀取或更新的復雜度是線性增長的（得益于一些優化，這些方法遍歷的范圍不會超過列表長度的一半，因此，讀取或更新成本最高的元素位于列表的中間位置）。如果打算編寫運行更快的 LinkedList 代碼，則需要使用 ListIterators。如果想要編寫 Queue/Deque 實現(只需讀取首尾兩個元素)，請轉而使用 ArrayDeque。

Vector —— ArrayList 先前的版本，包含所有同步方法。請盡量使用 ArrayList。

ArrayDeque – Deque implementation based on the array (circular buffer) with head/tail pointers. Unlike LinkedList, this class does not implement List interface, which means that you can not access anything except the first and the last elements. This class is generally preferable to LinkedList for queues/deques due to a limited amount of garbage it generates (old array will be discarded on the extensions).

ArrayDeque ——基于數組(循環緩沖)的 Deque 實現，帶有頭/尾(head/tail)指針。與 LinkedList 不同，該類并不實現 List 接口，這意味著除了首尾元素，無法讀取其他元素。由于該類生成的垃圾較少，在實現隊列或雙隊列時，該類比 LinkedList 更加適合（老數組在擴展時會被拋棄）。

Stack ——后進先出(LIFO)隊列。不要在生產代碼中使用該類?？捎萌我?Deque 實現替代之(ArrayDeque 優先)。

PriorityQueue ——基于priority(優先級)堆的隊列。采用自然排序或已知的 Comparator。其主要屬性—— poll/peek/remove/element 方法總是返回隊列中最小的余留元素。盡管如此，該隊列實現了 Iterable，不會按照排好的次序(或任何特定次序)迭代隊列。如果只需要隊列中的最小元素，該隊列往往比 TreeSet
之類的其他排序集合更可取。

HashMap ——最常見的一種映射實現，將鍵(key)映射至對應的值(value)，僅此而已。如果想要高效率的 hashcode 方法，可以考慮 get/put 方法，它們的復雜度是固定的。

EnumMap ——帶有 enum 鍵的映射。由于已知最大鍵數量以及內置的 enum 至 int 映射，此類的運行速度往往高于 HashMap。

Hashtable —— HashMap 先前的同步化版本，在新產品的代碼中盡量用 HashMap 替代之。

IdentityHashMap —— Map 的超特殊版本，違背了 Map 的通用約定：在比較引用時使用 == 而非調用 Object.equals 方法。這一屬性使得 IdentityHashMap 在各種圖遍歷算法中大顯神通——你可以在 IdentityHashMap 中輕易地存儲已經處理過的節點，連同一些無關數據。

LinkedHashMap —— HashMap 與 LinkedList 的結合體，所有元素的插入次序都存儲在 LinkedList 中，也因此，LinkedHashMap 的條目，鍵以及值都以插入次序迭代。就每個元素的內存消耗量而已，這是成本最高的 JDK 集合類型。

TreeMap ——基于有序導航型 Map 的紅黑樹。按照自然次序或給定的鍵 Comparator 對條目進行排序。此映射類要求 equals 與 Comparable/Comparator.compareTo 的實現必須一致。此類實現了一個 NavigableMap 接口：它允許獲得少于或多于給定鍵的映射；允許獲得一個 prev/next 條目(基于鍵的排序)；允許獲得給定范圍內的鍵的映射(這與 SQL
的 BETWEEN 操作符基本對應)以及此方法的許多變體。

WeakHashMap ——此映射通常用于數據緩存的實現。它將所有鍵都保存于 WeakReference，這意味著，如果沒有指向這些鍵對象的強引用，這些鍵就會被垃圾回收。另一方面，值卻用強引用保存。因此，你需要確保不存在從值指向鍵的引用，或者將值也保存在弱引用中：m.put(key, new WeakReference(value))。

HashSet ——基于帶有虛值(每個值的 Object 均相同) HashMap 的 set 實現。與 HashMap 的屬性相同。也因為這種實現方式，此類消耗的內存比該數據類型實際需要的內存要多。

EnumSet —— enum 值的集合。在 Java 中，每個 enum 都映射至一個 int 類型：每個 enum 值映射的 int 都互不相同。這使得 BitSet 之類的集合結構成為可能，每個 bit 都映射到一個不同的 enum 值。此類還存在兩種實現——包含單個 long 類型（可存儲64個 enum 值，足夠覆蓋99.9%的用例）的 RegularEnumSet 與包含 long[] 類型的 JumboEnumSet。

BitSet —— bit 集合。請牢記，可以使用 BitSet 表示整型的稠密集(比如從已知起點開始的 id)。此類使用 long[] 類型存儲 bit。

LinkedHashSet ——與 HashSet 類似，此類基于 LinkedHashMap
類實現。這是以插入次序保存元素的唯一集合類。

TreeSet ——與 HashSet 類似，此類基于 TreeMap 實例。這是標準 JDK 的單線程陣營中唯一的有序集合。

就像針對數組的 java.util.Arrays 包一樣，java.util.Collections 包提供了許多處理集合的好方法。

本文將要介紹的第一組方法會返回集合的各種視圖：

Collections.checkedCollection / checkedList / checkedMap / checkedSet / checkedSortedMap / checkedSortedSet —— 會返回集合的視圖，在運行時檢查所添加元素的類型。如果試圖添加類型不兼容的元素，會拋出 ClassCastException 異常。該功能能有效防止運行時造型(runtime casts)。

Collections.emptyList / emptyMap / emptySet ——當你需要返回不可變的空集合，而又不想分配任何對象時，此類方法便能派上用場。

Collections.singleton / singletonList / singletonMap —— 返回帶有單個條目的不可變 set/list/map。

Collections.synchronizedCollection / synchronizedList /
synchronizedMap / synchronizedSet / synchronizedSortedMap /

synchronizedSortedSet —— 返回包含所有同步方法的集合視圖(低成本又低效率的多線程方法，仍然不支持put-or-update之類的復合動作)。

Collections.unmodifiableCollection / unmodifiableList /
unmodifiableMap / unmodifiableSet / unmodifiableSortedMap /

unmodifiableSortedSet——返回集合的不可變視圖。當需要實現包含任意集合的不可變對象時尤其有用。

本文介紹的第二組方法都因為相同的原因被排除在集合之外：

Collections.addAll ——如果要往一個集合添加一定數量的元素或一個數組的內容，調用此方法。

Collections.binarySearch —— 與 Arrays.binarySearch 對于 arrays(數組)的作用相同。

Collections.disjoint —— 檢查2個集合之間不存在共同的元素。

Collections.fill —— 用給定值替換某個列表中的所有元素。

Collections.frequency —— 給定集合中有多少元素與給定對象相等。

Collections.indexOfSubList / lastIndexOfSubList —— 這些方法與
String.indexOf(String) / lastIndexOf(String) 相似，它們會找出給定列表中給定子列表首次或末次出現的情況。

Collections.max / min —— 基于自然排序或 Comparator 找出集合中的最大或最小元素。

Collections.replaceAll —— 在給定列表中用某個元素替代另一個元素。

Collections.reverse —— 顛倒給定列表中的元素次序。如果你打算在列表排序之后立即調用此方法，不如在進行元素排序時使用 Collections.reverseOrder 比較器。

Collections.rotate —— 根據給定距離旋轉列表中的元素。

Collections.shuffle ——打亂列表的排序。注意，你可以為此方法提供自己的隨機生成器，可以是 java.util.Random，java.util.ThreadLocalRandom 或 java.security.SecureRandom。

Collections.sort —— 根據自然排序或給定的 Comparator 對列表進行排序。

Collections.swap —— 根據給定的位置交換列表中的2個元素(許多開發者都親自編寫此方法)。

本部分將介紹 java.util.concurrent 包中提供的線程安全(thread-safe)集合類型。這些集合的主要特性在于能確保其方法的原子執行(atomic execution)。不過，不要忘記，涉及多個方法調用的 “add-or-update” 或 “check-then-update” 等復合動作(compound actions)仍然應該同步。因為，在復合動作第一步中查詢到的信息在執行第二個步驟之前可能已經失效。

大多數并發集合類型從 Java 1.5 開始引入。ConcurrentSkipListMap / ConcurrentSkipListSet 以及 LinkedBlockingDeque 是在 Java 1.6 開始啟用的。在 Java 1.7 中的最近更新為 ConcurrentLinkedDeque 與 LinkedTransferQueue 的加入。

CopyOnWriteArrayList ——列表實現，針對每次更新都創建一個底層數組的新拷貝。這一操作的成本很高，因此，當遍歷的次數遠大于更新時使用此類比較合適。此集合類型的常見用例為 listeners/observers 集合。

ArrayBlockingQueue —— 包含一個數組類的有界阻塞隊列。無法調整大小，因此，當向滿的隊列添加一個元素時，該方法調用會遭到阻塞，直到另一個線程從該隊列中提取出了一個元素。

ConcurrentLinkedDeque / ConcurrentLinkedQueue ——基于鏈表(linked
list)的無界隊列/雙隊列。往該隊列中添加元素不會遭到阻塞，但是要求此類集合的使用者(consumer)必須與其產出者(producer)保持至少相同的工作效率，否則就會出現內存耗盡的情況。此類還相當依賴 CAS (compare-and-set) 操作。

DelayQueue ——由 Delayed(延遲) 元素組成的無界阻塞隊列。其元素只有在延遲過期之后才能從隊列中剔除。隊首是剩余延遲值最小(包括負值，代表延遲已經過期)的元素。當想要實現一個由延遲任務組成的隊列時(無需手動實現，使用 ScheduledThreadPoolExecutor 即可)，此隊列便能派上用場。

LinkedBlockingDeque / LinkedBlockingQueue ——基于鏈表(linked list)的可選有界(可以在創建時指定最大容量，也可以不指定)隊列/雙隊列。以 ReentrantLock-s 為空/滿條件。

LinkedTransferQueue ——基于鏈表(linked list)的無界隊列。除了普通的隊列操作，此類還擁有一組傳遞方法(transfer methods)，允許產出者直接向等待中的使用者發送消息，從而解決了在隊列中存儲元素的需求。這是一個基于 CAS 操作的無鎖(lock-free)集合類型。

PriorityBlockingQueue —— PriorityQueue 的無界阻塞隊列版。

SynchronousQueue——不帶任何內部容量的阻塞隊列。因此，任何插入請求必須等待對應的刪除請求，反之亦然。如果你不需要 Queue 接口，同樣的功能可以通過 Exchanger 實現。

ConcurrentHashMap ——對 get 操作全并發、對 put 操作可配置并發的散列表(hash table)。該并發等級可通過構造函數參數(默認為16) concurrencyLevel 進行調整，該參數定義了映射內的劃分情況。在 put 操作中只有更新后的劃分會被鎖定。請牢記，此映射類型并不是 HashMap 算法的線程安全替代品 ——任何對此映射(或其他并發集合類)的 “get-then-put” 序列方法調用都必須是外部同步的。

ConcurrentSkipListMap ——基于跳躍表(skip list)的 ConcurrentNavigableMap 實現。本質上，此集合類可以作為 TreeMap 的線程安全替代物使用。

ConcurrentSkipListSet ——采用 ConcurrentSkipListMap 類進行存儲的并發集合。

CopyOnWriteArraySet ——采用 CopyOnWriteArrayList 類進行存儲的并發集合。

原始類型集合類：Trove 庫—— 對 Trove 庫的概述，Trove 庫包含了諸多存儲著 Java 原始類型的集合類(與大多數 JDK 集合類中的 Objects 不同)。

常見 Java 數據類型的內存消耗 ——第一部分 ——介紹了 enums 以及 EnumMap / EnumSet / BitSet / ArrayList / LinkedList / ArrayDeque 等類的內存消耗情況。

常見 Java 數據類型的內存消耗 ——第二部分 ——介紹了 HashMap / HashSet, LinkedHashMap / LinkedHashSet, TreeMap / TreeSet 以及 Java 7 中 PriorityQueue JDK 類的內存消耗情況，以及它們對應的 Trove 替代物。

如果你想對 Java 集合類有更深入的了解，筆者建議你從下面的書中找一本閱讀。

Cay S. Horstmann.《Java 核心. 卷一基礎篇(第九版)》(核心系列) ——第13章主講 Java 集合類。

Naftalin, Wadler. 《Java 泛類與集合類》 ——本書的第二部分(第10到17章)主講 Java 集合類。

Goetz, Peierls, Bloch, Bowbeer, Holmes, Lea.《Java 并發實踐》——最好的 Java 并發書，第5章主講 Java 1.5 中的并發集合類。

以下是所有 JDK 集合類的簡單總結:

OneAPM 能為您提供端到端的 Java 應用性能解決方案，我們支持所有常見的 Java 框架及應用服務器，助您快速發現系統瓶頸，定位異常根本原因。分鐘級部署，即刻體驗，Java 監控從來沒有如此簡單。想閱讀更多技術文章，請訪問 OneAPM 官方技術博客。

本文轉自 OneAPM 官方博客

原文地址：http://java-performance.info/java-collections-overview/