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

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

數(shù)組（Arrays）

數(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ù)組的同時保存其內(nèi)容痪寻，可調(diào)用該方法。
• Arrays.copyOfRange ——如果需要拷貝整個數(shù)組或其分段虽惭，可調(diào)用該方法橡类。
• Arrays.deepEquals, Arrays.deepHashCode ——支持嵌套子數(shù)組的 Arrays.equals 或 Arrays.hashCode 版本。
• Arrays.equals ——如果需要比較兩個數(shù)組是否相等趟妥，可調(diào)用此方法（不可調(diào)用數(shù)組自身的 equals 方法猫态，array.equals 方法未被重寫，因此只會比較對數(shù)組的引用披摄，而非其內(nèi)容亲雪。）此方法可以與 Java 5 中的 boxing(裝箱)與 varargs(可變參數(shù))特性并用，以編寫類 equals 方法的簡單實(shí)現(xiàn)——在比較對象類型之后疚膊，將所有類字段都傳給 Arrays.equals 即可义辕。
• Arrays.fill ——將整個數(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ī)則傀蚌，對整個數(shù)組或其分段進(jìn)行排序基显。若要利用已知的 Comparator 對 Object[] 進(jìn)行排序，也有一對 Arrays.sort 方法善炫。
• Arrays.toString ——打印數(shù)組的具體內(nèi)容撩幽。

如果需要將部分?jǐn)?shù)組（或整個數(shù)組）拷貝到另一個已有數(shù)組，你需要調(diào)用 System.arraycopy 方法箩艺，后者會將源數(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)用會分配足夠大的數(shù)組以存儲整個集合，因此 toArray 不必要分配很大的數(shù)組用于返回恢暖。

單線程集合(Single-threaded collections)

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

Lists(列表)

• ArrayList ——用處最大的 List 實(shí)現(xiàn)盛垦。包含一個數(shù)組與一個 int 類型，后者代表了數(shù)組中首個未使用元素所在的位置瓤漏。與其他 List 一樣腾夯，ArrayList 可以在需要的時候進(jìn)行擴(kuò)展。此外蔬充，元素讀取時間固定蝶俱，在列表尾部更新時成本很小（復(fù)雜度是固定的）饥漫，而在頭部更新時成本很高（復(fù)雜度是線性增長的）榨呆，這是因?yàn)? ArrayList 不變量——所有元素在底層數(shù)組中從索引(index)為0處開始，這意味著在插入元素時庸队，插入位置右邊的所有元素都要往右移积蜻；在移除元素時，移除位置右邊的所有元素都要往左移彻消。由于包含數(shù)組竿拆，該集合類型易于 CPU 緩存。（不過宾尚，也不是特別容易丙笋。因?yàn)槠浒?Objects，而后者其實(shí)是指向?qū)嶋H對象的指針）央勒。
• LinkedList ——Deque 實(shí)現(xiàn)，每個 Node(結(jié)點(diǎn))由一個值澳化，以及 prev 與 next 指針構(gòu)成崔步。這意味著，元素讀取或更新的復(fù)雜度是線性增長的（得益于一些優(yōu)化缎谷，這些方法遍歷的范圍不會超過列表長度的一半井濒，因此灶似，讀取或更新成本最高的元素位于列表的中間位置）。如果打算編寫運(yùn)行更快的 LinkedList 代碼瑞你，則需要使用 ListIterators酪惭。如果想要編寫 Queue/Deque 實(shí)現(xiàn)(只需讀取首尾兩個元素)，請轉(zhuǎn)而使用 ArrayDeque者甲。
• Vector —— ArrayList 先前的版本春感，包含所有同步方法。請盡量使用 ArrayList虏缸。

Queues(隊(duì)列)/deques(雙隊(duì)列)

• 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ì)列時，該類比 LinkedList 更加適合（老數(shù)組在擴(kuò)展時會被拋棄）慨灭。
• 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惶翻，不會按照排好的次序(或任何特定次序)迭代隊(duì)列姑蓝。如果只需要隊(duì)列中的最小元素，該隊(duì)列往往比 TreeSet
  之類的其他排序集合更可取吕粗。

Maps(映射)

• 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 的通用約定：在比較引用時使用 == 而非調(diào)用 Object.equals 方法厢汹。這一屬性使得 IdentityHashMap 在各種圖遍歷算法中大顯神通——你可以在 IdentityHashMap 中輕易地存儲已經(jīng)處理過的節(jié)點(diǎn)螟深，連同一些無關(guān)數(shù)據(jù)。
• LinkedHashMap —— HashMap 與 LinkedList 的結(jié)合體烫葬，所有元素的插入次序都存儲在 LinkedList 中界弧，也因此，LinkedHashMap 的條目厘灼，鍵以及值都以插入次序迭代夹纫。就每個元素的內(nèi)存消耗量而已，這是成本最高的 JDK 集合類型设凹。
• TreeMap ——基于有序?qū)Ш叫?Map 的紅黑樹舰讹。按照自然次序或給定的鍵 Comparator 對條目進(jìn)行排序。此映射類要求 equals 與 Comparable/Comparator.compareTo 的實(shí)現(xiàn)必須一致闪朱。此類實(shí)現(xiàn)了一個 NavigableMap 接口：它允許獲得少于或多于給定鍵的映射月匣；允許獲得一個 prev/next 條目(基于鍵的排序)；允許獲得給定范圍內(nèi)的鍵的映射(這與 SQL
  的 BETWEEN 操作符基本對應(yīng))以及此方法的許多變體奋姿。
• WeakHashMap ——此映射通常用于數(shù)據(jù)緩存的實(shí)現(xiàn)锄开。它將所有鍵都保存于 WeakReference，這意味著称诗，如果沒有指向這些鍵對象的強(qiáng)引用萍悴，這些鍵就會被垃圾回收。另一方面寓免，值卻用強(qiáng)引用保存癣诱。因此，你需要確保不存在從值指向鍵的引用袜香，或者將值也保存在弱引用中：m.put(key, new WeakReference(value))撕予。

Sets（集合）

• HashSet ——基于帶有虛值(每個值的 Object 均相同) HashMap 的 set 實(shí)現(xiàn)。與 HashMap 的屬性相同蜈首。也因?yàn)檫@種實(shí)現(xiàn)方式实抡，此類消耗的內(nèi)存比該數(shù)據(jù)類型實(shí)際需要的內(nèi)存要多。
• EnumSet —— enum 值的集合欢策。在 Java 中吆寨，每個 enum 都映射至一個 int 類型：每個 enum 值映射的 int 都互不相同。這使得 BitSet 之類的集合結(jié)構(gòu)成為可能踩寇，每個 bit 都映射到一個不同的 enum 值啄清。此類還存在兩種實(shí)現(xiàn)——包含單個 long 類型（可存儲64個 enum 值，足夠覆蓋99.9%的用例）的 RegularEnumSet 與包含 long[] 類型的 JumboEnumSet姑荷。
• BitSet —— bit 集合盒延。請牢記，可以使用 BitSet 表示整型的稠密集(比如從已知起點(diǎn)開始的 id)鼠冕。此類使用 long[] 類型存儲 bit添寺。
• LinkedHashSet ——與 HashSet 類似，此類基于 LinkedHashMap
  類實(shí)現(xiàn)懈费。這是以插入次序保存元素的唯一集合類计露。
• TreeSet ——與 HashSet 類似，此類基于 TreeMap 實(shí)例憎乙。這是標(biāo)準(zhǔn) JDK 的單線程陣營中唯一的有序集合票罐。

java.util.Collections

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

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

• Collections.checkedCollection / checkedList / checkedMap / checkedSet / checkedSortedMap / checkedSortedSet —— 會返回集合的視圖该押，在運(yùn)行時檢查所添加元素的類型。如果試圖添加類型不兼容的元素阵谚，會拋出 ClassCastException 異常蚕礼。該功能能有效防止運(yùn)行時造型(runtime casts)。
• Collections.emptyList / emptyMap / emptySet ——當(dāng)你需要返回不可變的空集合梢什，而又不想分配任何對象時奠蹬，此類方法便能派上用場。
• Collections.singleton / singletonList / singletonMap —— 返回帶有單個條目的不可變 set/list/map嗡午。
• Collections.synchronizedCollection / synchronizedList /
  synchronizedMap / synchronizedSet / synchronizedSortedMap /
  synchronizedSortedSet —— 返回包含所有同步方法的集合視圖(低成本又低效率的多線程方法囤躁，仍然不支持put-or-update之類的復(fù)合動作)。
• Collections.unmodifiableCollection / unmodifiableList /
  unmodifiableMap / unmodifiableSet / unmodifiableSortedMap /
  unmodifiableSortedSet——返回集合的不可變視圖荔睹。當(dāng)需要實(shí)現(xiàn)包含任意集合的不可變對象時尤其有用狸演。

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

• Collections.addAll ——如果要往一個集合添加一定數(shù)量的元素或一個數(shù)組的內(nèi)容，調(diào)用此方法应媚。
• Collections.binarySearch —— 與 Arrays.binarySearch 對于 arrays(數(shù)組)的作用相同严沥。
• Collections.disjoint —— 檢查2個集合之間不存在共同的元素。
• Collections.fill —— 用給定值替換某個列表中的所有元素中姜。
• Collections.frequency —— 給定集合中有多少元素與給定對象相等消玄。
• Collections.indexOfSubList / lastIndexOfSubList —— 這些方法與
  String.indexOf(String) / lastIndexOf(String) 相似，它們會找出給定列表中給定子列表首次或末次出現(xiàn)的情況丢胚。
• Collections.max / min —— 基于自然排序或 Comparator 找出集合中的最大或最小元素翩瓜。
• Collections.replaceAll —— 在給定列表中用某個元素替代另一個元素。
• Collections.reverse —— 顛倒給定列表中的元素次序携龟。如果你打算在列表排序之后立即調(diào)用此方法兔跌，不如在進(jìn)行元素排序時使用 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個元素(許多開發(fā)者都親自編寫此方法)夸楣。

并發(fā)集合

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

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

Lists(列表)

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

Queues(隊(duì)列)/deques(雙隊(duì)列)

• ArrayBlockingQueue —— 包含一個數(shù)組類的有界阻塞隊(duì)列。無法調(diào)整大小郭厌，因此袋倔，當(dāng)向滿的隊(duì)列添加一個元素時，該方法調(diào)用會遭到阻塞折柠，直到另一個線程從該隊(duì)列中提取出了一個元素宾娜。
• ConcurrentLinkedDeque / ConcurrentLinkedQueue ——基于鏈表(linked
  list)的無界隊(duì)列/雙隊(duì)列。往該隊(duì)列中添加元素不會遭到阻塞扇售，但是要求此類集合的使用者(consumer)必須與其產(chǎn)出者(producer)保持至少相同的工作效率前塔，否則就會出現(xiàn)內(nèi)存耗盡的情況。此類還相當(dāng)依賴 CAS (compare-and-set) 操作承冰。
• DelayQueue ——由 Delayed(延遲) 元素組成的無界阻塞隊(duì)列华弓。其元素只有在延遲過期之后才能從隊(duì)列中剔除。隊(duì)首是剩余延遲值最小(包括負(fù)值困乒，代表延遲已經(jīng)過期)的元素寂屏。當(dāng)想要實(shí)現(xiàn)一個由延遲任務(wù)組成的隊(duì)列時(無需手動實(shí)現(xiàn)，使用 ScheduledThreadPoolExecutor 即可)，此隊(duì)列便能派上用場迁霎。
• LinkedBlockingDeque / LinkedBlockingQueue ——基于鏈表(linked list)的可選有界(可以在創(chuàng)建時指定最大容量吱抚，也可以不指定)隊(duì)列/雙隊(duì)列。以 ReentrantLock-s 為空/滿條件考廉。
• LinkedTransferQueue ——基于鏈表(linked list)的無界隊(duì)列频伤。除了普通的隊(duì)列操作，此類還擁有一組傳遞方法(transfer methods)芝此，允許產(chǎn)出者直接向等待中的使用者發(fā)送消息，從而解決了在隊(duì)列中存儲元素的需求因痛。這是一個基于 CAS 操作的無鎖(lock-free)集合類型婚苹。
• PriorityBlockingQueue —— PriorityQueue 的無界阻塞隊(duì)列版。
• SynchronousQueue——不帶任何內(nèi)部容量的阻塞隊(duì)列鸵膏。因此膊升，任何插入請求必須等待對應(yīng)的刪除請求，反之亦然谭企。如果你不需要 Queue 接口廓译，同樣的功能可以通過 Exchanger 實(shí)現(xiàn)。

Maps(映射)

• ConcurrentHashMap ——對 get 操作全并發(fā)债查、對 put 操作可配置并發(fā)的散列表(hash table)非区。該并發(fā)等級可通過構(gòu)造函數(shù)參數(shù)(默認(rèn)為16) concurrencyLevel 進(jìn)行調(diào)整，該參數(shù)定義了映射內(nèi)的劃分情況盹廷。在 put 操作中只有更新后的劃分會被鎖定征绸。請牢記，此映射類型并不是 HashMap 算法的線程安全替代品 ——任何對此映射(或其他并發(fā)集合類)的 “get-then-put” 序列方法調(diào)用都必須是外部同步的俄占。
• ConcurrentSkipListMap ——基于跳躍表(skip list)的 ConcurrentNavigableMap 實(shí)現(xiàn)管怠。本質(zhì)上，此集合類可以作為 TreeMap 的線程安全替代物使用缸榄。

Sets（集合）

• ConcurrentSkipListSet ——采用 ConcurrentSkipListMap 類進(jìn)行存儲的并發(fā)集合渤弛。
• CopyOnWriteArraySet ——采用 CopyOnWriteArrayList 類進(jìn)行存儲的并發(fā)集合。

另請參閱

• 原始類型集合類：Trove 庫—— 對 Trove 庫的概述甚带，Trove 庫包含了諸多存儲著 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ā)集合類聚假。

總結(jié)

以下是所有 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/