HashSet的故事----Jdk源碼解讀，hashset----jdk源碼

HashSet的故事----Jdk源碼解讀，hashset----jdk源碼

Hash，我們在說HashMap的時候，已經知道Hash是散列，Map是映射了。

那麼Set又是什麼呢 ？

先來看看Set的翻譯是什麼

n. [數] 集合；一套；布景；[機] 裝置

這裡Set所取的含義是集合。而且是數學概念上的集合。數學概念上的集合有什麼特點呢？那就是Set中所有的元素不能重復。所以HashSet的意思就是以散列的形式維持一套不會有重復元素的集合。

接下來我們看看HashSet是怎麼被Jdk實現的吧。(其實邏輯非常簡單。)

類的聲明：

hashSet 繼承自AbstractSet，實現了Set類以及克隆接口和可序列化接口。

 public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable 

接口中定義了一個瞬時hashMap變量，這個變量是Set用來存儲元素的容器：

private transient HashMap<E,Object> map;

接著定義一個Object變量，暫且記住這個變量的作用：標記元素是否存在的，具體如何使用，在後邊的方法會介紹。

private static final Object PRESENT = new Object();

接著是五個構造函數：

1、無參構造函數

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

2、初始化時可以將集合中的元素直接添加到Set中的構造函數

注意看這個地方計算MAP初始化大小的方式，取出當前集合collection參數的size除以0.75+1，這個數值和16計算，取較大值。

這樣做的好處是，給map賦予一個足夠長的大小，這樣在給(防盜連接：本文首發自http://www.cnblogs.com/jilodream/ )map添加集合collection中元素的時候，map不需要反復rehash。同時如果集合collection中的元素較少時，仍然賦予一個較合適的大小16，為未來添加元素留下足夠的空間：

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

3、以初始容積大小，加載因子作為參數的構造函數

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

4、以初始容積大小作為參數的構造函數

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

5、非public的構造函數

這個構造函數的前兩個參數是初始容積和加載因子，第三個參數不會被使用，可以忽略，這個在jkd的注釋中有寫到。

同時這個構造函數所使用的map實例時一個linkedHashMap，這與前邊的構造函數有所區別。

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

接下來是實例方法：
返回一個迭代器，這個迭代器實質上返回的是Set中map的key的迭代器

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

返回set中map的長度，作為Set的長度

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

判斷Set是否為空，其實質其實上返回map的長度是否為0

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

contains(Object o)，Set的核心方法，判斷Set中是否存在指定元素o，實質上是判斷map中是否存在這個key

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

add(E e)，Set的核心方法，將元素e添加到Set中。

這個方法的本質，是將e作為key，present變量作為value存入map中。而map.put方法會返回原有的value值，如果是首次添加的話，會返回一個null。(防盜連接：本文首發自http://www.cnblogs.com/jilodream/ )所以add返回的結果表示當前map是否已經存在元素e。如果存在，則返回false，反之返回true。

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

remove(Object o)，Set的核心方法，移除Set中的o元素。

如果Set中存在該元素，則返回true。因為map中remove key時，會返回當前key對應的value。

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

清除Set中的元素

    public void clear() {
        map.clear();
    }

clone()方法。

克隆當前Set對象，通過代碼可以知道只克隆了當前Set對象，以及map對象。即二者的地址發生了改變，但是對於map中具體的元素，是沒有克隆的。

    @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);
        }
    }

接下來是正反序列化用到的兩個方法。

盡管這是兩個private的方法，但是虛擬機在正反序列化時仍然可以通過反射調用到他們。

先說序列化writeObject方法。

首先調用輸出流的defaultWriteObject()記錄下當前Set可以序列化的值，接著記錄map的容積和負載因子以及大小。接著遍歷map中的對象，依次記錄下key元素（value不用記錄，想想這是為什麼？）。

而反序列化則反向的從流中讀取數據，然後生成對象。

由於流是順序讀取的，因此反序列化時的順序，與序列化中時保持一致的。這裡不再過多的介紹正反序列化的內容。(防盜連接：本文首發自http://www.cnblogs.com/jilodream/ )

private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out any hidden serialization magic
        s.defaultWriteObject();

        // Write out HashMap capacity and load factor
        s.writeInt(map.capacity());
        s.writeFloat(map.loadFactor());

        // Write out size
        s.writeInt(map.size());

        // Write out all elements in the proper order.
        for (E e : map.keySet())
            s.writeObject(e);
    }
 private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden serialization magic
        s.defaultReadObject();

        // Read capacity and verify non-negative.
        int capacity = s.readInt();
        if (capacity < 0) {
            throw new InvalidObjectException("Illegal capacity: " +
                                             capacity);
        }

        // Read load factor and verify positive and non NaN.
        float loadFactor = s.readFloat();
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new InvalidObjectException("Illegal load factor: " +
                                             loadFactor);
        }

        // Read size and verify non-negative.
        int size = s.readInt();
        if (size < 0) {
            throw new InvalidObjectException("Illegal size: " +
                                             size);
        }

        // Set the capacity according to the size and load factor ensuring that
        // the HashMap is at least 25% full but clamping to maximum capacity.
        capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
                HashMap.MAXIMUM_CAPACITY);

        // Create backing HashMap
        map = (((HashSet<?>)this) instanceof LinkedHashSet ?
               new LinkedHashMap<E,Object>(capacity, loadFactor) :
               new HashMap<E,Object>(capacity, loadFactor));

        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            @SuppressWarnings("unchecked")
                E e = (E) s.readObject();
            map.put(e, PRESENT);
        }
    }

最後是spliterator()方法，這個方法是1.8中新添加的。

該方法返回的是map中對應的一個新的Spliterator實例。這裡簡單說下Spliterator的作用：spliterator是 split iterator的意思。也就是返回一個迭代器，但是這個迭代器是分割的，將元素分割成若干組，並不像原有的迭代器只能通過單一線程順序的訪問。它可以通過多線程並行的形式，訪問容器中的元素，加快元素的訪問效率。關於這個類的詳細使用，我會在後續的文章中(防盜連接：本文首發自http://www.cnblogs.com/jilodream/ )更新。

public Spliterator<E> spliterator() {
        return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
    }

通過查看jkd源代碼，我們可以發現HashSet的本質，是對map進行了一層封裝。使原有的y=f(x)形式可以更好的已數學Set的形式展現出來。