Set类源码解析

特性：唯一不重复，无序。
先看抽象类，里面知识定义了一些增删减改的方法，需要实现类去构建具体的方法。

public interface Set<E> extends Collection<E> {

首先HashSet的源码，可以看到定义了一个HashMap的实例，那么HashSet的底层原理也就是HashMap的底层实现。

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

    private transient HashMap<E,Object> map;

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }

从迭代的方法可以看出返回的是HashMap的.keySet().iterator(),此方法只能迭代返回HashMap.Node类的key值，那么显而易见，HashSet是将信息储存在HashMap的key中，同时还保证了Set中数据不重复的特性，同样也能够保存null数据。

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

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

// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();

/**
 * Constructs a set backed by the specified navigable map.
 */
TreeSet(NavigableMap<E,Object> m) {
    this.m = m;
}

/**
 * Constructs a new, empty tree set, sorted according to the
 * natural ordering of its elements.  All elements inserted into
 * the set must implement the {@link Comparable} interface.
 * Furthermore, all such elements must be <i>mutually
 * comparable</i>: {@code e1.compareTo(e2)} must not throw a
 * {@code ClassCastException} for any elements {@code e1} and
 * {@code e2} in the set.  If the user attempts to add an element
 * to the set that violates this constraint (for example, the user
 * attempts to add a string element to a set whose elements are
 * integers), the {@code add} call will throw a
 * {@code ClassCastException}.
 */
public TreeSet() {
    this(new TreeMap<E,Object>());
}

可以看到在构造函数中，默认为```new TreeMap<E,Object>()```也就是说TreeSet是利用```TreeMap```实现的，同样追溯```TreeSet```

A Red-Black tree based {@link NavigableMap} implementation.

这就很明显了，```TreeMap```就是实现了红黑树.
其中使用默认的或者是自建的```Comparator```,能够插入null键完全取决于你是否在比较器中处理了null的情况，默认是不能插入null。会显示空指针错误。

##LinkedHashSet

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

private static final long serialVersionUID = -2851667679971038690L;

/**
 * Constructs a new, empty linked hash set with the specified initial
 * capacity and load factor.
 *
 * @param      initialCapacity the initial capacity of the linked hash set
 * @param      loadFactor      the load factor of the linked hash set
 * @throws     IllegalArgumentException  if the initial capacity is less
 *               than zero, or if the load factor is nonpositive
 */
public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true);
}

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

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

可以看到
LinkedHashSet->HashSet->LinkedHashMap->HashMap
HashSet->HashMap
TreeSet->TreeMap->红黑树

总之，Set是个寄生虫，它的一切底层原理依赖于Map
并且依赖其key不重复的特性，实现set数据不重复的特性。