3.1 Collections框架

容器在Java語言開發中有著非常重要的作用，Java提供了多種類型的容器來滿足開發的需要，容器不僅在面試筆試中也是非常重要的一個知識點，在實際開發的過程中也是經常會用到。因此，對容器的掌握是非常有必要也是非常重要的。Java中的容器可以被分為兩類：

（1）Collection

Collection用來存儲獨立的元素，其中包括List、Set和Queue。其中List是按照插入的順序保存元素，Set中不能有重復的元素，而Queue按照排隊規則來處理容器中的元素。它們之間的關系如圖3-1所示。

（2）Map

Map用來存儲<鍵，值>對，這個容器允許通過鍵來查找值。Map也有多種實現類，如圖3-2所示。

Java Collections框架中包含了大量集合接口以及這些接口的實現類和操作它們的算法（例如排序、查找、反轉、替換、復制、取最小元素、取最大元素等），具體而言，主要提供了List（列表）、Queue（隊列）、Set（集合）、Stack（棧）和Map（映射表，用于存放鍵值對）等數據結構。其中List、Queue、Set、Stack都繼承自Collection接口。

Collection是整個集合框架的基礎，它里面存儲一組對象，表示不同類型的Collections，它的作用只是提供維護一組對象的基本接口而已。

下面分別介紹List，Set和Map三個接口。

1）Set表示數學意義上的集合概念，最主要的特點是集合中的元素不能重復，因此存入Set的每個元素都必須定義equals()方法來確保對象的唯一性。該結構有兩個比較常用的實現類：HashSet和TreeSet。其中TreeSet實現了SortedSet接口，因此TreeSet容器中的元素是有序的。

2）List又稱為有序的Collection，它按對象進入的順序保存對象，所以它能對列表中的每個元素的插入和刪除位置進行精確控制。同時，它可以保存重復的對象。LinkedList、ArrayList和Vector都實現了List接口。

3）Map提供了一個從鍵映射到值的數據結構。它用于保存鍵值對，其中值可以重復，但鍵是唯一的，不能重復。Java類庫中有多個實現該接口的類：HashMap、TreeMap、LinkedHashMap、WeakHashMap和IdentityHashMap。雖然它們都實現了相同的接口，但執行效率卻不是完全相同的。具體而言，HashMap是基于哈希表實現的，采用對象的hashCode可以進行快速查詢。LinkedHashMap采用列表來維護內部的順序。TreeMap基于紅黑樹的數據結構來實現，內部元素是按需排列的。