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

【編者按】本文作者為擁有十年金融軟件開發(fā)經(jīng)驗(yàn)的 Mikhail Vorontsov，文章主要概覽了所有標(biāo)準(zhǔn) Java 集合類型。文章系國內(nèi) ITOM 管理平臺(tái) OneAPM 編譯呈現(xiàn)，以下為正文：

本文將概覽所有標(biāo)準(zhǔn)的 Java 集合類型。我們將按照它們可區(qū)分的屬性與主要用例進(jìn)行分類。除此之外，我們還將窮舉在不同集合類型之間進(jìn)行數(shù)據(jù)轉(zhuǎn)換的方法。

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

Arrays.asList ——將 array(數(shù)組) 轉(zhuǎn)變?yōu)?List(列表)，后者可以傳值給其他標(biāo)準(zhǔn)的集合構(gòu)造函數(shù)。

Arrays.binarySearch ——對有序數(shù)組或其分段進(jìn)行快速查找。

Arrays.copyOf ——如果想在擴(kuò)展數(shù)組的同時(shí)保存其內(nèi)容，可調(diào)用該方法。

Arrays.copyOfRange ——如果需要拷貝整個(gè)數(shù)組或其分段，可調(diào)用該方法。

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

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

Arrays.fill ——將整個(gè)數(shù)組或其分段賦值為給定的值。

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

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

Arrays.toString ——打印數(shù)組的具體內(nèi)容。

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

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

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

此方法調(diào)用會(huì)分配足夠大的數(shù)組以存儲(chǔ)整個(gè)集合，因此 toArray 不必要分配很大的數(shù)組用于返回。

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

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

LinkedList ——Deque 實(shí)現(xiàn)，每個(gè) Node(結(jié)點(diǎn))由一個(gè)值，以及 prev 與 next 指針構(gòu)成。這意味著，元素讀取或更新的復(fù)雜度是線性增長的（得益于一些優(yōu)化，這些方法遍歷的范圍不會(huì)超過列表長度的一半，因此，讀取或更新成本最高的元素位于列表的中間位置）。如果打算編寫運(yùn)行更快的 LinkedList 代碼，則需要使用 ListIterators。如果想要編寫 Queue/Deque 實(shí)現(xiàn)(只需讀取首尾兩個(gè)元素)，請轉(zhuǎn)而使用 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 ——基于數(shù)組(循環(huán)緩沖)的 Deque 實(shí)現(xiàn)，帶有頭/尾(head/tail)指針。與 LinkedList 不同，該類并不實(shí)現(xiàn) List 接口，這意味著除了首尾元素，無法讀取其他元素。由于該類生成的垃圾較少，在實(shí)現(xiàn)隊(duì)列或雙隊(duì)列時(shí)，該類比 LinkedList 更加適合（老數(shù)組在擴(kuò)展時(shí)會(huì)被拋棄）。

Stack ——后進(jìn)先出(LIFO)隊(duì)列。不要在生產(chǎn)代碼中使用該類?？捎萌我?Deque 實(shí)現(xiàn)替代之(ArrayDeque 優(yōu)先)。

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

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

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

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

IdentityHashMap —— Map 的超特殊版本，違背了 Map 的通用約定：在比較引用時(shí)使用 == 而非調(diào)用 Object.equals 方法。這一屬性使得 IdentityHashMap 在各種圖遍歷算法中大顯神通——你可以在 IdentityHashMap 中輕易地存儲(chǔ)已經(jīng)處理過的節(jié)點(diǎn)，連同一些無關(guān)數(shù)據(jù)。

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

TreeMap ——基于有序?qū)Ш叫?Map 的紅黑樹。按照自然次序或給定的鍵 Comparator 對條目進(jìn)行排序。此映射類要求 equals 與 Comparable/Comparator.compareTo 的實(shí)現(xiàn)必須一致。此類實(shí)現(xiàn)了一個(gè) NavigableMap 接口：它允許獲得少于或多于給定鍵的映射；允許獲得一個(gè) prev/next 條目(基于鍵的排序)；允許獲得給定范圍內(nèi)的鍵的映射(這與 SQL
的 BETWEEN 操作符基本對應(yīng))以及此方法的許多變體。

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

HashSet ——基于帶有虛值(每個(gè)值的 Object 均相同) HashMap 的 set 實(shí)現(xiàn)。與 HashMap 的屬性相同。也因?yàn)檫@種實(shí)現(xiàn)方式，此類消耗的內(nèi)存比該數(shù)據(jù)類型實(shí)際需要的內(nèi)存要多。

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

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

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

TreeSet ——與 HashSet 類似，此類基于 TreeMap 實(shí)例。這是標(biāo)準(zhǔn) JDK 的單線程陣營中唯一的有序集合。

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

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

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

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

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

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

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

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

unmodifiableSortedSet——返回集合的不可變視圖。當(dāng)需要實(shí)現(xiàn)包含任意集合的不可變對象時(shí)尤其有用。

本文介紹的第二組方法都因?yàn)橄嗤脑虮慌懦诩现猓?/p>

Collections.addAll ——如果要往一個(gè)集合添加一定數(shù)量的元素或一個(gè)數(shù)組的內(nèi)容，調(diào)用此方法。

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

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

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

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

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

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

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

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

Collections.rotate —— 根據(jù)給定距離旋轉(zhuǎn)列表中的元素。

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

Collections.sort —— 根據(jù)自然排序或給定的 Comparator 對列表進(jìn)行排序。

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

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

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

CopyOnWriteArrayList ——列表實(shí)現(xiàn)，針對每次更新都創(chuàng)建一個(gè)底層數(shù)組的新拷貝。這一操作的成本很高，因此，當(dāng)遍歷的次數(shù)遠(yuǎn)大于更新時(shí)使用此類比較合適。此集合類型的常見用例為 listeners/observers 集合。

ArrayBlockingQueue —— 包含一個(gè)數(shù)組類的有界阻塞隊(duì)列。無法調(diào)整大小，因此，當(dāng)向滿的隊(duì)列添加一個(gè)元素時(shí)，該方法調(diào)用會(huì)遭到阻塞，直到另一個(gè)線程從該隊(duì)列中提取出了一個(gè)元素。

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

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

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

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

PriorityBlockingQueue —— PriorityQueue 的無界阻塞隊(duì)列版。

SynchronousQueue——不帶任何內(nèi)部容量的阻塞隊(duì)列。因此，任何插入請求必須等待對應(yīng)的刪除請求，反之亦然。如果你不需要 Queue 接口，同樣的功能可以通過 Exchanger 實(shí)現(xiàn)。

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

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

ConcurrentSkipListSet ——采用 ConcurrentSkipListMap 類進(jìn)行存儲(chǔ)的并發(fā)集合。

CopyOnWriteArraySet ——采用 CopyOnWriteArrayList 類進(jìn)行存儲(chǔ)的并發(fā)集合。

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

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

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

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

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

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

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

以下是所有 JDK 集合類的簡單總結(jié):

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

本文轉(zhuǎn)自 OneAPM 官方博客

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