HashSet
1，HashSet 概念
HashSet 是 Set 子接口的一个实现子类，它的底层由 HashMap 提供（数组+链表+红黑树），并借助 HashMap 的键来存储对象。由于是 Set 的实现子类，它具备 set 的无序、不可重复、非同步的特点；同时，由于 Hash 效果，它的查找会更快。
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
2，源码分析
同样的，我们还是关注 HashSet 的扩容机制。
2.1，基本属性
private transient HashMap<E,Object> map; //可见 hashset 实则就是 hashmap
//因为 hashset 只用到了键，所以值对象统一取一个静态对象 PRESENT 填充
//至于为什么不用 null，可能是为了避免被回收或是导致空指针异常等情况
private static final Object PRESENT = new Object();
2.2，构造方法
这里为了简单，我们其实只需要分析空参构造就可以了：
public HashSet() {
map = new HashMap<>();
}
这里其实实现了一个 map，因此我们有必要分析一下 map：（这里只分析一些和 Hashset 有关的实现）
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //默认初始化容量 16
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认加载因子 0.75
static final int TREEIFY_THRESHOLD = 8; //默认将数组树化的阈值 8
static final int MIN_TREEIFY_CAPACITY = 64; //数组树化时表的容量 64
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
2.3，主要方法
完成空参初始化之后，会返回一个如下结构的 hashSet：
table：即我们存放节点的数组；size：即我们添加元素的个数；
modcount：修改次数；threshold：数组扩容阈值
首先执行 add 方法，该方法返回是否添加成功标志，底层走 hashMap 的 put 方法，即 putVal 方法：
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
首先，根据 key 值进行 hash，命中索引。注意这里的 hash 并不仅仅是 hashcode。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
然后就开始执行我们真正的插入逻辑了，下面是完整代码。这里为了更加清晰，我们会截取片段进行分析：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//逻辑 1：第一次加入元素 table 为 null 时执行
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//逻辑 2：当前索引处为空可以添加元素
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//逻辑 3：当索引已经有元素时
else {
Node<K,V> e; K k;
//当 hash 相同且对象相同或对象内容相同时，无法插入
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果是 TreeNode 实例
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//上面情况都不是，说明他们的 hash 相同了，链表开始发挥作用
else {
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); //保留的 null 方法，没有实现
return null;
}
3，细节分析
3.1，第一次添加元素时的初始化
可以看到，在第一次添加时，会执行逻辑 1，主要进行确定 table 大小的方法 resize：
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//扩容机制
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
}
else if (oldThr > 0)
newCap = oldThr;
//第一次添加时，table 默认设置为 16
else {
newCap = DEFAULT_INITIAL_CAPACITY;//16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
此时，table 被设置为 16，阈值被设置为 16*0.75=12；设置阈值的目的是缓冲，到了阈值就开始提前扩容，防止一次添加过多的数据造成容器溢出。
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
然后开始执行逻辑 2，给 key 确定索引位置。这里有一个细节就是与运算，它有点类似模运算。a&b 的结果会被映射到 a-1 的空间里。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
至此一个元素加入完毕。
3.2，第二次添加元素
第二个元素开始加入时，会开始执行逻辑 2，后面流程类似，不再赘述。
3.3，第二次添加元素时相同元素的判断
第二次时添加相同元素，会开始执行逻辑 3。如果当前位置的对象 hash 和插入元素 hash 相同且对象相同或对象值相等，即将当前 node 对象 p 赋值给 e，使得 e!=null,插入失败。从而实现不能添加相同元素的机制。
这里先说明一下，什么是相同元素。一般我们认为，对象相同==或内容相同 equals 即为相同。当然，这里的相同规则可以由程序编写人员（简称程序员）自行重写 equals 方法实现。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
3.4，触发扩容机制
首先声明一下，这里的扩容指的是扩容 table 的大小。
当++size 大于 thread,开始执行 resize 里的扩容逻辑，即当 oldCap=oldTab.length>0 且小于 MAXIMUM_CAPACITY 时，进入以下判断：可见扩容机制是当前 oldCap=oldTab.length=DEFAULT_INITIAL_CAPACITY 的 2 倍；且 threshold 也是 2 倍。
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
随后：更新当前阈值，并重新建立容量为 newCap 的数组 table
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
然后，开始由 oldTab 将元素填充到 newTab，基本过程是逐个遍历赋值给 newTab
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果当前所引处结点的下一个结点为 null
if (e.next == null)
//注意，元素存放新数组时重新做了 hash
newTab[e.hash & (newCap - 1)] = e;
3.5，链表转红黑树
假设多个不同对象的 hashcode 相同，开始触发链表机制，即将 hash 相同的元素挂载到同一条链表上。这里通过死循环的方式找到挂载位置挂载元素，跳出死循环的机制只有两个：①找到挂载位置，挂载成功跳出；②遍历过程中发现当前元素和当前结点 hash 相同且对象相同或对象值相等，那么视为相同元素，挂载失败跳出。
else {
for (int binCount = 0; ; ++binCount) {
//当当前链表的第一个元素为 null 时，可以挂载节点
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // 8-1，挂载量达到 8 时开始转红黑树
treeifyBin(tab, hash); //红黑树，暂时不做分析，见 hashmap
break;
}
//如果发现
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//不断更新当前节点
p = e;
}
}
当挂载量达到阈值 7（8 个元素）时，开始执行 treeifyBin 方法：
可以看到当数组长度为达到 64 时，不会触发链表转红黑树的机制。所以当添加 hash 相同元素个数为 11 个时（9:16；10：32；11:64）会触发链表转红黑树机制。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//当 tab 为 null 或 tab 长度没有达到 64，实现扩容机制
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
4，总结
- hashset 底层是利用 hashmap 的键，即数组+链表（红黑树）的形式；hashset 是无序、不重复的；
- hashset 第一次数组扩容为 16，阈值取当前容量的 0.75；下次扩容容量和阈值均是当前值直接乘 2；
- 当链表节点数量为 8 且数组容量为 64 时，才会执行链表转红黑树机制。