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

Java中的HashSet

Java中的HashSet是Java集合框架（Java Collections Framework）的一部分，它實(shí)現(xiàn)了Set接口。HashSet存儲(chǔ)的元素是不重復(fù)的，并且它不保證集合的迭代順序。HashSet允許存儲(chǔ)null元素，但最多只能有一個(gè)null元素，因?yàn)榧现械脑厥歉鶕?jù)它們的hashCode()方法的返回值來存儲(chǔ)的，并且如果兩個(gè)元素的hashCode()值相同，那么它們的equals()方法也會(huì)被調(diào)用以確定它們是否相等。

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

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

HashSet的源碼分析

繼承與實(shí)現(xiàn)

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

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

重要屬性

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

// 使用HashMap來存儲(chǔ)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)建一個(gè)空的HashSet，其內(nèi)部的HashMap具有默認(rèn)的初始容量（16）和加載因子（0.75）。
• 帶初始容量的構(gòu)造：創(chuàng)建一個(gè)空的HashSet，其內(nèi)部的HashMap具有指定的初始容量和默認(rèn)的加載因子（0.75）。
• 帶初始容量和加載因子的構(gòu)造：創(chuàng)建一個(gè)空的HashSet，其內(nèi)部的HashMap具有指定的初始容量和指定的加載因子。
• 通過現(xiàn)有集合構(gòu)造：創(chuàng)建一個(gè)包含指定集合中所有元素的新集合，其內(nèi)部的HashMap具有默認(rèn)的加載因子（0.75）和足夠的初始容量來包含集合中的元素。

主要方法

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

擴(kuò)容機(jī)制

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

HashSet的存儲(chǔ)機(jī)制

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

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

自定義對象的處理

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

線程安全

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

HashSet和HashMap的對比

存儲(chǔ)方式不同：

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

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

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

存儲(chǔ)特性：

• HashSet：

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

不保證元素的迭代順序。

允許使用null元素。

• HashMap：

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

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

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

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

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