關于HashSet、LinkedHashSet、TreeSet

Set接口的實現類，最大特點是不允許出現重復元素；

HashSet：基于HashMap實現，一個性能相對較好的Set；

LinkedHashSet：基于LinkedHashMap實現，一個保存了插入順序的Set；

TreeSet；基于TreeSet實現，一個實現了排序的Set；

類圖關系

源碼分析

Set接口的實現類相對來說都比較簡單，如果熟悉HashMap、LinkedHashMap、TreeMap源碼的話，HashSet、LinkedHashSet、TreeSet的代碼會很好理解，因為基本上都是調用對應Map的方法來實現的；

HashSet部分源碼：

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

    //存儲元素的HashMap
    private transient HashMap<E,Object> map;

    // 一個冗余的空對象，用于在Map中存放key對應的value，Map中所有的鍵值對的value都是同一個空Object的引用
    private static final Object PRESENT = new Object();

    /**
     * 構造方法，直接生成一個對應的HashMap
     */
    public HashSet() {
        map = new HashMap<>();
    }

    //省略一部分代碼.....
    
    
    //返回HashMap的key迭代器，HashSet中的元素實際上就是HashMap中的key元素
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }

    //調用HashMap的put方法，將e-PRESENT鍵值對對象put到map中
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

    //省略一部分代碼.....
}

LinkedHashMap源碼,如下，代碼很少，主要是構造方法，

根據傳入的參數，調用父類HashSet的HashSet(int initialCapacity, float loadFactor, boolean dummy)方法，生成一個LinkedHashMap對象存儲集合元素：

package java.util;
public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
        
    private static final long serialVersionUID = -2851667679971038690L;

    public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }
    
    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }

    public LinkedHashSet() {
        super(16, .75f, true);
    }

    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }
}

HashSet中生成LinkedHashMap的構造方法HashSet(int initialCapacity, float loadFactor, boolean dummy)

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

TreeSet部分源碼：

有一個NavigableMap類型的Map和一個空對象，NavigableMap會在構造方法里被賦成一個TreeMap對象，PRESENT是所有鍵值對中value對象的同一個引用；

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
{
    /**
     * TreeMap對象
     */
    private transient NavigableMap<E,Object> m;

    // 空對象，所有Map鍵值對中value對象的同一個引用
    private static final Object PRESENT = new Object();

構造方法，可見TreeSet是基于TreeMap實現的：

    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

    public TreeSet() {
        this(new TreeMap<E,Object>());
    }

再看其它TreeSet中方法的源碼，基本都是通過調用TreeMap的方法實現；

 //省略部分代碼。。。
 public NavigableSet<E> descendingSet() {
        return new TreeSet<>(m.descendingMap());
    }
    public int size() {
        return m.size();
    }

    public boolean isEmpty() {
        return m.isEmpty();
    }
//省略部分代碼。。。