java集合（二）----HashSet源碼解析

關于HashSet的圖如下圖所示：

從上圖可以看出HashSet是Set接口的一個實作類，HashSet按Hash算法來存儲集合中的元素，是以具有好的存取和查找性能。

HashSet具有以下特點：

1，不能保證元素的排列順序，順序可能與添加順序不同，順序也可能發生變化

2，HashSet不是同步的。就是說，如果多個線程同時通路一個HashSet，假設有兩個或者兩個以上的線程同時修改了HashSet集合時，則必須通過代碼來保證其同步

3，集合元素值可以是null

以上是簡單的介紹HashSet，下面來看看HashSet的源碼：

一、HashSet源碼介紹：

1，HashSet（）方法：

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

源碼解析：

*功能：無參構造函數

*源碼思路：構造一個新的空的HashMap執行個體，它有預設的初始化容量，容量為16，負載數為0.75

2，public HashSet(Collection<? extends E> c)方法：

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

源碼分析：

-功能：構造一個新的set集合的構造函數，該構造函數包含集合c中的元素

-源碼思路：

-如果c的值是null，則跑出異常

3，public HashSet(int initialCapacity, float loadFactor)方法

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

源碼解析：

• 功能：構造一個新的set集合的構造函數，參數initialCapacity為hash map的初始容量，loadFactor為hashset的裝載系數

4. public HashSet(int initialCapacity)方法

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

源碼解析：

• 功能：構造一個新的set集合的構造函數，參數initialCapacity為hash map的初始容量

5. HashSet(int initialCapacity, float loadFactor, boolean dummy)方法：

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

源碼解析：

• 功能：構造一個新的，空的LinkedHashSet，這個構造函數隻适用于LinkedHashSet

6. public Iterator iterator()方法：

public Iterator<E> iterator() {
        return map.keySet().iterator();
    }
           

源碼解析：

• 功能：傳回集合的疊代器，通過調用map對象的keySet方法，擷取set集合的所有值

源碼思路：

• Set集合的操作都是通過map集合實作的，集合的傳回元素的順序是随機的，沒有順序

7. public int size()方法：

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

源碼解析：

• 功能：傳回集合中元素的個數

源碼思路：

• 調用map的size方法

8. public boolean isEmpty()方法：

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

源碼解析：

• 功能：判斷集合是否為空

源碼思路：

• 調用map的isEmpty方法，來判斷集合是否為空

9. public boolean contains(Object o)方法：

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

源碼解析：

• 功能：判斷集合中是否包含元素o

源碼思路：

• 調用map的containsKey方法，來判斷o是否在集合中，Set集合實際存儲在map中，set的值存儲為map集合的鍵。

10. public boolean add(E e)方法：

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

源碼解析：

• 功能：向集合中添加元素e
• 源碼思路：
• （1）調用map的put方法，将元素e插入到集合中，作為map的鍵存儲起來，鍵對應的值為HashSet類的PRESENT成員變量
• （2）如果集合中已經包含元素e，則不改變原集合，傳回false；如果集合中不包含元素e，則向集合中添加元素e，傳回true

11. public boolean remove(Object o)方法：

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

源碼解析：

• 功能：将集合中的元素o移除
• 源碼思路：
• （1）如果集合中存在元素o，則将其從集合中移除；
• （2）這裡面牽扯到一個問題：就是當容器類對象在調用remove、contains等方法時需要比較對象是否相等，這會涉及到對象類型的equals方法和hashCode方法。對于這一點稍後解釋。

12. public void clear()方法：

源碼解析：

• 功能：将集合中的全部元素移除
• 源碼思路：
  • 通過map的clear方法将集合中的元素全部移除

13. public Object clone()方法：

@SuppressWarnings("unchecked")
    public Object clone() {
        try {
            HashSet<E> newSet = (HashSet<E>) super.clone();
            newSet.map = (HashMap<E, Object>) map.clone();
            return newSet;
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
    }
           

源碼解析：

• 功能：淺拷貝
• 源碼思路：
  • 該方法隻是完成了淺拷貝，集合中的元素本身沒有被拷貝

二、HashSet注意事項：

1，當向集合中添加（add）、删除（remove）、是否包含（contains）：

• 當向HashSet集合中存入一個元素時，HashSet會調用該對象的hashCode（）方法來得到該對象的hashCode值，然後根據該hashCode值決定在HashSet中的存儲位置。如果兩個元素通過equals（）方法比價傳回true，但它們的hashCode（）方法傳回值不相等，HashSet會将它們存儲在不同的位置，仍然可以添加成功。
• 也就是說，HashSet集合判斷兩個元素是否相等的标準是兩個對象通過equlas（）方法比較相等，并且兩個對象的hashCode（）方法傳回值也相等。
• 對于自定義類型，需要重寫equals和hashCode方法（什麼時候能用到hashCode方法？一般來說，當這個對象用在map接口裡面，作為“鍵”使用時，會用到hashCode方法，因為hashCode的效率會更高。）

2，原則：

• 當把一個對象放入HashSet中時，如果需要重寫該對象對應類的equals（）方法，則也應該需要重寫其hashCode方法。規則就是：如果兩個對象通過equals（）方法比較傳回true，這兩個對象的hashCode值也應該相同。

三、hashCode對于HahSet是個怎樣的地位？

• 首先，hash算法的功能是：它能保證快速查找被檢索的對象，hash算法的價值在于速度。當需要查詢集合中某個元素時，hash算法可以直接根據元素的hashCode值計算出該元素的存儲位置，進而快速定位該元素。就像數組裡的索引，從表面看起來，HashSet集合裡面的元素都沒有索引，實際上當程式向HashSet集合中添加元素時，HashSet會根據該元素的hashCode值來計算它的存儲位置，這樣也可以快速定位該元素。
• 為什麼不使用數組呢？因為數組元素的索引是連續的，而且數組的長度是固定的，無法自由添加數組的長度。而HashSet是采用每個元素的hashCode值來電腦存儲位置，進而可以自由添加HashSet的長度，并可以根據元素的hashCode值來通路元素，是以，當以HashSet中通路元素時，HashSet先計算該元素的hashCode值（也就是調用該對象的hashCode方法的傳回值），然後直接到該hashCode值對應的位置去取出該元素-------這就是HashSet速度很快的原因了。

四、重寫hashCode（）方法的基本原則：

1，在程式運作過程中，同一個對象多次調用hashCode（）方法應該傳回相同的值

2，當兩個對象通過equals（）方法比較傳回true時，這兩個對象的hashCode（）方法應傳回相等的值

3，對象中用作equals（）方法比較标準的執行個體變量，都應該用于計算hashCode值

注意：當向HashSet中添加可變對象時，必須十分小心。如果修改HahSet集合中的對象，有可能導緻該對象與集合中的其他對象相等，進而導緻HashSet無法準确通路對象。