一、類庫結構圖概覽

容器對象僅能持有對象引用(對象的指針)，而不是Copy對象信息，從網上搜得幾張Java中集合類庫的結構圖，如下所示：

?

二、解說Collection

2.1 Collection

　　（1）Collection是最基本的集合接口，由Collection接口派生的兩個接口是List和Set。JDK提供的類都繼承自Collection的“子接口”，如List和Set。

　　（2）所有實現Collection接口的類都必須提供兩個標準的構造函數：無參數的構造函數和有一個Collection參數的構造函數。前者用于創建一個空的Collection，后者用于創建一個新的Collection，允許用戶復制一個Collection。

　　（3）不論Collection的實際類型如何，它都支持一個iterator()的方法，該方法返回一個迭代子，可逐一訪問Collection中每一個元素。用法如下：

Iterator it = collection.iterator(); // 獲得一個迭代子 while(it.hasNext()) {Object obj = it.next(); // 得到下一個元素 }

?

2.2 Collection和Map區別：

（1）Collection類型，每個位置只有一個元素。

（2）Map類型，持有key-value形式的數據（鍵值對），即其元素是成對的對象。

?

三、細說List、Set、Map

3.1 List：以某種插入順序來維護元素順序，另外元素可以重復。

　　　　ArrayList：是用數組來實現的，讀取速度快，插入與刪除速度慢（因為插入與刪除時要移動后面的元素），適合于隨機訪問。ArrayList初始化時不可指定容量，如果以new ArrayList()方式創建時，初始容量為10個；如果以new ArrayList(Collection c)初始化時，容量為c.size()*1.1，即增加10%的容量。當向ArrayList中添加一個元素時，先進行容器的容量調整，如果容量不夠時，則增加至原來的1.5倍加1，再然后把元素加入到容器中，即以原始容量的0.5倍比率增加。

　　　　LinkedList：是用雙向鏈表來實現的，刪除與插入速度快，讀取速度較慢，因為它讀取時是從頭向尾或從尾向頭查找元素，適合于元素的插入與刪除操作。

　　　　Vector：功能與ArrayList幾乎相同，也是用數組來實現的，其添加、刪除等都是基于線程同步的。當一個Iterator正在被使用，如果另一個線程改變了Vector的狀態，這時將拋出ConcurrentModificationException異常，因此必須捕獲該異常。Vector初始化時可以設定容量，如果以new Vector()方式創建，則其初始容量為10，超過容量時以2倍容量增加；如果以new Vector(Collection c)方式創建，則其初始容量為c.size()*1.1，超過時以2倍容量增加；如果以new Vector(int initialCapacity, int capacityIncrement)，則以capacityIncrement容量單位增加。

　　　　Stack：Stack繼承自Vector，實現一個后進先出的堆棧，線程同步。

?

3.2 Set：Set接口不保證維護元素的次序，隨機訪問不具有意義（List或數組具備隨機訪問性質），存入Set的每個元素必須是唯一的（即元素不可重復），也就是說加入Set的Object必須定義equals()方法以確保對象的唯一性。

　　　　HashSet：HashSet是最常用的，其查詢速度最快（采用散列函數），存入HashSet的對象必須定義hashCode()方法，因為其內部以HashMap來實現，?它不保證集合的迭代順序，特別是它不保證該順序恒久不變。此類允許使用?null元素，其實現不是同步的。

　　　　LinkedHashSet：繼承了HashSet，其內部使用LinkedHashMap實現（使用鏈表維護元素的順序(哈希函數+鏈表)），在使用迭代器遍歷LinkedHashSet時，結果會按元素插入的次序顯示。

　　　　TreeSet：TreeSet實現了SortedSet接口，其內部以TreeMap來實現，生成一個總是處于排序狀態的Set。

?

3.3 Map：Map提供的不是對象與數組的關聯，而是對象和對象的關聯。

　　　　TreeMap：鍵以某種排序規則排序，其內部以red-black（紅-黑）樹數據結構來實現，實現了SortedMap接口

　　　　HashMap:?HashMap是以哈希表數據結構來實現的，查找對象時通過哈希函數計算其位置，它是為快速查詢而設計的，其內部定義了一個hash表數組（Entry[] table），元素會通過哈希轉換函數將元素的哈希地址轉換成數組中存放的索引，如果有沖突，則使用散列鏈表的形式將所有相同哈希地址的元素串起來。

　　　　LinkedHashMap：繼承HashMap，其內部實體LinkedHashMap.Entry繼承自HashMap.Entry，LinkedHashMap.Entry在HashMap.Entry的基礎上新增了兩個實體引用（Entry before, after），這樣實體可以相互串鏈起來形成鏈，并且在LinkedHashMap中定義了一個頭節點（Entry header）用來指向循環雙向鏈的第一個元素（通過after指向）與最后一個元素（通過before指向）。在添加一個元素時，先通過父類HashMap將元素加入到hash表數組里，然后再在鏈尾（header.before指向位置）添加（當然這一過程只是調整LinkedHashMap.Entry對象內部的before、after而已，并不是創建一個新的鏈表結構向里加）；刪除一個元素時，先從hash表數組中刪除，再將被刪除的元素徹底的從雙向鏈中斷開，其實在鏈中添加與刪除操作與LinkedList是一樣的。

　　　　WeakHashMap：WeakHashMap是一種改進的HashMap，若一個key不再被外部所引用，那么該key可以被GC回收。

　　　　Hashtable：Hashtable是以哈希表數據結構來實現的，解決沖突時與HashMap一樣，也是采用了散列鏈表的形式，不過性能比HashMap要低。

?

3.4 集合中的鍵值是否允許為null

（1）List：可以有多個null。

（2）HashSet：能插入一個null（其內部以HashMap實現?），忽略重復元素（即不插入重復元素）。

（3）TreeSet：不能插入null?（其內部以TreeMap?實現?）?，且元素不能重復，如果待插入的元素已經存在，則不插入。

（4）HashMap：允許一個null鍵與多個null值；若鍵重復，則覆蓋以前值。

（5）HashTable：不允許null鍵與null值(否則運行進報空指針異常)；若鍵重復，則覆蓋以前值。

?（6）TreeMap：不允許null鍵(實際上可以插入一個null鍵，如果這個Map里只有一個元素是不會報錯的，因為一個元素時沒有排序操作，也就不會報空指針異常，但如果插入第二個時就會立即報錯)，但允許多個null值；若鍵重復，則覆蓋以前值。

?

此處看一個HashMap的簡單示例：若鍵重復，則覆蓋以前值

package com.test;import java.util.*;public class Test {public static void main(String[] args) {Map map = new HashMap();map.put("Rajib Sarma", "100");map.put("Rajib Sarma", "200");// The value "100" is replaced by "200".map.put("Sazid Ahmed", "200");Iterator iter = map.entrySet().iterator();while (iter.hasNext()) {Map.Entry entry = (Map.Entry) iter.next();Object key = entry.getKey();Object val = entry.getValue();System.out.println(key);System.out.println(val);}} }

結果如下：

Sazid Ahmed 200 Rajib Sarma 200

?

四、應用場景

4.1 對List的選擇

（1）對于隨機查詢與迭代遍歷操作，數組比所有的容器都要快。

（2）從中間的位置插入和刪除元素，LinkedList要比ArrayList快，特別是刪除操作。

（3）Vector通常不如ArrayList快，且應該避免使用，它目前仍然存在于類庫中的原因是為了支持過去的代碼。

（4）最佳實踐：將ArrayList作為默認首選，只有當程序的性能因經常從list中間進行插入和刪除而變差的時候才去選擇LinkedList。當然了，如果只是使用固定數量的元素，就應該選擇數組了。

?

4.2 對Set的選擇

（1）HashSet的性能總比TreeSet好(特別是最常用的添加和查找元素操作)。

（2）TreeSet存在的唯一原因是，它可以維持元素的排序狀態，所以只有當你需要一個排好序的Set時，才應該使用TreeSet。

（3）對于插入操作，LinkedHashSet比HashSet略微慢一點：這是由于維護鏈表所帶來額外開銷造成的。不過，因為有了鏈表，遍歷LinkedHashSet會比HashSet更快。

?

4.3 對Map的選擇

（1）HashMap和Hashtable的效率大致相同(通常HashMap更快一點，所以HashMap有意取代Hashtable)。

（2）TreeMap通常比HashMap慢，因為要維護排序。

（3）HashMap正是為快速查詢而設計的。

（4）LinkedHashMap比HashMap慢一點，因為它維護散列數據結構的同時還要維護鏈表。

?

五、Iterator

http://blog.csdn.net/chenssy/article/details/37521461

5.1 Iterator對ArrayList(LinkedList)的操作限制

（1）剛實例化的迭代器如果還沒有進行后移操作(next)是不能馬上進行刪除與修改操作的。

（2）進行添加操作后是不能立即進行刪除與修改操作的。

（3）進行刪除操作后可以進行添加，但不能進行修改操作。

（4）進行修改后是可以立即進行刪除與添加操作的。

（5）可以用ListIterator對集合連續添加與修改，但不能連續刪除。

?

5.2 通過迭代器修改集合結構

在使用迭代器遍歷集合時，我們不能通過集合本身來修改集合的結構（添加、刪除），只能通過迭代器來操作。

下面是對HashMap進行刪除操作的測試，其它集合也是這樣：

package com.test;import java.util.*; import java.util.Map.Entry;public class Test {public static void main(String[] args) {Map map = new HashMap();map.put(1, 1);map.put(2, 3);Set entrySet = map.entrySet();Iterator it = entrySet.iterator();while (it.hasNext()) {Entry entry = (Entry) it.next();/** 可以通過迭代器來修改集合結構，但前提是要在已執行過next或前移操作，* 否則會拋異常：IllegalStateException*///it.remove();/** 拋異常：ConcurrentModificationException* 不能使用集合本身來修改集合的結構*/// map.remove(entry.getKey());}//end while System.out.println(map);} }

?

六、HashMap

6.1 HashMap的數據結構

HashMap是一個數組和鏈表的結合體（在數據結構稱“鏈表散列“），如下圖所示：

　　當我們往HashMap中put元素的時候，先根據key的hash值得到這個元素在數組中的位置（即下標），然后就可以把這個元素放到對應的位置中了。如果這個元素所在的位置上已經存放有其他元素，那么在同一個位置上的元素將以鏈表的形式存放，新加入的元素放在鏈頭，之前的元素放在鏈尾，如下圖所示：

注意：與TreeMap不同，HashMap不保證元素順序，根據需要該容器可能會對元素重新哈希，元素的順序會被打散，因此不同時間迭代同一個HashMap的順序可能會不同。

?

?

6.2 HashMap和Hashtable的區別

（1）在HashMap中，可以允許null作為鍵，且只可以有一個，否則覆蓋，但可以有一個或多個值為null。當get()方法返回null時，既可以表示 HashMap中沒有該鍵，也可以表示該鍵所對應的值為null，所以HashMap不能由get()方法來判斷是否存在某個鍵，而應該用containsKey()方法來判斷；而Hashtable不允許null鍵與null值。

（2）HashMap中hash數組的默認大小是16，而且一定是2的多少次方；HashTable中hash數組的默認大小是11，增加的方式是 int newCapacity = oldCapacity * 2 + 1;，即增加至2倍（而不是2倍加1，因為擴容是在增加元素前進行的，在擴容后會將新增元素放入容器中）。另外兩者的默認負載因子都是0.75。

（3）HashMap是Map接口的一個實現類；Hashtable是Dictionary的子類

public class HashMap extends AbstractMap implements Map public class Hashtable extends Dictionary implements Map

（4）HashMap中的方法在缺省情況下是非同步的，而Hashtable中的方法是同步的。在多線程應用程序中，我們應該使用Hashtable；而對于HashMap，則需要額外的同步機制（其實HashMap的同步問題可通過Collections的一個靜態方法得到解決：Map Collections.synchronizedMap(Map m)，當然也可以自己在使用地方加鎖）。

　　注：java.util.concurrent.ConcurrentHashMap是HashMap的線程安全版，同HashMap相比，ConcurrentHashMap不僅保證了訪問的線程安全性，而且在效率上與Hashtable相比，有較大的提高。

（5）兩者遍歷方式的內部實現不同，HashMap、Hashtable均使用了Iterator，而由于歷史原因，Hashtable還使用了Enumeration的方式 。

（6）求哈希地址與哈希地址轉hash數組（Entry table[]）索引的方法不同，如下所示：

HashTable直接使用對象的hashCode：

int hash = key.hashCode();//直接使用鍵的hashCode方法求哈希值 //哈希地址轉hash數組索引，先使用最大正int數與，這樣將負轉正數，再與數組長度求模得到存入的hash數組索引位置 int index = (hash & 0x7FFFFFFF) % tab.length;

HashMap重新計算hash值，而且用位運算&代替求模：

int hash = hash(k); int i = indexFor(hash, table.length); static int hash(Object x) { //以鍵本身的hash碼為基礎求哈希地址，但看不懂是什么意思 int h = x.hashCode(); h += ~(h << 9); h ^= (h >>> 14); h += (h << 4); h ^= (h >>> 10); return h; }
static int indexFor(int h, int length) { return h & (length-1);//將哈希地址轉換成哈希數組中存入的索引號 }

?

?

補充：

（1）當以自己的對象做為HashMap、HashTable、LinkedHashMap、HashSet 、LinkedHashSet 的鍵時，一定要重寫hashCode ()與equals ()方法，因為Object的hashCode()是返回內存地址，且equals()方法也是比較內存地址，所以當要在這些hash集合中查找時，如果是另外new出的新對象是查不到的，除非重寫這兩個方法。因為AbstractMap類的containsKey(Object key)方法實現如下：

if (e.hash == hash && eq(k, e.key))//先比對hashcode，再使用equals return true; static boolean eq(Object x, Object y) { return x == y || x.equals(y); }

Java中的集合框架的哈希是以一個對象查找另外一個對象，所以重寫hasCode與equals方法很重要。String對象是可以作為鍵的，因為已重寫了這兩個方法。

（2）重寫hashCode()與equals()這兩個方法是針對哈希類，至于其它集合，如果要用public boolean contains(Object o)或containsValue(Object value)查找時，只需要實現equals()方法即可，他們都只使用對象的 equals方法進行比對，沒有使用 hashCode方法。

（3）TreeMap/TreeSet：放入其中的元素一定要具有自然比較能力(即要實現java.lang.Comparable接口)或者在構造TreeMap/TreeSet時傳入一個比較器(實現java.util.Comparator接口)，如果在創建時沒有傳入比較器，而放入的元素也沒有自然比較能力時，會出現類型轉換錯誤(因為在沒有較器時，會試著轉成Comparable型)。

兩種比較接口如下：

//自然比較器 public interface java.lang.Comparable { public int compareTo(Object o); } public interface java.util.Comparator { int compare(Object o1, Object o2); boolean equals(Object obj); }

（4）在多線程環境下，可以使用Collections類的相應靜態方法來包裝相應的集合類，使它們線程安全：

A、public static Collection synchronizedCollection (Collection c)方法的實質是返回包裝后的SynchronizedCollection子類。

B、使用Collections的synchronizedList、synchronizedMap、synchronizedSet等方法來獲取經過包裝了的同步集合（如：List list = Collections.synchronizedList(new LinkedList(...));或?Collections.synchronizedMap(originMap)?）

?

Collections代碼如下：

public class Collections { //... static Collection synchronizedCollection(Collection c, Object mutex) { return new SynchronizedCollection(c, mutex); } public static List synchronizedList(List list) { //... } static Set synchronizedSet(Set s, Object mutex) { //... } public static Map synchronizedMap(Map m) { return new SynchronizedMap(m); } //... static class SynchronizedCollection implements Collection, Serializable { Collection c; // 對給定集合進行同步（包裝） Object mutex; // 對象鎖，可以自己設置 //... SynchronizedCollection(Collection c, Object mutex) { this.c = c; this.mutex = mutex; } public int size() { synchronized (mutex) { return c.size(); } } public boolean isEmpty() { synchronized (mutex) { return c.isEmpty(); } } //... } static class SynchronizedList extends SynchronizedCollection implements List { List list; SynchronizedList(List list, Object mutex) { super(list, mutex); this.list = list; } public Object get(int index) { synchronized (mutex) { return list.get(index); } } //... } static class SynchronizedSet extends SynchronizedCollection implements Set { SynchronizedSet(Set s) { super(s); } //... } //... }

?

?

隊列類圖：

Deque（雙端隊列）：兩端都可以進出的隊列。當我們約束從隊列的一端進出時，就形成了另一種存取模式，它遵循先進后出原則，這就是棧結構。

?

參考資料

（1）http://www.blogjava.net/EvanLiu/archive/2007/11/12/159884.html

（2）http://www.cnblogs.com/CarpenterLee/p/5440428.html

（3）http://www.cnblogs.com/caca/p/java_Hashtable.html

轉載于:https://www.cnblogs.com/studyLog-share/p/4691431.html

總結

以上是生活随笔為你收集整理的java集合浅谈（一）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。