10.HashSet源碼解析

1.類注釋

1. HashSet的底層實作基于HashMap，是以疊代時不能保證按照插入順序進行疊代。
2. HashSet的add、remove、contanins、size等方法的耗時性能，不會随着資料量的增加而增加，原因跟HashMap底層的數組資料結構有關，不管資料量多大，不考慮hash沖突的情況下，時間複雜度都是O(1)。
3. HashSet是線程不安全的，如果需要安全請自行加鎖，或者使用Collections的synchronizedSet方法。
4. 疊代過程中，如果資料結構被改變，會快速失敗，會抛出 ConcurrentModificationException異常。

2.實作方式

從類注釋中看到，HashSet的實作是基于HashMap的，在Java中，要基于基礎類進行創新實作，有兩種辦法。一是繼承基礎類，覆寫基礎類的方法，比如說繼承HashMap , 覆寫其add方法。另一種方法是組合基礎類，通過調用基礎類的方法，來複用基礎類的能力。

HashSet使用的是後者，通過組合HashMap，來使用其提供的功能，其優點主要有如下兩點。首先，繼承表示父子類是同一個事物，而Set和Map表達的是兩種事物，是以繼承不妥，而且Java文法限制，子類隻能繼承一個父類，後續難以擴充。其次，組合更加靈活，可以任意的組合現有的基礎類，并且可以在基礎類的方法基礎上進行擴充、編排等，而且方法命名相對靈活，無需和基礎類的方法名稱保持一緻，具體實作源碼如下所示。

源碼

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable{
    //把HashMap組合進來，key是Hashset的key，value是下面的PRESENT
    private transient HashMap<E,Object> map;
    
    //HashMap中的value
    private static final Object PRESENT = new Object();
}      

源碼解析

1. 在使用HashSet時，比如add方法，隻有一個入參，但組合的Map的add方法卻有key和value兩個入參，對應上Map的話，key就是add的入參，value就是第二行代碼中的PRESENT，此處設計非常巧妙，用一個預設值PRESENT來代替Map的Value。
2. 如果HashSet是被共享的，當多個線程通路的時候，就會有線程安全問題，因為後續的所有操作中，并沒有加鎖。

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable{
    //對HashMap的容量進行計算
    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }
    
    public boolean add(E e) {
    //直接使用HashMap的put方法，進行一些簡單的邏輯判斷
        return map.put(e, PRESENT)==null;
    }
}      

1. Math.max((int)(c.size() / .75f) + 1 , 16)，是對HashMap的容量進行了計算，翻譯成中文就是取括号中兩個數的最大值(期望的值 / 0.75 + 1，預設值是16)。從計算中可以看出HashSet的實作者對HashMap的底層實作是非常清楚的，主要展現在兩個方面，和16比較大小的意思是說，如果給定HashMap初始容量小于16 ，就按照HashMap預設的16初始化即可，如果大于16，就按照給定值進行初始化。
2. HashSet的其他方法就相對簡單了，就是對Map的API進行了一些包裝，如上述的add方法。