Collection [I]

Collection 層次結構 中的根介面。Collection 表示一組對象，這些對象也稱為 collection 的元素。一些 collection 允許有重覆的元素，而另一些則不允許。一些 collection 是有序的，而另一些則是無序的。JDK 不提供此介面的任何直接 實現：它提供更具體的子介面（如 Set 和 List）實現。此介面通常用來傳遞 collection，併在需要最大普遍性的地方操作這些 collection。

包 (bag) 或多集合 (multiset)（可能包含重覆元素的無序 collection）應該直接實現此介面。

所有通用的 Collection 實現類（通常通過它的一個子介面間接實現 Collection）應該提供兩個“標準”構造方法：一個是 void（無參數）構造方法，用於創建空 collection；另一個是帶有 Collection 類型單參數的構造方法，用於創建一個具有與其參數相同元素新的 collection。實際上，後者允許用戶複製任何 collection，以生成所需實現類型的一個等效 collection。儘管無法強制執行此約定（因為介面不能包含構造方法），但是 Java 平臺庫中所有通用的 Collection 實現都遵從它。 

+--List [I]

public class Listextends Componentimplements ItemSelectable, Accessible

List 組件為用戶提供了一個可滾動的文本項列表。可設置此 list，使其允許用戶進行單項或多項選擇。

+--ArrayList [C]

+--LinkedList [C]

List 介面的鏈接列表實現。實現所有可選的列表操作，並且允許所有元素（包括 null）。除了實現 List 介面外，LinkedList 類還為在列表的開頭及結尾 get、remove 和 insert 元素提供了統一的命名方法。這些操作允許將鏈接列表用作堆棧、隊列或雙端隊列。

此類實現 Deque 介面，為 add、poll 提供先進先出隊列操作，以及其他堆棧和雙端隊列操作。

所有操作都是按照雙重鏈接列表的需要執行的。在列表中編索引的操作將從開頭或結尾遍歷列表（從靠近指定索引的一端）。

+--Vector [C]

Vector 類可以實現可增長的對象數組。與數組一樣，它包含可以使用整數索引進行訪問的組件。但是，Vector 的大小可以根據需要增大或縮小，以適應創建 Vector 後進行添加或移除項的操作。

每個向量會試圖通過維護 capacity 和 capacityIncrement 來優化存儲管理。capacity 始終至少應與向量的大小相等；這個值通常比後者大些，因為隨著將組件添加到向量中，其存儲將按 capacityIncrement 的大小增加存儲塊。應用程式可以在插入大量組件前增加向量的容量；這樣就減少了增加的重分配的量。 

+--Stack [C]

 Stack 類表示後進先出（LIFO）的對象堆棧。它通過五個操作對類 Vector 進行了擴展 ，允許將向量視為堆棧。它提供了通常的 push 和 pop 操作，以及取堆棧頂點的 peek 方法、測試堆棧是否為空的 empty 方法、在堆棧中查找項並確定到堆棧頂距離的 search 方法。 

+--Set [I]

一個不包含重覆元素的 collection。更確切地講，set 不包含滿足 e1.equals(e2) 的元素對 e1 和 e2，並且最多包含一個 null 元素。正如其名稱所暗示的，此介面模仿了數學上的 set 抽象。

在所有構造方法以及 add、equals 和 hashCode 方法的協定上，Set 介面還加入了其他規定，這些規定超出了從 Collection 介面所繼承的內容。出於方便考慮，它還包括了其他繼承方法的聲明（這些聲明的規範已經專門針對 Set 介面進行了修改，但是沒有包含任何其他的規定）。

對這些構造方法的其他規定是（不要奇怪），所有構造方法必須創建一個不包含重覆元素的 set（正如上面所定義的）。

註：如果將可變對象用作 set 元素，那麼必須極其小心。如果對象是 set 中某個元素，以一種影響 equals 比較的方式改變對象的值，那麼 set 的行為就是不確定的。此項禁止的一個特殊情況是不允許某個 set 包含其自身作為元素

+--HashSet [C]

此類實現 Set 介面，由哈希表（實際上是一個 HashMap 實例）支持。它不保證 set 的迭代順序；特別是它不保證該順序恆久不變。此類允許使用 null 元素。

此類為基本操作提供了穩定性能，這些基本操作包括 add、remove、contains 和 size，假定哈希函數將這些元素正確地分佈在桶中。對此 set 進行迭代所需的時間與 HashSet 實例的大小（元素的數量）和底層 HashMap 實例（桶的數量）的“容量”的和成比例。因此，如果迭代性能很重要，則不要將初始容量設置得太高（或將載入因數設置得太低）。

註意，此實現不是同步的。如果多個線程同時訪問一個哈希 set，而其中至少一個線程修改了該 set，那麼它必須 保持外部同步。這通常是通過對自然封裝該 set 的對象執行同步操作來完成的。如果不存在這樣的對象，則應該使用 Collections.synchronizedSet 方法來“包裝” set。最好在創建時完成這一操作，以防止對該 set 進行意外的不同步訪問：

+--LinkedHashSet [C]

具有可預知迭代順序的 Set 介面的哈希表和鏈接列表實現。此實現與 HashSet 的不同之外在於，後者維護著一個運行於所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序，即按照將元素插入到 set 中的順序（插入順序）進行迭代。註意，插入順序不 受在 set 中重新插入的 元素的影響。（如果在 s.contains(e) 返回 true 後立即調用 s.add(e)，則元素 e 會被重新插入到 set s 中。）

此實現可以讓客戶免遭未指定的、由 HashSet 提供的通常雜亂無章的排序工作，而又不致引起與 TreeSet 關聯的成本增加。使用它可以生成一個與原來順序相同的 set 副本，並且與原 set 的實現無關：

     void foo(Set s) {
         Set copy = new LinkedHashSet(s);
         ...
     }
 

如果模塊通過輸入得到一個 set，複製這個 set，然後返回由此副本決定了順序的結果，這種情況下這項技術特別有用。（客戶通常期望內容返回的順序與它們出現的順序相同。）

此類提供所有可選的 Set 操作，並且允許 null 元素。與 HashSet 一樣，它可以為基本操作（add、contains 和 remove）提供穩定的性能，假定哈希函數將元素正確地分佈到存儲段中。由於增加了維護鏈接列表的開支，其性能很可能會比 HashSet 稍遜一籌，不過，這一點例外：LinkedHashSet 迭代所需時間與 set 的大小 成正比，而與容量無關。HashSet 迭代很可能支出較大，因為它所需迭代時間與其容量 成正比。

鏈接的哈希 set 有兩個影響其性能的參數：初始容量 和載入因數。它們與 HashSet 中的定義極其相同。註意，為初始容量選擇非常高的值對此類的影響比對 HashSet 要小，因為此類的迭代時間不受容量的影響。

註意，此實現不是同步的。如果多個線程同時訪問鏈接的哈希 set，而其中至少一個線程修改了該 set，則它必須 保持外部同步。這一般通過對自然封裝該 set 的對象進行同步操作來完成。如果不存在這樣的對象，則應該使用 Collections.synchronizedSet 方法來“包裝”該 set。最好在創建時完成這一操作，以防止意外的非同步訪問： 

+--SortedSet [I]

進一步提供關於元素的總體排序 的 Set。這些元素使用其自然順序進行排序，或者根據通常在創建有序 set 時提供的 Comparator 進行排序。該 set 的迭代器將按元素升序遍歷 set。提供了一些附加的操作來利用這種排序。（此介面是 SortedMap 的 set 對應介面）。

插入有序 set 的所有元素都必須實現 Comparable 介面（或者被指定的比較器所接受）。另外，所有這些元素都必須是可互相比較的：對於有序 set 中的任意兩個元素 e1 和 e2，執行 e1.compareTo(e2)（或 comparator.compare(e1, e2)）都不得拋出 ClassCastException。試圖違反此限制將導致違反規則的方法或者構造方法調用拋出 ClassCastException。

註意，如果有序 set 要正確實現 Set 介面，則有序 set 所維持的順序（無論是否提供了明確的比較器）都必須與 equals 一致。（有關與 equals 一致 的精確定義，請參閱 Comparable 介面或 Comparator 介面。）這是因為 Set 介面是按照 equals 操作定義的，但有序 set 使用它的 compareTo（或 compare）方法對所有元素進行比較，因此從有序 set 的角度來看，此方法認為相等的兩個元素就是相等的。即使順序與 equals 不一致，有序 set 的行為仍然是 定義良好的，只不過沒有遵守 Set 介面的常規協定。

所有通用有序 set 實現類都應該提供 4 個“標準”構造方法：1) void（無參數）構造方法，它創建一個空的有序 set，按照元素的自然順序進行排序。2) 帶有一個 Comparator 類型參數的構造方法，它創建一個空的有序 set，根據指定的比較器進行排序。3) 帶有一個 Collection 類型參數的構造方法，它創建一個新的有序 set，其元素與參數相同，按照元素的自然順序進行排序。4) 帶有一個 SortedSet 類型參數的構造方法，它創建一個新的有序 set，其元素和排序方法與輸入的有序 set 相同。無法保證強制實施此建議，因為介面不能包含構造方法。

註：一些方法返回具有受限範圍的子集。這些範圍區間是半開的，也就是說，它們包括低端點，但不包括高端點（如果適用）。如果需要一個閉區間（同時包含兩個端點），且元素類型允許計算給定值的後繼值，則只需要請求從 lowEndpoint 到 successor(highEndpoint) 的子區間。例如，假設 s 是一個字元串有序 set。下麵的語句將得到一個包含 s 中從 low 到 high（包括）所有字元串的視圖：

   SortedSet<String> sub = s.subSet(low, high+"\0");

可使用類似的技術生成開區間（兩個端點都不包括）。下麵的語句得到包含 s 中從 low 到 high（不包括）所有字元串的視圖：

   SortedSet<String> sub = s.subSet(low+"\0", high);

+--TreeSet [C]

基於 TreeMap 的 NavigableSet 實現。使用元素的自然順序對元素進行排序，或者根據創建 set 時提供的 Comparator 進行排序，具體取決於使用的構造方法。

此實現為基本操作（add、remove 和 contains）提供受保證的 log(n) 時間開銷。

註意，如果要正確實現 Set 介面，則 set 維護的順序（無論是否提供了顯式比較器）必須與 equals 一致。（關於與 equals 一致 的精確定義，請參閱 Comparable 或 Comparator。）這是因為 Set 介面是按照 equals 操作定義的，但 TreeSet 實例使用它的 compareTo（或 compare）方法對所有元素進行比較，因此從 set 的觀點來看，此方法認為相等的兩個元素就是相等的。即使 set 的順序與 equals 不一致，其行為也是 定義良好的；它只是違背了 Set 介面的常規協定。

註意，此實現不是同步的。如果多個線程同時訪問一個 TreeSet，而其中至少一個線程修改了該 set，那麼它必須 外部同步。這一般是通過對自然封裝該 set 的對象執行同步操作來完成的。如果不存在這樣的對象，則應該使用 Collections.synchronizedSortedSet 方法來“包裝”該 set。此操作最好在創建時進行，以防止對 set 的意外非同步訪問：

   SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

此類的 iterator 方法返回的迭代器是快速失敗 的：在創建迭代器之後，如果從結構上對 set 進行修改，除非通過迭代器自身的 remove 方法，否則在其他任何時間以任何方式進行修改都將導致迭代器拋出 ConcurrentModificationException。因此，對於併發的修改，迭代器很快就完全失敗，而不會冒著在將來不確定的時間發生不確定行為的風險。

註意，迭代器的快速失敗行為無法得到保證，一般來說，存在不同步的併發修改時，不可能作出任何肯定的保證。快速失敗迭代器盡最大努力拋出 ConcurrentModificationException。因此，編寫依賴於此異常的程式的做法是錯誤的，正確做法是：迭代器的快速失敗行為應該僅用於檢測 bug。 

Map [I]

public interface Map<K,V>

將鍵映射到值的對象。一個映射不能包含重覆的鍵；每個鍵最多只能映射到一個值。

此介面取代 Dictionary 類，後者完全是一個抽象類，而不是一個介面。

Map 介面提供三種collection 視圖，允許以鍵集、值集或鍵-值映射關係集的形式查看某個映射的內容。映射順序 定義為迭代器在映射的 collection 視圖上返回其元素的順序。某些映射實現可明確保證其順序，如 TreeMap 類；另一些映射實現則不保證順序，如 HashMap 類。

註：將可變對象用作映射鍵時必須格外小心。當對象是映射中某個鍵時，如果以影響 equals 比較的方式更改了對象的值，則映射的行為將是不確定的。此項禁止的一種特殊情況是不允許某個映射將自身作為一個鍵包含。雖然允許某個映射將自身作為值包含，但請格外小心：在這樣的映射上 equals 和 hashCode 方法的定義將不再是明確的。 

+--SortedMap [I]

進一步提供關於鍵的總體排序 的 Map。該映射是根據其鍵的自然順序進行排序的，或者根據通常在創建有序映射時提供的 Comparator 進行排序。對有序映射的 collection 視圖（由 entrySet、keySet 和 values 方法返回）進行迭代時，此順序就會反映出來。要採用此排序方式，還需要提供一些其他操作（此介面是 SortedSet 的對應映射）。

插入有序映射的所有鍵都必須實現 Comparable 介面（或者被指定的比較器接受）。另外，所有這些鍵都必須是可互相比較的：對有序映射中的任意兩個鍵 k1 和 k2 執行 k1.compareTo(k2)（或 comparator.compare(k1, k2)）都不得拋出 ClassCastException。試圖違反此限制將導致違反規則的方法或者構造方法調用拋出 ClassCastException。

註意，如果有序映射要正確實現 Map 介面，則有序映射所維持的順序（無論是否提供了明確的比較器）都必須與 equals 一致。（有關與 equals 一致 的精確定義，請參閱 Comparable 介面或 Comparator 介面）。這是因為 Map 介面是按照 equals 操作定義的，但有序映射使用它的 compareTo（或 compare）方法對所有鍵進行比較，因此從有序映射的角度來看，此方法認為相等的兩個鍵就是相等的。即使順序與 equals 不一致，樹映射的行為仍然是 定義良好的，只不過沒有遵守 Map 介面的常規協定。 

+--TreeMap [C]

public class TreeMap<K,V>extends AbstractMap<K,V>implements NavigableMap<K,V>, Cloneable, Serializable

基於紅黑樹（Red-Black tree）的 NavigableMap 實現。該映射根據其鍵的自然順序進行排序，或者根據創建映射時提供的 Comparator 進行排序，具體取決於使用的構造方法。

此實現為 containsKey、get、put 和 remove 操作提供受保證的 log(n) 時間開銷。這些演算法是 Cormen、Leiserson 和 Rivest 的 Introduction to Algorithms 中的演算法的改編。

註意，如果要正確實現 Map 介面，則有序映射所保持的順序（無論是否明確提供了比較器）都必須與 equals 一致。（關於與 equals 一致 的精確定義，請參閱 Comparable 或 Comparator）。這是因為 Map 介面是按照 equals 操作定義的，但有序映射使用它的 compareTo（或 compare）方法對所有鍵進行比較，因此從有序映射的觀點來看，此方法認為相等的兩個鍵就是相等的。即使排序與 equals 不一致，有序映射的行為仍然是 定義良好的，只不過沒有遵守 Map 介面的常規協定。 

+--Hashtable [C]

public class Hashtable<K,V>extends Dictionary<K,V>implements Map<K,V>, Cloneable, Serializable

此類實現一個哈希表，該哈希表將鍵映射到相應的值。任何非 null 對象都可以用作鍵或值。

為了成功地在哈希表中存儲和獲取對象，用作鍵的對象必須實現 hashCode 方法和 equals 方法。

Hashtable 的實例有兩個參數影響其性能：初始容量 和載入因數。容量 是哈希表中桶 的數量，初始容量 就是哈希表創建時的容量。註意，哈希表的狀態為 open：在發生“哈希衝突”的情況下，單個桶會存儲多個條目，這些條目必須按順序搜索。載入因數 是對哈希表在其容量自動增加之前可以達到多滿的一個尺度。初始容量和載入因數這兩個參數只是對該實現的提示。關於何時以及是否調用 rehash 方法的具體細節則依賴於該實現。

通常，預設載入因數(.75)在時間和空間成本上尋求一種折衷。載入因數過高雖然減少了空間開銷，但同時也增加了查找某個條目的時間（在大多數 Hashtable 操作中，包括 get 和 put 操作，都反映了這一點）。

初始容量主要控制空間消耗與執行 rehash 操作所需要的時間損耗之間的平衡。如果初始容量大於 Hashtable 所包含的最大條目數除以載入因數，則永遠 不會發生 rehash 操作。但是，將初始容量設置太高可能會浪費空間。

如果很多條目要存儲在一個 Hashtable 中，那麼與根據需要執行自動 rehashing 操作來增大表的容量的做法相比，使用足夠大的初始容量創建哈希表或許可以更有效地插入條目。

下麵這個示例創建了一個數字的哈希表。它將數字的名稱用作鍵：

   Hashtable<String, Integer> numbers
     = new Hashtable<String, Integer>();
   numbers.put("one", 1);
   numbers.put("two", 2);
   numbers.put("three", 3);

要獲取一個數字，可以使用以下代碼：

   Integer n = numbers.get("two");
     if (n != null) {
         System.out.println("two = " + n);
     }
   }

+--HashMap [C]

public class HashMap<K,V>extends AbstractMap<K,V>implements Map<K,V>, Cloneable, Serializable

基於哈希表的 Map 介面的實現。此實現提供所有可選的映射操作，並允許使用 null 值和 null 鍵。（除了非同步和允許使用 null 之外，HashMap 類與 Hashtable 大致相同。）此類不保證映射的順序，特別是它不保證該順序恆久不變。

此實現假定哈希函數將元素適當地分佈在各桶之間，可為基本操作（get 和 put）提供穩定的性能。迭代 collection 視圖所需的時間與 HashMap 實例的“容量”（桶的數量）及其大小（鍵-值映射關係數）成比例。所以，如果迭代性能很重要，則不要將初始容量設置得太高（或將載入因數設置得太低）。

HashMap 的實例有兩個參數影響其性能：初始容量 和載入因數。容量 是哈希表中桶的數量，初始容量只是哈希表在創建時的容量。載入因數 是哈希表在其容量自動增加之前可以達到多滿的一種尺度。當哈希表中的條目數超出了載入因數與當前容量的乘積時，則要對該哈希表進行 rehash 操作（即重建內部數據結構），從而哈希表將具有大約兩倍的桶數。

通常，預設載入因數 (.75) 在時間和空間成本上尋求一種折衷。載入因數過高雖然減少了空間開銷，但同時也增加了查詢成本（在大多數 HashMap 類的操作中，包括 get 和 put 操作，都反映了這一點）。在設置初始容量時應該考慮到映射中所需的條目數及其載入因數，以便最大限度地減少 rehash 操作次數。如果初始容量大於最大條目數除以載入因數，則不會發生 rehash 操作。

如果很多映射關係要存儲在 HashMap 實例中，則相對於按需執行自動的 rehash 操作以增大表的容量來說，使用足夠大的初始容量創建它將使得映射關係能更有效地存儲。 

+--LinkedHashMap [C]

public class LinkedHashMap<K,V>extends HashMap<K,V>implements Map<K,V>

Map 介面的哈希表和鏈接列表實現，具有可預知的迭代順序。此實現與 HashMap 的不同之處在於，後者維護著一個運行於所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序，該迭代順序通常就是將鍵插入到映射中的順序（插入順序）。註意，如果在映射中重新插入 鍵，則插入順序不受影響。（如果在調用 m.put(k, v) 前 m.containsKey(k) 返回了 true，則調用時會將鍵 k 重新插入到映射 m 中。）

此實現可以讓客戶避免未指定的、由 HashMap（及 Hashtable）所提供的通常為雜亂無章的排序工作，同時無需增加與 TreeMap 相關的成本。使用它可以生成一個與原來順序相同的映射副本，而與原映射的實現無關：

     void foo(Map m) {
         Map copy = new LinkedHashMap(m);
         ...
     }

如果模塊通過輸入得到一個映射，複製這個映射，然後返回由此副本確定其順序的結果，這種情況下這項技術特別有用。（客戶通常期望返回的內容與其出現的順序相同。）

提供特殊的構造方法來創建鏈接哈希映射，該哈希映射的迭代順序就是最後訪問其條目的順序，從近期訪問最少到近期訪問最多的順序（訪問順序）。這種映射很適合構建 LRU 緩存。調用 put 或 get 方法將會訪問相應的條目（假定調用完成後它還存在）。putAll 方法以指定映射的條目集迭代器提供的鍵-值映射關係的順序，為指定映射的每個映射關係生成一個條目訪問。任何其他方法均不生成條目訪問。特別是，collection 視圖上的操作不 影響底層映射的迭代順序。 

+--WeakHashMap [C]

public class WeakHashMap<K,V>extends AbstractMap<K,V>implements Map<K,V>

以弱鍵 實現的基於哈希表的 Map。在 WeakHashMap 中，當某個鍵不再正常使用時，將自動移除其條目。更精確地說，對於一個給定的鍵，其映射的存在並不阻止垃圾回收器對該鍵的丟棄，這就使該鍵成為可終止的，被終止，然後被回收。丟棄某個鍵時，其條目從映射中有效地移除，因此，該類的行為與其他的 Map 實現有所不同。

null 值和 null 鍵都被支持。該類具有與 HashMap 類相似的性能特征,並具有相同的效能參數初始容量 和載入因數。

像大多數 collection 類一樣，該類是不同步的。可以使用 Collections.synchronizedMap 方法來構造同步的 WeakHashMap。

該類主要與這樣的鍵對象一起使用，其 equals 方法使用 == 運算符來測試對象標識。一旦這種鍵被丟棄，就永遠無法再創建了，所以，過段時間後在 WeakHashMap 中查找此鍵是不可能的，不必對其項已移除而感到驚訝。該類十分適合與 equals 方法不是基於對象標識的鍵對象一起使用，比如，String 實例。然而，對於這種可重新創建的鍵對象，鍵若丟棄，就自動移除 WeakHashMap 條目，這種表現令人疑惑。

WeakHashMap 類的行為部分取決於垃圾回收器的動作，所以，幾個常見的（雖然不是必需的）Map 常量不支持此類。因為垃圾回收器在任何時候都可能丟棄鍵，WeakHashMap 就像是一個被悄悄移除條目的未知線程。特別地，即使對 WeakHashMap 實例進行同步，並且沒有調用任何賦值方法，在一段時間後 size 方法也可能返回較小的值，對於 isEmpty 方法，返回 false，然後返回 true，對於給定的鍵，containsKey 方法返回 true 然後返回 false，對於給定的鍵，get 方法返回一個值，但接著返回 null，對於以前出現在映射中的鍵，put 方法返回 null，而 remove 方法返回 false，對於鍵 set、值 collection 和條目 set 進行的檢查，生成的元素數量越來越少。

WeakHashMap 中的每個鍵對象間接地存儲為一個弱引用的指示對象。因此，不管是在映射內還是在映射之外，只有在垃圾回收器清除某個鍵的弱引用之後，該鍵才會自動移除。