Java 容器源碼分析之集合類詳解

集合類說明及差別

Collection ├List │├LinkedList │├ArrayList │└Vector │　└Stack └Set Map ├Hashtable ├HashMap └WeakHashMap

Collection 接口

Collection 是最基本的集合接口，一個 Collection 代表一組 Object，即 Collection 的元素（Elements）。一些 Collection 允許相同的元素而另一些不行。一些能排序而另一些不行。Java SDK 不提供直接繼承自 Collection 的類，Java SDK 提供的類都是繼承自 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。

List 接口

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

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

LinkedList 類

　　 LinkedList 實作了 List 接口，允許 null 元素。此外 LinkedList 提供額外的 get，remove，insert 方法在 LinkedList 的首部或尾部。這些操作使 LinkedList 可被用作堆棧（stack），隊列（queue）或雙向隊列（deque）。 　　 注意 LinkedList 沒有同步方法。如果多個線程同時通路一個 List，則必須自己實作通路同步。一種解決方法是在建立 List 時構造一個同步的 List： 　　　　

List list = Collections.synchronizedList(new LinkedList(...));           

ArrayList 類

　　 ArrayList 實作了可變大小的數組。它允許所有元素，包括 null。ArrayList 沒有同步。 size，isEmpty，get，set 方法運作時間為常數。但是 add 方法開銷為分攤的常數，添加 n 個元素需要 O(n)的時間。其他的方法運作時間為線性。 　　 每個 ArrayList 執行個體都有一個容量（Capacity），即用于存儲元素的數組的大小。這個容量可随着不斷添加新元素而自動增加，但是增長算法 并沒有定義。當需要插入大量元素時，在插入前可以調用 ensureCapacity 方法來增加 ArrayList 的容量以提高插入效率。 　　 和 LinkedList 一樣，ArrayList 也是非同步的（unsynchronized）。

Vector 類

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

Stack 類

　　 Stack 繼承自 Vector，實作一個後進先出的堆棧。Stack 提供5個額外的方法使得 Vector 得以被當作堆棧使用。基本的 push 和 pop 方法，還有 peek 方法得到棧頂的元素，empty 方法測試堆棧是否為空，search 方法檢測一個元素在堆棧中的位置。Stack 剛建立後是空棧。

Set 接口

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

Map 接口

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

Hashtable 類

　　 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”：

　　　　Hashtable numbers = new Hashtable();
　　　　numbers.put(“one”, new Integer(1));
　　　　numbers.put(“two”, new Integer(2));
　　　　numbers.put(“three”, new Integer(3));           

要取出一個數，比如2，用相應的 key：

　　　　Integer n = (Integer)numbers.get(“two”);
　　　　System.out.println(“two = ” + n);           

由于作為 key 的對象将通過計算其散列函數來确定與之對應的 value 的位置，是以任何作為 key的對象都必須實作 hashCode 和 equals 方法。hashCode 和 equals 方法繼承自根類 Object，如果你用自定義的類當作 key 的話，要相當小心，按照散列函數的定義，如果兩個對象相同，即 obj1.equals(obj2)=true，則它們的 hashCode 必須相同，但如果兩個對象不同，則它們的 hashCode 不一定不同，如果兩個不同對象的 hashCode 相同，這種現象稱為沖突，沖突會導緻操作哈希表的時間開銷增大，是以盡量定義好的 hashCode()方法，能加快哈希表的操作。 　　 如果相同的對象有不同的 hashCode，對哈希表的操作會出現意想不到的結果（期待的 get 方法傳回 null），要避免這種問題，隻需要牢記一條：要同時複寫 equals 方法和 hashCode 方法，而不要隻寫其中一個。

Hashtable 是同步的。

HashMap 類

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

WeakHashMap 類

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

總結

　　 如果涉及到堆棧，隊列等操作，應該考慮用 List，對于需要快速插入，删除元素，應該使用LinkedList，如果需要快速随機通路元素，應該使用 ArrayList。 　　 如果程式在單線程環境中，或者通路僅僅在一個線程中進行，考慮非同步的類，其效率較高，如果多個線程可能同時操作一個類，應該使用同步的類。 　　 要特别注意對哈希表的操作，作為 key 的對象要正确複寫 equals 和 hashCode 方法。 　　 盡量傳回接口而非實際的類型，如傳回 List 而非 ArrayList，這樣如果以後需要将 ArrayList換成 LinkedList 時，用戶端代碼不用改變。這就是針對抽象程式設計。

同步性

Vector 是同步的。這個類中的一些方法保證了 Vector 中的對象是線程安全的。而 ArrayList 則是異步的，是以 ArrayList 中的對象并不是線程安全的。因為同步的要求會影響執行的效率，是以如果你不需要線程安全的集合那麼使用 ArrayList 是一個很好的選擇，這樣可以避免由于同步帶來的不必要的性能開銷。

資料增長

從内部實作機制來講 ArrayList 和 Vector 都是使用數組(Array)來控制集合中的對象。當你向這兩種類型中增加元素的時候，如果元素的數目 超出了内部數組目前的長度它們都需要擴充内部數組的長度，Vector 預設情況下自動增長原來一倍的數組長度，ArrayList 是原來的50%,是以最 後你獲得的這個集合所占的空間總是比你實際需要的要大。是以如果你要在集合中儲存大量的資料那麼使用 Vector 有一些優勢，因為你可以通過設定集合的初 始化大小來避免不必要的資源開銷。

使用模式

在 ArrayList 和 Vector 中，從一個指定的位置（通過索引）查找資料或是在集合的末尾增加、移除一個元素所花費的時間是一樣的，這個時間我們用 O(1)表示。但是，如果在集合的其他位置增加或移除元素那麼花費的時間會呈線形增長：O(n-i)，其中 n 代表集合中元素的個數，i 代表元素增加或移除元素的索引位置。為什麼會這樣呢？以為在進行上述操作的時候集合中第 i 和第 i 個元素之後的所有元素都要執行位移的操作。這一切意味着什麼呢？

這意味着，你隻是查找特定位置的元素或隻在集合的末端增加、移除元素，那麼使用 Vector 或ArrayList 都可以。如果是其他操作，你最好選擇其他的集合操作類。比如，LinkList 集合類在增加或移除集合中任何位置的元素所花費的時間都是一樣的?O(1)，但它在索引一個元素的使用缺比較慢 －O(i),其中 i 是索引的位置.使用 ArrayList 也很容易，因為你可以簡單的使用索引來代替建立 iterator 對象的操作。LinkList 也會為每個插入的元素建立對象，所有你要明白它也會帶來額外的開銷。

最後，在《Practical Java》一書中 Peter Haggar 建議使用一個簡單的數組（Array）來代替 Vector 或 ArrayList。尤其是對于執行效率要求高的程式更應如此。因為使用數組 (Array)避免了同步、額外的方法調用和不必要的重新配置設定空間的操作。

互相差別

Vector 和 ArrayList

1，vector 是線程同步的，是以它也是線程安全的，而 arraylist 是線程異步的，是不安全的。如果不考慮到線程的安全因素，一般用 arraylist 效率比較高。

2，如果集合中的元素的數目大于目前集合數組的長度時，vector 增長率為目前數組長度的100%,而 arraylist 增長率為目前數組長度的50%.如過在集合中使用資料量比較大的資料，用 vector 有一定的優勢。

3，如果查找一個指定位置的資料，vector 和 arraylist 使用的時間是相同的，都是0(1),這個時候使用 vector 和 arraylist 都可以。而如果移動一個指定位置的資料花費的時間為 0(n-i)n 為總長度，這個時候就應該考慮到使用 linklist,因為它移動一個指定位置的資料所花費的時間為 0(1),而查詢一個指定位置的資料時花費的時間為 0(i)。

ArrayList 和 Vector 是采用數組方式存儲資料，此數組元素數大于實際存儲的資料以便增加和插入元素，都允許直接序号索引元素，但是插入資料要設計到數組元素移動 等記憶體操作，是以索引資料快插入資料慢，Vector 由于使用了 synchronized 方法（線程安全）是以性能上比ArrayList 要差，LinkedList 使用雙向連結清單實作存儲，按序号索引資料需要進行向前或向後周遊，但是插入資料時隻需要記錄本項的前後項即可，是以插入數度較快！

arraylist 和 linkedlist

1.ArrayList 是實作了基于動态數組的資料結構，LinkedList 基于連結清單的資料結構。 2.對于随機通路 get 和 set，ArrayList 覺得優于 LinkedList，因為 LinkedList 要移動指針。 3.對于新增和删除操作 add 和 remove，LinedList 比較占優勢，因為 ArrayList 要移動資料。 這一點要看實際情況的。若隻對單條資料插入或删除，ArrayList 的速度反而優于 LinkedList。但若是批量随機的插入删除資料，LinkedList 的速度大大優于 ArrayList. 因為 ArrayList 每插入一條資料，要移動插入點及之後的所有資料。

HashMap 與 TreeMap

(注) 文章出處：http://www.diybl.com/course/3_program/java/javaxl/200875/130233.html

1、HashMap 通過 hashcode 對其内容進行快速查找，而 TreeMap 中所有的元素都保持着某種固定的順序，如果你需要得到一個有序的結果你就應該使用 TreeMap（HashMap 中元素的排列順序是不固定的）。

HashMap 中元素的排列順序是不固定的）。

2、HashMap 通過 hashcode 對其内容進行快速查找，而 TreeMap 中所有的元素都保持着某種固定的順序，如果你需要得到一個有序的結果你就應該使用 TreeMap（HashMap 中元素的排列順序是不固定的）。集合架構”提供兩種正常的 Map 實作：HashMap 和 TreeMap (TreeMap 實作SortedMap 接口)。

3、在 Map 中插入、删除和定位元素，HashMap 是最好的選擇。但如果您要按自然順序或自定義順序周遊鍵，那麼 TreeMap 會更好。使用 HashMap 要求添加的鍵類明确定義了 hashCode()和 equals()的實作。　　這個 TreeMap 沒有調優選項，因為該樹總處于平衡狀态。

結過研究，在原作者的基礎上我還發現了一點，二樹 map 一樣，但順序不一樣，導緻 hashCode()不一樣。 同樣做測試： 在 hashMap 中，同樣的值的 map,順序不同，equals 時，false; 而在 treeMap 中，同樣的值的 map,順序不同,equals 時，true，說明，treeMap 在 equals()時是整理了順序了的。

hashtable 與 hashmap

一.曆史原因:Hashtable 是基于陳舊的 Dictionary 類的，HashMap 是 Java 1.2 引進的 Map 接口的一個實作

二.同步性:Hashtable 是線程安全的，也就是說是同步的，而 HashMap 是線程式不安全的，不是同步的

三.值：隻有 HashMap 可以讓你将空值作為一個表的條目的 key 或 value

熬夜不易,點選請老王喝杯烈酒！！！！！！！