java Collections Framework

一、集合類的引入

通常，程序總是根據運行時才知道某些條件去創建對象，在此之前，不知道所需對象的數量，甚至不知道確切的類型。為解決這個普遍的編程問題，需要在任何時刻和任何位置創建任何數量的對象，就不能創建命名的引用來持有每一個對象。 MyType aReference;

Java有多重形式保存對象，如數組。但是數組有固定的尺寸，在更一般的情況中，很多的時候是你在程序中不知道需要創建多少個對象，或者是否需要更復雜的方式來存儲對象，因此數組尺寸固定這一限制過于受限了。

所以在Java實用類庫中專門提供了一套動態對象數組的操作類——類集框架，在Java中類集框架實際上也就是對數據結構的Java實現。集合框架是為表示和操作集合而規定的一種統一的標準的體系結構。任何集合框架都包含三大塊內容：對外的接口、接口的實現和對集合運算的算法。其中最基本的類型是Collection(List，Set，Queue)，Map。

容器類只能容納對象引用，基本類型會自動裝箱，一個數組，既可以直接容納基本類型的數據，亦可容納指向對象的引用。

二、什么是集合框架

那么有了集合的概念，什么是集合框架呢？集合框架是為表示和操作集合而規定的一種統一的標準的體系結構。任何集合框架都包含三大塊內容：對外的接口、接口的實現和對集合運算的算法。

接口：即表示集合的抽象數據類型。接口提供了讓我們對集合中所表示的內容進行單獨操作的可能。

實現：也就是集合框架中接口的具體實現。實際它們就是那些可復用的數據結構。

算法：在一個實現了某個集合框架中的接口的對象身上完成某種有用的計算的方法，例如查找、排序等。這些算法通常是多態的，因為相同的方法可以在同一個接口被多個類實現時有不同的表現。

三、使用集合框架的好處

1、它減少了程序設計的辛勞

集合框架通過提供有用的數據結構和算法使你能集中注意力于你的程序的重要部分上，而不是為了讓程序能正常運轉而將注意力于低層設計上。通過這些在無關API之間的簡易的互用性，使你免除了為改編對象或轉換代碼以便聯合這些API而去寫大量的代碼。

2、它提高了程序速度和質量

集合框架通過提供對有用的數據結構和算法的高性能和高質量的實現使你的程序速度和質量得到提高。因為每個接口的實現是可互換的，所以你的程序可以很容易的通過改變一個實現而進行調整。另外，你將可以從寫你自己的數據結構的苦差事中解脫出來，從而有更多時間關注于程序其它部分的質量和性能。

3、減少去學習和使用新的API 的辛勞

許多API天生的有對集合的存儲和獲取。在過去，這樣的API都有一些子API幫助操縱它的集合內容，因此在那些特殊的子API之間就會缺乏一致性，你也不得不從零開始學習，并且在使用時也很容易犯錯。而標準集合框架接口的出現使這個問題迎刃而解。

4、減少了設計新API的努力

設計者和實現者不用再在每次創建一種依賴于集合內容的API時重新設計，他們只要使用標準集合框架的接口即可。

5、集合框架鼓勵軟件的復用

對于遵照標準集合框架接口的新的數據結構天生即是可復用的。同樣對于操作一個實現了這些接口的對象的算法也是如此。

四、Java1.2之前的容器類庫

在Java2之前，Java是沒有完整的集合框架的。它只有一些簡單的可以自擴展的容器類，比如Vector，Stack，HashTable等。

1、Vector

Vector中包含的元素可以通過一個整型的索引值取得，它的大小可以在添加或移除元素時自動增加或縮小。然而，Vector的設計卻存在極多缺陷（下面會說到）。

2、Stack

Stack是一種后進先出（LIFO）的堆棧序列，重要特點是先放入的東西最后才能被取出。

3、Hashtable

Hashtable與Java2中的Map類似，可以看成一種關聯或映射數組，可以將兩個或多個毫無關系的對象相關聯，與數組不同的是它的大小可以動態變化。

五、Java2中的容器類庫

 簡化后

六、公用類

集合框架中還有兩個很實用的公用類：Collections和Arrays。

6.1、Collections

Collections提供了對一個Collection容器進行諸如排序、復制、查找和填充等一些非常有用的方法，Arrays則是對一個數組進行類似的操作。

6.2、Arrays類

java.util里面有一個Arrays類，它包括了一組可用于數組的static方法，這些方法都是一些實用工具。其中有四個基本方法：用來比較兩個數組是否相等的equals()；用來填充的fill()；用來對數組進行排序的sort()；以及用于在一個已排序的數組中查找元素的binarySearch()。所有這些方法都對PRimitive和Object進行了重載。此外還有一個asList()方法，它接受一個數組，然后把它轉成一個List容器。

七、主要集合類

Java中類集框架實際上也就是對數據結構的Java實現。其中最基本的類型是Collection(List，Set，Queue)、Map。

7.1、List

List的最重要的特征就是有序；它會確保以插入順序保存元素，允許重復。

List在Collection的基礎上添加了大量方法，使之能在序列中間插入和刪除元素。（只對LinkedList推薦使用）List可以制造ListIterator對象，你除了能用它在List的中間插入和刪除元素之外，還能用它沿兩個方法遍歷List。

7.1.1、ArrayList

ArrayList*：一個用數組實現的List。能進行快速的隨機訪問，但是往列表中間插入和刪除元素的時候比較慢。

7.1.2、LinkedList

內部實現是鏈表，它適合于在鏈表中間需要頻繁進行插入和刪除操作。

LinkedList：對順序訪問進行了優化。在List中間插入和刪除元素的代價也不高。隨機訪問的速度相對較慢。此外它還有addFirst()，addLast()，getFirst()，getLast()，removeFirst()和removeLast()等方法，你能把它當成棧（stack），隊列（queue）或雙向隊列（deque）來用。

7.1.3、LinkedList的用途

用LinkedList做一個棧

“棧（stack）”有時也被稱為“后進先出”（LIFO）的容器。就是說，最后一個被“壓”進棧中的東西，會第一個“彈”出來。LinkedList的方法能直接實現棧的功能，所以你完全可以不寫Stack而直接使用LinkedList。

用LinkedList做一個隊列

隊列（queue）是一個“先進先出”（FIFO）容器。也就是，你把一端把東西放進去，從另一端把東西取出來。所以你放東西的順序也就是取東西的順序。LinkedList有支持隊列的功能的方法，所以它也能被當作Queue來用。

用LinkedList做一個deque（雙向隊列）

它很像隊列，只是你可以從任意一端添加和刪除元素。

7.2、Set

Set接口也是Collection的一種擴展,與List不同的是，在Set中的對象元素不能重復。加入Set的每個元素必須是唯一的；否則，Set是不會把它加進去的。它的常用具體實現有HashSet和TreeSet類、LinkedHashSet類。他們保存對象的順序是和不一樣的，這是因為它們是用不同的方法來存儲和查找元素的。（TreeSet用了一種叫紅黑樹的數據結構【red-black tree datastructure】來為元素排序，而HashSet則用了“專為快速查找而設計”的散列函數。LinkedHashSet在內部用散列來提高查詢速度，但是它看上去像是用鏈表來保存元素的插入順序的。）

7.2.1、HashSet

為優化查詢速度而設計的Set，能快速定位一個元素。要放進HashSet里面的Object還得定義hashCode()。

7.2.2、TreeSet

TreeSet則將放入其中的元素按序存放，這就要求你放入其中的對象是可排序的，這就用到了集合框架提供的另外兩個實用類Comparable和Comparator。一個類是可排序的，它就應該實現Comparable接口。

7.2.3、LinkedHashSet

一個在內部使用鏈表的Set，既有HashSet的查詢速度，又能保存元素被加進去的順序（插入順序）。用Iterator遍歷Set的時候，它是按插入順序進行訪問的。

7.3、Map

Map是一種把鍵對象和值對象進行關聯的容器，一個Map容器中的鍵對象不允許重復，這是為了保持查找結果的一致性;如果有兩個鍵對象一樣，那你想得到那個鍵對象所對應的值對象時就有問題了，可能你得到的并不是你想的那個值對象，結果會造成混亂，

鍵和值的關聯很簡單，用put(Objectkey,Objectvalue)方法即可將一個鍵與一個值對象相關聯。用get(Object key)可得到與此key對象所對應的值對象。也可以用containsKey()和containsValue()測試Map是否包含有某個鍵或值。

Java標準類庫里有好幾種Map：HashMap，TreeMap，LinkedHashMap

7.3.1、HashMap：

基于hash表的實現。（用它來代替Hashtable）提供時間恒定的插入與查詢。在構造函數種可以設置hash表的capacity和load factor。可以通過構造函數來調節其性能。

7.3.2、TreeMap

基于紅黑樹數據結構的實現。它們是按順序排列的。TreeMap是Map中唯一有subMap()方法的實現。這個方法能讓你獲取這個樹中的一部分。

7.3.3、LinkedHashMap

很像HashMap，但是用Iterator進行遍歷的時候，它會按插入順序或最先使用的順序（least-recently-used(LRU)order）進行訪問。除了用Iterator外，其他情況下，只是比HashMap稍慢一點。用Iterator的情況下，由于是使用鏈表來保存內部順序，因此速度會更快。

7.4、Queue：

隊列通常（但并非一定）以 FIFO（先進先出）的方式排序各個元素。

7.4.1、LinkedList:

提供了方法支持隊列的行為，因此可以作為Queue的一種實現，將LinkedList向上轉型為Queue使用。

7.4.2、PriorityQueue

一個基于優先級堆的無界優先級隊列。優先級隊列的元素按照其自然順序進行排序，或者根據構造隊列時提供的Comparator進行排序，具體取決于所使用的構造方法。優先級隊列不允許使用null元素。依靠自然順序的優先級隊列還不允許插入不可比較的對象（這樣做可能導致ClassCastException）。