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

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

特點

1. 無序集合，不保證存儲元素的順序，沒有索引

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

3. 可以存儲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源碼，其操作底層都是通過調(diào)用HashMap方法實現(xiàn)的，HashSet會將元素存儲在HashMap的key集合中，然后為value賦一個static空對象PRESENT。

HashSet不能存儲重復(fù)元素，因為HashMap的key集合不可以重復(fù)，本質(zhì)也是通過equals()和hashCode()來判定兩個對象是否重復(fù)，因此將對象存儲在HashSet之前，必須先重寫對象的equals()和hashCode()方法。

hashCode原則：

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

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

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

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

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

2.底層實際上是HashMap()

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

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

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

這里的key就是要添加的元素，value是一個object類型的共享常量，占了一個坑位，并沒有實際意義。

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

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

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

例（不重寫方法）：

輸出：

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

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

key：待添加的元素。

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

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

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

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

（1）首次添加元素 key

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

resize()方法：

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

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

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 ，同時獲取到當(dāng)前位置上的所存儲的鏈表的頭節(jié)點，并將節(jié)點賦值給變量 p ，若該節(jié)點為空（即當(dāng)前位置無數(shù)據(jù)），就把待添加元素 key 封裝成一個節(jié)點Node，放到當(dāng)前位置當(dāng)作該鏈表的頭節(jié)點。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

總結(jié)

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

最新評論