Set总结

首先一个Set不包括重复元素（包括可变对象）的Collection，是一种无序的集合。Set不包含满 a.equals(b) 的元素对a和b，并且最多有一个null。

Paste_Image.png

如图所示实现Set接口的重要类有HashSet（无序不重复），LinkedHashSet（按放入顺序有序不重复），TreeSet（按红黑树方式有序不重复），EnumSet，ConcurrentSkipListSet（来自于java.util.concurrent包），CopyOnWriteArraySet（来自于java.util.concurrent包）。
在Set接口中没有新增任何方法，所有方法均来自其父接口。它无法提供像List中按位存取的方法。在数学上一个集合有三个性质：确定性，互异性，无序性。

HashSet的特点、实现机制

a) HashSet的特点：

HashSet中存放的元素是无序的，底层是用HashMap实现的，在其中的add()函数中调用HashMap的put（）方法并把要放入的元素设置为Key，而value是一个Object类型的名为PRESENT的常量，由于用到了散列函数，因此其存取速度是非常快的，在地址空间很大的情况下它的存取速度可以达到O(1)级。

b）HashSet的实现机制：

首先需要了解一下散列或者哈希的用法。我们知道，当数据量很大时hash函数计算的结果将会重复，按照下图所示的形式进行存贮。

Paste_Image.png

在HashSet中有个loadFactor（负载因子），对于上图所示总共有11个位置，目前有4个位置已经存放，即40%的空间已被使用。
在HashSet的默认实现中，初始容量为16，负载因子为0.75，也就是说当有75%的空间已被使用，将会进行一次再散列（再哈希），之前的散列表（数组）将被删除，新增加的散列表是之前散列表长度的2倍，最大值为Integer.MAX_VALUE。
负载因子越高，内存使用率越大，元素的寻找时间越长。
负载因子越低，内存使用率越小，元素的寻找时间越短。
从上图可以看出，当哈希值相同时，将存放在同一个位置，使用链表方式依次链接下去。

c）注意：

HashSet基于HashMap无容量限制。
HashSet非线程安全。

TreeSet的特点、实现机制

a）TreeSet特点

TreeSet中所放的元素是有序的，并且元素是不能重复的。

b）TreeSet实现机制

TreeSet底层使用TreeMap实现，和HashSet一样，将每个要放入的元素放到key的位置，value位置放的是一个Object类型的常量。

c）注意

TreeSet基于TreeMap实现，支持排序；
TreeSet是非线程安全的。

LinkedHashSet的特点、实现机制

a）LinkedHashSet的特点：

LinkedHashSet保证了按照插入顺序有序，继承自HashSet，没有实现新的可以使用的方法。

b）LinkedHashSet实现机制：

LinkedHashSet继承自HashSet，构造时使用了在HashSet中被忽略的构造方法：
HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<E,Object>(initialCapacity, loadFactor); }
所以LinkedHashSet集合同样是根据元素的hashCode值来决定元素的存储位置，但是它同时使用链表维护元素的次序。这样使得元素看起 来像是以插入顺序保存的，也就是说，当遍历该集合时候，LinkedHashSet将会以元素的添加顺序访问集合的元素。LinkedHashSet在迭代访问Set中的全部元素时，性能比HashSet好，但是插入时性能稍微逊色于HashSet。