Set、HashSet、LinkedHashSet

set接口基本介绍

1. 无序(添加和取出的顺序不一致),没有索引
2. 不允许重复元素，所有最多包含一个null

HashSet

1. HashSet实现了Set接口
2. HashSet实际上是HashMap
   

HashSet细节

set.add("jack"); true
set.add("jack"); false
set.add(new Cat("tom")); true
set.add(new Cat("tom")); true

//重点
set.add(new String("hello")); true
set.add(new String("hello")); false

HashSet底层是HashMap，添加一个元素时，先得到hash值，会转成索引值，找到存储数据表table，看这个索引的位置是否已经存放有元素，如果没有就直接加入，如果有，就调用equals比较，如果相同就放弃添加，如果不同就添加到此链表后面，在Java8中如果一条连链表个数等于默认值8，并且table>=64 就转换成红黑树

执行过程:

1. 执行 HashSet()

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

2. 执行 add()

public boolean add(E e) {
    return map.put(e, PRESENT)==null; 
    //private static final Object PRESENT = new Object();
}

3. 执行 put(),该方法会执行hash(key) 得到key对应的hash值(h = key.hashCode()) ^ (h >>> 16)

public V put(K key, V value) { //key="java" value = PRESENT
    return putVal(hash(key), key, value, false, true);
}

4. 执行 putVal()

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                 boolean evict) {
      Node<K,V>[] tab; Node<K,V> p; int n, i;
      if ((tab = table) == null || (n = tab.length) == 0) //table就是存放节点的数组
          n = (tab = resize()).length;

      //根据key，得到hash去计算该key应该存到table表的哪个索引位置
      //并把这个位置的对象赋给p
      //判断p是否为null，如果为空表示还没有存放元素，就创建一个node放在末尾
      if ((p = tab[i = (n - 1) & hash]) == null)
          tab[i] = newNode(hash, key, value, null);
      else {
          Node<K,V> e; K k;
          if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) //如果当前索引位置对应的链表的第一个元素和准备添加的key的hash值一样 ，准备加入的key和p指向的Node节点是同一个对象，或者不是同一个对象，但是内容相同
              e = p;
          //再判断 p 是不是一颗红黑树，
          //如果是一颗红黑树，就调用 putTreeVal，来进行添加
          else if (p instanceof TreeNode)
              e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
          else { //如果table对应索引位置，已经是一个链表，就依次比较
                  //(1)依次和该链表的每个元素比较后，都不相同，就使用for循环比较，把元素添加到链表后，立即判断是否达到8个节点，如果达到就调用treeifyBin()对当前列表进行树化(红黑树)。在转成红黑树时，还进行判断，如果该table数组大小 小于64先扩容，否则转成红黑树
                  //(2)在比较的过程中，有相同情况就break
                  //
              for (int binCount = 0; ; ++binCount) {
                  if ((e = p.next) == null) {
                      p.next = newNode(hash, key, value, null);
                      if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                          treeifyBin(tab, hash);
                      break;
                  }
                  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);
      return null;
  }

HashSet的扩容

1. 底层的HashMap，第一次添加时，table数组扩容到16，临界值(threshold)是16 * 加载因子 (loadFactor)是0.75 = 12
2. 如果table数组使用到了临界值12，就会扩容到16 * 2 = 32，新的临界值就是32 * 0.75 = 24，依次类推
3. 在java8中，如果一条链表的元素个数到达TREEIFY_THRESHOLD(默认是8)，并且table的大小>=MIN_TREEIFY_CAPACITY(模拟64)，就会进行树化(红黑树)，否则仍然采用数组进行扩容机制