Java八股文——集合「Set篇」

Set集合有什么特點？如何實現key無重復的？

面試官您好，Set 集合是 Java 集合框架中的一個重要接口，它繼承自 Collection 接口，其最顯著的特點和設計目標就是存儲一組不重復的元素。

一、Set集合的主要特點：

元素唯一性 (Uniqueness)：
- 這是 Set 最核心的特點。Set 中不允許包含重復的元素。如果你嘗試向一個 Set 中添加一個已經存在的元素（根據 equals() 方法判斷為相同），那么添加操作通常會失敗（或者說，不會改變 Set 的內容），并且 add() 方法會返回 false。
- 這種唯一性是基于對象的 equals() 方法來判斷的。
無序性 (Unordered) 或特定順序 (Ordered)：
- Set 接口本身并不保證元素的任何特定順序。
- 具體的 Set 實現類會決定元素的存儲順序：
  - HashSet：是最常用的 Set 實現，它不保證元素的順序，元素的存儲和迭代順序可能與插入順序不同，并且可能會隨時間變化（例如，在擴容后）。
  - LinkedHashSet：它繼承自 HashSet，但額外維護了一個雙向鏈表來記錄元素的插入順序。因此，LinkedHashSet保證元素按照插入順序進行迭代。
  - TreeSet：它實現了 SortedSet 接口，能夠將元素保持在排序狀態。元素可以按照其自然順序（如果元素實現了 Comparable 接口）或者根據創建 TreeSet 時提供的 Comparator 進行排序。
允許null元素：
- 大多數 Set 實現（如 HashSet 和 LinkedHashSet）允許包含一個null元素。因為 null 也是唯一的。
- TreeSet 默認情況下不允許 null 元素（除非其 Comparator 特別處理了 null 的比較），因為 null 無法進行自然的比較。

二、Set如何實現元素（或稱之為Key）無重復的原理：

Set 接口的實現類通常是基于對應的Map實現來保證元素唯一性的。它們巧妙地利用了 Map 中鍵（Key）的唯一性特性。

HashSet的實現原理：
- HashSet 內部實際上是持有一個HashMap實例。
- 當你向 HashSet 中 add(E e) 一個元素時，這個元素 e 實際上是被當作 HashMap 的鍵（Key） 來存儲的。
- HashMap 的值（Value）部分對于 HashSet 來說并不重要，所以 HashSet 內部會使用一個固定的、虛擬的Object對象（名為PRESENT）作為所有鍵對應的值。

// HashSet 源碼片段 (示意)
private transient HashMap<E,Object> map;
private static final Object PRESENT = new Object();public boolean add(E e) {return map.put(e, PRESENT) == null;
}

因此，HashSet 添加元素的邏輯就轉換為了向內部 HashMap 中 put(element, PRESENT)。
- HashMap 在 put 操作時，會遵循以下步驟來確保鍵的唯一性：
  1. 計算hashCode()：首先計算要添加的元素（作為 Key）的 hashCode() 值，以確定其在 HashMap 內部數組中的存儲位置（哈希桶）。
  2. 檢查沖突并調用equals()：
    - 如果哈希桶為空，直接存入。
    - 如果哈希桶不為空（發生哈希沖突），則會遍歷該桶中的鏈表或紅黑樹，對每個已存在的鍵，使用要添加元素的 equals() 方法進行比較。
    - 如果 equals() 方法返回 true，說明找到了一個與待添加元素相等的鍵，HashMap 不會再次插入這個鍵（而是可能會更新其值，但對于 HashSet，值是固定的 PRESENT，所以實際上是不做任何改變）。
    - 如果遍歷完整個桶都沒有找到 equals() 相等的鍵，則將新元素（作為鍵）添加到鏈表或紅黑樹中。
- 由于 HashMap 保證了其鍵的唯一性，所以依賴于 HashMap 的 HashSet 也就自然地保證了其元素的唯一性。

LinkedHashSet的實現原理：
- 與 HashSet 類似，LinkedHashSet 內部持有的是一個 LinkedHashMap實例。
- LinkedHashMap 在 HashMap 的基礎上額外維護了一個雙向鏈表來記錄鍵的插入順序。因此，LinkedHashSet 能夠保證元素的迭代順序與插入順序一致，同時通過 LinkedHashMap 鍵的唯一性來保證元素的唯一性。
TreeSet的實現原理：
- TreeSet 內部持有的是一個 TreeMap實例(或者更準確地說，是一個 NavigableMap，通常是 TreeMap)。
- 元素被作為 TreeMap 的鍵存儲，值同樣是虛擬的 PRESENT 對象。
- TreeMap 是基于紅黑樹實現的，它通過元素的自然順序（Comparable）或自定義比較器（Comparator）來對鍵進行排序和比較。當添加元素時，TreeMap 會根據比較結果來判斷元素是否已存在（比較結果為0則認為已存在），從而保證元素的唯一性，并維持元素的排序狀態。

總結來說，Set集合通過其內部依賴的Map實現（如HashMap,LinkedHashMap,TreeMap）來巧妙地實現了元素的唯一性。核心機制是：將待添加的元素作為Map的鍵，利用Map在存儲鍵時會先通過hashCode()定位，再通過equals()(或compareTo()對于TreeSet) 精確判斷鍵是否重復的特性，來確保Set中不會出現重復元素。

有序的Set是什么？記錄插入順序的集合是什么？

面試官您好，關于 Java 中有序的 Set 集合以及能記錄插入順序的 Set 集合，主要涉及到以下兩種實現：

一、有序的Set(SortedSet / NavigableSet)

當提到“有序的 Set”，通常指的是元素在集合中按照某種比較規則（自然順序或自定義順序）保持排序狀態。

主要實現類：TreeSet
- TreeSet 實現了 NavigableSet 接口，而 NavigableSet 又繼承了 SortedSet 接口。
- 排序機制：
  - TreeSet 的底層是基于紅黑樹 (Red-Black Tree) 實現的（內部實際上依賴一個 TreeMap）。
  - 它能保證元素在集合中始終處于排序狀態。排序規則可以是：
    1. 自然順序：如果存入 TreeSet 的元素實現了 java.lang.Comparable 接口，并且其 compareTo() 方法定義了元素間的自然比較順序（如數字的大小、字符串的字典序）。
    2. 自定義順序：如果在創建 TreeSet 時提供了一個 java.util.Comparator 對象，那么元素將按照這個比較器定義的規則進行排序。
- 特點：
  - 元素唯一（Set 的基本特性）。
  - 元素有序（按照定義的比較規則）。
  - 提供了豐富的導航方法（如 first(), last(), lower(), higher(), floor(), ceiling(), 以及獲取子集的方法），這些都得益于其有序性。
  - 查找、插入、刪除操作的時間復雜度通常是 O(log N)。
- 注意：TreeSet 默認情況下不允許存入 null 元素，因為 null 無法進行自然的比較。如果需要支持 null，必須提供一個能處理 null 的 Comparator。

二、記錄插入順序的Set

當提到“記錄插入順序的 Set”，指的是集合中的元素在迭代時，其順序與它們被添加到集合中的順序保持一致。

主要實現類：LinkedHashSet
- LinkedHashSet 繼承自 HashSet，并在其基礎上增加了一個機制來維護元素的插入順序。
- 順序機制：
  - LinkedHashSet 內部實際上依賴一個 LinkedHashMap。
  - LinkedHashMap 在 HashMap 的基礎上，額外維護了一個雙向鏈表。這個鏈表連接了所有存入的條目（在 LinkedHashSet 中即元素），并記錄了它們的插入順序。
- 特點：
  - 元素唯一（Set 的基本特性，由其內部 LinkedHashMap 的鍵唯一性保證）。
  - 迭代順序與插入順序一致。這是它與 HashSet（無序）和 TreeSet（按比較規則排序）的主要區別。
  - 查找、插入、刪除操作的平均時間復雜度與 HashSet 類似，通常是 O(1)（假設哈希函數分布良好），但由于維護鏈表的額外開銷，其性能常數因子會略大于 HashSet。
  - 允許一個 null 元素。

總結對比：

特性	`TreeSet`	`LinkedHashSet`	`HashSet` (作為參照)
元素唯一	是	是	是
順序性	按比較規則排序(自然順序或自定義比較器)	按插入順序	無序
底層實現	紅黑樹 (基于 `TreeMap`)	哈希表 + 雙向鏈表 (基于 `LinkedHashMap`)	哈希表 (基于 `HashMap`)
`null`支持	默認不允許 (除非 `Comparator` 支持)	允許一個 `null`	允許一個 `null`
主要用途	需要排序的唯一元素集合	需要保持插入順序的唯一元素集合	不需要特定順序的唯一元素集合

因此：

如果您需要一個根據元素值本身進行排序的 Set，那么應該選擇 TreeSet。
如果您需要一個保持元素插入順序的 Set，那么應該選擇 LinkedHashSet。
如果您對順序沒有要求，只關心元素的唯一性和高效的存取，那么通常選擇 HashSet。

LinkedHashSet 保證的是插入順序，而不是元素本身的自然排序。TreeSet 才保證元素本身的自然排序（或比較器排序）。

Comparable 和 Comparator 的區別

面試官您好，Comparable 和 Comparator 都是 Java 中用于對象比較和排序的核心接口，但它們在設計和使用上有著明確的區別：

一、Comparable接口

定義與來源：
- Comparable 接口位于 java.lang 包下。
- 它只包含一個方法：int compareTo(T o)。
設計意圖 (內比較器 / 自然排序)：
- Comparable 的設計意圖是讓一個類的對象自身具備可比較性。當一個類實現了 Comparable 接口，就意味著這個類的實例可以相互比較大小，它們擁有了所謂的“自然排序”順序。
- 可以把它看作是對象的 “內比較器”或“默認比較規則”。
使用方式：
- 類需要直接實現Comparable接口，并重寫 compareTo(T o) 方法來定義其比較邏輯。
- compareTo(T o) 方法的返回值約定：
  - 如果當前對象 (this) 小于參數對象 o，返回負整數。
  - 如果當前對象 (this) 等于參數對象 o，返回零。
  - 如果當前對象 (this) 大于參數對象 o，返回正整數。
- 一旦類實現了 Comparable，其對象就可以直接被一些排序工具使用，例如：
  - Collections.sort(List<T> list)：如果 List 中的元素類型 T 實現了 Comparable，可以直接調用此方法進行排序。
  - Arrays.sort(T[] a)：同理。
  - TreeSet<T> 和 TreeMap<K,V>：如果元素/鍵 T 或 K 實現了 Comparable，它們在存入這些集合時會自動按自然順序排序。
示例場景：
- 像 String, Integer, Date 等 Java 內置的許多類都實現了 Comparable 接口，定義了它們各自的自然排序規則（如字符串按字典序，數字按大小）。
- 如果我們有一個自定義的 Student 類，我們可能希望它默認按學號排序，那么 Student 類就可以實現 Comparable<Student> 并重寫 compareTo 方法比較學號。

二、Comparator接口

定義與來源：
- Comparator 接口位于 java.util 包下。
- 它主要包含一個方法：int compare(T o1, T o2)。（Java 8 之后還增加了一些默認方法和靜態方法，如 thenComparing, comparingInt 等，用于構建更復雜的比較器）。
設計意圖 (外比較器 / 定制排序)：
- Comparator 的設計意圖是提供一種獨立于對象本身的比較邏輯。它允許我們為那些沒有實現 Comparable 接口的類定義排序規則，或者為已經實現了 Comparable 接口的類提供額外的、不同的排序方式。
- 可以把它看作是對象的 “外比較器”或“定制比較規則”。它像一個“裁判”，專門負責比較兩個對象。
使用方式：
- 創建一個單獨的類來實現Comparator<T>接口，并重寫 compare(T o1, T o2) 方法。
- 或者，更常見的是使用匿名內部類或Lambda 表達式(Java 8+) 來創建一個 Comparator 實例。
- compare(T o1, T o2) 方法的返回值約定：
  - 如果 o1 小于 o2，返回負整數。
  - 如果 o1 等于 o2，返回零。
  - 如果 o1 大于 o2，返回正整數。
- 使用 Comparator 時，通常需要將其作為參數傳遞給排序工具：
  - Collections.sort(List<T> list, Comparator<? super T> c)
  - Arrays.sort(T[] a, Comparator<? super T> c)
  - new TreeSet<T>(Comparator<? super T> comparator)
  - new TreeMap<K,V>(Comparator<? super K> comparator)
示例場景：
- 正如您提到的，如果我們有一個 Song 對象，它可能實現了 Comparable 按歌名排序。但我們有時又想按歌手名排序，或者按發行日期排序，這時就可以創建不同的 Comparator<Song> 實現來滿足這些不同的排序需求。
- 對于第三方庫中的類，如果它們沒有實現 Comparable 或者其自然排序不符合我們的要求，我們就可以通過 Comparator 來定義自己的排序邏輯，而無需修改這些類的源碼。

三、總結與選擇：

特性	`Comparable` (內比較器)	`Comparator` (外比較器)
定義位置	`java.lang`	`java.util`
實現方式	類自身實現接口	單獨的比較器類實現接口，或 Lambda/匿名內部類
方法簽名	`int compareTo(T o)`	`int compare(T o1, T o2)`
主要作用	定義對象的自然排序/默認排序規則	定義對象的定制排序/多種排序規則
耦合性	比較邏輯與類本身耦合	比較邏輯與類解耦
靈活性	一種排序規則	可提供多種排序規則
使用場景	當類有明確的、主要的“自然”比較方式時	當需要多種排序方式，或無法修改類源碼，或排序邏輯與業務場景相關時

簡單來說：

如果一個類有其主要的、通用的比較方式（“自然順序”），那么讓這個類實現 Comparable 接口。
如果需要多種不同的排序方式，或者目標類無法修改（比如是第三方庫的類），或者排序邏輯與特定業務場景緊密相關而非對象的固有屬性，那么應該使用 Comparator。

在實際開發中，兩者經常結合使用。例如，一個類可以實現 Comparable 定義其默認排序，同時我們也可以提供多個 Comparator 來滿足不同的定制化排序需求。

無序性和不可重復性的含義是什么

面試官您好，在討論 Java 集合（特別是像 HashSet 這樣的 Set 實現或 HashMap 的鍵集）時，我們經常提到“無序性”和“不可重復性”，它們的具體含義如下：

一、無序性 (Unordered)

核心含義：
- “無序性”指的是元素在集合中的存儲順序和迭代（遍歷）順序通常與它們的添加順序不一致，并且這種順序通常是不固定的，可能會因為集合內部狀態的變化（如擴容）而改變。
- 正如您所指出的，無序性不等于隨機性 (Randomness)。隨機性意味著每次迭代的順序都可能是完全不可預測且不同的。而對于像 HashSet 這樣的集合，雖然迭代順序與插入順序無關，但在不發生結構性修改（如添加、刪除導致擴容）的情況下，對同一個 HashSet 實例多次迭代，通常會得到相同的元素序列。
原因 (主要針對基于哈希的集合，如HashSet,HashMap)：
- 無序性主要是由其底層數據結構和元素定位機制決定的。
- 對于基于哈希表實現的集合（如 HashSet 內部依賴 HashMap），元素在底層數組中的存儲位置是根據元素的哈希碼 (hashCode()**)**計算得到的。
- 哈希碼本身與元素的添加順序無關。不同的元素，即使添加順序相鄰，它們的哈希碼可能差異很大，從而被映射到底層數組的不同、不連續的位置。
- 因此，當你迭代這樣一個集合時，你實際上是在按某種順序（可能是數組索引順序，加上處理哈希沖突的鏈表/樹的順序）訪問這些由哈希碼決定的存儲位置，這個順序自然就不是元素的插入順序。
需要區分的集合：
- HashSet：是典型的無序集合。
- LinkedHashSet：它雖然是 Set，但通過內部維護一個雙向鏈表來記錄元素的插入順序，所以它是有序的（按插入順序）。
- TreeSet：它也不是無序的，而是按元素的自然順序或自定義比較器順序進行排序的。

二、不可重復性 (No Duplicates / Uniqueness)

核心含義：
- “不可重復性”指的是集合中不能包含兩個或多個“相等”的元素。
- 這個“相等”的判斷標準是基于元素的 equals()方法。如果嘗試向集合中添加一個元素 e1，而集合中已經存在一個元素 e2 使得 e1.equals(e2) 返回 true，那么添加操作通常會失敗（或不改變集合內容），add() 方法會返回 false。
實現機制 (主要針對Set實現)：
- 正如您所說，為了正確實現不可重復性，特別是對于自定義對象，必須同時正確地重寫其equals()方法和hashCode()方法。
- hashCode()的作用：
  - 當向基于哈希的 Set（如 HashSet）中添加元素時，首先會計算元素的 hashCode() 來快速定位其在底層哈希表中的潛在存儲位置（哈希桶）。
- equals()的作用：
  - 如果通過 hashCode() 定位到的哈希桶中已經存在一個或多個元素（即發生哈希沖突），那么集合會逐個調用待添加元素的 equals() 方法與桶中已存在的元素進行比較。
  - 只有當 equals() 方法都返回 false 時，才認為新元素與桶中所有現有元素都不相等，此時才會將新元素添加到該桶中。如果任何一次 equals() 比較返回 true，則認為新元素是重復的，不予添加。
- equals()和hashCode()的協定：
  - 如果 a.equals(b) 為 true，那么 a.hashCode() 必須等于 b.hashCode()。這是保證 Set 能夠正確工作的關鍵。如果相等的對象哈希碼不同，它們可能會被放到不同的桶里，Set 就無法檢測到它們的重復。
示例：
- 如果 Set 中已有一個字符串 "hello"，再嘗試添加另一個內容也是 "hello" 的字符串對象，由于 String 類正確實現了 equals() (比較內容) 和 hashCode() (基于內容計算)，第二個 "hello" 會被認為是重復的，不會被添加。
- 對于自定義的 Person 對象，如果我們希望只要 id 相同就認為是同一個人，那么 Person 類的 equals() 方法就應該只比較 id，并且其 hashCode() 方法也應該主要基于 id 來計算。

總結：

無序性主要描述的是元素在集合中的存儲和迭代順序與添加順序無關，這是由底層哈希定位機制決定的，它不等于隨機。
不可重復性是 Set 的核心特性，意味著集合中不允許存在equals()判斷相等的多個元素，其正確實現依賴于元素類型正確重寫 equals() 和 hashCode() 方法。

理解這兩點對于選擇和使用合適的集合類型非常重要。

比較 HashSet、LinkedHashSet 和 TreeSet 三者的異同

面試官您好，HashSet, LinkedHashSet, 和 TreeSet 都是 Java 集合框架中 Set 接口的重要實現類，它們在保證元素唯一性的基礎上，各自具有不同的特點和適用場景。

一、共同點：

實現Set接口：它們都實現了 java.util.Set 接口，因此都具備 Set 的核心特性。
元素唯一性：它們都能保證集合中的元素是唯一的，不允許重復（根據元素的 equals() 方法判斷）。
非線程安全：這三個類本身都不是線程安全的。如果在多線程環境下需要對它們進行并發修改，必須進行外部同步，或者使用 java.util.concurrent 包下對應的線程安全集合（如 CopyOnWriteArraySet 或通過 Collections.newSetFromMap(new ConcurrentHashMap<>()) 創建）。
允許null元素 (大部分情況)：
- HashSet 和 LinkedHashSet 都允許存儲一個 null 元素。
- TreeSet 默認情況下不允許 null 元素（除非其構造時傳入的 Comparator 明確支持對 null 的比較），因為 null 無法進行自然的比較。

二、主要區別：

主要區別在于它們的底層數據結構不同，這直接導致了它們在元素順序性、性能特性和適用場景上的差異。

HashSet
- 底層數據結構：基于哈希表實現，內部實際上是依賴一個 HashMap 實例。元素作為 HashMap 的鍵存儲，值是一個固定的 PRESENT 對象。
- 元素順序性：無序。它不保證元素的任何特定存儲或迭代順序，元素的順序可能與插入順序不同，并且可能隨時間變化（如擴容后）。
- 性能特性：
  - 添加（add）、刪除（remove）、查找（contains）操作的平均時間復雜度是O(1)（假設哈希函數分布良好，哈希沖突不嚴重）。
  - 最壞情況下的時間復雜度（哈希沖突嚴重導致鏈表過長）是 O(N)。在 JDK 1.8+ 中，當鏈表過長會轉換為紅黑樹，此時最壞情況為 O(log N)。
- 適用場景：當對集合中元素的順序沒有要求，只關心元素的唯一性和高效的存取操作時，HashSet 是最常用的選擇。
LinkedHashSet
- 底層數據結構：基于哈希表 + 雙向鏈表實現。它繼承自 HashSet，內部依賴一個 LinkedHashMap 實例。
- 元素順序性：有序，保持插入順序。迭代時，元素將按照它們被添加到集合中的順序出現。
- 性能特性：
  - 添加、刪除、查找操作的平均時間復雜度仍然是O(1)（與 HashSet 類似）。
  - 但由于需要額外維護雙向鏈表，其性能常數因子會略大于 HashSet（即，在相同數據量和哈希分布下，LinkedHashSet 的操作會比 HashSet 稍微慢一點點）。
- 適用場景：當既需要保證元素的唯一性，又需要保持元素插入時的順序時，LinkedHashSet 是理想選擇。例如，實現 LRU (Least Recently Used) 緩存的鍵集合時，或者需要按歷史記錄順序展示唯一項時。
TreeSet
- 底層數據結構：基于紅黑樹 (Red-Black Tree) 實現。內部依賴一個 TreeMap 實例（更準確地說是 NavigableMap）。
- 元素順序性：有序，按照元素的比較規則排序。
  - 可以是元素的自然順序（如果元素實現了 Comparable 接口）。
  - 也可以是根據創建 TreeSet 時提供的自定義比較器 (Comparator) 的順序。
- 性能特性：
  - 添加、刪除、查找操作的時間復雜度是O(log N)，其中 N 是集合中元素的數量。這是由紅黑樹的特性決定的。
- 適用場景：當需要一個自動排序的、元素唯一的集合時，TreeSet 是最佳選擇。它還提供了豐富的導航方法（如獲取最小/最大元素、獲取某個范圍的子集等）。

三、總結列表：

特性	`HashSet`	`LinkedHashSet`	`TreeSet`
元素唯一	是	是	是
線程安全	否	否	否
`null`支持	允許一個	允許一個	默認不允許 (除非 `Comparator` 支持)
順序性	無序	按插入順序	按比較規則排序 (自然/自定義)
底層實現	哈希表 (基于 `HashMap`)	哈希表 + 雙向鏈表 (基于 `LinkedHashMap`)	紅黑樹 (基于 `TreeMap`)
性能 (平均)	O(1) (add, remove, contains)	O(1) (add, remove, contains) (略慢于HashSet)	O(log N) (add, remove, contains)
主要用途	快速存取，無序唯一集合	保持插入順序的唯一集合	自動排序的唯一集合，支持導航操作