1,、Java容器類庫的簡化圖，下面是集合類庫更加完備的圖,。包括抽象類和遺留構(gòu)件（不包括Queue的實現(xiàn)）：

2,、ArrayList初始化時不可指定容量,，如果以new ArrayList()方式創(chuàng)建時，初始容量為10個,；如果以new ArrayList(Collection c)初始化時，容量為c.size()*1.1,，即增加10%的容量,；當(dāng)向ArrayList中添加一個元素時，先進行容器的容量調(diào)整,，如果容量不夠時，則增加至原來的1.5倍加1,，再然后把元素加入到容器中，即以原始容量的0.5倍比率增加,。

3,、Vector：初始化時容量可以設(shè)定,，如果以new Vector()方式創(chuàng)建時，則初始容量為10,，超過容量時以2倍容量增加。如果以new Vector(Collection c)方式創(chuàng)建時,，初始容量為c.size()*1.1,，超過時以2倍容量增加,。如果以new Vector(int initialCapacity, int capacityIncrement)，則以capacityIncrement容量增加,。

4、集合特點：

• 
  List：保證以某種特定插入順序來維護元素順序,，即保持插入的順序,，另外元素可以重復(fù)。


• 
  ArrayList：是用數(shù)組實現(xiàn)的,，讀取速度快,，插入與刪除速度慢（因為插入與刪除時要移動后面的元素），適合于隨機訪問,。


• 
  Vector：功能與ArrayList幾乎相同,，也是以數(shù)組實現(xiàn)，添加,，刪除,，讀取，設(shè)置都是基于線程同步的,。


• 
  LinkedList：雙向鏈表來實現(xiàn)，刪除與插入速度快,，讀取速度較慢,，因為它讀取時是從頭向尾（如果節(jié)點在鏈的前半部分），或尾向頭（如果節(jié)點在鏈的后半部分）查找元素,。因此適合于元素的插入與刪除操作,。


• 
  Set：維持它自己的內(nèi)部排序，隨機訪問不具有意義,。另外元素不可重復(fù),。


• 
  HashSet：是最常用的，查詢速度最快,，因為 內(nèi)部以HashMap來實現(xiàn)，所以插入元素不能保持插入次序,。


• 
  LinkedHashSet：繼承了HashSet，保持元素的插入次序，因為內(nèi)部使用LinkedHashMap實現(xiàn),，所以能保持元素插入次序,。


• 
  TreeSet：基于TreeMap，生成一個總是處于排序狀態(tài)的set,，它實現(xiàn)了SortedSet接口,，內(nèi)部以 TreeMap來實現(xiàn)


• 
  TreeMap：鍵以某種排序規(guī)則排序，內(nèi)部以red-black（紅-黑）樹數(shù)據(jù)結(jié)構(gòu)實現(xiàn),，實現(xiàn)了SortedMap接口,，具體可參《RED-BLACK(紅黑)樹的實現(xiàn)TreeMap源碼閱讀 》


• 
  HashMap: 以哈希表數(shù)據(jù)結(jié)構(gòu)實現(xiàn),，查找對象時通過哈希函數(shù)計算其位置，它是為快速查詢而設(shè)計的，其內(nèi)部定義了一個hash表數(shù)組（Entry[] table）,，元素會通過哈希轉(zhuǎn)換函數(shù)將元素的哈希地址轉(zhuǎn)換成數(shù)組中存放的索引,，如果有沖突,，則使用散列鏈表的形式將所有相同哈希地址的元素串起來，可能通過查看HashMap.Entry的源碼它是一個單鏈表結(jié)構(gòu),。


• 
  Hashtable:也是以哈希表數(shù)據(jù)結(jié)構(gòu)實現(xiàn)的，解決沖突時與HashMap也一樣也是采用了散列鏈表的形式,，不過性能比HashMap要低,。


• 
  LinkedHashMap:繼承HashMap，內(nèi)部實體LinkedHashMap.Entry繼承自HashMap.Entry,，LinkedHashMap.Entry在HashMap.Entry的基礎(chǔ)上新增了兩個實體引用（Entry before, after）,，這樣實體可以相互串鏈起來形成鏈，并且在LinkedHashMap中就定義了一個頭節(jié)點（Entry header）用來指向循環(huán)雙向鏈的第一個元素（通過after指向）與最后一個元素（通過before指向）,。在添加一個元素時，先會通過父類HashMap將元素加入到hash表數(shù)組里,，然后再會在鏈尾（header.before指向位置）添加（當(dāng)然這一過程只是調(diào)整LinkedHashMap.Entry對象內(nèi)部的before, after而已,，而不是真真創(chuàng)建一個什么新的鏈表結(jié)構(gòu)向里加那樣）,；刪除先從hash表數(shù)組中刪除,，再將被刪除的元素徹底的從雙向鏈中斷開,。其實在鏈中添加與刪除操作與LinkedList是一樣的,，可以參考《Java集合框架之LinkedList及ListIterator實現(xiàn)源碼分析 》

5、Hashtable和HashMap的區(qū)別：

• 
  Hashtable中的方法是同步的,，而HashMap中的方法在缺省情況下是非同步的,。在多線程應(yīng)用程序中,，我們應(yīng)該使用Hashtable,；而對于HashMap,，則需要額外的同步機制,。但HashMap的同步問題可通過Collections的一個靜態(tài)方法得到解決：Map Collections.synchronizedMap(Map m)，當(dāng)然與可以自己在使用地方加鎖,。

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

• 
  HashTable使用Enumeration,，HashMap使用Iterator。

• 
  Hashtable是Dictionary的子類,，HashMap是Map接口的一個實現(xiàn)類；

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

• 
  求哈希地址與哈希地址轉(zhuǎn)hash數(shù)組（Entry table[]）索引方法不同：

HashTable直接使用對象的hashCode：

Java代碼  

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

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

Java代碼  

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

  HashMap實現(xiàn)圖：

6、集合中鍵值是否允許null小結(jié)

• 
  List：可以有多個null,，可以有重復(fù)值,。


• 
  HashSet：能插入一個null（因為內(nèi)部是以 HashMap實現(xiàn) ）,，忽略不插入重復(fù)元素,。


• 
  TreeSet：不能插入null （因為內(nèi)部是以 TreeMap 實現(xiàn) ） ,，元素不能重復(fù)，如果待插入的元素存在,，則忽略不插入，對元素進行排序,。


• 
  HashMap：允許一個null鍵與多個null值，若重復(fù)鍵,，則覆蓋以前值。


• 
  TreeMap：不允許null鍵(實際上可以插入一個null鍵,，如果這個Map里只有一個元素是不會報錯的,，因為一個元素時沒有進行排序操作，也就不會報空指針異常,，但如果插入第二個時就會立即報錯),，但允許多個null值,，覆蓋已有鍵值。


• 
  HashTable：不允許null鍵與null值(否則運行進報空指針異常),。也會覆蓋以重復(fù)值?；诰€程同步。

7,、對List的選擇：

• 
  對于隨機查詢與迭代遍歷操作，數(shù)組比所有的容器都要快,。


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


• 
  Vector通常不如ArrayList快，則且應(yīng)該避免使用,，它目前仍然存在于類庫中的原因是為了支持過去的代碼。


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

8,、對Set的選擇：

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


• 
  TreeSet存在的唯一原因是,，它可以維持元素的排序狀態(tài)，所以只有當(dāng)你需要一個排好序的Set時,，才應(yīng)該使用TreeSet。


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

9,、對Map的選擇：

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


• 
  TreeMap通常比HashMap慢,，因為要維護排序。


• 
  HashMap正是為快速查詢而設(shè)計的,。


• 
  LinkedHashMap比HashMap慢一點，因為它維護散列數(shù)據(jù)結(jié)構(gòu)的同時還要維護鏈表,。

10、Stack基于線程安全,，Stack類是用Vector來實現(xiàn)的(public　class Stack extends Vector)，但最好不要用集合API里的這個實現(xiàn)棧,，因為它繼承于Vector,，本就是一個錯誤的設(shè)計,，應(yīng)該是一個組合的設(shè)計關(guān)系,。

11、Iterator對ArrayList(LinkedList)的操作限制：

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


• 
  可以用ListIterator對集合連續(xù)添加與修改,，但不能連續(xù)刪除。


• 
  進行添加操作后是不能立即進行刪除與修改操作的,。


• 
  進行刪除操作后可以進行添加,，但不能進行修改操作。


• 
  進行修改后是可以立即進行刪除與添加操作的,。

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

Java代碼  

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

String對象是可以準確做為鍵的，因為已重寫了這兩個方法,。

因此，Java中的集合框架中的哈希是以一個對象查找另外一個對象，所以重寫hasCode與equals方法很重要,。

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

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

兩種比較接口：

Java代碼  

1. //自然比較器  
2. public interface java.lang.Comparable {  
3.     public int compareTo(Object o);  
4. }  
5.   
6. public interface java.util.Comparator {  
7.     int compare(Object o1, Object o2);  
8.     boolean equals(Object obj);  
9. }  

15,、Collection或Map的同步控制：可以使用Collections類的相應(yīng)靜態(tài)方法來包裝相應(yīng)的集合類,，使他們具線程安全,，如public static Collection synchronizedCollection (Collection c)方法實質(zhì)返回的是包裝后的SynchronizedCollection子類,，當(dāng)然你也可以使用Collections的synchronizedList、synchronizedMap,、synchronizedSet方法來獲取不同的經(jīng)過包裝了的同步集合,，其代碼片斷：

Java代碼  

1. public class Collections {  
2.   
3.     //...  
4.   
5.     static Collection synchronizedCollection(Collection c, Object mutex) {  
6.         return new SynchronizedCollection(c, mutex);  
7.     }  
8.   
9.     public static List synchronizedList(List list) {  
10.         //...  
11.     }  
12.   
13.     static Set synchronizedSet(Set s, Object mutex) {  
14.         //...  
15.     }  
16.   
17.     public static Map synchronizedMap(Map m) {  
18.         return new SynchronizedMap(m);  
19.     }  
20.   
21.     //...  
22.     static class SynchronizedCollection implements Collection, Serializable {  
23.   
24.         Collection c; // 對哪個集合進行同步（包裝）  
25.         Object mutex; // 對象鎖,，可以自己設(shè)置  
26.   
27.         //...  
28.         SynchronizedCollection(Collection c, Object mutex) {  
29.             this.c = c;  
30.             this.mutex = mutex;  
31.         }  
32.   
33.         public int size() {  
34.             synchronized (mutex) {  
35.                 return c.size();  
36.             }  
37.         }  
38.   
39.         public boolean isEmpty() {  
40.             synchronized (mutex) {  
41.                 return c.isEmpty();  
42.             }  
43.         }  
44.         //...  
45.     }  
46.   
47.     static class SynchronizedList extends SynchronizedCollection implements List {  
48.   
49.         List list;  
50.   
51.         SynchronizedList(List list, Object mutex) {  
52.             super(list, mutex);  
53.             this.list = list;  
54.         }  
55.   
56.         public Object get(int index) {  
57.             synchronized (mutex) {  
58.                 return list.get(index);  
59.             }  
60.         }  
61.         //...  
62.     }  
63.   
64.     static class SynchronizedSet extends SynchronizedCollection implements Set {  
65.         SynchronizedSet(Set s) {  
66.             super(s);  
67.         }  
68.         //...  
69.     }  
70.     //...  
71. }  

由包裝的代碼可以看出只是把原集合的相應(yīng)方法放在同步塊里調(diào)用罷了,。

16,、通過迭代器修改集合結(jié)構(gòu)
在使用迭代器遍歷集合時,，我們不能通過集合本身來修改集合的結(jié)構(gòu)（添加,、刪除）,，只能通過迭代器來操作,，下面是拿對HashMap刪除操作的測試，其它集合也是這樣：

Java代碼  

1. public static void main(String[] args) {  
2.  Map map = new HashMap();  
3.  map.put(1, 1);  
4.  map.put(2, 3);  
5.  Set entrySet = map.entrySet();  
6.  Iterator it = entrySet.iterator();  
7.  while (it.hasNext()) {  
8.   Entry entry = (Entry) it.next();  
9.   /* 
10.    * 可以通過迭代器來修改集合結(jié)構(gòu),，但前提是要在已執(zhí)行過 next 或 
11.    * 前移操作，否則會拋異常：IllegalStateException 
12.    */  
13.   // it.remove();  
14.   /* 
15.    * 拋異常：ConcurrentModificationException 因為通過 迭代 器操 
16.    * 作時,，不能使用集合本身來修 
17.    * 改集合的結(jié)構(gòu) 
18.    */  
19.   // map.remove(entry.getKey());  
20.  }  
21.  System.out.println(map);  
22. }