1. Set接口基本介绍
- Set是无序集合（添加和取出的顺序不一致，但取出的顺序是固定的），没有索引
- 不允许重复元素，所以最多包含一个null
- 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接口的子接口。
- 可以使用迭代器
- 增强for循环
- 不能使用索引的方式来获取
2 HashSet
2.1 HashSet的全面说明
- HashSet实现了Set接口，类定义如下：
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
- HashSet实际上是HashMap，HashSet的无参构造函数如下：
public HashSet() {
map = new HashMap<>();
}
- 可以存放null值，但因为不能重复，所以只能存放一个null
- HashSet不保证元素是有序的，取决于hash之后，在确定索引的结果，也因此取出顺序是固定的
- 不能有重复元素/对象。
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()):
- HashSet底层是HashMap
- 添加一个元素是，先得到hash值，会转成索引值
- 找到存储数据表table，看这个索引位置是否已经存放的有元素
- 如果没有，直接加入
- 如果有，调用equals比较内容，如果相同，就放弃添加，如果不相同，则添加到最后，形成链表
- 在Java8中，如果一条链表的元素个数超过TREEIFY_THRESHOLD(默认是8),并且table的大小 >= MIN_TRESHOLD_CAPACITY(默认是64)，就会进行树化(红黑树)
- HashSet底层的HashMap，第一次添加时，table数组扩容到16，临界值(threshold)是16*0.75(加载因子, loadFactor) = 12;
- 如果table数组使用到了临界值12，或者某条单链长度超过8，就会扩容到16*2 = 32，新的临界值就是32*0.75 = 24。以此类推
- 在Java8中，如果一条链表的元素个数达到TREE_THRESHOLD(默认是8),并且table的大小>=MIN_TREEIFY_CAPACITY(默认是64)，就会进行树化(红黑树)，否则仍然采用数组扩容机制
- 临界值比较的是table中的所有节点个数，不论这个节点是直接存储在table中，还是附加在某一条链表后
- 如果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