java-對象管理-集合

在實際的項目開發中會有很多的對象，如何高效、友善地管理對象，成為影響程式性能與可維護性的重要環節。Java 提供了集合架構來解決此類問題，線性表、連結清單、哈希表等是常用的資料結構，在進行 Java 開發時，JDK 已經為我們提供了一系列相應的類來實作基本的資料結構，所有類都在 java.util 這個包裡。

Collection 接口

Collection 是最基本的集合接口，一個 Collection 代表一組 Object，即 Collection 的元素（Elements）。一些 Collection 允許相同的元素、支援對元素進行排序，另一些則不行。JDK 不提供直接繼承自 Collection 的類，JDK 提供的類都是繼承自 Collection 的子接口，如 List 和 Set。所有實作 Collection 接口的類都必須提供兩個标準的構造函數，無參數的構造函數用于建立一個空的 Collection，有一個 Collection 參數的構造函數用于建立一個新的 Collection，這個新的 Collection 與傳入的 Collection 有相同的元素，後一個構造函數允許使用者複制一個 Collection。

如何周遊 Collection 中的每一個元素？

不論 Collection 的實際類型如何，它都支援一個 iterator() 的方法，該方法傳回一個疊代子，使用該疊代子即可逐一通路 Collection 中每一個元素。典型的用法如下：

Iterator it = collection.iterator(); // 獲得一個疊代子

while(it.hasNext()){

Object obj = it.next(); // 得到下一個元素

}

Collection 接口派生的兩個接口是 List 和 Set。

Collection 接口提供的主要方法：

boolean add(Object o) 添加對象到集合；

boolean remove(Object o) 删除指定的對象；

int size() 傳回目前集合中元素的數量；

boolean contains(Object o) 查找集合中是否有指定的對象；

boolean isEmpty() 判斷集合是否為空；

Iterator iterator() 傳回一個疊代器；

boolean containsAll(Collection c) 查找集合中是否有集合 C 中的元素；

boolean addAll(Collection c) 将集合 C 中所有的元素添加給該集合；

void clear() 删除集合中所有元素；

void removeAll(Collection c) 從集合中删除 C 集合中也有的元素；

void retainAll(Collection c) 從集合中删除集合 C 中不包含的元素。

List 接口

List 是有序的 Collection，使用此接口能夠精确的控制每個元素插入的位置。使用者能夠使用索引（元素在 List 中的位置，類似于數組下标）來通路 List 中的元素，這類似于 Java 的數組。和下文要提到的 Set 不同，List 允許有相同的元素。

除了具有 Collection 接口必備的 iterator() 方法外，List 還提供一個 listIterator() 方法，傳回一個 ListIterator 接口。和标準的 Iterator 接口相比，ListIterator 多了一些 add() 之類的方法，允許添加、删除、設定元素、向前或向後周遊等功能。實作 List 接口的常用類有 LinkedList，ArrayList，Vector 和 Stack 等。

List 接口提供的主要方法：

void add(int index,Object element) 在指定位置上添加一個對象；

boolean addAll(int index,Collection c) 将集合 C 的元素添加到指定的位置；

Object get(int index) 傳回 List 中指定位置的元素；

int indexOf(Object o) 傳回第一個出現元素 O 的位置；

Object removeint(int index) 删除指定位置的元素；

Object set(int index,Object element) 用元素 element 取代位置 index 上的元素, 傳回被取代的元素。

Map 接口

Map 沒有繼承 Collection 接口。Map 提供 Key 到 Value 的映射，一個 Map 中不能包含相同的 Key，每個 Key 隻能映射一個 Value。Map 接口提供 3 種集合的視圖，Map 的内容可以被當作一組 Key 集合，一組 Value 集合，或者一組 Key-Value 映射。

Map 提供的主要方法：

boolean equals(Object o) 比較對象；

boolean remove(Object o) 删除一個對象；

put(Object key,Object value) 添加 key 和 value。

RandomAccess 接口

RandomAccess 接口是一個标志接口，本身并沒有提供任何方法，任務凡是通過調用 RandomAccess 接口的對象都可以認為是支援快速随機通路的對象。此接口的主要目的是辨別那些可支援快速随機通路的 List 實作。任何一個基于數組的 List 實作都實作了 RaodomAccess 接口，而基于連結清單的實作則都沒有。因為隻有數組能夠進行快速的随機通路，而對連結清單的随機通路需要進行連結清單的周遊。是以，此接口的好處是，可以在應用程式中知道正在處理的 List 對象是否可以進行快速随機通路，進而針對不同的 List 進行不同的操作，以提高程式的性能。

LinkedList 實作了 List 接口，允許 Null 元素。此外 LinkedList 提供額外的 Get、Remove、Insert 等方法在 LinkedList 的首部或尾部操作資料。這些操作使得 LinkedList 可被用作堆棧（Stack）、隊列（Queue）或雙向隊列（Deque）。請注意 LinkedList 沒有同步方法，它不是線程同步的，即如果多個線程同時通路一個 List，則必須自己實作通路同步。一種解決方法是在建立 List 時構造一個同步的 List，方法如

ArrayList 實作了可變大小的數組。它允許所有元素，包括 Null。Size、IsEmpty、Get、Set 等方法的運作時間為常數，但是 Add 方法開銷為分攤的常數，添加 N 個元素需要 O(N) 的時間，其他的方法運作時間為線性。

每個 ArrayList 執行個體都有一個容量（Capacity），用于存儲元素的數組的大小，這個容量可随着不斷添加新元素而自動增加。當需要插入大量元素時，在插入前可以調用 ensureCapacity 方法來增加 ArrayList 的容量以提高插入效率。和 LinkedList 一樣，ArrayList 也是線程非同步的（unsynchronized）。

Vector 非常類似于 ArrayList，差別是 Vector 是線程同步的。由 Vector 建立的 Iterator，雖然和 ArrayList 建立的 Iterator 是同一接口，但是，因為 Vector 是同步的，當一個 Iterator 被建立而且正在被使用，另一個線程改變了 Vector 的狀态（例如，添加或删除了一些元素），這時調用 Iterator 的方法時将抛出 ConcurrentModificationException，是以必須捕獲該異常。

Stack 繼承自 Vector，實作了一個後進先出的堆棧。Stack 提供 5 個額外的方法使得 Vector 得以被當作堆棧使用。除了基本的 Push 和 Pop 方法，還有 Peek 方法得到棧頂的元素，Empty 方法測試堆棧是否為空，Search 方法檢測一個元素在堆棧中的位置。注意，Stack 剛建立後是空棧。

Set 是一種不包含重複的元素的 Collection，即任意的兩個元素 e1 和 e2 都有 e1.equals(e2)=false。Set 最多有一個 null 元素。很明顯，Set 的構造函數有一個限制條件，傳入的 Collection 參數不能包含重複的元素。請注意，必須小心操作可變對象（Mutable Object），如果一個 Set 中的可變元素改變了自身狀态，這可能會導緻一些問題。

Hashtable 繼承 Map 接口，實作了一個基于 Key-Value 映射的哈希表。任何非空（non-null）的對象都可作為 Key 或者 Value。添加資料使用 Put(Key，Value)，取出資料使用 Get(Key)，這兩個基本操作的時間開銷為常數。

Hashtable 通過 Initial Capacity 和 Load Factor 兩個參數調整性能。通常預設的 Load Factor 0.75 較好地實作了時間和空間的均衡。增大 Load Factor 可以節省空間但相應的查找時間将增大，會影響像 Get 和 Put 這樣的操作。使用 Hashtable 的簡單示例，将 1、2、3 這三個數字放到 Hashtable 裡面，他們的 Key 分别是”one”、”two”、”three”，代碼如清單 2 所示。

由于作為 Key 的對象将通過計算其散列函數來确定與之對應的 Value 的位置，是以任何作為 key 的對象都必須實作 HashCode 和 Equals 方法。HashCode 和 Equals 方法繼承自根類 Object，如果你用自定義的類當作 Key 的話，要相當小心，按照散列函數的定義，如果兩個對象相同，即 obj1.equals(obj2)=true，則它們的 HashCode 必須相同，但如果兩個對象不同，則它們的 HashCode 不一定不同，如果兩個不同對象的 HashCode 相同，這種現象稱為沖突，沖突會導緻操作哈希表的時間開銷增大，是以盡量定義好的 HashCode() 方法，能加快哈希表的操作。

如果相同的對象有不同的 HashCode，對哈希表的操作會出現意想不到的結果（期待的 Get 方法傳回 Null），要避免這種問題，最好同時複寫 Equals 方法和 HashCode 方法，而不要隻寫其中一個。

HashMap 和 Hashtable 類似，不同之處在于 HashMap 是線程非同步的，并且允許 Null，即 Null Value 和 Null Key。但是将 HashMap 視為 Collection 時（values() 方法可傳回 Collection），其疊代子操作時間開銷和 HashMap 的容量成比例。是以，如果疊代操作的性能相當重要的話，不要将 HashMap 的初始化容量設得過高，或者 Load Factor 參數設定過低。

WeakHashMap 是一種改進的 HashMap，它對 Key 實行“弱引用”，如果一個 Key 不再被外部所引用，那麼該 Key 可以被 GC 回收。

ArrayList、Vector、LinkedList 均來自 AbstractList 的實作，而 AbstractList 直接實作了 List 接口，并擴充自 AbstarctCollection。ArrayList 和 Vector 使用了數組實作，ArrayList 沒有對任何一個方法提供線程同步，是以不是線程安全的，Vector 中絕大部分方法都做了線程同步，是一種線程安全的實作。LinkedList 使用了循環雙向連結清單資料結構，由一系清單項連接配接而成，一個表項總是包含 3 個部分，元素内容、前驅表項和後驅表項。

當 ArrayList 對容量的需求超過目前數組的大小時，需要進行擴容。擴容過程中，會進行大量的數組複制操作，而數組複制時，最終将調用 System.arraycopy() 方法。LinkedList 由于使用了連結清單的結構，是以不需要維護容量的大小，然而每次的元素增加都需要建立一個 Entry 對象，并進行更多的指派操作，在頻繁的系統調用下，對性能會産生一定的影響，在不間斷地生成新的對象還是占用了一定的資源。而因為數組的連續性，是以總是在尾端增加元素時，隻有在空間不足時才産生數組擴容和數組複制。

ArrayList 是基于數組實作的，而數組是一塊連續的記憶體空間，如果在數組的任意位置插入元素，必然導緻在該位置後的所有元素需要重新排列，是以其效率較差，盡可能将資料插入到尾部。LinkedList 不會因為插入資料導緻性能下降。

ArrayList 的每一次有效的元素删除操作後都要進行數組的重組，并且删除的元素位置越靠前，數組重組時的開銷越大，要删除的元素位置越靠後，開銷越小。LinkedList 要移除中間的資料需要便利完半個 List。

HashMap 是将 Key 做 Hash 算法，然後将 Hash 值映射到記憶體位址，直接取得 Key 所對應的資料。在 HashMap 中，底層資料結構使用的是數組，所謂的記憶體位址即數組的下标索引。HashMap 的高性能需要保證以下幾點：

Hash 算法必須是高效的；

Hash 值到記憶體位址 (數組索引) 的算法是快速的；

根據記憶體位址 (數組索引) 可以直接取得對應的值。

HashMap 實際上是一個連結清單的數組。前面已經介紹過，基于 HashMap 的連結清單方式實作機制，隻要 HashCode() 和 Hash() 方法實作得足夠好，能夠盡可能地減少沖突的産生，那麼對 HashMap 的操作幾乎等價于對數組的随機通路操作，具有很好的性能。但是，如果 HashCode() 或者 Hash() 方法實作較差，在大量沖突産生的情況下，HashMap 事實上就退化為幾個連結清單，對 HashMap 的操作等價于周遊連結清單，此時性能很差。

HashMap 的一個功能缺點是它的無序性，被存入到 HashMap 中的元素，在周遊 HashMap 時，其輸出是無序的。如果希望元素保持輸入的順序，可以使用 LinkedHashMap 替代。

LinkedHashMap 繼承自 HashMap，具有高效性，同時在 HashMap 的基礎上，又在内部增加了一個連結清單，用以存放元素的順序。

HashMap 通過 hash 算法可以最快速地進行 Put() 和 Get() 操作。TreeMap 則提供了一種完全不同的 Map 實作。從功能上講，TreeMap 有着比 HashMap 更為強大的功能，它實作了 SortedMap 接口，這意味着它可以對元素進行排序。TreeMap 的性能略微低于 HashMap。如果在開發中需要對元素進行排序，那麼使用 HashMap 便無法實作這種功能，使用 TreeMap 的疊代輸出将會以元素順序進行。LinkedHashMap 是基于元素進入集合的順序或者被通路的先後順序排序，TreeMap 則是基于元素的固有順序 (由 Comparator 或者 Comparable 确定)。

LinkedHashMap 是根據元素增加或者通路的先後順序進行排序，而 TreeMap 則根據元素的 Key 進行排序。

WeakHashMap 特點是當除了自身有對 Key 的引用外，如果此 Key 沒有其他引用，那麼此 Map 會自動丢棄該值。如清單 8 所示代碼聲明了兩個 Map 對象，一個是 HashMap，一個是 WeakHashMap，同時向兩個 map 中放入 A、B 兩個對象，當 HashMap 删除 A，并且 A、B 都指向 Null 時，WeakHashMap 中的 A 将自動被回收掉。出現這個狀況的原因是，對于 A 對象而言，當 HashMap 删除并且将 A 指向 Null 後，除了 WeakHashMap 中還儲存 A 外已經沒有指向 A 的指針了，是以 WeakHashMap 會自動舍棄掉 a，而對于 B 對象雖然指向了 null，但 HashMap 中還有指向 B 的指針，是以 WeakHashMap 将會保留 B 對象。

WeakHashMap 主要通過 expungeStaleEntries 這個函數來實作移除其内部不用的條目，進而達到自動釋放記憶體的目的。基本上隻要對 WeakHashMap 的内容進行通路就會調用這個函數，進而達到清除其内部不再為外部引用的條目。但是如果預先生成了 WeakHashMap，而在 GC 以前又不曾通路該 WeakHashMap, 那不是就不能釋放記憶體了嗎？

出現記憶體溢出問題，WeakHashMap 這個時候并沒有自動幫我們釋放不用的記憶體。

運作結果發現這次測試輸出正常, 不再出現記憶體溢出問題。

總的來說，WeakHashMap 并不是你什麼也幹它就能自動釋放内部不用的對象的，而是在你通路它的内容的時候釋放内部不用的對象。

WeakHashMap 實作弱引用，是因為它的 Entry

請注意它構造父類的語句：“super(key, queue);”，傳入的是 Key，是以 Key 才是進行弱引用的，Value 是直接強引用關聯在 this.value 之中。在 System.gc() 時，Key 中的 Byte 數組進行了回收，而 Value 依然保持 (Value 被強關聯到 Entry 上，Entry 又關聯在 Map 中，Map 關聯在 ArrayList 中)。

For 循環中每次都 New 一個新的 WeakHashMap，在 Put 操作後，雖然 GC 将 WeakReference 的 Key 中的 Byte 數組回收了，并将事件通知到了 ReferenceQueue，但後續卻沒有相應的動作去觸發 WeakHashMap 去處理 ReferenceQueue，是以 WeakReference 包裝 Key 依然存在于 WeakHashMap 中，其對應的 value 也當然存在。

那 value 是何時被清除的呢? 對清單 10 和清單 11 兩個示例程式進行分析可知，清單 11 的 maps.get(j).size() 觸發了 Value 的回收，那又如何觸發的呢？檢視 WeakHashMap 源碼可知,Size 方法調用了 expungeStaleEntries 方法，該方法對 JVM 要回收的的 Entry(Quene 中) 進行周遊，并将 Entry 的 Value 置空，回收了記憶體。是以效果是 Key 在 GC 的時候被清除，Value 在 Key 清除後通路 WeakHashMap 被清除。

WeakHashMap 類是線程不同步的，可以使用 Collections.synchronizedMap 方法來構造同步的 WeakHashMap, 每個鍵對象間接地存儲為一個弱引用的訓示對象。是以，不管是在映射内還是在映射之外，隻有在垃圾回收器清除某個鍵的弱引用之後，該鍵才會自動移除。需要注意的是，WeakHashMap 中的值對象由普通的強引用保持。是以應該小心謹慎，確定值對象不會直接或間接地強引用其自身的鍵，因為這會阻止鍵的丢棄。注意，值對象可以通過 WeakHashMap 本身間接引用其對應的鍵，這就是說，某個值對象可能強引用某個其他的鍵對象，而與該鍵對象相關聯的值對象轉而強引用第一個值對象的鍵。

處理此問題的一種方法是，在插入前将值自身包裝在 WeakReferences 中，如：m.put(key, new WeakReference(value))，然後，分别用 get 進行解包，該類所有“collection 視圖方法”傳回的疊代器均是快速失敗的，在疊代器建立之後，如果從結構上對映射進行修改，除非通過疊代器自身的 Remove 或 Add 方法，其他任何時間任何方式的修改，疊代器都将抛出 ConcurrentModificationException。是以，面對并發的修改，疊代器很快就完全失敗，而不是冒着在将來不确定的時間任意發生不确定行為的風險。

注意，我們不能確定疊代器不失敗，一般來說，存在不同步的并發修改時，不可能做出任何完全确定的保證。