1. Set接口基本介绍

1. Set是无序集合（添加和取出的顺序不一致，但取出的顺序是固定的），没有索引
2. 不允许重复元素，所以最多包含一个null
3. JDK API中Set接口的实现类有：
   Abstract, ConcurrentHashMap.KeySetView, ConcurrentSkipListSet, CopyOnWriteArraySet, EnumSet, HashSet, JobStateReasons, LinkedHashSet, TreeSet

1.1 Set接口的常用方法

Set接口和List接口一样，都是Collection的子接口，因此常用方法和Collection接口一样

1.2 Set接口的遍历方法

同Collection的遍历方式一样，因为Set接口是Collection接口的子接口。

1. 可以使用迭代器
2. 增强for循环
3. 不能使用索引的方式来获取

2 HashSet

2.1 HashSet的全面说明

1. HashSet实现了Set接口，类定义如下：

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

2. HashSet实际上是HashMap，HashSet的无参构造函数如下：

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

3. 可以存放null值，但因为不能重复，所以只能存放一个null
4. HashSet不保证元素是有序的，取决于hash之后，在确定索引的结果，也因此取出顺序是固定的
5. 不能有重复元素/对象。

2.2 有关重复元素的经典问题

//定义一个类
class Dog{
    private String name;
    public Dog(String name){
        this.name = name;
    }
}
//定义一个HashSet
Set<Object> set = new HashSet<>();
set.add(new Dog("dog"));
set.add(new Dog("dog"));
System.out.println(set);

两个dog都能添加成功！前面不是说不能有重复元素吗？事实上，HashSet判断元素是否重复依靠的是HashCode，而上面的代码并没有重写HashCode和equals方法，导致HashSet在判断两个Dog对象是否重复时，是以地址为依据判断的，而两个对象实例其在堆上的内存必然是不一样的，因此他们两个被认为是不同的实例。
相同的问题使用String再来验证一下：

set.add("john");
set.add("john");
System.out.println(set);

毫无疑问地添加失败了，这是因为"john"被放在了常量池中，地址不变了吗？

set.add(new String("john"));
set.add(new String("john"));
System.out.println(set);

结果仍然添加失败，这两个String对象的内存地址不同，却仍被准确识别为重复元素，是因为String类重写了HashCode和equals方法，HashSet在判断过程中比较的是二者的内容是否一致，而不再是地址了

2.3 HashSet底层机制说明

HashSet底层是HashMap，HashMap底层是(数组+链表+红黑树)
HashSet添加元素的操作(hash()+equals()):

1. HashSet底层是HashMap
2. 添加一个元素是，先得到hash值，会转成索引值
3. 找到存储数据表table，看这个索引位置是否已经存放的有元素
4. 如果没有，直接加入
5. 如果有，调用equals比较内容，如果相同，就放弃添加，如果不相同，则添加到最后，形成链表
6. 在Java8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD(默认是8),并且table的大小 >= MIN_TRESHOLD_CAPACITY(默认是64)，就会进行树化(红黑树)
7. HashSet底层的HashMap，第一次添加时，table数组扩容到16，临界值(threshold)是16*0.75(加载因子, loadFactor) = 12;
8. 如果table数组使用到了临界值12，或者某条单链长度超过8，就会扩容到16*2 = 32，新的临界值就是32*0.75 = 24。以此类推
9. 在Java8中，如果一条链表的元素个数达到TREE_THRESHOLD(默认是8),并且table的大小>=MIN_TREEIFY_CAPACITY(默认是64)，就会进行树化(红黑树)，否则仍然采用数组扩容机制
10. 临界值比较的是table中的所有节点个数，不论这个节点是直接存储在table中，还是附加在某一条链表后
11. 如果table没有达到64，而单链长度超过8，会立即触发扩容，并且每次检测到超长都会触发一次扩容，即使没有达到threshold，直到table长度达到64后，触发树化

2.4 set.add()调用过程

    HashSet<Object> set = new HashSet<>();
    set.add("john");

以上代码的调用过程如下图：

2.4 set.add()调用过程

    HashSet<Object> set = new HashSet<>();
    set.add("john");

以上代码的调用过程如下图：

图中标注了调用顺序和返回顺序
其中，最关键的方法：final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)详细分解如下：

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        //定义了一些辅助变量，table就是HashMap的一个数组，类型是Node[]
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //if语句表示如果当前table是null，或者length==0，就第一次扩容到16
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //(1) 根据key得到Hash,去计算该key应该存放到table的那个索引位置，并把这个位置的对象赋给p
        //(2) 判断p是否为null
        //(2.1) 如果p为null,表示该位置还没有存放过元素,即没有发生哈希冲突，就创建一个Node(key="java",value=PRESENT)，
        //      就放在该位置 tab[i] = new Node(hash,key,value,null);
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

            //(2.2) 如果p不为null,表示该位置已经存放过元素，即发生了哈希碰撞，
        else {
            //定义了一些辅助变量。一个开发技巧的提示：在需要的局部变量(辅助变量)时再创建
            Node<K,V> e; K k;
            //(2.2.1) 如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样，并且满足下面两个条件之一，就认为传入了重复元素，不能加入
            // 条件一： 准备加入的key和 p指向的Node节点的key是同一个对象
            // 条件二： 调用equals()方法比较二者，结果为ture，即认为他们内容相同，注意，这里的equals()方法是程序员定义的，不是单纯的比较内容
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //再判断p是不是一棵红黑树，如果是一颗红黑树，就调用putTreeVal()来添加
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

            else {
                //如果table对应索引位置已经是一个链表，就用for循环比较
                for (int binCount = 0; ; ++binCount) {
                    //(1) 依次和链表的每一个元素比较后，都不相同，将该元素添加至该链表最后
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //在把元素添加到链表后，立即判断该链表长度是否超过8个节点，如果是，就尝试将该链表转化为红黑树
                        //在进行树化时，还有一层判断：if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize();
                        //如果if条件成立，就会先对table扩容；如果不成立，在转化成红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //(2) 如果比较过程中发现重复元素，退出返回
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;  //每次比较后，指针后移
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);//该方法是HashMap留给子类实现的方法，对于HashMap来说，是一个空方法
        return null;//返回null代表成功，否则会在前面的return语句中返回当前索引指向的对象
    }

其中，最关键的方法：final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)详细分解如下：

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        //定义了一些辅助变量，table就是HashMap的一个数组，类型是Node[]
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //if语句表示如果当前table是null，或者length==0，就第一次扩容到16
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //(1) 根据key得到Hash,去计算该key应该存放到table的那个索引位置，并把这个位置的对象赋给p
        //(2) 判断p是否为null
        //(2.1) 如果p为null,表示该位置还没有存放过元素,即没有发生哈希冲突，就创建一个Node(key="java",value=PRESENT)，
        //      就放在该位置 tab[i] = new Node(hash,key,value,null);
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

            //(2.2) 如果p不为null,表示该位置已经存放过元素，即发生了哈希碰撞，
        else {
            //定义了一些辅助变量。一个开发技巧的提示：在需要的局部变量(辅助变量)时再创建
            Node<K,V> e; K k;

            //(2.2.1) 如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样
            // 并且满足下面两个条件之一，就认为传入了重复元素，不能加入
            // 条件一： 准备加入的key和 p指向的Node节点的key是同一个对象
            // 条件二： 调用equals()方法比较二者，结果为ture，即认为他们内容相同，注意，这里的equals()方法是程序员定义的，不是单纯的比较内容
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //再判断p是不是一棵红黑树，如果是一颗红黑树，就调用putTreeVal()来添加
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

            else {
                //如果table对应索引位置已经是一个链表，就用for循环比较
                for (int binCount = 0; ; ++binCount) {
                    //(1) 依次和链表的每一个元素比较后，都不相同，将该元素添加至该链表最后
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //在把元素添加到链表后，立即判断该链表长度是否超过8个节点，如果是，就尝试将该链表转化为红黑树
                        //在进行树化时，还有一层判断：if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize();
                        //如果if条件成立，就会先对table扩容，知道64；如果不成立，在转化成红黑树
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    //(2) 如果比较过程中发现重复元素，退出返回
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;  //每次比较后，指针后移
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);//该方法是HashMap留给子类实现的方法，对于HashMap来说，是一个空方法
        return null;//返回null代表成功
    }