站在巨人肩膀上看源碼-HashSet

DevTTL 發(fā)布于2019-08-15 18:14 / 2178人閱讀

摘要：實(shí)際運(yùn)行上面程序?qū)⒖吹匠绦蜉敵觯@是因?yàn)榕袛鄡蓚€(gè)對(duì)象相等的標(biāo)準(zhǔn)除了要求通過(guò)方法比較返回之外，還要求兩個(gè)對(duì)象的返回值相等。通常來(lái)說(shuō)，所有參與計(jì)算返回值的關(guān)鍵屬性，都應(yīng)該用于作為比較的標(biāo)準(zhǔn)。

1.HashSet概述：

　　HashSet實(shí)現(xiàn)Set接口，由哈希表（實(shí)際上是一個(gè)HashMap實(shí)例）支持。它不保證set 的迭代順序；特別是它不保證該順序恒久不變。此類(lèi)允許使用null元素。HashSet中不允許有重復(fù)元素，這是因?yàn)镠ashSet是基于HashMap實(shí)現(xiàn)的，HashSet中的元素都存放在HashMap的key上面，而value中的值都是統(tǒng)一的一個(gè)private static final Object PRESENT = new Object();。HashSet跟HashMap一樣，都是一個(gè)存放鏈表的數(shù)組。

　　HashSet中add方法調(diào)用的是底層HashMap中的put()方法，而如果是在HashMap中調(diào)用put，首先會(huì)判斷key是否存在，如果key存在則修改value值，如果key不存在這插入這個(gè)key-value。而在set中，因?yàn)関alue值沒(méi)有用，也就不存在修改value值的說(shuō)法，因此往HashSet中添加元素，首先判斷元素（也就是key）是否存在，如果不存在這插入，如果存在著不插入，這樣HashSet中就不存在重復(fù)值。

2.HashSet的實(shí)現(xiàn)：

對(duì)于HashSet而言，它是基于HashMap實(shí)現(xiàn)的，HashSet底層使用HashMap來(lái)保存所有元素，更確切的說(shuō)，HashSet中的元素，只是存放在了底層HashMap的key上，而value使用一個(gè)static final的Object對(duì)象標(biāo)識(shí)。因此HashSet 的實(shí)現(xiàn)比較簡(jiǎn)單，相關(guān)HashSet的操作，基本上都是直接調(diào)用底層HashMap的相關(guān)方法來(lái)完成，HashSet的源代碼如下：

public class HashSet
    extends AbstractSet
    implements Set, Cloneable, java.io.Serializable
{
    static final long serialVersionUID = -5024744406713321676L;

    // 底層使用HashMap來(lái)保存HashSet中所有元素。
    private transient HashMap map;
    
    // 定義一個(gè)虛擬的Object對(duì)象作為HashMap的value，將此對(duì)象定義為static final。
    private static final Object PRESENT = new Object();

    /**
     * 默認(rèn)的無(wú)參構(gòu)造器，構(gòu)造一個(gè)空的HashSet。
      * 
     * 實(shí)際底層會(huì)初始化一個(gè)空的HashMap，并使用默認(rèn)初始容量為16和加載因子0.75。
      */
    public HashSet() {
        map = new HashMap();
    }

    /**
     * 構(gòu)造一個(gè)包含指定collection中的元素的新set。
      *
     * 實(shí)際底層使用默認(rèn)的加載因子0.75和足以包含指定
     * collection中所有元素的初始容量來(lái)創(chuàng)建一個(gè)HashMap。
     * @param c 其中的元素將存放在此set中的collection。
     */
    public HashSet(Collection c) {
        map = new HashMap(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

    /**
     * 以指定的initialCapacity和loadFactor構(gòu)造一個(gè)空的HashSet。
     *
     * 實(shí)際底層以相應(yīng)的參數(shù)構(gòu)造一個(gè)空的HashMap。
     * @param initialCapacity 初始容量。
     * @param loadFactor 加載因子。
     */
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap(initialCapacity, loadFactor);
    }

    /**
     * 以指定的initialCapacity構(gòu)造一個(gè)空的HashSet。
     *
     * 實(shí)際底層以相應(yīng)的參數(shù)及加載因子loadFactor為0.75構(gòu)造一個(gè)空的HashMap。
     * @param initialCapacity 初始容量。
     */
    public HashSet(int initialCapacity) {
        map = new HashMap(initialCapacity);
    }

    /**
     * 以指定的initialCapacity和loadFactor構(gòu)造一個(gè)新的空鏈接哈希集合。
     * 此構(gòu)造函數(shù)為包訪(fǎng)問(wèn)權(quán)限，不對(duì)外公開(kāi)，實(shí)際只是是對(duì)LinkedHashSet的支持。
     *
     * 實(shí)際底層會(huì)以指定的參數(shù)構(gòu)造一個(gè)空LinkedHashMap實(shí)例來(lái)實(shí)現(xiàn)。
     * @param initialCapacity 初始容量。
     * @param loadFactor 加載因子。
     * @param dummy 標(biāo)記。
     */
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap(initialCapacity, loadFactor);
    }

    /**
     * 返回對(duì)此set中元素進(jìn)行迭代的迭代器。返回元素的順序并不是特定的。
     * 
     * 底層實(shí)際調(diào)用底層HashMap的keySet來(lái)返回所有的key。
     * 可見(jiàn)HashSet中的元素，只是存放在了底層HashMap的key上，
     * value使用一個(gè)static final的Object對(duì)象標(biāo)識(shí)。
     * @return 對(duì)此set中元素進(jìn)行迭代的Iterator。
     */
    public Iterator iterator() {
        return map.keySet().iterator();
    }

    /**
     * 返回此set中的元素的數(shù)量（set的容量）。
     *
     * 底層實(shí)際調(diào)用HashMap的size()方法返回Entry的數(shù)量，就得到該Set中元素的個(gè)數(shù)。
     * @return 此set中的元素的數(shù)量（set的容量）。
     */
    public int size() {
        return map.size();
    }

    /**
     * 如果此set不包含任何元素，則返回true。
     *
     * 底層實(shí)際調(diào)用HashMap的isEmpty()判斷該HashSet是否為空。
     * @return 如果此set不包含任何元素，則返回true。
     */
    public boolean isEmpty() {
        return map.isEmpty();
    }

    /**
     * 如果此set包含指定元素，則返回true。
     * 更確切地講，當(dāng)且僅當(dāng)此set包含一個(gè)滿(mǎn)足(o==null ? e==null : o.equals(e))
     * 的e元素時(shí)，返回true。
     *
     * 底層實(shí)際調(diào)用HashMap的containsKey判斷是否包含指定key。
     * @param o 在此set中的存在已得到測(cè)試的元素。
     * @return 如果此set包含指定元素，則返回true。
     */
    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    /**
     * 如果此set中尚未包含指定元素，則添加指定元素。
     * 更確切地講，如果此 set 沒(méi)有包含滿(mǎn)足(e==null ? e2==null : e.equals(e2))
     * 的元素e2，則向此set 添加指定的元素e。
     * 如果此set已包含該元素，則該調(diào)用不更改set并返回false。
     *
     * 底層實(shí)際將將該元素作為key放入HashMap。
     * 由于HashMap的put()方法添加key-value對(duì)時(shí)，當(dāng)新放入HashMap的Entry中key
     * 與集合中原有Entry的key相同（hashCode()返回值相等，通過(guò)equals比較也返回true），
     * 新添加的Entry的value會(huì)將覆蓋原來(lái)Entry的value，但key不會(huì)有任何改變，
     * 因此如果向HashSet中添加一個(gè)已經(jīng)存在的元素時(shí)，新添加的集合元素將不會(huì)被放入HashMap中，
     * 原來(lái)的元素也不會(huì)有任何改變，這也就滿(mǎn)足了Set中元素不重復(fù)的特性。
     * @param e 將添加到此set中的元素。
     * @return 如果此set尚未包含指定元素，則返回true。
     */
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

    /**
     * 如果指定元素存在于此set中，則將其移除。
     * 更確切地講，如果此set包含一個(gè)滿(mǎn)足(o==null ? e==null : o.equals(e))的元素e，
     * 則將其移除。如果此set已包含該元素，則返回true
     * （或者：如果此set因調(diào)用而發(fā)生更改，則返回true）。（一旦調(diào)用返回，則此set不再包含該元素）。
     *
     * 底層實(shí)際調(diào)用HashMap的remove方法刪除指定Entry。
     * @param o 如果存在于此set中則需要將其移除的對(duì)象。
     * @return 如果set包含指定元素，則返回true。
     */
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }

    /**
     * 從此set中移除所有元素。此調(diào)用返回后，該set將為空。
     *
     * 底層實(shí)際調(diào)用HashMap的clear方法清空Entry中所有元素。
     */
    public void clear() {
        map.clear();
    }

    /**
     * 返回此HashSet實(shí)例的淺表副本：并沒(méi)有復(fù)制這些元素本身。
     *
     * 底層實(shí)際調(diào)用HashMap的clone()方法，獲取HashMap的淺表副本，并設(shè)置到HashSet中。
     */
    public Object clone() {
        try {
            HashSet newSet = (HashSet) super.clone();
            newSet.map = (HashMap) map.clone();
            return newSet;
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
    }
}

3.示例：

接下來(lái)看一個(gè)示例程序，測(cè)試一下自己是否真正掌握了HashSet 集合的功能。

package com.spring.test;

import java.util.HashSet;
import java.util.Set;

class Name   
{   
    private String first;    
    private String last;    
       
    public Name(String first, String last)    
    {    
        this.first = first;    
        this.last = last;    
    }    
  
    public boolean equals(Object o)    
    {    
        if (this == o)    
        {    
            return true;    
        }    
           
        if (o.getClass() == Name.class)    
        {    
            Name n = (Name)o;    
            return n.first.equals(first)    
                && n.last.equals(last);    
        }    
        return false;    
    }    
} 

public class TestSet {
    
    public static void main(String[] args){
        
        Set s = new HashSet();   
        s.add(new Name("abc", "123"));   
        System.out.println(   
        s.contains(new Name("abc", "123")));

    }
}

上面程序中向 HashSet 里添加了一個(gè) new Name("abc", "123") 對(duì)象之后，立即通過(guò)程序判斷該 HashSet 是否包含一個(gè) new Name("abc", "123") 對(duì)象。粗看上去，很容易以為該程序會(huì)輸出 true。實(shí)際運(yùn)行上面程序?qū)⒖吹匠绦蜉敵?false，這是因?yàn)?HashSet 判斷兩個(gè)對(duì)象相等的標(biāo)準(zhǔn)除了要求通過(guò) equals() 方法比較返回 true 之外，還要求兩個(gè)對(duì)象的 hashCode() 返回值相等。而上面程序沒(méi)有重寫(xiě) Name 類(lèi)的 hashCode() 方法，兩個(gè) Name 對(duì)象的 hashCode() 返回值并不相同，因此 HashSet 會(huì)把它們當(dāng)成 2 個(gè)對(duì)象處理，因此程序返回 false。
由此可見(jiàn)，當(dāng)我們?cè)噲D把某個(gè)類(lèi)的對(duì)象當(dāng)成 HashMap 的 key，或試圖將這個(gè)類(lèi)的對(duì)象放入 HashSet 中保存時(shí)，重寫(xiě)該類(lèi)的 equals(Object obj) 方法和 hashCode() 方法很重要，而且這兩個(gè)方法的返回值必須保持一致：當(dāng)該類(lèi)的兩個(gè)的 hashCode() 返回值相同時(shí)，它們通過(guò) equals() 方法比較也應(yīng)該返回 true。通常來(lái)說(shuō)，所有參與計(jì)算 hashCode() 返回值的關(guān)鍵屬性，都應(yīng)該用于作為 equals() 比較的標(biāo)準(zhǔn)。如下程序就正確重寫(xiě)了 Name 類(lèi)的 hashCode() 和 equals() 方法，程序如下：

package com.spring.test;

import java.util.HashSet;
import java.util.Set;

class Name   
{   
    private String first;    
    private String last;    
       
    public Name(String first, String last){    
        this.first = first;    
        this.last = last;    
    }    
    
    // 根據(jù) first 判斷兩個(gè) Name 是否相等   
    public boolean equals(Object o){    
        if (this == o){    
            return true;    
        }    
        
        if (o.getClass() == Name.class){    
            Name n = (Name)o;    
            return n.first.equals(first);    
        }    
        return false;    
    } 
    
    // 根據(jù) first 計(jì)算 Name 對(duì)象的 hashCode() 返回值   
    public int hashCode(){    
        return first.hashCode();    
    }
    
    public String toString(){    
        return"Name[first=" + first + ", last=" + last + "]";    
    } 

} 

public class TestSet {
    
    public static void main(String[] args){
        
        Set set = new HashSet();   
        set.add(new Name("abc", "123"));
        set.add(new Name("abc", "456"));
        System.out.println(set);   
    }
}

上面程序中提供了一個(gè) Name 類(lèi)，該 Name 類(lèi)重寫(xiě)了 equals() 和 toString() 兩個(gè)方法，這兩個(gè)方法都是根據(jù) Name 類(lèi)的 first 實(shí)例變量來(lái)判斷的，當(dāng)兩個(gè)Name 對(duì)象的 first 實(shí)例變量相等時(shí)，這兩個(gè) Name 對(duì)象的 hashCode() 返回值也相同，通過(guò) equals() 比較也會(huì)返回 true。
程序主方法先將第一個(gè) Name 對(duì)象添加到 HashSet 中，該 Name 對(duì)象的 first 實(shí)例變量值為"abc"，接著程序再次試圖將一個(gè) first 為"abc"的 Name 對(duì)象添加到 HashSet 中，很明顯，此時(shí)沒(méi)法將新的 Name 對(duì)象添加到該 HashSet 中，因?yàn)榇颂幵噲D添加的 Name 對(duì)象的 first 也是" abc"，HashSet 會(huì)判斷此處新增的Name 對(duì)象與原有的 Name 對(duì)象相同，因此無(wú)法添加進(jìn)入，這時(shí)輸出 set 集合時(shí)將看到該集合里只包含一個(gè) Name 對(duì)象，就是第一個(gè)、last 為"123"的 Name 對(duì)象。

4.總結(jié)：

（1）HashSet 的實(shí)現(xiàn)其實(shí)非常簡(jiǎn)單，它只是封裝了一個(gè) HashMap 對(duì)象來(lái)存儲(chǔ)所有的集合元素，所有放入 HashSet 中的集合元素實(shí)際上由 HashMap 的 key 來(lái)保存，而 HashMap 的 value 則存儲(chǔ)了一個(gè) PRESENT，它是一個(gè)靜態(tài)的 Object 對(duì)象。

（2）對(duì)于HashSet中保存的對(duì)象，請(qǐng)注意正確重寫(xiě)其equals和hashCode方法，以保證放入的對(duì)象的唯一性。