Java 中集合常用類及其詳解

public interface Map<K,V>

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

此接口取代 Dictionary 類，后者完全是一個抽象類，而不是一個接口。

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

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

所有通用的映射實現類應該提供兩個“標準的”構造方法：一個 void（無參數）構造方法，用于創建空映射；一個是帶有單個 Map 類型參數的構造方法，用于創建一個與其參數具有相同鍵-值映射關系的新映射。實際上，后一個構造方法允許用戶復制任意映射，生成所需類的一個等價映射。盡管無法強制執行此建議（因為接口不能包含構造方法），但是 JDK 中所有通用的映射實現都遵從它。

此接口中包含的“破壞”方法可修改其操作的映射，如果此映射不支持該操作，這些方法將拋出 UnsupportedOperationException。如果是這樣，那么在調用對映射無效時，這些方法可以（但不要求）拋出 UnsupportedOperationException。例如，如果某個不可修改的映射（其映射關系是“重疊”的）為空，則對該映射調用 putAll(Map) 方法時，可以（但不要求）拋出異常。

某些映射實現對可能包含的鍵和值有所限制。例如，某些實現禁止 null 鍵和值，另一些則對其鍵的類型有限制。嘗試插入不合格的鍵或值將拋出一個未經檢查的異常，通常是 NullPointerException 或 ClassCastException。試圖查詢是否存在不合格的鍵或值可能拋出異常，或者返回 false；某些實現將表現出前一種行為，而另一些則表現后一種。一般來說，試圖對不合格的鍵或值執行操作且該操作的完成不會導致不合格的元素被插入映射中時，將可能拋出一個異常，也可能操作成功，這取決于實現本身。這樣的異常在此接口的規范中標記為“可選”。

此接口是 Java Collections Framework 的成員。

Collections Framework 接口中的很多方法是根據 equals 方法定義的。例如，containsKey(Object key) 方法的規范中寫道：“當且僅當此映射包含針對滿足 (key==null ? k==null : key.equals(k)) 的鍵 k 的映射關系時，返回 true”。不 應將此規范解釋為：調用具有非空參數 key 的 Map.containsKey 將導致對任意的鍵 k 調用 key.equals(k)。實現可隨意進行優化，以避免調用 equals，例如，可首先比較兩個鍵的哈希碼（Object.hashCode() 規范保證哈希碼不相等的兩個對象不會相等）。一般來說，只要實現者認為合適，各種 Collections Framework 接口的實現可隨意利用底層 Object 方法的指定行為。

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 操作以增大表的容量來說，使用足夠大的初始容量創建它將使得映射關系能更有效地存儲。

注意，此實現不是同步的。如果多個線程同時訪問一個哈希映射，而其中至少一個線程從結構上修改了該映射，則它必須 保持外部同步。（結構上的修改是指添加或刪除一個或多個映射關系的任何操作；僅改變與實例已經包含的鍵關聯的值不是結構上的修改。）這一般通過對自然封裝該映射的對象進行同步操作來完成。如果不存在這樣的對象，則應該使用 Collections.synchronizedMap 方法來“包裝”該映射。最好在創建時完成這一操作，以防止對映射進行意外的非同步訪問，如下所示：

   Map m = Collections.synchronizedMap(new HashMap(...));

由所有此類的“collection 視圖方法”所返回的迭代器都是快速失敗 的：在迭代器創建之后，如果從結構上對映射進行修改，除非通過迭代器本身的 remove 方法，其他任何時間任何方式的修改，迭代器都將拋出 ConcurrentModificationException。因此，面對并發的修改，迭代器很快就會完全失敗，而不冒在將來不確定的時間發生任意不確定行為的風險。

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

此類是 Java Collections Framework 的成員。

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 視圖上的操作不 影響底層映射的迭代順序。

可以重寫 removeEldestEntry(Map.Entry) 方法來實施策略，以便在將新映射關系添加到映射時自動移除舊的映射關系。

此類提供所有可選的 Map 操作，并且允許 null 元素。與 HashMap 一樣，它可以為基本操作（add、contains 和 remove）提供穩定的性能，假定哈希函數將元素正確分布到桶中。由于增加了維護鏈接列表的開支，其性能很可能比 HashMap 稍遜一籌，不過這一點例外：LinkedHashMap 的 collection 視圖迭代所需時間與映射的大小 成比例。HashMap 迭代時間很可能開支較大，因為它所需要的時間與其容量 成比例。

鏈接的哈希映射具有兩個影響其性能的參數：初始容量和加載因子。它們的定義與 HashMap 極其相似。要注意，為初始容量選擇非常高的值對此類的影響比對 HashMap 要小，因為此類的迭代時間不受容量的影響。

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

    Map m = Collections.synchronizedMap(new LinkedHashMap(...));

結構修改是指添加或刪除一個或多個映射關系，或者在按訪問順序鏈接的哈希映射中影響迭代順序的任何操作。在按插入順序鏈接的哈希映射中，僅更改與映射中已包含鍵關聯的值不是結構修改。在按訪問順序鏈接的哈希映射中，僅利用 get 查詢映射不是結構修改。）

Collection（由此類的所有 collection 視圖方法所返回）的 iterator 方法返回的迭代器都是快速失敗 的：在迭代器創建之后，如果從結構上對映射進行修改，除非通過迭代器自身的 remove 方法，其他任何時間任何方式的修改，迭代器都將拋出 ConcurrentModificationException。因此，面對并發的修改，迭代器很快就會完全失敗，而不冒將來不確定的時間任意發生不確定行為的風險。

注意，迭代器的快速失敗行為無法得到保證，因為一般來說，不可能對是否出現不同步并發修改做出任何硬性保證。快速失敗迭代器會盡最大努力拋出 ConcurrentModificationException。因此，編寫依賴于此異常的程序的方式是錯誤的，正確做法是：迭代器的快速失敗行為應該僅用于檢測程序錯誤。

此類是 Java Collections Framework 的成員。

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);

     }

   }

由所有類的“collection 視圖方法”返回的 collection 的 iterator 方法返回的迭代器都是快速失敗 的：在創建 Iterator 之后，如果從結構上對 Hashtable 進行修改，除非通過 Iterator 自身的 remove 方法，否則在任何時間以任何方式對其進行修改，Iterator 都將拋出ConcurrentModificationException。因此，面對并發的修改，Iterator 很快就會完全失敗，而不冒在將來某個不確定的時間發生任意不確定行為的風險。由 Hashtable 的鍵和元素方法返回的 Enumeration 不 是快速失敗的。

注意，迭代器的快速失敗行為無法得到保證，因為一般來說，不可能對是否出現不同步并發修改做出任何硬性保證。快速失敗迭代器會盡最大努力拋出 ConcurrentModificationException。因此，為提高這類迭代器的正確性而編寫一個依賴于此異常的程序是錯誤做法：迭代器的快速失敗行為應該僅用于檢測程序錯誤。

從Java 2 平臺 v1.2起，此類就被改進以實現 Map 接口，使它成為 Java Collections Framework 中的一個成員。不像新的 collection 實現，Hashtable 是同步的

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 接口的常規協定。

注意，此實現不是同步的。如果多個線程同時訪問一個映射，并且其中至少一個線程從結構上修改了該映射，則其必須 外部同步。（結構上的修改是指添加或刪除一個或多個映射關系的操作；僅改變與現有鍵關聯的值不是結構上的修改。）這一般是通過對自然封裝該映射的對象執行同步操作來完成的。如果不存在這樣的對象，則應該使用 Collections.synchronizedSortedMap 方法來“包裝”該映射。最好在創建時完成這一操作，以防止對映射進行意外的不同步訪問，如下所示：

   SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

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

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

此類及其視圖中的方法返回的所有 Map.Entry 對都表示生成它們時的映射關系的快照。它們不 支持 Entry.setValue 方法。（不過要注意的是，使用 put 更改相關映射中的映射關系是有可能的。）

此類是 Java Collections Framework 的成員。

public interface SortedMap<K,V>

extends Map<K,V>

進一步提供關于鍵的總體排序 的 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 接口的常規協定。

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

注：一些方法返回具有受限鍵范圍的子映射。這些范圍區間是半開的，也就是說，它們包括低端點，但不包括高端點（如果適用）。如果需要一個閉區間（同時包括兩個端點），且鍵類型允許計算給定鍵值的后繼值，則只需要請求從 lowEndpoint 到 successor(highEndpoint) 的子區間。例如，假設 m 是一個用字符串作為鍵的映射。下面的語句將得到一個包含 m 中鍵在 low 和 high（包括）之間的所有鍵-值映射關系的視圖：

   SortedMap<String, V> sub = m.subMap(low, high+"\0");

可使用類似的技術生成一個開區間 （兩個端點都不包括）。下面的語句將得到一個包含 m 中鍵在 low 和 high（不包括）之間的所有鍵-值映射關系的視圖：

   SortedMap<String, V> sub = m.subMap(low+"\0", high);

此接口是 Java Collections Framework 的成員。

public interface Set<E>

extends Collection<E>

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

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

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

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

某些 set 實現對其所包含的元素有所限制。例如，某些實現禁止 null 元素，而某些則對其元素的類型所有限制。試圖添加不合格的元素會拋出未經檢查的異常，通常是 NullPointerException 或 ClassCastException。試圖查詢不合格的元素是否存在可能會拋出異常，也可能簡單地返回 false；某些實現會采用前一種行為，而某些則采用后者。概括地說，試圖對不合格元素執行操作時，如果完成該操作后不會導致在 set 中插入不合格的元素，則該操作可能拋出一個異常，也可能成功，這取決于實現的選擇。此接口的規范中將這樣的異常標記為“可選”。

此接口是 Java Collections Framework 的成員。

public class HashSet<E>

extends AbstractSet<E>

implements Set<E>, Cloneable, Serializable

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

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

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

   Set s = Collections.synchronizedSet(new HashSet(...));

此類的 iterator 方法返回的迭代器是快速失敗 的：在創建迭代器之后，如果對 set 進行修改，除非通過迭代器自身的 remove 方法，否則在任何時間以任何方式對其進行修改，Iterator 都將拋出 ConcurrentModificationException。因此，面對并發的修改，迭代器很快就會完全失敗，而不冒將來在某個不確定時間發生任意不確定行為的風險。

注意，迭代器的快速失敗行為無法得到保證，因為一般來說，不可能對是否出現不同步并發修改做出任何硬性保證。快速失敗迭代器在盡最大努力拋出 ConcurrentModificationException。因此，為提高這類迭代器的正確性而編寫一個依賴于此異常的程序是錯誤做法：迭代器的快速失敗行為應該僅用于檢測 bug。

此類是 Java Collections Framework 的成員。

public class LinkedHashSet<E>

extends HashSet<E>

implements Set<E>, Cloneable, Serializable

具有可預知迭代順序的 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。最好在創建時完成這一操作，以防止意外的非同步訪問：

     Set s = Collections.synchronizedSet(new LinkedHashSet(...));

 

此類的 iterator 方法返回的迭代器是快速失敗 的：在迭代器創建之后，如果對 set 進行修改，除非通過迭代器自身的 remove 方法，其他任何時間任何方式的修改，迭代器都將拋出 ConcurrentModificationException。因此，面對并發的修改，迭代器很快就會完全失敗，而不冒將來不確定的時間任意發生不確定行為的風險。

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

此類是 Java Collections Framework 的成員。

public class TreeSet<E>

extends AbstractSet<E>

implements NavigableSet<E>, Cloneable, Serializable

基于 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。

此類是 Java Collections Framework 的成員。

public interface SortedSet<E>

extends Set<E>

進一步提供關于元素的總體排序 的 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);

此接口是 Java Collections Framework 的成員。