Java Set笔记

Set种类

Set接口的特性，Set接口继承了Collection接口，Set集合中不能包含重复的元素，每个元素必须是唯一的，你只要将元素加入set中，重复的元素会自动移除。

Java中提供了HashSet、TreeSet、LinkedHashSet三种常用的Set实现。

HashSet实现

HashSet底层通过HashMap实现。

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

HashSet存储元素是无序的，元素的哈希码进行存储的，HashSet根据每个存储对象的哈希码值（调用hashCode方法获得），用固定的算法算出它的存储索引，把存储对象存放在一个叫做散列表的相应位置中，如果对应的位置没有其它元素，就只需要直接存入；如果该位置已经有元素了，就会将新对象跟该位置的所有对象进行比较（调用equals（）方法），以查看容器中是否已经存在该对象，若不存在，就存放该对象，若已经存在，就直接使用该对象。

HashSet的存储结构是个链表数组，每一个数组元素就是一个链表，类似这种数据结构称为散列表。数组用于存储元素，该存储元素对应的数组下标是调用hashCode方法返回的存储元素的哈希码。当后加入元素的哈希码与已经加入的元素哈希码相同时，HashSet就会创建一个链表，将相同哈希码的元素存入一个链表，并将该链表的头指针存储到哈希码对应的数组元素中。

HashSet和TreeSet

HashSet底层数据结构是哈希表，TreeSet底层数据结构是红黑树。

TreeSet保证元素的排序方式：

自然排序(这种排序方式可以理解成元素本身具备比较性)让元素所属的类实现Comparable接口。
比较器排序(这种排序可以理解成集合类具备比较性)让集合构造方法接收Comparator的实现类对象，实现方式可以用匿名类来实现。

LinkedHashSet

是HashSet子类，LinkedHashSet集合也是根据元素hashCode值来决定元素存储位置，但它同时使用链表维护元素的次序，这样使的元素看起来是以插入的顺序保存的。也就是说当遍历LinkedHashSet集合里的元素时，HashSet将会按元素的添加顺序来访问集合里的元素。

LinkedHashSet需要维护元素的插入顺序，因此性能略低于HashSet的性能，但是在迭代访问Set里的全部元素时，将有很好的性能，因为它以列表来维护内部顺序。