Java集合類整體框架

Java集合工具包位于Java.util包下，包含了很多常用的數據結構，如數組、鏈表、棧、隊列、集合、哈希表等。學習Java集合框架下大致可以分為如下五個部分：List列表、Set集合、Map映射、迭代器（Iterator、Enumeration）、工具類（Arrays、Collections）。

Java集合類的整體框架如下：

Java集合類的整體框架圖

從上圖中可以看出，集合類主要分為兩大類：Collection和Map。

Collection是List、Set等集合高度抽象出來的接口，它包含了這些集合的基本操作，它主要又分為兩大部分：List和Set。

List接口通常表示一個列表（數組、隊列、鏈表、棧等），其中的元素可以重復，常用實現類為ArrayList和LinkedList，另外還有不常用的Vector。另外，LinkedList還是實現了Queue接口，因此也可以作為隊列使用。

Set接口通常表示一個集合，其中的元素不允許重復（通過hashcode和equals函數保證），常用實現類有HashSet和TreeSet，HashSet是通過Map中的HashMap實現的，而TreeSet是通過Map中的TreeMap實現的。另外，TreeSet還實現了SortedSet接口，因此是有序的集合（集合中的元素要實現Comparable接口，并覆寫Compartor函數才行）。 我們看到，抽象類AbstractCollection、AbstractList和AbstractSet分別實現了Collection、List和Set接口，這就是在Java集合框架中用的很多的適配器設計模式，用這些抽象類去實現接口，在抽象類中實現接口中的若干或全部方法，這樣下面的一些類只需直接繼承該抽象類，并實現自己需要的方法即可，而不用實現接口中的全部抽象方法。

Map是一個映射接口，其中的每個元素都是一個key-value鍵值對，同樣抽象類AbstractMap通過適配器模式實現了Map接口中的大部分函數，TreeMap、HashMap、WeakHashMap等實現類都通過繼承AbstractMap來實現，另外，不常用的HashTable直接實現了Map接口，它和Vector都是JDK1.0就引入的集合類。

Iterator是遍歷集合的迭代器（不能遍歷Map，只用來遍歷Collection），Collection的實現類都實現了iterator()函數，它返回一個Iterator對象，用來遍歷集合，ListIterator則專門用來遍歷List。而Enumeration則是JDK1.0時引入的，作用與Iterator相同，但它的功能比Iterator要少，它只能再Hashtable、Vector和Stack中使用。

Arrays和Collections是用來操作數組、集合的兩個工具類，例如在ArrayList和Vector中大量調用了Arrays.Copyof()方法，而Collections中有很多靜態(tài)方法可以返回各集合類的synchronized版本，即線程安全的版本，當然了，如果要用線程安全的結合類，首選Concurrent并發(fā)包下的對應的集合類。

常用的集合類分析：

• ArrayList簡介

ArrayList是基于數組實現的，是一個動態(tài)數組，其容量能自動增長，類似于C語言中的動態(tài)申請內存，動態(tài)增長內存。

ArrayList不是線程安全的，只能在單線程環(huán)境下，多線程環(huán)境下可以考慮用collections.synchronizedList(List l)函數返回一個線程安全的ArrayList類，也可以使用concurrent并發(fā)包下的CopyOnWriteArrayList類。

ArrayList實現了Serializable接口，因此它支持序列化，能夠通過序列化傳輸，實現了RandomAccess接口，支持快速隨機訪問，實際上就是通過下標序號進行快速訪問，實現了Cloneable接口，能被克隆。

ArrayList基于數組實現，可以通過下標索引直接查找到指定位置的元素，因此查找效率高，但每次插入或刪除元素，就要大量地移動元素，插入刪除元素的效率低。

在查找給定元素索引值等的方法中，源碼都將該元素的值分為null和不為null兩種情況處理，ArrayList中允許元素為null。

• LinkedList簡介

LinkedList是基于雙向循環(huán)鏈表實現的，除了可以當作鏈表來操作外，它還可以當作棧，隊列和雙端隊列來使用。

LinkedList同樣是非線程安全的，只在單線程下適合使用。

LinkedList實現了Serializable接口，因此它支持序列化，能夠通過序列化傳輸，實現了Cloneable接口，能被克隆。

在查找和刪除某元素時，源碼中都劃分為該元素為null和不為null兩種情況來處理，LinkedList中允許元素為null。

• Vector簡介

Vector也是基于數組實現的，是一個動態(tài)數組，其容量能自動增長。

Vector是JDK1.0引入了，它的很多實現方法都加入了同步語句，因此是線程安全的（其實也只是相對安全，有些時候還是要加入同步語句來保證線程的安全），可以用于多線程環(huán)境。

Vector沒有實現Serializable接口，因此它不支持序列化，實現了Cloneable接口，能被克隆，實現了RandomAccess接口，支持快速隨機訪問。

同樣在查找給定元素索引值等的方法中，源碼都將該元素的值分為null和不為null兩種情況處理，Vector中也允許元素為null。

• HashMap簡介

HashMap是基于哈希表實現的，每一個元素都是一個key-value對，其內部通過單鏈表解決沖突問題，容量不足（超過了閾值）時，同樣會自動增長。

HashMap是非線程安全的，只是用于單線程環(huán)境下，多線程環(huán)境下可以采用concurrent并發(fā)包下的concurrentHashMap。

HashMap實現了Serializable接口，因此它支持序列化，實現了Cloneable接口，能被克隆。

HashMap的存儲結構

圖中，紫色部分即代表哈希表，也稱為哈希數組，數組的每個元素都是一個單鏈表的頭節(jié)點，鏈表是用來解決沖突的，如果不同的key映射到了數組的同一位置處，就將其放入單鏈表中。

HashMap中key和value都允許為null。

• Hashtable簡介

HashTable同樣是基于哈希表實現的，同樣每個元素都是key-value對，其內部也是通過單鏈表解決沖突問題，容量不足（超過了閾值）時，同樣會自動增長。

Hashtable也是JDK1.0引入的類，是線程安全的，能用于多線程環(huán)境中。

Hashtable同樣實現了Serializable接口，它支持序列化，實現了Cloneable接口，能被克隆。

針對Hashtable，HashMap的比較來總結。

• 二者的存儲結構和解決沖突的方法都是相同的。
• HashTable在不指定容量的情況下的默認容量為11，而HashMap為16，Hashtable不要求底層數組的容量一定要為2的整數次冪，而HashMap則要求一定為2的整數次冪。
• Hashtable中key和value都不允許為null，而HashMap中key和value都允許為null（key只能有一個為null，而value則可以有多個為null）。

• LinkedHashMap簡介

LinkedHashMap是HashMap的子類，因此它具有HashMap的所有特性，同樣允許key和value為null。與HashMap有著同樣的存儲結構，但它加入了一個雙向鏈表的頭結點，將所有put到LinkedHashmap的節(jié)點一一串成了一個雙向循環(huán)鏈表，因此它保留了節(jié)點插入的順序，可以使節(jié)點的輸出順序與輸入順序相同。

LinkedHashMap可以用來實現LRU算法

LinkedHashMap同樣是非線程安全的，只在單線程環(huán)境下使用。

LinkedHashMap結構如下：

實際上就是HashMap和LinkedList兩個集合類的存儲結構的結合。在LinkedHashMapMap中，所有put進來的Entry都保存在如第一個圖所示的哈希表中，但它又額外定義了一個以head為頭結點的空的雙向循環(huán)鏈表，每次put進來Entry，除了將其保存到對哈希表中對應的位置上外，還要將其插入到雙向循環(huán)鏈表的尾部。

總結：

• List 可以通過下標 (1,2..) 來取得值，值可以重復而 Set 只能通過游標來取值，并且值是不能重復的

• ArrayList ， Vector ， LinkedList 是 List 的實現類

• ArrayList 是線程不安全的， Vector 是線程安全的，這兩個類底層都是由數組實現的

• LinkedList 是線程不安全的，底層是由鏈表實現的

• Map 是鍵值對集合
  HashTable 和 HashMap 是 Map 的實現類
  HashTable 是線程安全的，不能存儲 null 值
  HashMap 不是線程安全的，可以存儲 null 值

• Stack類：繼承自Vector，實現一個后進先出的棧。提供了幾個基本方法，push、pop、peak、empty、search等。

• Queue接口：提供了幾個基本方法，offer、poll、peek等。實現類有LinkedList、PriorityQueue等。