HashSet底層竟然是HashMap實(shí)現(xiàn)

HashSet雖然實(shí)現(xiàn)的是Set - Collection接口，但其源碼是通過(guò)new HashMap()實(shí)現(xiàn)的，底層數(shù)據(jù)結(jié)構(gòu)是哈希表，存取都比較快，線(xiàn)程不安全。

特點(diǎn)

1. 無(wú)序集合，不保證存儲(chǔ)元素的順序，沒(méi)有索引

2. 不能存儲(chǔ)重復(fù)元素

3. 可以存儲(chǔ)Null

存取基本操作

Iterator的獲取跟ArrayList一樣：

HashSet<String> hashSet = new HashSet<>();
        hashSet.add("asf");
        hashSet.add("bnk");
        hashSet.add("lsk");
        hashSet.add("owie");
        System.out.println(hashSet);
        Iterator<String> it = hashSet.iterator();
        while (it.hasNext()) {
            String ele = (String) it.next();
            System.out.println(ele);
        }
        System.out.println("---------------------------");
        for (String ele : hashSet) {
            System.out.println(ele);
        }

查看HashSet源碼，其操作底層都是通過(guò)調(diào)用HashMap方法實(shí)現(xiàn)的，HashSet會(huì)將元素存儲(chǔ)在HashMap的key集合中，然后為value賦一個(gè)static空對(duì)象PRESENT。

HashSet不能存儲(chǔ)重復(fù)元素，因?yàn)镠ashMap的key集合不可以重復(fù)，本質(zhì)也是通過(guò)equals()和hashCode()來(lái)判定兩個(gè)對(duì)象是否重復(fù)，因此將對(duì)象存儲(chǔ)在HashSet之前，必須先重寫(xiě)對(duì)象的equals()和hashCode()方法。

hashCode原則：

兩個(gè)對(duì)象的hashCode()相等，equals()未必返回true

兩個(gè)對(duì)象equals()返回true，它們的hashCode()一定相等

HashMap中，只有兩個(gè)對(duì)象hashCode()相等，且equals()相同，才判定為重復(fù)元素，重寫(xiě)對(duì)象的equals()方法一定要同時(shí)重寫(xiě)hashCode()以符合原則。

HashSet底層實(shí)現(xiàn)解析

1.實(shí)現(xiàn)了Set接口

2.底層實(shí)際上是HashMap()

底層數(shù)據(jù)結(jié)構(gòu)為：Node[]數(shù)組 + 單鏈表 + 紅黑樹(shù)

Set set = new HashSet();使用無(wú)參構(gòu)造方法創(chuàng)建hashset對(duì)象，實(shí)際上創(chuàng)建了hashmap，初始大小默認(rèn)為16，加載因子默認(rèn)為 0.75.

當(dāng)調(diào)用add方法添加元素時(shí)，其實(shí)調(diào)用的是map.put()方法

這里的key就是要添加的元素，value是一個(gè)object類(lèi)型的共享常量，占了一個(gè)坑位，并沒(méi)有實(shí)際意義。

當(dāng)返回值為null的時(shí)候，說(shuō)明添加成功

解析：首先，調(diào)用map.put();方法，跟蹤發(fā)現(xiàn)實(shí)際上調(diào)用putVal();方法

參數(shù)說(shuō)明：hash(key)：hash()函數(shù)的返回值，返回的并不是key的hashCode值，而是經(jīng)過(guò)處理hashCode得到的值（目的就是盡可能減少hash沖突），（若待加入元素 key 為 基礎(chǔ)數(shù)據(jù)類(lèi)型 或 封裝數(shù)據(jù)類(lèi)型（Java中已經(jīng)重寫(xiě)），不需要重寫(xiě) equals 和 hashCode方法；若key為自定義數(shù)據(jù)類(lèi)型，往往需要重寫(xiě) equals 和 hashCode 方法。

例（不重寫(xiě)方法）：

輸出：

說(shuō)明是兩個(gè)不同的對(duì)象，但是理論上應(yīng)該是相同對(duì)象。

具體要不要重寫(xiě)方法以及如何重寫(xiě)，都要根據(jù)實(shí)際需求決定

key：待添加的元素。

value：共享常量PRESENT，沒(méi)有實(shí)際意義（因?yàn)閯?chuàng)建的是hashset對(duì)象，并沒(méi)有value，但是當(dāng)頂層創(chuàng)建的是hashmap對(duì)象時(shí)候，調(diào)用的直接是map.put()方法，那value對(duì)應(yīng)的就是實(shí)際當(dāng)中的value，就沒(méi)有PRESENT了）。

onlyIfAbsent*：若為true，則不改變現(xiàn)存的value，默認(rèn)為false。

evict*：若為false，表示當(dāng)前表處于創(chuàng)建模式。

putVal();方法的具體實(shí)現(xiàn)

（1）首次添加元素 key

首先，創(chuàng)建兩個(gè)臨時(shí)變量 Node類(lèi)型的數(shù)組 Node[] tab,Node<k,v>類(lèi)型的 p，判斷當(dāng)前hash表是否為空，若滿(mǎn)足條件，調(diào)用resize()方法，擴(kuò)容。

resize()方法：

由于用無(wú)參構(gòu)造器創(chuàng)建對(duì)象，因此hashtable為空，oldCap為0，oldThr為0，if條件不滿(mǎn)足跳過(guò)，進(jìn)入else

新數(shù)組容量 newCap 為默認(rèn)大小 16，新的加載因子為默認(rèn) 0.75，newThr為擴(kuò)容閾值（即當(dāng)數(shù)組的數(shù)據(jù)量達(dá)到閾值以后，就會(huì)擴(kuò)容，目的就是當(dāng)并發(fā)量過(guò)大以后，能夠有緩沖空間）。

newThr = 加載因子*數(shù)組大小 ，在大小都默認(rèn)的情況下，閾值為12

最后 return 擴(kuò)容后的數(shù)組，并返回 putVal(); 方法中繼續(xù)：

在 if ((p = tab[i = (n - 1) & hash]) == null) 中，首先用算法 i = (n - 1) & hash獲得當(dāng)前 待添加元素 key 應(yīng)該添加的數(shù)組下標(biāo) i ，同時(shí)獲取到當(dāng)前位置上的所存儲(chǔ)的鏈表的頭節(jié)點(diǎn)，并將節(jié)點(diǎn)賦值給變量 p ，若該節(jié)點(diǎn)為空（即當(dāng)前位置無(wú)數(shù)據(jù)），就把待添加元素 key 封裝成一個(gè)節(jié)點(diǎn)Node，放到當(dāng)前位置當(dāng)作該鏈表的頭節(jié)點(diǎn)。

最后操作計(jì)數(shù)+1，數(shù)據(jù)量size+1，并且若size大于擴(kuò)容閾值，則進(jìn)行擴(kuò)容。返回 null 表示添加成功。（到此往數(shù)組中首次添加元素操作結(jié)束）

（2）添加重復(fù)元素流程分析

在鏈表上找是否有重復(fù)元素，只能從頭節(jié)點(diǎn)遍歷該鏈表。當(dāng) if 條件判斷當(dāng)前下標(biāo) i 位置上不為空的時(shí)候（即鏈表頭節(jié)點(diǎn)），就要開(kāi)始遍歷。

定義需要的變量 Node<k,v> e （一個(gè)指針） ,以及 K k首先判斷頭節(jié)點(diǎn)是否與待添加的元素重復(fù)：

1）hash值是否相等，這是前提（重復(fù)元素hashCode值必相等，則hash值也必相等）

2）待添加元素 key 與 當(dāng)前節(jié)點(diǎn)的 key 是否是同一對(duì)象，或者帶添加的 key 與當(dāng)前節(jié)點(diǎn)的 key 內(nèi)容 是否相等，兩者若有一個(gè)相同則說(shuō)明是重復(fù)元素

若頭節(jié)點(diǎn)就重復(fù)，則把頭節(jié)點(diǎn) p 賦給 e;（否則，判斷當(dāng)前頭節(jié)點(diǎn) p 是否是紅黑樹(shù)類(lèi)型）

若是樹(shù)類(lèi)型，則按照樹(shù)節(jié)點(diǎn)進(jìn)行操作。若不是樹(shù)類(lèi)型，則繼續(xù)遍歷當(dāng)前鏈表：

這里的 for 是一個(gè)死循環(huán)，退出的條件就是找到重復(fù)元素或遍歷到鏈表結(jié)尾(肯定可以退出)。

判斷是否重復(fù)，與上面的條件一樣。

①若遍歷到結(jié)尾沒(méi)有發(fā)現(xiàn)重復(fù)元素，則將待添加的元素 key 封裝成Node對(duì)象，添加在鏈表結(jié)尾，同時(shí)，檢查當(dāng)前鏈表節(jié)點(diǎn)數(shù)量是否達(dá)到樹(shù)化（將鏈表轉(zhuǎn)成紅黑樹(shù)）的閾值默認(rèn)是 8，若達(dá)到閾值，則首先檢查當(dāng)前數(shù)組的大小是否達(dá)到64，若達(dá)到，則將該鏈表轉(zhuǎn)成紅黑樹(shù)；若沒(méi)達(dá)到64，則先對(duì)數(shù)組進(jìn)行擴(kuò)容；否則退出循環(huán)，返回 e 為空。static final int TREEIFY_THRESHOLD = 8;

②若遍歷發(fā)現(xiàn)有重復(fù)元素，退出循環(huán)，此時(shí)的變量 e 就是重復(fù)元素。若頂層創(chuàng)建的對(duì)象是HashSet();則下面的語(yǔ)句沒(méi)有意義，因?yàn)関alue值是共享的PRESENT；若是頂層是 HashMap(k,v) 對(duì)象，下面語(yǔ)句表達(dá)的是：當(dāng)在map數(shù)組中發(fā)現(xiàn)已經(jīng)存入key了，就把待添加鍵值對(duì)的value 替換掉舊的value，key不變。

不管創(chuàng)建哪種對(duì)象，返回值都不為空，說(shuō)明添加失敗。（到此添加重復(fù)元素流程結(jié)束）

補(bǔ)充總結(jié)：

①hashSet()底層實(shí)現(xiàn)的其實(shí)是hashMap()，數(shù)據(jù)結(jié)構(gòu)相同都是數(shù)組+單鏈表，元素?cái)?shù)據(jù)類(lèi)型是HashMap的內(nèi)部類(lèi)Node類(lèi)型–Node<k,v>

②利用無(wú)參構(gòu)造方法創(chuàng)建HashSet，默認(rèn)大小16，加載因子 0.75，擴(kuò)容為原大小的 2 倍，擴(kuò)容閾值 = 數(shù)組大小 * 加載因子。（也可用有參構(gòu)造方法創(chuàng)建對(duì)象，設(shè)定大小或加載因子）

③HashSet中的add();方法其實(shí)就是map.put()方法，只是由于添加的都是單一元素(參數(shù)key)，并不是<k,v>鍵值對(duì)，所以統(tǒng)一用共享value（常量PRESENT）。

④HashSet不允許存儲(chǔ)元素重復(fù)，就和HashMap不允許重復(fù)的key一樣，只是HahsSet沒(méi)有用到value。

⑤添加元素的時(shí)候，要先得到key的hashCode值，經(jīng)過(guò)hash函數(shù)后得到hash值，再經(jīng)過(guò)一次計(jì)算得到待添加的key應(yīng)該存放的數(shù)組下標(biāo)。若當(dāng)前下標(biāo)對(duì)應(yīng)位置不為空，則遍歷該鏈表，查找是否有重復(fù)元素（若重復(fù)，則不添加；反之，加在鏈表尾部）；若當(dāng)前下標(biāo)位置上為空，則之間添加到當(dāng)前位置并作為頭節(jié)點(diǎn)。（這也就是為什么，實(shí)際存儲(chǔ)順序和實(shí)際輸出順序不一致）

總結(jié)

以上為個(gè)人經(jīng)驗(yàn)，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論