天天看點

java集合(二)----HashSet源碼解析

關于HashSet的圖如下圖所示:

java集合(二)----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無法準确通路對象。