Set集合

首先从顶层类来介绍：

Set:

set定义：不可重复存储的数据接口。

set接口相关的一些方法：

public interface Set<E> extends Collection<E> {
   // Query Operations
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();  //返回一个包含set中所有元素的数组
    <T> T[] toArray(T[] a); //返回一个包含此set中所有元素的数组；返回数组的运行时类型是指定数组的类型

    // Modification Operations
    boolean add(E e);
    boolean remove(Object o);

    // Bulk Operations
    boolean containsAll(Collection<?> c); //如果此set包含指定 collection 的所有元素，则返回 true
    boolean addAll(Collection<? extends E> c);
    boolean retainAll(Collection<?> c); //仅保留set中那些包含在指定 collection中的元素
    boolean removeAll(Collection<?> c); //移除set中那些包含在指定 collection中的元素
    void clear();

    // Comparison and hashing
    boolean equals(Object o);
    int hashCode(); //返回set的哈希码
    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT);
    }
}

可以看到set接口继承自Collection接口，这些方法就不介绍了，前面都有介绍。
接下来再看下一层的抽象实现类AbstractSet:

public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {

    protected AbstractSet() {
    }


    // 比较指定对象与此 set的相等性，如果指定的对象也是一个set，并且两个set有相同的大小，元素，则返回true。
    public boolean equals(Object o) {
        if (o == this)
            return true;

        //1.先检查指定的对象是不是set
        if (!(o instanceof Set))
            return false;
        Collection<?> c = (Collection<?>) o;
        //2.再检查指定set的大小与这个set的大小是否相等
        if (c.size() != size())
            return false;
        try {
            //3.最后检查这个set是否包含指定set中的所有元素
            return containsAll(c);
        } catch (ClassCastException unused)   {
            return false;
        } catch (NullPointerException unused) {
            return false;
        }
    }

    //返回此set的哈希码值:即该set中所有元素的哈希值之和
    public int hashCode() {
        int h = 0;
        Iterator<E> i = iterator();
        while (i.hasNext()) {
            E obj = i.next();
            if (obj != null)
                h += obj.hashCode();
        }
        return h;
    }

    //从此 set中移除包含在指定 collection中的所有元素
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        boolean modified = false;

        //如果此set的大小>指定集合c的大小
        if (size() > c.size()) {
            //迭代指定集合c中的元素，并在此set中逐个删除
            for (Iterator<?> i = c.iterator(); i.hasNext(); )
                modified |= remove(i.next()); 
        } else {
            for (Iterator<?> i = iterator(); i.hasNext(); ) {
                if (c.contains(i.next())) {
                    i.remove();
                    modified = true;
                }
            }
        }
        return modified;
    }
}

接下来就是本文的几个重点之一：HashSet

hashSet：散列表，无序的数据存储结构.简单介绍下hashCode的概念：在Object中（如果该类没有覆盖hashCode（）方法的话）表示某个对象内存的一个映射数字，通过该数字可以找到对应的对象内存块，类似于数据库中的索引的概念，当然有些类会重写hashCode方法，例如字符串，基本类型的封装类等。由于在集合类添加元素（包括但是不限于）等判断两个对象是否一样时我们是利用equals方法比较的，如果equals的比较结果为true，则hashCode也必须相同,这里就要求equals重写了则应该也要重写hashCode，以保证他们的对应关系。

　　知道了hashCode的概念后，我们就可以大概了解hashSet的原理了：hashSet通过hashCode建立一个索引表，用于储存其内的所有对象的内存位置，add元素进来的时候，通过该表便可以快速地判断元素是否在set内，在取元素的时候，也可以通过该表快速定位对象了，这样可以保证其快速高效地添加和查询元素。

　　具体的set内部原理大概是这样的：java中会将set的内部存储机构分为多个链表（即链表数组）（我们下面称这些链表为桶），在添加元素时，通过元素的hashCode和桶的个数取余，得到的余数表示了该对象需要装到哪个桶中，只要保证桶数目够多，便可快速定位到该对象所在的位置，当发生hashCode重复时，调用冲突解决算法：该算法将hashCode相同但是eauqls为false的方法放在一个单独的链表中。具体请看下面的丑图：

好了，上图大概阐明了set的主要数据结构，归根到底就是一句话：set是利用hashCode进行对象定位，利用链表数组进行存储的数据结构！

一个小例子：

public class SimpleCollection {
    public static void main(String[] args) {
        Set<Person> sp=new HashSet<>();
        sp.add(new Person("gxx"));
        sp.add(new Person("gxx"));
        System.out.println(sp.size());


    }
}

class Person{
    private  String name;
    public Person(String name){
        this.name=name;
    }
    public String getName() {
        return name;
    }

    @Override
    public boolean equals(Object obj) {
        return obj instanceof Person 
                ? this.name==((Person)obj).getName()
                :false
                ;
    }
    @Override
    public int hashCode() {
        return name.hashCode();
    }
}

自定义类使用hashset存储，为什么需要重写equals和hashcode方法？
https://jingyan.baidu.com/article/d5a880eb8fb61d13f147cc99.html

接下来就是HashSet的方法：

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;


    private static final Object PRESENT = new Object();


    public HashSet() {
        map = new HashMap<>();
    }


    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }


    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }


    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }


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


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


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


    public boolean isEmpty() {
        return map.isEmpty();
    }


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


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


    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }


    public void clear() {
        map.clear();
    }


    @SuppressWarnings("unchecked")
    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(e);
        }
    }


    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // Write out any hidden serialization magic
        s.defaultWriteObject();

        // Write out HashMap capacity and load factor
        s.writeInt(map.capacity());
        s.writeFloat(map.loadFactor());

        // Write out size
        s.writeInt(map.size());

        // Write out all elements in the proper order.
        for (E e : map.keySet())
            s.writeObject(e);
    }


    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // Read in any hidden serialization magic
        s.defaultReadObject();

        // Read capacity and verify non-negative.
        int capacity = s.readInt();
        if (capacity < 0) {
            throw new InvalidObjectException("Illegal capacity: " +
                                             capacity);
        }

        // Read load factor and verify positive and non NaN.
        float loadFactor = s.readFloat();
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new InvalidObjectException("Illegal load factor: " +
                                             loadFactor);
        }

        // Read size and verify non-negative.
        int size = s.readInt();
        if (size < 0) {
            throw new InvalidObjectException("Illegal size: " +
                                             size);
        }

        // Set the capacity according to the size and load factor ensuring that
        // the HashMap is at least 25% full but clamping to maximum capacity.
        capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
                HashMap.MAXIMUM_CAPACITY);

        // Create backing HashMap
        map = (((HashSet<?>)this) instanceof LinkedHashSet ?
               new LinkedHashMap<E,Object>(capacity, loadFactor) :
               new HashMap<E,Object>(capacity, loadFactor));

        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            @SuppressWarnings("unchecked")
                E e = (E) s.readObject();
            map.put(e, PRESENT);
        }
    }


    public Spliterator<E> spliterator() {
        return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
    }
}

可以看出来底层全是map的实现，所以在以后介绍map时候具体阐述。

LinkedHashSet:
LinkedHashSet的特征:
LinkedHashSet是HashSet的一个子类，LinkedHashSet也根据HashCode的值来决定元素的存储位置，但同时它还用一个链表来维护元素的插入顺序，插入的时候即要计算hashCode又要维护链表，而遍历的时候只需要按链表来访问元素。查看LinkedHashSet的源码发现它是样的，

//LinkedHashSet 源码

public class LinkedHashSet extends HashSet  
    implements Set, Cloneable, Serializable  
{  

    public LinkedHashSet(int i, float f)  
    {  
        super(i, f, true);  
    }  

....  

在JAVA7中， LinkedHashSet没有定义任何方法，只有四个构造函数，它的构造函数调用了父类（HashSet)的带三个参数的构造方法，父类的构造函数如下，
//HashSet构造函数

    HashSet(int i, float f, boolean flag)  
    {  
        map = new LinkedHashMap(i, f);  
    }  

……
由此可知，LinkedHashSet本质上也是从LinkedHashMap而来，LinkedHashSet的所有方法都继承自HashSet, 而它能维持元素的插入顺序的性质则继承自LinkedHashMap.
下面是一个LinkedHashSet维持元素插入顺序的例子，

TreeSet Vs HashSet:
　首先，hashTree既然包含数组机构，那肯定在所有桶数到达临界点时，要进行大规模的扩桶操作，这样毫无疑问会大大影响性能。当然，也正因为它的无序性和包含链表的部分特性（数组链表嘛），它的插入元素是非常快的（毕竟插入时不用重新排序嘛），另外，它的查询操作速度上也还可以，毕竟它包含了一种数组的结构在里面（数组性质就是通过游标可以快速定位嘛）；

　　　　然后呢，再说treeSet吧，作为树状的结构，扩展时时不存在什么问题的，但是在插入元素的时候，显然要重新排列数据，所以插入输入肯定比不上hashSet的。当然，在查询元素中，treeSet的速度可不是盖的，毕竟人家是tree的结构（就算是简单的二叉有序树复杂度也只是logn）。
　　　　总的来说：hashSet扩展性不好，但是查和插入（删除也一样）速度都不错；treeSet扩展性不错，查速度也不错，就是插入会速度慢点。

参考博文：
http://blog.csdn.net/lirx_tech/article/details/51514248
https://www.cnblogs.com/UniqueColor/p/5707704.html
https://www.cnblogs.com/lcplcpjava/p/6602049.html
http://blog.csdn.net/solafy/article/details/52960777