在Java中有各種的數(shù)據(jù)結(jié)構(gòu)，有數(shù)組，鏈表，集合等等，我們也都經(jīng)常使用，但是很多在寫業(yè)務(wù)代碼的時候，很少去看這個源碼問題，所以我們今天來看看這個關(guān)于Java 中的一個集合，也就是 HashSet。

Java中的HashSet

Java中的HashSet是Java集合框架（Java Collections Framework）的一部分，它實現(xiàn)了Set接口。HashSet存儲的元素是不重復(fù)的，并且它不保證集合的迭代順序。HashSet允許存儲null元素，但最多只能有一個null元素，因為集合中的元素是根據(jù)它們的hashCode()方法的返回值來存儲的，并且如果兩個元素的hashCode()值相同，那么它們的equals()方法也會被調(diào)用以確定它們是否相等。

至于內(nèi)部實現(xiàn)，我們來看一下：

HashSet實際上是基于HashMap實現(xiàn)的，它使用HashMap來存儲元素。HashSet中的每個元素都存儲為HashMap中的一個鍵（key），而對應(yīng)的值（value）則是一個固定的對象（在Java 8及更高版本中，這個對象是一個名為PRESENT的靜態(tài)常量，而在Java 7及更早版本中，它通常是一個Object類型的空值，如null或新創(chuàng)建的Object()實例）。

HashSet的源碼分析

繼承與實現(xiàn)

HashSet類繼承自AbstractSet類，并實現(xiàn)了Set、Cloneable和java.io.Serializable接口。這意味著HashSet是一個集合，支持克隆和序列化。

public class HashSet<E>  
    extends AbstractSet<E>  
    implements Set<E>, Cloneable, java.io.Serializable

重要屬性

HashSet中最重要的屬性是一個HashMap，用于存儲HashSet中的元素。HashMap的鍵是HashSet中的元素，而所有的鍵都映射到同一個虛擬的值（PRESENT），這個值是一個靜態(tài)常量，用于占位。

// 使用HashMap來存儲HashSet的元素  
private transient HashMap<E,Object> map;  
// HashMap中所有鍵對應(yīng)的虛擬值  
private static final Object PRESENT = new Object();

構(gòu)造方法

HashSet提供了多種構(gòu)造方法，包括無參構(gòu)造、帶初始容量的構(gòu)造、帶初始容量和加載因子的構(gòu)造，以及通過現(xiàn)有集合構(gòu)造的構(gòu)造方法。

• 無參構(gòu)造：創(chuàng)建一個空的HashSet，其內(nèi)部的HashMap具有默認(rèn)的初始容量（16）和加載因子（0.75）。
• 帶初始容量的構(gòu)造：創(chuàng)建一個空的HashSet，其內(nèi)部的HashMap具有指定的初始容量和默認(rèn)的加載因子（0.75）。
• 帶初始容量和加載因子的構(gòu)造：創(chuàng)建一個空的HashSet，其內(nèi)部的HashMap具有指定的初始容量和指定的加載因子。
• 通過現(xiàn)有集合構(gòu)造：創(chuàng)建一個包含指定集合中所有元素的新集合，其內(nèi)部的HashMap具有默認(rèn)的加載因子（0.75）和足夠的初始容量來包含集合中的元素。

主要方法

• add(E e)：向HashSet中添加一個元素。如果元素不存在，則將其添加到HashMap中，并返回true；如果元素已存在，則不執(zhí)行任何操作并返回false。
• remove(Object o)：從HashSet中移除一個元素。如果元素存在，則將其從HashMap中移除并返回true；如果元素不存在，則返回false。
• contains(Object o)：檢查HashSet中是否包含指定的元素。如果包含，則返回true；否則返回false。

擴容機制

當(dāng)HashMap中的元素數(shù)量超過其容量和加載因子的乘積時（即達(dá)到閾值），HashMap會進(jìn)行擴容。擴容操作會創(chuàng)建一個新的數(shù)組，并將舊數(shù)組中的元素重新計算哈希值后存儲到新數(shù)組中。HashSet的擴容機制依賴于其內(nèi)部HashMap的擴容機制。

HashSet的存儲機制

基于哈希表：HashSet 內(nèi)部維護了一個哈希表（HashMap 的實例），用于存儲集合中的元素。在 HashSet 中，每個元素實際上都作為 HashMap 的一個鍵（key）存儲，而對應(yīng)的值（value）則是一個固定的對象（在 Java 8 及以后版本中，這個固定對象是一個 PRESENT 常量，它是一個 Object 類型的靜態(tài)常量，作為 HashMap 的值存在）。

哈希沖突：由于哈希表的大小是有限的，多個鍵可能通過哈希函數(shù)映射到哈希表的同一個位置，這種現(xiàn)象稱為哈希沖突。HashSet（通過其內(nèi)部的 HashMap）使用鏈表或紅黑樹（在 Java 8 及更高版本中，當(dāng)鏈表長度超過一定閾值時，鏈表會轉(zhuǎn)換為紅黑樹以提高查找效率）來解決哈希沖突。

自定義對象的處理

當(dāng)在HashSet中存儲自定義對象時，需要重寫這些對象的hashCode()和equals()方法。這是因為HashSet（通過其內(nèi)部的HashMap）使用這兩個方法來檢查元素的相等性和確定元素的哈希碼。如果這兩個方法沒有被正確重寫，那么HashSet可能無法正確地存儲和比較自定義對象。

線程安全

HashSet不是線程安全的。如果在多線程環(huán)境下使用，需要外部同步或使用其他并發(fā)集合，如ConcurrentHashMap的鍵集合視圖（盡管這不是HashSet，但提供了一種線程安全的集合實現(xiàn)方式）。然而，Java還提供了Collections.synchronizedSet方法來將任何Set包裝成一個線程安全的Set，但這通常不是最高效的并發(fā)解決方案。

HashSet和HashMap的對比

存儲方式不同：

• HashSet：存儲的是不重復(fù)的元素集合，這些元素可以是任意類型的對象。HashSet實際上是通過HashMap來實現(xiàn)的，它只使用了HashMap的鍵部分，而所有的鍵都映射到同一個虛擬的值（通常是null或某個特定的對象，如PRESENT）。
• HashMap：存儲的是鍵值對（Key-Value Pair），其中鍵是唯一的，而值可以重復(fù)。HashMap允許你根據(jù)鍵來快速查找、更新或刪除對應(yīng)的值。

實現(xiàn)接口不同：

• HashSet：實現(xiàn)了Set接口，繼承自AbstractSet類。
• HashMap：實現(xiàn)了Map接口，繼承自AbstractMap類。

存儲特性：

• HashSet：

不允許存儲重復(fù)的元素。

不保證元素的迭代順序。

允許使用null元素。

• HashMap：

鍵（Key）是唯一的，值（Value）可以重復(fù)。

允許使用null鍵和null值（但最多只能有一個null鍵）。

提供了基于鍵的快速查找、插入和刪除操作。

底層數(shù)據(jù)結(jié)構(gòu)：

• HashSet：底層實際上是一個HashMap實例，它使用哈希表來存儲元素。哈希表是一個無序的數(shù)據(jù)結(jié)構(gòu)，通過哈希函數(shù)將元素映射到數(shù)組的某個位置。
• HashMap：同樣使用哈希表來存儲鍵值對。每個鍵值對都通過哈希函數(shù)計算出一個哈希碼，然后根據(jù)這個哈希碼將鍵值對存儲在數(shù)組的某個位置。如果發(fā)生哈希沖突（即不同的鍵計算出相同的哈希碼），則通過鏈表或紅黑樹（在Java 8及更高版本中）來解決。