5-4 HashSet源码解读
1.HashSet底层是HashMap
2.添加一个元素时，会先得到hash值-会转成索引值
3.找到存储数据表table，看这个索引位置是否已经存放有元素
4.如果没有，直接加入
5.如果有，调用equals()方法比较。如果相同，就放弃添加，如果不相同，则添加到最后
6.在Java 1.8中，如果一条链表的个数到达TREEIFY_THRESHOLD(默认是8),并且table的大小>=MIN_TREEIFY_CAPACITY(默认值为64),就会进行树化（红黑树）
分析HashSet添加元素底层如何实现
1.执行HashSet()构造器
public HashSet() {
//创建一个HashMap作为底层
map = new HashMap<>();
}
2.执行add()方法
//这里PRESENT为哨兵value，只是占位map(k,v)中的v参数，没有实际意义
private static final Object PRESENT = new Object();
public boolean add(E e){
return map.put(e,PRESENT)；
}
3.执行put()方法
//key为我们想放进去的值 value为哨兵value PRESENT
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
hash算法
static final int hash(Object key) {
int h;
//避免碰撞
return (key == null) ? 0:(h = key.hashCode()) ^ (h >>>16);
}
4.执行putVal()方法
final V putBal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
//定义辅助变量
Node<K,V>[] tab; Node<K, V> p; int n,i;
//table就是HashMap的一个数组，类型是Node[]
//将table的值赋给tab 如果tab为null或tab的大小为0
if((tab = table) == null || (n = tab.length) == 0)
//resize()方法重新定义tab的长度，初始值为16.返回扩容之后的Node数组Node[]。
n = (tab.resize()).length;
//(1)根据用key得到的hash值，去计算该key应该放到table的哪个索引位置。并把这个对象的值赋给p
//(2)判断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;
//如果当前索引位置对应的链表的第一个元素和准备添加key的hash值一样
//并且满足下面两个条件之一:
//(1)准备加入的key和p指向Node节点的key是同一个对象
//(2)p指向的Node节点的key的equals()和准备加入的key比较后相同
//就不能加入
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循环比较
*(1)依次和链表的每一个元素比较厚，都不相等，则加入该链表最后
*注意：把元素添加到链表后，立即判断该链表是否已经到达8个节点
*如果是，就调用treeifyBin()方法对当前这个链表进行树化（转成红黑树）
*注意：在转成红黑树时要进行判断，判断条件:
*if(tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)) MIN_TREEIFY_CAPACITY=6
* resize();
*如果上面条件成立，先对table进行扩容
*只有上面条件不成立，才进行转化红黑树
*(2)依次和该链表每一个元素比较过程中，如果有相同情况，直接break
*/
for(int binCount = 0;;++binCount) {
p.next = newNode(hash, key, value, null);
//链表长度大于8,判断是否转成红黑树
if(binCount >= TREEIFYTHRESHOLD - 1)
treeifyBin(tab, hash);
break;
//及时更新
p = e;
}
}
//如果存在这个映射就覆盖
if(e != null) {
V oldValue = e.value;
if(!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
//没有返回null，添加失败
return oldValue;
}
}
++modCount;
if(++size > threshold)
resize();
//留给HashMap子类实现的afterNodeInsertion(evict)方法
afterNodeInsertion(evict);
//添加成功
return null;
}