一、HashSet介紹

HashSet是Set接口的子類，其內(nèi)部采用了HashMap作為數(shù)據(jù)存儲(chǔ)，HashSet其實(shí)就是在操作HashMap的key。

• HashSet是無序存儲(chǔ)的，不能保證元素的順序；
• HashSet并沒有進(jìn)行同步處理，因此是線程不安全的；
• HashSet可以存儲(chǔ)null元素，但只能存儲(chǔ)一個(gè)。

二、源碼解析

1、HashSet實(shí)現(xiàn)的接口

如下圖：

觀察上圖：

• AbstractSet類：該類提供了Set接口的骨架實(shí)現(xiàn)，通過擴(kuò)展此類來實(shí)現(xiàn)集合的過程與通過擴(kuò)展AbstractCollection實(shí)現(xiàn)集合的過程相同，除了此類的子類中的所有方法和構(gòu)造函數(shù)都必須遵守由Set接口施加的附加約束（例如，添加方法不能允許將一個(gè)對(duì)象的多個(gè)實(shí)例添加到集合中）。
• Set接口：繼承Collection接口，添加了所有構(gòu)造函數(shù)的約定以及add，equals和hashCode方法的約定
• Serializable接口：主要用于序列化，即：能夠?qū)?duì)象寫入磁盤。與之對(duì)應(yīng)的還有反序列化操作，就是將對(duì)象從磁盤中讀取出來。因此如果要進(jìn)行序列化和反序列化，ArrayList的實(shí)例對(duì)象就必須實(shí)現(xiàn)這個(gè)接口，否則在實(shí)例化的時(shí)候程序會(huì)報(bào)錯(cuò)（java.io.NotSerializableException）。
• Cloneable接口：實(shí)現(xiàn)Cloneable接口的類能夠調(diào)用clone方法，如果沒有實(shí)現(xiàn)Cloneable接口就調(diào)用方法，就會(huì)拋出異常（java.lang.CloneNotSupportedException）。

2、HashSet中的變量

序列化ID

static final long serialVersionUID = -5024744406713321676L

底層使用HashMap來保存所有元素，確切說存儲(chǔ)在map的key中，并使用transient關(guān)鍵字修飾，防止被序列化

private transient HashMap<E,Object> map

常量，構(gòu)造一個(gè)虛擬的對(duì)象PRESENT，默認(rèn)為map的value值（HashSet中只需要用到鍵，而HashMap是key-value鍵值對(duì)，使用PRESENT作為value的默認(rèn)填充值，解決差異問題）

private static final Object PRESENT = new Object()

3、HashSet的構(gòu)造方法

（1）無參構(gòu)造

    public HashSet() {
        map = new HashMap<>();
    }

總結(jié)：默認(rèn)的無參構(gòu)造，其底層會(huì)初始化一個(gè)空的HashMap，并使用默認(rèn)初始容量16和負(fù)載因子0.75。

（2）帶集合參數(shù)的構(gòu)造方法

    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

總結(jié)：帶集合參數(shù)的構(gòu)造方法，底層使用默認(rèn)的負(fù)載因子0.75和足以包含指定集合中所有怨怒是的初始容量來構(gòu)造一個(gè)HashMap。

（3）帶初始容量的構(gòu)造方法

    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

總結(jié)：以指定初始容量的HashMap構(gòu)造一個(gè)HashSet。

（4） 帶初始容量和負(fù)載因子的構(gòu)造方法

    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

總結(jié)：構(gòu)造一個(gè)具有初始容量和負(fù)載因子的HashMap。

4、常用方法分析

（1）add()方法

add方法底層實(shí)際上是將該元素作為key添加到HashMap中，而PRESENT是作為默認(rèn)的map的value值。

如果添加的元素不存在，則加入到map中，并返回true。如果該元素已經(jīng)存在，則返回false。

map的put方法在添加key-value對(duì)時(shí)，如果新放入HashMap的Entry中key與集合中原有的Entry的key相同，則新添加的Entry的value會(huì)覆蓋原來Entry的value，但是key不會(huì)改變。

因此，如果向HashSet中添加一個(gè)已經(jīng)存在的元素時(shí)，新添加的集合元素不會(huì)被放入HashMap中，原有的元素也不會(huì)有任何改變，因此Set中的元素也就不會(huì)重復(fù)了

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

（2）remove()方法

如果給定的元素在HashSet中，則將其移除，其底層調(diào)用HashMap的remove()方法刪除指定Entry。

    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

（3） size()方法

返回HashSet中元素的個(gè)數(shù)

    public int size() {
        return map.size();
    }

（4）isEmpty()方法

判斷HashSet是否為空

    public boolean isEmpty() {
        return map.isEmpty();
    }

（5）contains()方法

如果HashSet中包含指定元素，則返回true。否則返回false

    public boolean contains(Object o) {
        return map.containsKey(o);
    }

5、HashSet與LinkedHashSet

在HashSet的源碼中有這樣一個(gè)構(gòu)造函數(shù)：

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

可以看到該構(gòu)造函數(shù)為包訪問權(quán)限，不對(duì)外公開。該構(gòu)造函數(shù)以指定的初始容量和負(fù)載因子構(gòu)造一個(gè)新的空鏈表哈希集合，其實(shí)它是對(duì)LinkedHashSet的支持。

我們可以看看LinkedHashSet的繼承關(guān)系：

因此，在這里我們可以簡(jiǎn)單的對(duì)LinkedHashSet進(jìn)行分析，它在實(shí)現(xiàn)了Set接口、Cloneable接口和Serializable接口的同時(shí)，也繼承了HashSet。

LinkedHashSet的特點(diǎn)如下：

• LinkedHashSet 是 HashSet 的子類
• LinkedHashSet 底層是一個(gè) LinkedHashMap，底層維護(hù)了一個(gè)數(shù)組+雙向鏈表
• LinkedHashSet 根據(jù)元素的 hashCode 值來決定元素的存儲(chǔ)位置，同時(shí)使用鏈表維護(hù)元素的次序，這使得元素看起來是以插入順序保存的。
• LinkedHashSet 不允許添重復(fù)元素

來看看LinkedHashSet的構(gòu)造方法

    //使用指定的初始容量和負(fù)載因子構(gòu)造一個(gè)新的哈希集合
    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }
    //使用指定的初始容量和負(fù)載因子構(gòu)造新的哈希集合
    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }
    //無參構(gòu)造方法，默認(rèn)容量16，負(fù)載因子0.75
    public LinkedHashSet() {
        super(16, .75f, true);
    }
    //基于集合構(gòu)造一個(gè)帶有指定元素的非空哈希集合
    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }

LinkedHashSet維護(hù)了一個(gè)hash表和雙向鏈表，且通過head和tail分別指向鏈表的頭和尾，每一個(gè)節(jié)點(diǎn)有before和after屬性，這樣可以形成雙向鏈表。

在添加一個(gè)元素時(shí)，先求hash值，再求索引，確定該元素在table表中的位置，然后將添加的元素加入到雙向鏈表（如果該元素已經(jīng)存在，則不添加）

三、總結(jié)

1、HashSet總結(jié)

（1）基于HashMap實(shí)現(xiàn)的，默認(rèn)構(gòu)造函數(shù)是構(gòu)建一個(gè)初始容量為16，負(fù)載因子為0.75 的HashMap。封裝了一個(gè) HashMap 對(duì)象來存儲(chǔ)所有的集合元素，所有放入 HashSet 中的集合元素實(shí)際上由 HashMap 的 key 來保存，而 HashMap 的 value 則存儲(chǔ)了一個(gè) PRESENT，它是一個(gè)靜態(tài)的 Object 對(duì)象。

（2）當(dāng)我們?cè)噲D把某個(gè)類的對(duì)象當(dāng)成 HashMap的 key，或試圖將這個(gè)類的對(duì)象放入 HashSet 中保存時(shí)，重寫該類的equals(Object obj)方法和 hashCode() 方法很重要，而且這兩個(gè)方法的返回值必須保持一致：當(dāng)該類的兩個(gè)的 hashCode() 返回值相同時(shí)，它們通過 equals() 方法比較也應(yīng)該返回 true。通常來說，所有參與計(jì)算 hashCode() 返回值的關(guān)鍵屬性，都應(yīng)該用于作為 equals() 比較的標(biāo)準(zhǔn)。

（3）HashSet的其他操作都是基于HashMap的。

2、LinkedHashSet總結(jié)

LinkedHashSet 底層使用 LinkedHashMap 來保存所有元素，它繼承于 HashSet，其所有的方法操作上又與 HashSet 相同，因此 LinkedHashSet 的實(shí)現(xiàn)上非常簡(jiǎn)單，只提供了四個(gè)構(gòu)造方法，并通過傳遞一個(gè)標(biāo)識(shí)參數(shù)，調(diào)用父類的構(gòu)造器，底層構(gòu)造一個(gè) LinkedHashMap 來實(shí)現(xiàn)，在相關(guān)操作上與父類 HashSet 的操作相同，直接調(diào)用父類 HashSet 的方法即可。

到此這篇關(guān)于Java中HashSet和LinkedHashSet詳解的文章就介紹到這了,更多相關(guān)HashSet和LinkedHashSet內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論