Java--Set的三个具体实现类

HashSet

HashSet继承AbstractSet类，实现Set、Cloneable、Serializable接口。其中AbstractSet提供Set接口的骨干实现，从而最大限度地减少了实现此接口所需的工作。Set接口是一种不包括重复元素的Collection。HashSet是无序的，不能保证迭代的次序。可以存储null值，同时是线程不安全的，底层实现是HashMap。

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

构造器

/**
* 创建一个空的set，起底层的HashMap的默认初始容量为16，默认的加载因子为0.75
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
    map = new HashMap<>();
}

/**
 * 创建一个包含指定集合中元素的set。
 * 其底层的HashMap使用默认负载因子（0.75）和足以容纳指定集合中的元素的初始容量创建的
 * 其初始容量的计算公式为Math.max((int) (c.size()/.75f) + 1, 16)，c即为传入集合的大小
 * @param c the collection whose elements are to be placed into this set
 * @throws NullPointerException if the specified collection is null
 */
public HashSet(Collection<? extends E> c) {
    map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
    addAll(c);
}

/**
 * 创建一个空的set，其底层的HashMap的容量为指定的容量initialCapacity，
 * 加载因子为指定的loadFactor
 * @param      initialCapacity   the initial capacity of the hash map
 * @param      loadFactor        the load factor of the hash map
 * @throws     IllegalArgumentException if the initial capacity is less
 *             than zero, or if the load factor is nonpositive
 */
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

/**
 * 创建一个空的set，其底层的HashMap的容量为指定的容量initialCapacity，
 * 加载因子为默认的0.75
 * @param      initialCapacity   the initial capacity of the hash table
 * @throws     IllegalArgumentException if the initial capacity is less
 *             than zero
 */
public HashSet(int initialCapacity) {
    map = new HashMap<>(initialCapacity);
}

容量 * 加载因子=threshold，为这个容器的临界值，当存储的元素到了这个临界值，那么容器就会自动扩容。

方法

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

该方法的作用是：如果指定的元素尚不存在，则将其添加到该集合中。可以看到add方法的底层实现是将指定的元素存入到声明的HashMap中，将元素值作为map的key，然后指定一个PRESENT作为value。

这个value值是一个常量，所有添加到set中的元素，最终添加到对应的hashmap中的时候，对应的value都是PRESENT：

private static final Object PRESENT = new Object();

添加到set的元素实际存储到了map的key中，这也能够保证存入到set中的元素不会重复。

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

iterator()方法返回对此 set 中元素进行迭代的迭代器。返回元素的顺序并不是特定的。底层调用HashMap的keySet返回所有的key，这点反应了HashSet中的所有元素都是保存在HashMap的key中，value则是使用的PRESENT对象，该对象为static final。

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

size()返回此 set 中的元素的数量（set 的容量）。底层调用HashMap的size方法，返回HashMap容器的大小。

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

contains()，判断某个元素是否存在于HashSet()中，存在返回true，否则返回false。

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

clone返回此 HashSet 实例的浅表副本：并没有复制这些元素本身。

LinkedHashSet

LinkedHashSet继承自HashSet，源码更少、更简单，唯一的区别是LinkedHashSet内部使用的是LinkHashMap。这样做的意义或者好处就是LinkedHashSet中的元素顺序是可以保证的，也就是说遍历序和插入序是一致的。

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

其内部的构造方法：

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

LinkedHashSet的父类是HashSet，其构造方法中调用的父类构造方法super，指的就是HashSet中这个默认访问权限的构造器：

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

可以看出LinkedHashSet内部使用的是LinkHashMap。这样做的意义或者好处就是LinkedHashSet中的元素顺序是可以保证的，也就是说遍历序和插入序是一致的。

LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。

TreeSet

TreeSet会对集合里的元素按照指定的顺序进行排序，它的底层数据结构依据的是红-黑二叉树。如果想要往TreeSet集合中存入自定义类型的元素，有两种方案：

1、（自然排序）这个元素对应的类要么自身实现了Comparable接口，重写了其中的compareTo方法，在方法内定义比较算法, 根据大小关系, 返回正数负数或零，在使用TreeSet存储对象的时候, add()方法内部就会自动调用compareTo()方法进行比较, 根据比较结果使用二叉树形式进行存储。TreeSet方法保证元素唯一性的方式：就是参考比较方法的结果是否为0，如果return 0，视为两个对象重复，不存储。

2、自定义一个比较器类，继承Comparator，定义存入集合的元素是如何比较的。TreeSet，它根据指定比较器进行排序。插入到该set的所有元素都必须能够由指定比较器进行相互比较：对于set中的任意两个元素e1和e2，执行 comparator.compare(e1, e2) 都不得抛出 ClassCastException。如果用户试图将违反此约束的元素添加到 set 中，则add调用将抛出ClassCastException。

如果存入集合的元素既不支持自身比较性，又没有为这个集合传入自定义的比较器对象，那么就会抛出异常：

Exception in thread "main" java.lang.ClassCastException: com.test2.B cannot be cast to java.lang.Comparable

TreeSet是非同步的。TreeSet实际上是TreeMap实现的。TreeSet不支持快速随机遍历，只能通过迭代器进行遍历！

比较HashSet、LinkedHashSet和TreeSet三者的异同

HashSet 是 Set 接口的主要实现类，HashSet 的底层是 HashMap，线程不安全的，可以存储null值；

LinkedHashSet 是 HashSet 的子类，底层是LinkHashMap，能够按照添加的顺序遍历；

TreeSet 底层使用红黑树，能够按照按照某种规则对元素进行排序，排序的方式有自然排序和定制排序。集合中的元素是有序的，集合中的元素是唯一的。