在實(shí)際的項(xiàng)目開(kāi)發(fā)中會(huì)有很多的對(duì)象，如何高效、方便地管理對(duì)象，成為影響程序性能與可維護(hù)性的重要環(huán)節(jié)。Java 提供了集合框架來(lái)解決此類(lèi)問(wèn)題，線性表、鏈表、哈希表等是常用的數(shù)據(jù)結(jié)構(gòu)，在進(jìn)行 Java 開(kāi)發(fā)時(shí)，JDK 已經(jīng)為我們提供了一系列相應(yīng)的類(lèi)來(lái)實(shí)現(xiàn)基本的數(shù)據(jù)結(jié)構(gòu)，所有類(lèi)都在 java.util 這個(gè)包里，清單1 描述了集合類(lèi)的關(guān)系。
清單 1.集合類(lèi)之間關(guān)系
Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│ └Stack
└Set
Map
├Hashtable
├HashMap
└WeakHashMap
集合接口
Collection 接口
Collection 是最基本的集合接口，一個(gè) Collection 代表一組 Object，即 Collection 的元素（Elements）。一些 Collection 允許相同的元素、支持對(duì)元素進(jìn)行排序，另一些則不行。JDK 不提供直接繼承自 Collection 的類(lèi)，JDK 提供的類(lèi)都是繼承自 Collection 的子接口，如 List 和 Set。所有實(shí)現(xiàn) Collection 接口的類(lèi)都必須提供兩個(gè)標(biāo)準(zhǔn)的構(gòu)造函數(shù)，無(wú)參數(shù)的構(gòu)造函數(shù)用于創(chuàng)建一個(gè)空的 Collection，有一個(gè) Collection 參數(shù)的構(gòu)造函數(shù)用于創(chuàng)建一個(gè)新的 Collection，這個(gè)新的 Collection 與傳入的 Collection 有相同的元素，后一個(gè)構(gòu)造函數(shù)允許用戶(hù)復(fù)制一個(gè) Collection。
如何遍歷 Collection 中的每一個(gè)元素？
不論 Collection 的實(shí)際類(lèi)型如何，它都支持一個(gè) iterator() 的方法，該方法返回一個(gè)迭代子，使用該迭代子即可逐一訪問(wèn) Collection 中每一個(gè)元素。典型的用法如下：
|
1
2
3
4
5
6
7
|
Iterator it = collection.iterator(); // 獲得一個(gè)迭代子 while(it.hasNext()){ Object obj = it.next(); // 得到下一個(gè)元素 } |
Collection 接口派生的兩個(gè)接口是 List 和 Set。
Collection 接口提供的主要方法：
1、boolean add(Object o) 添加對(duì)象到集合；
2、boolean remove(Object o) 刪除指定的對(duì)象；
3、int size() 返回當(dāng)前集合中元素的數(shù)量；
4、boolean contains(Object o) 查找集合中是否有指定的對(duì)象；
5、boolean isEmpty() 判斷集合是否為空；
6、Iterator iterator() 返回一個(gè)迭代器；
7、boolean containsAll(Collection c) 查找集合中是否有集合 C 中的元素；
8、boolean addAll(Collection c) 將集合 C 中所有的元素添加給該集合；
9、void clear() 刪除集合中所有元素；
10、void removeAll(Collection c) 從集合中刪除 C 集合中也有的元素；
11、void retainAll(Collection c) 從集合中刪除集合 C 中不包含的元素。
List 接口
List 是有序的 Collection，使用此接口能夠精確的控制每個(gè)元素插入的位置。用戶(hù)能夠使用索引（元素在 List 中的位置，類(lèi)似于數(shù)組下標(biāo)）來(lái)訪問(wèn) List 中的元素，這類(lèi)似于 Java 的數(shù)組。和下文要提到的 Set 不同，List 允許有相同的元素。
除了具有 Collection 接口必備的 iterator() 方法外，List 還提供一個(gè) listIterator() 方法，返回一個(gè) ListIterator 接口。和標(biāo)準(zhǔn)的 Iterator 接口相比，ListIterator 多了一些 add() 之類(lèi)的方法，允許添加、刪除、設(shè)定元素、向前或向后遍歷等功能。實(shí)現(xiàn) List 接口的常用類(lèi)有 LinkedList，ArrayList，Vector 和 Stack 等。
List 接口提供的主要方法：
1、void add(int index,Object element) 在指定位置上添加一個(gè)對(duì)象；
2、boolean addAll(int index,Collection c) 將集合 C 的元素添加到指定的位置；
3、Object get(int index) 返回 List 中指定位置的元素；
4、int indexOf(Object o) 返回第一個(gè)出現(xiàn)元素 O 的位置；
5、Object removeint(int index) 刪除指定位置的元素；
6、Object set(int index,Object element) 用元素 element 取代位置 index 上的元素, 返回被取代的元素。
Map 接口
Map 沒(méi)有繼承 Collection 接口。Map 提供 Key 到 Value 的映射，一個(gè) Map 中不能包含相同的 Key，每個(gè) Key 只能映射一個(gè) Value。Map 接口提供 3 種集合的視圖，Map 的內(nèi)容可以被當(dāng)作一組 Key 集合，一組 Value 集合，或者一組 Key-Value 映射。
Map 提供的主要方法：
1、boolean equals(Object o) 比較對(duì)象；
2、boolean remove(Object o) 刪除一個(gè)對(duì)象；
3、put(Object key,Object value) 添加 key 和 value。
RandomAccess 接口
RandomAccess 接口是一個(gè)標(biāo)志接口，本身并沒(méi)有提供任何方法，任務(wù)凡是通過(guò)調(diào)用 RandomAccess 接口的對(duì)象都可以認(rèn)為是支持快速隨機(jī)訪問(wèn)的對(duì)象。此接口的主要目的是標(biāo)識(shí)那些可支持快速隨機(jī)訪問(wèn)的 List 實(shí)現(xiàn)。任何一個(gè)基于數(shù)組的 List 實(shí)現(xiàn)都實(shí)現(xiàn)了 RaodomAccess 接口，而基于鏈表的實(shí)現(xiàn)則都沒(méi)有。因?yàn)橹挥袛?shù)組能夠進(jìn)行快速的隨機(jī)訪問(wèn)，而對(duì)鏈表的隨機(jī)訪問(wèn)需要進(jìn)行鏈表的遍歷。因此，此接口的好處是，可以在應(yīng)用程序中知道正在處理的 List 對(duì)象是否可以進(jìn)行快速隨機(jī)訪問(wèn)，從而針對(duì)不同的 List 進(jìn)行不同的操作，以提高程序的性能。
集合類(lèi)介紹
LinkedList 類(lèi)
LinkedList 實(shí)現(xiàn)了 List 接口，允許 Null 元素。此外 LinkedList 提供額外的 Get、Remove、Insert 等方法在 LinkedList 的首部或尾部操作數(shù)據(jù)。這些操作使得 LinkedList 可被用作堆棧（Stack）、隊(duì)列（Queue）或雙向隊(duì)列（Deque）。請(qǐng)注意 LinkedList 沒(méi)有同步方法，它不是線程同步的，即如果多個(gè)線程同時(shí)訪問(wèn)一個(gè) List，則必須自己實(shí)現(xiàn)訪問(wèn)同步。一種解決方法是在創(chuàng)建 List 時(shí)構(gòu)造一個(gè)同步的 List，方法如
|
1
|
List list = Collections.synchronizedList(new LinkedList(…))； |
ArrayList 類(lèi)
ArrayList 實(shí)現(xiàn)了可變大小的數(shù)組。它允許所有元素，包括 Null。Size、IsEmpty、Get、Set 等方法的運(yùn)行時(shí)間為常數(shù)，但是 Add 方法開(kāi)銷(xiāo)為分?jǐn)偟某?shù)，添加 N 個(gè)元素需要 O(N) 的時(shí)間，其他的方法運(yùn)行時(shí)間為線性。
每個(gè) ArrayList 實(shí)例都有一個(gè)容量（Capacity），用于存儲(chǔ)元素的數(shù)組的大小，這個(gè)容量可隨著不斷添加新元素而自動(dòng)增加。當(dāng)需要插入大量元素時(shí)，在插入前可以調(diào)用 ensureCapacity 方法來(lái)增加 ArrayList 的容量以提高插入效率。和 LinkedList 一樣，ArrayList 也是線程非同步的（unsynchronized）。
ArrayList 提供的主要方法：
1、Boolean add(Object o) 將指定元素添加到列表的末尾；
2、Boolean add(int index,Object element) 在列表中指定位置加入指定元素；
3、Boolean addAll(Collection c) 將指定集合添加到列表末尾；
4、Boolean addAll(int index,Collection c) 在列表中指定位置加入指定集合；
5、Boolean clear() 刪除列表中所有元素；
6、Boolean clone() 返回該列表實(shí)例的一個(gè)拷貝；
7、Boolean contains(Object o) 判斷列表中是否包含元素；
8、Boolean ensureCapacity(int m) 增加列表的容量，如果必須，該列表能夠容納 m 個(gè)元素；
9、Object get(int index) 返回列表中指定位置的元素；
10、Int indexOf(Object elem) 在列表中查找指定元素的下標(biāo)；
11、Int size() 返回當(dāng)前列表的元素個(gè)數(shù)。
Vector 類(lèi)
Vector 非常類(lèi)似于 ArrayList，區(qū)別是 Vector 是線程同步的。由 Vector 創(chuàng)建的 Iterator，雖然和 ArrayList 創(chuàng)建的 Iterator 是同一接口，但是，因?yàn)?Vector 是同步的，當(dāng)一個(gè) Iterator 被創(chuàng)建而且正在被使用，另一個(gè)線程改變了 Vector 的狀態(tài)（例如，添加或刪除了一些元素），這時(shí)調(diào)用 Iterator 的方法時(shí)將拋出 ConcurrentModificationException，因此必須捕獲該異常。
Stack 類(lèi)
Stack 繼承自 Vector，實(shí)現(xiàn)了一個(gè)后進(jìn)先出的堆棧。Stack 提供 5 個(gè)額外的方法使得 Vector 得以被當(dāng)作堆棧使用。除了基本的 Push 和 Pop 方法，還有 Peek 方法得到棧頂?shù)脑兀珽mpty 方法測(cè)試堆棧是否為空，Search 方法檢測(cè)一個(gè)元素在堆棧中的位置。注意，Stack 剛創(chuàng)建后是空棧。
Set 類(lèi)
Set 是一種不包含重復(fù)的元素的 Collection，即任意的兩個(gè)元素 e1 和 e2 都有 e1.equals(e2)=false。Set 最多有一個(gè) null 元素。很明顯，Set 的構(gòu)造函數(shù)有一個(gè)約束條件，傳入的 Collection 參數(shù)不能包含重復(fù)的元素。請(qǐng)注意，必須小心操作可變對(duì)象（Mutable Object），如果一個(gè) Set 中的可變?cè)馗淖兞俗陨頎顟B(tài)，這可能會(huì)導(dǎo)致一些問(wèn)題。
Hashtable 類(lèi)
Hashtable 繼承 Map 接口，實(shí)現(xiàn)了一個(gè)基于 Key-Value 映射的哈希表。任何非空（non-null）的對(duì)象都可作為 Key 或者 Value。添加數(shù)據(jù)使用 Put(Key，Value)，取出數(shù)據(jù)使用 Get(Key)，這兩個(gè)基本操作的時(shí)間開(kāi)銷(xiāo)為常數(shù)。
Hashtable 通過(guò) Initial Capacity 和 Load Factor 兩個(gè)參數(shù)調(diào)整性能。通常缺省的 Load Factor 0.75 較好地實(shí)現(xiàn)了時(shí)間和空間的均衡。增大 Load Factor 可以節(jié)省空間但相應(yīng)的查找時(shí)間將增大，會(huì)影響像 Get 和 Put 這樣的操作。使用 Hashtable 的簡(jiǎn)單示例，將 1、2、3 這三個(gè)數(shù)字放到 Hashtable 里面，他們的 Key 分別是”one”、”two”、”three”，代碼如清單 2 所示。
清單 2 .Hashtable 示例
|
1
2
3
4
|
Hashtable numbers = new Hashtable();numbers.put(“one”, new Integer(1));numbers.put(“two”, new Integer(2));numbers.put(“three”, new Integer(3)); |
如果我們需要取出一個(gè)數(shù)，比如 2，可以用相應(yīng)的 key 來(lái)取出，代碼如清單 3 所示。
清單 3.從 Hastable 讀取數(shù)據(jù)
|
1
2
|
Integer n = (Integer)numbers.get(“two”);System.out.println(“two =”+ n); |
由于作為 Key 的對(duì)象將通過(guò)計(jì)算其散列函數(shù)來(lái)確定與之對(duì)應(yīng)的 Value 的位置，因此任何作為 key 的對(duì)象都必須實(shí)現(xiàn) HashCode 和 Equals 方法。HashCode 和 Equals 方法繼承自根類(lèi) Object，如果你用自定義的類(lèi)當(dāng)作 Key 的話，要相當(dāng)小心，按照散列函數(shù)的定義，如果兩個(gè)對(duì)象相同，即 obj1.equals(obj2)=true，則它們的 HashCode 必須相同，但如果兩個(gè)對(duì)象不同，則它們的 HashCode 不一定不同，如果兩個(gè)不同對(duì)象的 HashCode 相同，這種現(xiàn)象稱(chēng)為沖突，沖突會(huì)導(dǎo)致操作哈希表的時(shí)間開(kāi)銷(xiāo)增大，所以盡量定義好的 HashCode() 方法，能加快哈希表的操作。
如果相同的對(duì)象有不同的 HashCode，對(duì)哈希表的操作會(huì)出現(xiàn)意想不到的結(jié)果（期待的 Get 方法返回 Null），要避免這種問(wèn)題，最好同時(shí)復(fù)寫(xiě) Equals 方法和 HashCode 方法，而不要只寫(xiě)其中一個(gè)。
HashMap 類(lèi)
HashMap 和 Hashtable 類(lèi)似，不同之處在于 HashMap 是線程非同步的，并且允許 Null，即 Null Value 和 Null Key。但是將 HashMap 視為 Collection 時(shí)（values() 方法可返回 Collection），其迭代子操作時(shí)間開(kāi)銷(xiāo)和 HashMap 的容量成比例。因此，如果迭代操作的性能相當(dāng)重要的話，不要將 HashMap 的初始化容量設(shè)得過(guò)高，或者 Load Factor 參數(shù)設(shè)置過(guò)低。
WeakHashMap 類(lèi)
WeakHashMap 是一種改進(jìn)的 HashMap，它對(duì) Key 實(shí)行“弱引用”，如果一個(gè) Key 不再被外部所引用，那么該 Key 可以被 GC 回收。
集合類(lèi)實(shí)踐
ArrayList、Vector、LinkedList 均來(lái)自 AbstractList 的實(shí)現(xiàn)，而 AbstractList 直接實(shí)現(xiàn)了 List 接口，并擴(kuò)展自 AbstarctCollection。ArrayList 和 Vector 使用了數(shù)組實(shí)現(xiàn)，ArrayList 沒(méi)有對(duì)任何一個(gè)方法提供線程同步，因此不是線程安全的，Vector 中絕大部分方法都做了線程同步，是一種線程安全的實(shí)現(xiàn)。LinkedList 使用了循環(huán)雙向鏈表數(shù)據(jù)結(jié)構(gòu)，由一系列表項(xiàng)連接而成，一個(gè)表項(xiàng)總是包含 3 個(gè)部分，元素內(nèi)容、前驅(qū)表項(xiàng)和后驅(qū)表項(xiàng)。
當(dāng) ArrayList 對(duì)容量的需求超過(guò)當(dāng)前數(shù)組的大小時(shí)，需要進(jìn)行擴(kuò)容。擴(kuò)容過(guò)程中，會(huì)進(jìn)行大量的數(shù)組復(fù)制操作，而數(shù)組復(fù)制時(shí)，最終將調(diào)用 System.arraycopy() 方法。LinkedList 由于使用了鏈表的結(jié)構(gòu)，因此不需要維護(hù)容量的大小，然而每次的元素增加都需要新建一個(gè) Entry 對(duì)象，并進(jìn)行更多的賦值操作，在頻繁的系統(tǒng)調(diào)用下，對(duì)性能會(huì)產(chǎn)生一定的影響，在不間斷地生成新的對(duì)象還是占用了一定的資源。而因?yàn)閿?shù)組的連續(xù)性，因此總是在尾端增加元素時(shí)，只有在空間不足時(shí)才產(chǎn)生數(shù)組擴(kuò)容和數(shù)組復(fù)制。
ArrayList 是基于數(shù)組實(shí)現(xiàn)的，而數(shù)組是一塊連續(xù)的內(nèi)存空間，如果在數(shù)組的任意位置插入元素，必然導(dǎo)致在該位置后的所有元素需要重新排列，因此其效率較差，盡可能將數(shù)據(jù)插入到尾部。LinkedList 不會(huì)因?yàn)椴迦霐?shù)據(jù)導(dǎo)致性能下降。
ArrayList 的每一次有效的元素刪除操作后都要進(jìn)行數(shù)組的重組，并且刪除的元素位置越靠前，數(shù)組重組時(shí)的開(kāi)銷(xiāo)越大，要?jiǎng)h除的元素位置越靠后，開(kāi)銷(xiāo)越小。LinkedList 要移除中間的數(shù)據(jù)需要便利完半個(gè) List。
清單 4. ArrayList 和 LinkedList 使用代碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
import java.util.ArrayList;import java.util.LinkedList; public class ArrayListandLinkedList { public static void main(String[] args){ long start = System.currentTimeMillis(); ArrayList list = new ArrayList(); Object obj = new Object(); for(int i=0;i<5000000;i++){ list.add(obj); } long end = System.currentTimeMillis(); System.out.println(end-start); start = System.currentTimeMillis(); LinkedList list1 = new LinkedList(); Object obj1 = new Object(); for(int i=0;i<5000000;i++){ list1.add(obj1); } end = System.currentTimeMillis(); System.out.println(end-start); start = System.currentTimeMillis(); Object obj2 = new Object(); for(int i=0;i<1000;i++){ list.add(0,obj2); } end = System.currentTimeMillis(); System.out.println(end-start); start = System.currentTimeMillis(); Object obj3 = new Object(); for(int i=0;i<1000;i++){ list1.add(obj1); } end = System.currentTimeMillis(); System.out.println(end-start); start = System.currentTimeMillis(); list.remove(0); end = System.currentTimeMillis(); System.out.println(end-start); start = System.currentTimeMillis(); list1.remove(250000); end = System.currentTimeMillis(); System.out.println(end-start); }} |
清單 5. 運(yùn)行輸出
|
1
2
3
4
5
6
|
639129669690015 |
HashMap 是將 Key 做 Hash 算法，然后將 Hash 值映射到內(nèi)存地址，直接取得 Key 所對(duì)應(yīng)的數(shù)據(jù)。在 HashMap 中，底層數(shù)據(jù)結(jié)構(gòu)使用的是數(shù)組，所謂的內(nèi)存地址即數(shù)組的下標(biāo)索引。HashMap 的高性能需要保證以下幾點(diǎn)：
1、Hash 算法必須是高效的；
2、Hash 值到內(nèi)存地址 (數(shù)組索引) 的算法是快速的；
3、根據(jù)內(nèi)存地址 (數(shù)組索引) 可以直接取得對(duì)應(yīng)的值。
HashMap 實(shí)際上是一個(gè)鏈表的數(shù)組。前面已經(jīng)介紹過(guò)，基于 HashMap 的鏈表方式實(shí)現(xiàn)機(jī)制，只要 HashCode() 和 Hash() 方法實(shí)現(xiàn)得足夠好，能夠盡可能地減少?zèng)_突的產(chǎn)生，那么對(duì) HashMap 的操作幾乎等價(jià)于對(duì)數(shù)組的隨機(jī)訪問(wèn)操作，具有很好的性能。但是，如果 HashCode() 或者 Hash() 方法實(shí)現(xiàn)較差，在大量沖突產(chǎn)生的情況下，HashMap 事實(shí)上就退化為幾個(gè)鏈表，對(duì) HashMap 的操作等價(jià)于遍歷鏈表，此時(shí)性能很差。
HashMap 的一個(gè)功能缺點(diǎn)是它的無(wú)序性，被存入到 HashMap 中的元素，在遍歷 HashMap 時(shí)，其輸出是無(wú)序的。如果希望元素保持輸入的順序，可以使用 LinkedHashMap 替代。
LinkedHashMap 繼承自 HashMap，具有高效性，同時(shí)在 HashMap 的基礎(chǔ)上，又在內(nèi)部增加了一個(gè)鏈表，用以存放元素的順序。
HashMap 通過(guò) hash 算法可以最快速地進(jìn)行 Put() 和 Get() 操作。TreeMap 則提供了一種完全不同的 Map 實(shí)現(xiàn)。從功能上講，TreeMap 有著比 HashMap 更為強(qiáng)大的功能，它實(shí)現(xiàn)了 SortedMap 接口，這意味著它可以對(duì)元素進(jìn)行排序。TreeMap 的性能略微低于 HashMap。如果在開(kāi)發(fā)中需要對(duì)元素進(jìn)行排序，那么使用 HashMap 便無(wú)法實(shí)現(xiàn)這種功能，使用 TreeMap 的迭代輸出將會(huì)以元素順序進(jìn)行。LinkedHashMap 是基于元素進(jìn)入集合的順序或者被訪問(wèn)的先后順序排序，TreeMap 則是基于元素的固有順序 (由 Comparator 或者 Comparable 確定)。
LinkedHashMap 是根據(jù)元素增加或者訪問(wèn)的先后順序進(jìn)行排序，而 TreeMap 則根據(jù)元素的 Key 進(jìn)行排序。
清單 6 所示代碼演示了使用 TreeMap 實(shí)現(xiàn)業(yè)務(wù)邏輯的排序。
清單 6. TreeMap 實(shí)現(xiàn)排序
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
import java.util.Iterator;import java.util.Map;import java.util.TreeMap; public class Student implements Comparable<Student>{ public String name;public int score;public Student(String name,int score){this.name = name;this.score = score;} @Override//告訴 TreeMap 如何排序public int compareTo(Student o) {// TODO Auto-generated method stubif(o.score<this.score){return 1;}else if(o.score>this.score){return -1;}return 0;} @Overridepublic String toString(){StringBuffer sb = new StringBuffer();sb.append("name:");sb.append(name);sb.append(" ");sb.append("score:");sb.append(score);return sb.toString();} public static void main(String[] args){TreeMap map = new TreeMap();Student s1 = new Student("1",100);Student s2 = new Student("2",99);Student s3 = new Student("3",97);Student s4 = new Student("4",91);map.put(s1, new StudentDetailInfo(s1));map.put(s2, new StudentDetailInfo(s2));map.put(s3, new StudentDetailInfo(s3));map.put(s4, new StudentDetailInfo(s4)); //打印分?jǐn)?shù)位于 S4 和 S2 之間的人Map map1=((TreeMap)map).subMap(s4, s2);for(Iterator iterator=map1.keySet().iterator();iterator.hasNext();){Student key = (Student)iterator.next();System.out.println(key+"->"+map.get(key));}System.out.println("subMap end"); //打印分?jǐn)?shù)比 s1 低的人map1=((TreeMap)map).headMap(s1);for(Iterator iterator=map1.keySet().iterator();iterator.hasNext();){Student key = (Student)iterator.next();System.out.println(key+"->"+map.get(key));}System.out.println("subMap end"); //打印分?jǐn)?shù)比 s1 高的人map1=((TreeMap)map).tailMap(s1);for(Iterator iterator=map1.keySet().iterator();iterator.hasNext();){Student key = (Student)iterator.next();System.out.println(key+"->"+map.get(key));}System.out.println("subMap end");} } class StudentDetailInfo{Student s;public StudentDetailInfo(Student s){this.s = s;}@Overridepublic String toString(){return s.name + "'s detail information";}} |
清單 7 .運(yùn)行輸出
|
1
2
3
4
5
6
7
8
9
|
name:4 score:91->4's detail informationname:3 score:97->3's detail informationsubMap endname:4 score:91->4's detail informationname:3 score:97->3's detail informationname:2 score:99->2's detail informationsubMap endname:1 score:100->1's detail informationsubMap end |
WeakHashMap 特點(diǎn)是當(dāng)除了自身有對(duì) Key 的引用外，如果此 Key 沒(méi)有其他引用，那么此 Map 會(huì)自動(dòng)丟棄該值。如清單 8 所示代碼聲明了兩個(gè) Map 對(duì)象，一個(gè)是 HashMap，一個(gè)是 WeakHashMap，同時(shí)向兩個(gè) map 中放入 A、B 兩個(gè)對(duì)象，當(dāng) HashMap 刪除 A，并且 A、B 都指向 Null 時(shí)，WeakHashMap 中的 A 將自動(dòng)被回收掉。出現(xiàn)這個(gè)狀況的原因是，對(duì)于 A 對(duì)象而言，當(dāng) HashMap 刪除并且將 A 指向 Null 后，除了 WeakHashMap 中還保存 A 外已經(jīng)沒(méi)有指向 A 的指針了，所以 WeakHashMap 會(huì)自動(dòng)舍棄掉 a，而對(duì)于 B 對(duì)象雖然指向了 null，但 HashMap 中還有指向 B 的指針，所以 WeakHashMap 將會(huì)保留 B 對(duì)象。
清單 8.WeakHashMap 示例代碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
|
import java.util.HashMap;import java.util.Iterator;import java.util.Map;import java.util.WeakHashMap; public class WeakHashMapTest { public static void main(String[] args) throws Exception { String a = new String("a"); String b = new String("b"); Map weakmap = new WeakHashMap(); Map map = new HashMap(); map.put(a, "aaa"); map.put(b, "bbb"); weakmap.put(a, "aaa"); weakmap.put(b, "bbb"); map.remove(a); a=null; b=null; System.gc(); Iterator i = map.entrySet().iterator(); while (i.hasNext()) { Map.Entry en = (Map.Entry)i.next(); System.out.println("map:"+en.getKey()+":"+en.getValue()); } Iterator j = weakmap.entrySet().iterator(); while (j.hasNext()) { Map.Entry en = (Map.Entry)j.next(); System.out.println("weakmap:"+en.getKey()+":"+en.getValue()); } }} |
清單 9 .運(yùn)行輸出
|
1
2
|
map:b:bbbweakmap:b:bbb |
WeakHashMap 主要通過(guò) expungeStaleEntries 這個(gè)函數(shù)來(lái)實(shí)現(xiàn)移除其內(nèi)部不用的條目，從而達(dá)到自動(dòng)釋放內(nèi)存的目的。基本上只要對(duì) WeakHashMap 的內(nèi)容進(jìn)行訪問(wèn)就會(huì)調(diào)用這個(gè)函數(shù)，從而達(dá)到清除其內(nèi)部不再為外部引用的條目。但是如果預(yù)先生成了 WeakHashMap，而在 GC 以前又不曾訪問(wèn)該 WeakHashMap, 那不是就不能釋放內(nèi)存了嗎？
清單 10. WeakHashMapTest1
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
import java.util.ArrayList;import java.util.List;import java.util.WeakHashMap; public class WeakHashMapTest1 { public static void main(String[] args) throws Exception { List<WeakHashMap<byte[][], byte[][]>> maps = new ArrayList<WeakHashMap<byte[][], byte[][]>>(); for (int i = 0; i < 1000; i++) { WeakHashMap<byte[][], byte[][]> d = new WeakHashMap<byte[][], byte[][]>(); d.put(new byte[1000][1000], new byte[1000][1000]); maps.add(d); System.gc(); System.err.println(i); } }} |
不改變?nèi)魏?JVM 參數(shù)的情況運(yùn)行清單 10 所示代碼，由于 Java 默認(rèn)內(nèi)存是 64M，拋出內(nèi)存溢出了錯(cuò)誤。
清單 11. 運(yùn)行輸出
|
1
2
3
4
5
6
7
8
|
241242243Exception in thread "main" java.lang.OutOfMemoryError: Java heap spaceat WeakHashMapTest1.main(WeakHashMapTest1.java:10) |
果不其然，WeakHashMap 這個(gè)時(shí)候并沒(méi)有自動(dòng)幫我們釋放不用的內(nèi)存。清單 12 所示代碼不會(huì)出現(xiàn)內(nèi)存溢出問(wèn)題。
清單 12. WeakHashMapTest2
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
import java.util.ArrayList;import java.util.List;import java.util.WeakHashMap; public class WeakHashMapTest2 { public static void main(String[] args) throws Exception { List<WeakHashMap<byte[][], byte[][]>> maps = new ArrayList<WeakHashMap<byte[][], byte[][]>>(); for (int i = 0; i < 1000; i++) { WeakHashMap<byte[][], byte[][]> d = new WeakHashMap<byte[][], byte[][]>(); d.put(new byte[1000][1000], new byte[1000][1000]); maps.add(d); System.gc(); System.err.println(i); for (int j = 0; j < i; j++) { System.err.println(j + " size" + maps.get(j).size()); } } }} |
運(yùn)行結(jié)果發(fā)現(xiàn)這次測(cè)試輸出正常, 不再出現(xiàn)內(nèi)存溢出問(wèn)題。
總的來(lái)說(shuō)，WeakHashMap 并不是你什么也干它就能自動(dòng)釋放內(nèi)部不用的對(duì)象的，而是在你訪問(wèn)它的內(nèi)容的時(shí)候釋放內(nèi)部不用的對(duì)象。
WeakHashMap 實(shí)現(xiàn)弱引用，是因?yàn)樗?Entry<K,V>是繼承自 WeakReference<K>的，
在 WeakHashMap$Entry<K,V>的類(lèi)定義及構(gòu)造函數(shù)里面如清單 13 所示。
清單13. WeakHashMap 類(lèi)定義
|
1
2
3
4
5
6
7
|
private static class Entry<K,V> extends WeakReference<K>implements Map.Entry<K,V> Entry(K key, V value, ReferenceQueue<K> queue,int hash, Entry<K,V> next) {super(key, queue);this.value = value;this.hash = hash;this.next = next;} |
請(qǐng)注意它構(gòu)造父類(lèi)的語(yǔ)句：“super(key, queue);”，傳入的是 Key，因此 Key 才是進(jìn)行弱引用的，Value 是直接強(qiáng)引用關(guān)聯(lián)在 this.value 之中。在 System.gc() 時(shí)，Key 中的 Byte 數(shù)組進(jìn)行了回收，而 Value 依然保持 (Value 被強(qiáng)關(guān)聯(lián)到 Entry 上，Entry 又關(guān)聯(lián)在 Map 中，Map 關(guān)聯(lián)在 ArrayList 中)。
For 循環(huán)中每次都 New 一個(gè)新的 WeakHashMap，在 Put 操作后，雖然 GC 將 WeakReference 的 Key 中的 Byte 數(shù)組回收了，并將事件通知到了 ReferenceQueue，但后續(xù)卻沒(méi)有相應(yīng)的動(dòng)作去觸發(fā) WeakHashMap 去處理 ReferenceQueue，所以 WeakReference 包裝 Key 依然存在于 WeakHashMap 中，其對(duì)應(yīng)的 value 也當(dāng)然存在。
那 value 是何時(shí)被清除的呢? 對(duì)清單 10 和清單 11 兩個(gè)示例程序進(jìn)行分析可知，清單 11 的 maps.get(j).size() 觸發(fā)了 Value 的回收，那又如何觸發(fā)的呢？查看 WeakHashMap 源碼可知,Size 方法調(diào)用了 expungeStaleEntries 方法，該方法對(duì) JVM 要回收的的 Entry(Quene 中) 進(jìn)行遍歷，并將 Entry 的 Value 置空，回收了內(nèi)存。所以效果是 Key 在 GC 的時(shí)候被清除，Value 在 Key 清除后訪問(wèn) WeakHashMap 被清除。
WeakHashMap 類(lèi)是線程不同步的，可以使用 Collections.synchronizedMap 方法來(lái)構(gòu)造同步的 WeakHashMap, 每個(gè)鍵對(duì)象間接地存儲(chǔ)為一個(gè)弱引用的指示對(duì)象。因此，不管是在映射內(nèi)還是在映射之外，只有在垃圾回收器清除某個(gè)鍵的弱引用之后，該鍵才會(huì)自動(dòng)移除。需要注意的是，WeakHashMap 中的值對(duì)象由普通的強(qiáng)引用保持。因此應(yīng)該小心謹(jǐn)慎，確保值對(duì)象不會(huì)直接或間接地強(qiáng)引用其自身的鍵，因?yàn)檫@會(huì)阻止鍵的丟棄。注意，值對(duì)象可以通過(guò) WeakHashMap 本身間接引用其對(duì)應(yīng)的鍵，這就是說(shuō)，某個(gè)值對(duì)象可能強(qiáng)引用某個(gè)其他的鍵對(duì)象，而與該鍵對(duì)象相關(guān)聯(lián)的值對(duì)象轉(zhuǎn)而強(qiáng)引用第一個(gè)值對(duì)象的鍵。
處理此問(wèn)題的一種方法是，在插入前將值自身包裝在 WeakReferences 中，如：m.put(key, new WeakReference(value))，然后，分別用 get 進(jìn)行解包，該類(lèi)所有“collection 視圖方法”返回的迭代器均是快速失敗的，在迭代器創(chuàng)建之后，如果從結(jié)構(gòu)上對(duì)映射進(jìn)行修改，除非通過(guò)迭代器自身的 Remove 或 Add 方法，其他任何時(shí)間任何方式的修改，迭代器都將拋出 ConcurrentModificationException。因此，面對(duì)并發(fā)的修改，迭代器很快就完全失敗，而不是冒著在將來(lái)不確定的時(shí)間任意發(fā)生不確定行為的風(fēng)險(xiǎn)。
注意，我們不能確保迭代器不失敗，一般來(lái)說(shuō)，存在不同步的并發(fā)修改時(shí)，不可能做出任何完全確定的保證。
總結(jié)
綜合前面的介紹和實(shí)例代碼，我們可以知道，如果涉及到堆棧、隊(duì)列等操作，應(yīng)該考慮用 List。對(duì)于需要快速插入、刪除元素等操作，應(yīng)該使用 LinkedList。如果需要快速隨機(jī)訪問(wèn)元素，應(yīng)該使用 ArrayList。如果程序在單線程環(huán)境中，或者訪問(wèn)僅僅在一個(gè)線程中進(jìn)行，考慮非同步的類(lèi)，其效率較高。如果多個(gè)線程可能同時(shí)操作一個(gè)類(lèi)，應(yīng)該使用同步的類(lèi)。要特別注意對(duì)哈希表的操作，作為 Key 的對(duì)象要正確復(fù)寫(xiě) Equals 和 HashCode 方法。盡量返回接口而非實(shí)際的類(lèi)型，如返回 List 而非 ArrayList，這樣如果以后需要將 ArrayList 換成 LinkedList 時(shí)，客戶(hù)端代碼不用改變，這就是針對(duì)抽象進(jìn)行編程思想。
本文只是針對(duì)應(yīng)用層面的分享，希望對(duì)大家優(yōu)化Java集合類(lèi)操作有所幫助。
