文章目錄

• • 前言
  • • 集合類別
    • • 線性集合類
      • • ArrayList
        • LinkedList 、Queue、Deque
        • Vector
        • Stack
      • 映射集合類
      • • HashMap
        • TreeMap
        • LinkedHashMap
        • WeakHashMap
        • Hashtable
        • IdentifyHashMap
      • 一般集合類
      • • HashSet
        • TreeSet
        • LinkedHashSet
    • 線程安全分類
    • • 非線程安全的集合類：
      • 線程安全的集合類：

前言

在之前的文章中我們介紹了一下 Java 集合框架中的一些類并對一些常用的類的源碼和設計理念進行了解析。那么在這篇文章中我們來將之前介紹過的一些集合類做個總結，并補充一些沒有涉及到的知識點。我們從幾個不同的角度來進行分類。在此之前我們來看看整個 Java 集合框架的類圖：

接下來根據(jù)不同的分類角度來進行分類，首先是按集合類別：

集合類別

線性集合類

說到線性集合類我們腦海里第一個想到的基本上都是 ArrayList ，確實，這個類太常用了，當然除了這個類，Java 集合框架中還有一些其他的有用的線性集合類，我們來一一看一下

ArrayList

具體的解析可以參考：ArrayList

這里直接說結論了：ArrayList 內(nèi)部通過數(shù)組來保存元素，默認初始容量為 10，之后以 1.5 倍進行擴容。每次擴容時新建一個新的數(shù)組，然后將原數(shù)組中的元素復制到新數(shù)組中（直接復制引用），之后將原數(shù)組中的元素清除，數(shù)組引用指向新的數(shù)組。插入元素和刪除元素的時間復雜度都是 O(n)，獲取元素的時間復雜度為 O(1)， ArrayList 是非線程安全的類。

LinkedList 、Queue、Deque

具體的解析可以參考： LinkedList

LinkedList 內(nèi)部以雙向鏈表的結構來保存元素，每一個元素都是一個雙向鏈表節(jié)點。每次來一個元素，就新建一個鏈表節(jié)點并將這個節(jié)點插入當前的雙向鏈表尾部，時間復雜度為 O(1)。刪除元素的時候也是通過要刪除元素的值來找到對應的鏈表節(jié)點，之后將這個鏈表節(jié)點從雙向鏈表中移除，尋找鏈表節(jié)點的時間復雜度為 O(n)，刪除節(jié)點的時間復雜度為 O(1)，因此整個刪除節(jié)點的時間復雜度為 O(n)。此外，因為 LinkedList 實現(xiàn)了 Deque 接口，因此也可以將其作為隊列/雙端隊列使用。最后， LinkedList 也是非線程安全的類。

Vector

具體解析可以參考：Vector

Vector 和 ArrayList 類似，內(nèi)部都是采用數(shù)組來保存元素，而其與 ArrayList 最大的區(qū)別在于 Vecotr 是線程安全的類。因此，如果需要用線程安全的線性結構，可以采用 Vecotor ，也可以采用其他的方法（后文介紹）。

Stack

具體的解析可以參考：Stack

該類繼承自 Vector，因此也是線程安全的類，其提供了 “棧” 這種數(shù)據(jù)結構的一些操作元素 API，入棧、出棧、取棧頂元素等。

映射集合類

同樣的，說到映射集合類（Map），腦海里面第一個想到的就是 HashMap，這個類也算是我們最常用的一個類之一了，當然也還有其他的一些有用的映射類，我們來看看：

HashMap

具體解析可以參考：HashMap

HashMap 提供了一種高效的兩種數(shù)據(jù)之間的映射能力。內(nèi)部提供了一個 table 表，其實就是數(shù)組，不過數(shù)組元素為自定義的實現(xiàn)了 Map.Entry 接口的對象。Map.Entry 就描述了一個完整的鍵值對對象。通過鍵的 hash 值來決定當前鍵值對元素所在的數(shù)組下標。其默認的初始元素容量為 16，擴容因子默認為 0.75，當容量達到當前最大容量 * 擴容因子的值時，進行擴容。 每次擴容的時候容量翻倍。這樣保證每次進行鍵值對進行 hash 時可以通過位運算來代替取余操作（防止得到的數(shù)組下標越界），提高效率。當出現(xiàn) hash 值沖突的時候，先采用鏈地址法處理（使用單鏈表將沖突的元素連接），當某個沖突鏈表的長度不小于 8 時，將其樹化（轉(zhuǎn)換為紅黑樹，加快查找速度）。 HashMap 是非線程安全的類。

TreeMap

具體的解析可以參考：TreeMap

同 HashMap 一樣，TreeMap 也是提供了一種數(shù)據(jù)之間的的映射能力，但是這里并沒有用高效來形容它，是因為同 HashMap 相比，它的效率還是略低，因為其還提供對鍵排序的功能，我們在遍歷 TreeMap 的時候，元素的遍歷順序已經(jīng)是根據(jù)某種規(guī)則排序后的序列，為了達成這種功能，其內(nèi)部借助了一種平衡二叉樹（紅黑樹）的數(shù)據(jù)結構來實現(xiàn)。當我們在插入新的元素的時候，其依據(jù)定義的排序規(guī)則來找到合適的位置進行插入。所以其插入元素的過程是來一個插一個，所以在 TreeMap 中并沒有初始容量和擴容的概念。而插入、刪除、查詢等操作的時間復雜度為 O(logn)。n 為樹中的節(jié)點總數(shù)，即為元素總數(shù)。

LinkedHashMap

具體解析可以參考：LinkedHashMap

我們知道 HashMap 在遍歷時的元素順序和插入時的元素順序是不一定相同的，那么有時候我們可能有這種需求，即使得遍歷時的元素順序和插入時一致，此時我們就可以考慮使用 LinkedHashMap，因為 LinkedHashMap 是繼承于 HashMap 的，只不過為了維護元素順序和插入時的保持一致，LinkedHashMap 在 HashMap 節(jié)點的基礎上增加了指向前驅(qū)和后繼節(jié)點的引用，也就是通過雙向鏈表來維護元素的順序。而同時留有一些擴展方法，一些緩存算法（LRU）就可以通過 LinkedHashMap 來輕松實現(xiàn)。

WeakHashMap

具體解析可以參考：WeakHashMap

由于弱引用（詳解 Java 的四種引用）的出現(xiàn)，使得 WeakHashMap 可以做到保證其所引用的元素不會導致 OutofMemoryError 異常。同 HashMap 一樣， WeakHashMap 內(nèi)部也是通過數(shù)組來儲存元素的，WeakHashMap 默認的初始容量是 16，最大容量為 1 << 30 ；默認擴容因子為 0.75；可以指定初始容量，但是處理過后的初始容量一定是 2 的次冪，好處是可以通過 & 運算來代替 % 運算提高效率；每次擴容時容量翻倍。節(jié)點（Entry）之間利用單項鏈表之間來處理 hash 值沖突。

Hashtable

具體解析可參考：Hashtable

和 HashMap 類似，不過其是線程安全的類，其實也就是在每個操作元素的方法前加入 synchronized 關鍵字修飾，效率不高，我們完全有更好的方法來代替這個，同時具體的擴容機制和 HashMap 也略有不同：默認初始容量為 11，擴容因子為 0.75，每次擴容后的容量變?yōu)橹叭萘康?2 倍 + 1。這個類已經(jīng)被標為 Legacy（遺留類），即不被推薦使用。關于其的替代，后面將會介紹。

IdentifyHashMap

具體解析可參考：IdentifyHashMap

之前介紹的 Map 都是通過具體元素的 key 的 equals 方法來判斷元素等價，而這個 Map 中則是通過最原始的方法（Object 的 equals 方法）來判斷，即如果兩個對象不是同一個對象，即使其內(nèi)部屬性值相同，那么也被當做不等價。其內(nèi)部通過一個 Object 類型的數(shù)組來儲存元素，即鍵值都用這個數(shù)組儲存，鍵所在的下標是偶數(shù)（0、2、4…），值所在的下標是對應的鍵下標 + 1。同時，存入元素也按照相同的規(guī)則。如果 當前元素個數(shù) * 3 > table.length（包括了鍵和值）。那么進行擴容，擴容是數(shù)組容量翻倍。table 數(shù)組的最大容量是 1 << 30，默認初始容量為 32。

一般集合類

為了統(tǒng)一，這里給它起了個名字叫一般集合類，其實就是 Set 了。

因為集合類內(nèi)部都是借助了對應的 Map 來進行實現(xiàn)，所以理解了 Map 接口的相關具體類，Set 的相關類就非常簡單了。這里用一篇文章總結了一下 Set 接口下的具體類：Java 集合框架（7）.

HashSet

內(nèi)部通過 HashMap 實現(xiàn)，效率較高。但是元素取出的順序和存入的順序不一定相同

TreeSet

內(nèi)部通過 TreeMap 實現(xiàn)，將元素按照一定規(guī)則排序，取出的元素順序是按照某個規(guī)則排好序的。這個排序規(guī)則可以在創(chuàng)建 TreeSet 對象的時候通過參數(shù)傳入，或者存入的元素類型實現(xiàn) Comparable 接口。

LinkedHashSet

內(nèi)部通過 LinkedHashMap 實現(xiàn)，可以實現(xiàn)元素取出的順序和存入的順序相同

線程安全分類

下面按照線程安全來對各個集合類進行介紹，同時會介紹一些之前提到過的一些其他的集合類

非線程安全的集合類：

ArrayList、LinkedList、Queue、Deque （Queue 和 Deque 是兩個接口，其實現(xiàn)是 LinkedList，所以也是非線程安全的）。

HashMap、TreeMap、LinkedHashMap、WeakHashMap、IdentifyHashMap

HashSet、TreeMap、LinkedHashSet

線程安全的集合類：

Vector、Stack、 CopyOnWriteArrayList（JDK 1.5）

Hashtable、ConcurrentHashMap（JDK 1.5）

上面說的 HashSet、TreeMap、LinkedHashSet 都是非線程安全的，那么我們就沒有線程安全的 Set 集合用嗎，其實并不是，這里有兩種方法來解決這個問題：

1、我們已經(jīng)知道 Set 集合內(nèi)部都是通過對應的 Map 實現(xiàn)的，那么我們自定義一個 Set 集合類，內(nèi)部用一個線程安全的 Map 來實現(xiàn)不就行了嗎。對于具體的實現(xiàn)，可以參考下面的代碼：

public class ThreadSafeSet<E> extends AbstractSet<E> implements Set<E> {private static int DEFAULT_INIT_CAPACITY = 16;private static float DEFAULT_LOAD_FACTOR = 0.7F;private static Object VALUE = new Object();private ConcurrentMap<E, Object> concurrentMap;public ThreadSafeSet() {this(DEFAULT_INIT_CAPACITY, DEFAULT_LOAD_FACTOR);}public ThreadSafeSet(int initCapacity, float loadFactor) {concurrentMap = new ConcurrentHashMap<>(DEFAULT_INIT_CAPACITY, DEFAULT_LOAD_FACTOR);}@Overridepublic int size() {return concurrentMap.size();}@Overridepublic boolean isEmpty() {return concurrentMap.isEmpty();}@Overridepublic boolean contains(Object o) {return concurrentMap.containsKey(o);}@Overridepublic Iterator<E> iterator() {return concurrentMap.keySet().iterator();}@Overridepublic boolean add(Object e) {return concurrentMap.put((E) e, VALUE) == null;}@Overridepublic boolean remove(Object o) {return concurrentMap.remove(o) != null;} }

2、除了上面的方式外，在集合工具類 Collections 中已經(jīng)提供了一些方法來創(chuàng)造一些線程安全的集合：

可以看到，這里面有一些以 synchronized 開頭的方法名，接受的參數(shù)也是有 List、Map、Set 等集合，這些方法就可以返回一些線程安全的集合，我們隨便挑一個方法來看：

public static <T> Set<T> synchronizedSet(Set<T> s) {return new SynchronizedSet<>(s); }

這里直接返回了一個 SynchronizedSet 對象，這個類繼承于 SynchronizedCollection 類，我們來看看這個類：

/*** @serial include*/ static class SynchronizedCollection<E> implements Collection<E>, Serializable {private static final long serialVersionUID = 3053995032091335093L;final Collection<E> c; // Backing Collectionfinal Object mutex; // Object on which to synchronizeSynchronizedCollection(Collection<E> c) {this.c = Objects.requireNonNull(c);mutex = this;}SynchronizedCollection(Collection<E> c, Object mutex) {this.c = Objects.requireNonNull(c);this.mutex = Objects.requireNonNull(mutex);}public int size() {synchronized (mutex) {return c.size();}}public boolean isEmpty() {synchronized (mutex) {return c.isEmpty();}}public boolean contains(Object o) {synchronized (mutex) {return c.contains(o);}}public Object[] toArray() {synchronized (mutex) {return c.toArray();}}public <T> T[] toArray(T[] a) {synchronized (mutex) {return c.toArray(a);}}public Iterator<E> iterator() {return c.iterator(); // Must be manually synched by user!}public boolean add(E e) {synchronized (mutex) {return c.add(e);}}public boolean remove(Object o) {synchronized (mutex) {return c.remove(o);}}public boolean containsAll(Collection<?> coll) {synchronized (mutex) {return c.containsAll(coll);}}public boolean addAll(Collection<? extends E> coll) {synchronized (mutex) {return c.addAll(coll);}}public boolean removeAll(Collection<?> coll) {synchronized (mutex) {return c.removeAll(coll);}}public boolean retainAll(Collection<?> coll) {synchronized (mutex) {return c.retainAll(coll);}}public void clear() {synchronized (mutex) {c.clear();}}public String toString() {synchronized (mutex) {return c.toString();}}// Override default methods in Collection@Overridepublic void forEach(Consumer<? super E> consumer) {synchronized (mutex) {c.forEach(consumer);}}@Overridepublic boolean removeIf(Predicate<? super E> filter) {synchronized (mutex) {return c.removeIf(filter);}}@Overridepublic Spliterator<E> spliterator() {return c.spliterator(); // Must be manually synched by user!}@Overridepublic Stream<E> stream() {return c.stream(); // Must be manually synched by user!}@Overridepublic Stream<E> parallelStream() {return c.parallelStream(); // Must be manually synched by user!}private void writeObject(ObjectOutputStream s) throws IOException {synchronized (mutex) {s.defaultWriteObject();}} }

可以看到，這里面對元素操作的方法全都用了 synchronized 關鍵字修飾，而本身也只是調(diào)用了對應類的對應方法，所以說 Collections 類中為我們準備的線程安全的集合類就是把相關的方法都用 synchronized 關鍵字修飾了一下以保證線程安全。接下來看看 SynchronizedSet：

/*** @serial include*/ static class SynchronizedSet<E> extends SynchronizedCollection<E> implements Set<E> {private static final long serialVersionUID = 487447009682186044L;SynchronizedSet(Set<E> s) {super(s);}SynchronizedSet(Set<E> s, Object mutex) {super(s, mutex);}public boolean equals(Object o) {if (this == o)return true;synchronized (mutex) {return c.equals(o);}}public int hashCode() {synchronized (mutex) {return c.hashCode();}} }

這個類里面沒有多余的元素操作的方法，因為 Set 集合中的操作元素的方法都已經(jīng)被其父類 SynchronizedCollection 涵蓋了。那么對于其余的集合類也是一樣的道理。

其實 Collections 類是 Java 集合框架的類庫，里面有很多的集合相關操作的方法（排序、二分查找、逆轉(zhuǎn)元素順序等），于此對應的還有一個類：Arrays，也是一個工具類庫，與 Collections 不同的是 Arrays 更多的是針對數(shù)組和線性集合，而 Collestions 針對的更多是集合框架中的類。

好了，關于 Java 中的集合框架到這里就告一段落了。其實在 java.util.concurrent 包中還有一些具有線程安全的集合，我們已經(jīng)看過了 ConcurrentHashMap，其余的由于不太常用（對我來說，因為我主要是 Android 開發(fā)），這里就不細講了，有興趣的小伙伴可以去看看里面的一些類。到這里 Java 集合框架系列就結束了，如果以后有新的體會再來補充吧如果覺得本系列對您有幫助，請不要吝嗇您的贊。如果覺得文章中有什么不正確的地方，還請多多指點。下個系列應該會是關于 Java 類體系的專題，里面會有一些令人期待的新知識點。那么下個系列再見～

謝謝觀看。。。

我的博客即將搬運同步至騰訊云+社區(qū)，邀請大家一同入駐：https://cloud.tencent.com/developer/support-plan?invite_code=3o2apkp87k2sc

總結

以上是生活随笔為你收集整理的Java 集合框架（8）---- 总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。