Java集合框架

**Java 集合框架**（**Java collections framework**）是一個包含一系列實作可重複使用集合的資料結構的類別和介面集合。雖然稱為「框架」，其使用方式卻像個函式庫。集合框架提供了定義各式各樣集合的介面和實作上述集合的類別。

## 與陣列的不同處

集合和陣列在兩者保持物件參考核可被視作為一個團體上有著功能上的相似處。集合和陣列其中一點不同的是，集合在宣告時不需要指定固定的容量。集合可以在新增或移除內容時自動地增加或縮減其容量。
另外，集合無法收納基本資料型態，像是整數（int）、長整數（long）或者雙精度浮點數（double）。取而代之的是，集合可以收納上述基本資料型態的包裹類別（Integer、Long、Double）。

## 歷史

集合介面在 JDK 1.2 先行版版本時納入，並包含少數簡單的資料結構類別，但當時並未包含完整的集合框架。
原本在 Java 典型集中物件的方法是使用陣列（array）、向量（Vector）或者雜湊表（Hashtable）類別來處理。但上述的類別並不容易擴展，而且並沒有一個標準的介面。
當時若想使用可重用集合資料結構，也是有數種第三方框架可供選擇。最廣為使用的例如道格・利亞的_集合包_（Collections package）的_集合包_

集合框架主要由約書亞・布洛克設計且開發，並於 JDK 1.2 中匯入。它重新使用了不少來自道格・利亞的集合包的概念和類別，並在最後使後者過時。 
道格・利亞後來投入發展並行性 Java 包，並在其使用了和集合框架有關的類別。而後來並行性工具在 JDK 5.0 以 JSR 166 匯入。

## 架構

在 Java，幾乎全部的集合都衍生自 java.util.Collection。集合介面定義了所有集合的基本部件。介面中定義了**加入**（add）和**移除**（remove）兩種方法來增加或移除該集合內的元素。另一個必要的方法例如**轉成陣列**（toArray），用於把該集合的所有轉換成基本陣列。最後，一個名為_含有_（contains）的方法用來檢查某元素是否在該集合內。集合這個介面是 java.lang.Iterable 的子介面，故此集合可被用於 For-each 函式的查詢目標。（Iterable 介面包含方法**疊代器**（iterator）來讓 For-each 函式使用）。所有的集合都具有一個疊代器來遍詢集合內的所有元素。另外，集合也是一個 Java 的泛型。任何集合皆須要寫成能接受任何類別。例如：**集合 <字串>**可以用來存放字串，而且在其中的所有元素提出來都被視作字串，而不需要另外轉型。使用時，角括號裡面填入該集合應該存放哪種類別。

### 三種集合

集合可分為三種：**有序列表**（ordered lists）、**對映表**（maps）和**集**（sets）。有序列表容許程式設計師依序地加入元素，並以同樣的順序取回元素，例如等候列表。在有序列表介面底下有兩個子介面，分別為**列表**（Lists）和**佇列**（Queue）。對映表使用索引來參考物件並取回其值。在對映表介面底下有一個子介面**對映表**（Map）。集是一種可供遍巡的無序集合，但當中不允許重複的物件存在。在其中有個子介面**集**（Set）。

### 列表介面

列表在集合框架下藉由 java.util.List 介面實作，其將列表定義為一種更靈活的陣列。元素有特定的順序，而且容許相同的元素存在。元素可被放置在特定的位置，也可以在列表中被搜尋。以下兩種舉例為實作了列表介面的具體物件:

* java.util.ArrayList: 其將列表實作為一種陣列。當操作其方法並填入類別時，該種類別會把元素存在某個所屬陣列當中。
* java.util.LinkedList: 這個類別將元素包裝成節點，而每個節點包含前一節點和後一節點的指標。這種列表藉由讀取上述的指標來在節點中巡查並操作元素。元素可以藉由操作指標來掛上和脫離節點，來簡單地實現新增或刪除。

### 堆疊類別

堆疊可由 java.util.Stack 建立。其提供方法來**推入**（push）或**彈出**（pop）當中的元素。堆疊會依循後進先出的原則來回傳元素。意即，最後推入的元素會最先彈出。java.util.Stack 是 Java 所提供的堆疊標準實作。其延伸了 java.util.Vector 並加入了 5 種新操作來讓向量可被看成堆疊。除提供了推入和彈出方法外，還提供了**窺**（Seek）方法來檢查最上方的元素、檢查堆疊是否空白的方法、還有尋找並檢查某元素離最上方有多遠的方法。當堆疊被建立時，當中不含任何元素。

### 佇列類別

java.util.Queue 定義了佇列資料結構，也就是將元素以其加入的順序來排序的集合。新加入的元素會放在對列的最末端，而提出物件時會先從最頂端開始提出。這實現了先進先出的模式。在這介面下有 java.util.LinkedList, java.util.ArrayDeque, 和 java.util.PriorityQueue。

### 集介面

Java 的 java.util.Set 定義了集。集不能包含任何重複的元素，另外集也沒有順序。也因為如此，在集內的元素無法以索引存取。在集底下實作了**雜湊集**（java.util.HashSet）、**連結雜湊集**（java.util.LinkedHashSet）和**樹狀集**（java.util.TreeSet）。雜湊集使用**雜湊對映表**（java.util.HashMap）來儲存元素和其雜湊值來防止重複。連結雜湊集藉由建立雙向連結列表來按照各個元素的加入順序進行聯繫，如此可以保持這個集的順序。樹狀集使用紅黑樹來確保沒有重複的元素。另外，如此的實作容許樹狀集能實作**已排序集**（java.util.SortedSet）。
跟一般的集所不同的是，已排序集會藉由元素的**與之比較**（compareTo）方法、或於已排序集建構式當中提供的函式，來對其中元素進行排序。如此可以輕鬆取得已排序集當中的第一和第末元素，或者由某最大和最小值為區間來取得子集。

已排序集還可藉由**可導航集**（java.util.NavigableSet）介面擴充。可導航集和已排序集很像，不過有著額外的新方法，像是**地板**（floor）、**天花板**（ceiling）、**更低**（lower）和**更高**（higher）。這些方法可以按照某參數來在可導航集尋找符合條件的元素。另外，可導航集也提供了一個疊代器，可用於遍詢其中的元素。

### 對映表介面

Java 的 java.util.Map 定義了對映表。對映表是一種以索引和元素掛鉤的簡單資料結構。如果在對映表內以雜湊值代表某元素的索引，則這個對映表實質上是一個集。如果以一個遞增號碼來做索引，則實質上為一個列表。在對映表底下實作了**雜湊表**（java.util.HashMap）、**連結雜湊表**（java.util.LinkedHashMap）、和**樹狀表**（java.util.TreeMap）。雜湊表會儲存索引值的雜湊值來做為比對並提出該索引連接的元素之用。連結雜湊表進一步拓展了上述架構，它增加了一個雙向連結串列來連結當中的元素，使其能儲存元素加入時的順序。樹狀表使用紅黑樹來比對索引值。

對映表介面藉由他的子介面，**已排序對映表**（java.util.SortedMap），得到進一步的拓展。已排序對映表會藉由索引的**與之比較**（compareTo）方法、或於已排序對映表建構式當中提供的函式，來對其中索引進行排序。如此可以輕鬆取得已排序對映表當中的第一和第末索引，或者由某最大和最小值為區間來取得索引與值來建立子對映表。

## 參見

* 容器

## 注釋

## 參考資料

## 外部連結