詳細(xì)解讀 Java 中的 HashSet
在Java中有各種的數(shù)據(jù)結(jié)構(gòu)，有數(shù)組，鏈表，集合等等，我們也都經(jīng)常使用，但是很多在寫業(yè)務(wù)代碼的時(shí)候，很少去看這個(gè)源碼問(wèn)題，所以我們今天來(lái)看看這個(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()方法的返回值來(lái)存儲(chǔ)的，并且如果兩個(gè)元素的hashCode()值相同，那么它們的equals()方法也會(huì)被調(diào)用以確定它們是否相等。
至于內(nèi)部實(shí)現(xiàn)，我們來(lái)看一下：
HashSet實(shí)際上是基于HashMap實(shí)現(xiàn)的，它使用HashMap來(lái)存儲(chǔ)元素。HashSet中的每個(gè)元素都存儲(chǔ)為HashMap中的一個(gè)鍵（key），而對(duì)應(yīng)的值（value）則是一個(gè)固定的對(duì)象（在Java 8及更高版本中，這個(gè)對(duì)象是一個(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來(lái)存儲(chǔ)HashSet的元素
private transient HashMap<E,Object> map;
// HashMap中所有鍵對(duì)應(yīng)的虛擬值
private static final Object PRESENT = new Object();構(gòu)造方法
HashSet提供了多種構(gòu)造方法，包括無(wú)參構(gòu)造、帶初始容量的構(gòu)造、帶初始容量和加載因子的構(gòu)造，以及通過(guò)現(xiàn)有集合構(gòu)造的構(gòu)造方法。
- 無(wú)參構(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具有指定的初始容量和指定的加載因子。
- 通過(guò)現(xiàn)有集合構(gòu)造：創(chuàng)建一個(gè)包含指定集合中所有元素的新集合，其內(nèi)部的HashMap具有默認(rèn)的加載因子（0.75）和足夠的初始容量來(lái)包含集合中的元素。
主要方法
- 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ù)量超過(guò)其容量和加載因子的乘積時(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ǔ)，而對(duì)應(yīng)的值（value）則是一個(gè)固定的對(duì)象（在 Java 8 及以后版本中，這個(gè)固定對(duì)象是一個(gè) PRESENT 常量，它是一個(gè) Object 類型的靜態(tài)常量，作為 HashMap 的值存在）。
哈希沖突：由于哈希表的大小是有限的，多個(gè)鍵可能通過(guò)哈希函數(shù)映射到哈希表的同一個(gè)位置，這種現(xiàn)象稱為哈希沖突。HashSet（通過(guò)其內(nèi)部的 HashMap）使用鏈表或紅黑樹(shù)（在 Java 8 及更高版本中，當(dāng)鏈表長(zhǎng)度超過(guò)一定閾值時(shí)，鏈表會(huì)轉(zhuǎn)換為紅黑樹(shù)以提高查找效率）來(lái)解決哈希沖突。
自定義對(duì)象的處理
當(dāng)在HashSet中存儲(chǔ)自定義對(duì)象時(shí)，需要重寫這些對(duì)象的hashCode()和equals()方法。這是因?yàn)镠ashSet（通過(guò)其內(nèi)部的HashMap）使用這兩個(gè)方法來(lái)檢查元素的相等性和確定元素的哈希碼。如果這兩個(gè)方法沒(méi)有被正確重寫，那么HashSet可能無(wú)法正確地存儲(chǔ)和比較自定義對(duì)象。
線程安全
HashSet不是線程安全的。如果在多線程環(huán)境下使用，需要外部同步或使用其他并發(fā)集合，如ConcurrentHashMap的鍵集合視圖（盡管這不是HashSet，但提供了一種線程安全的集合實(shí)現(xiàn)方式）。然而，Java還提供了Collections.synchronizedSet方法來(lái)將任何Set包裝成一個(gè)線程安全的Set，但這通常不是最高效的并發(fā)解決方案。
HashSet和HashMap的對(duì)比
存儲(chǔ)方式不同：
- HashSet：存儲(chǔ)的是不重復(fù)的元素集合，這些元素可以是任意類型的對(duì)象。HashSet實(shí)際上是通過(guò)HashMap來(lái)實(shí)現(xiàn)的，它只使用了HashMap的鍵部分，而所有的鍵都映射到同一個(gè)虛擬的值（通常是null或某個(gè)特定的對(duì)象，如PRESENT）。
- HashMap：存儲(chǔ)的是鍵值對(duì)（Key-Value Pair），其中鍵是唯一的，而值可以重復(fù)。HashMap允許你根據(jù)鍵來(lái)快速查找、更新或刪除對(duì)應(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í)例，它使用哈希表來(lái)存儲(chǔ)元素。哈希表是一個(gè)無(wú)序的數(shù)據(jù)結(jié)構(gòu)，通過(guò)哈希函數(shù)將元素映射到數(shù)組的某個(gè)位置。
- HashMap：同樣使用哈希表來(lái)存儲(chǔ)鍵值對(duì)。每個(gè)鍵值對(duì)都通過(guò)哈希函數(shù)計(jì)算出一個(gè)哈希碼，然后根據(jù)這個(gè)哈希碼將鍵值對(duì)存儲(chǔ)在數(shù)組的某個(gè)位置。如果發(fā)生哈希沖突（即不同的鍵計(jì)算出相同的哈希碼），則通過(guò)鏈表或紅黑樹(shù)（在Java 8及更高版本中）來(lái)解決。
