集合_HashSet(HashMap)扩容机制源码简析
先说明一个问题：为什么说分析HashSet实际上是在分析HashMap？
因为HashSet的构造方法，本质上都是调用HashMap的构造方法，对其内部维护的HashMap对象map进行初始化
private transient HashMap<E,Object> map;
public HashSet() {
map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}众所周知HashMap的存储方式为K-V键值对，而HashSet的存储方式从表面上来看为仅存储key，其原因是HashSet中存在PRESENT属性，该属性为Object类型，其作用为：作为K-V键值对中的value。所以实际上HashSet的存储方式也为K-V键值对，但value恒为PRESENT（通过HashMap实现，必然是存储键值对的）
在HashMap中，value是可重复的，而key是不可重复的，该特性在HashSet上体现为"元素不可重复"（HashSet添加元素时只要求传入key）
private static final Object PRESENT = new Object();扩容机制源码简析
调用HashSet的add方法，内部调用HashMap的put方法，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);
}为了可读性，对于代码的解读写在注释中
关于putVal方法
//元素重复指的是key重复 即传入的key与链表中的key存在重复 发生重复时将放弃添加
//若遍历完链表都不存在重复的key 则将key与value作为参数（还有hash和next）创建结点 链接在链表尾结点（1.8之前是链接在头结点）
//而value是允许重复的 如HashSet中value恒为PRESENT
//size指的是HashSet(HashMap)集合中的元素个数 而不是集合内部维护的数组存放了元素的索引的个数
//例如 table.length == 16 只在索引0处存在一个长度为4的链表 其他索引处为空 此时size == 4而不是1
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//定义辅助变量
// tab指向table
// n=table.length
// p最初指向链表的头结点（此次准备添加的元素的hash对应的索引处的链表）
// i=索引
//table是HashMap中用于存储数据的数组 类型为Node<K, V> 即数组中的元素都是链表（若有元素的话）
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> p; int n, i;
//若table == null 或 table.length == 0 则进行第一次扩容（扩容为16）
//扩容后用n重新记录扩容后的table长度
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//n-1按位与hash（该hash不是hashCode 是hashCode经过按位异或无符号右移十六位的结果）计算得出索引 将该索引对应的链表的头结点赋值给p
//若n=16 即n=2^4 则(n-1)&hash表示取hash二进制数的后四位 而四位二进制数的表示范围为0-15 覆盖了数组当前的所有索引
//若p == null 即头结点为空 则代表此处尚未存储元素 将在该索引下创建一个新的结点作为头结点（参数为hash、key、value（PRESENT）、next）
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//hash对应的索引不为空时 即存在链表时
else {
//定义辅助变量
HashMap.Node<K,V> e; K k;
//若头结点的key的hash与准备添加的元素（后简称元素）的key的hash相等（hashCode相等）
//且头结点的key与元素的key相等或元素的key不为null且头结点的key与元素的key经equals判断相等
//这边说明一点 虽然p.hash与hash经计算得出的索引相同 但是不能想当然地认为p.hash == hash 因为决定索引的是二者的二进制数的后n位（2^n == 容量）
//该if语句等价于 重复元素无法添加 除非hash相等且equals判断为true
//所以hashCode与equals的重写总是成双成对的（设计者设计的规则 或许有其深意 但具体是什么我不清楚）
//此处举例String类 Sting类重写了hashCode方法与equals方法
//对于String类而言 两个String对象只要内容相同 则计算得出的hashCode就相同 且equals判断为true 即使这两个对象都是通过new创建的（均不指向字符串常量池）
//此时对于内容相同的两个String对象 同时符合一、三判断 故新元素不能被添加
//若此时存在一个类 只重写了hashCode方法或equals方法 该类的两个对象就无法同时通过一、三判断 即可以被添加
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//将p的引用赋值给e 此时e != null 将走放弃添加的方法
e = p;
//判断链表是否为一颗红黑树 若是则调用putTreeVal方法添加元素
else if (p instanceof TreeNode)
e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//进行元素添加
else {
//遍历链表
for (int binCount = 0; ; ++binCount) {
//若一直遍历至尾结点都未找到相同元素 则进行添加 并break
//此时e == null
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//添加元素时 链表的长度>=8 将进行树化（即添加完元素后 链表长度为9时 将进行树化）
//但还需要满足一个条件 table.length >= MIN_TREEIFY_CAPACITY（默认为64） 否则不进行树化 而是进行扩容
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//若遍历时检测到存在相同元素 则放弃添加 并break
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//等价于 p = p.next
p = e;
}
}
//若放弃添加 则e必然不等于null（元素重复） 即必然走该方法
//该方法返回e.value e指向发生元素重复的结点（HashSet通过HashMap实现 其value恒为PRESENT）
if (e != null) { // existing mapping for key
V oldValue = e.value;
//HashMap中的putVal方法的onlyIfAbsent参数为false 故该判断恒成立
//即使在HashSet中value != null恒成立（value != null恒成立代表key发生重复即放弃添加）
//故重复元素中的新元素的value必将覆盖旧元素的value
//这代表着什么呢？
//HashMap中数据是以键值对的方式存在的
//key发生重复时不添加新的结点 但是新元素的value将覆盖旧元素的value
//此为"修改" 即修改指定key值对应的结点的value
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//该方法交由HashMap的子类实现 在HashMap中是一个空方法
afterNodeAccess(e);
//即使oldValue == null 但也与 return null 是不同的
return oldValue;
}
}
++modCount;
//判断添加该元素时（注意是++size 也就是说size不受此次添加的元素的影响）数组中存储的元素是否已经超越了临界值threshold
//若超过临界值threshold将进行扩容
if (++size > threshold)
resize();
//该方法交由HashMap的子类实现 在HashMap中是一个空方法
afterNodeInsertion(evict);
//返回null代表添加成功
return null;
}关于扩容函数resize
//扩容
//简而言之：数组容量在第一次扩容时将扩容至16 或通过构造函数指定的容量（会经过tableSizeFor方法处理 暂存于临界值threshold） 后续扩容将扩容至先前容量的两倍
//加载因子DEFAULT_LOAD_FACTOR（默认为0.75） 加载因子可自定义 即通过构造函数为loadFactory赋值 加载因子*容量=临界值
//临界值会随着数组的扩容而扩容 系数同样为2（大多数情况下）
//size超过临界值时表示数组需要进行扩容的（size等于临界值时不会）
@SuppressWarnings("ALL")
final HashMap.Node<K,V>[] resize() {
HashMap.Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//数组存在容量 换言之数组不是初始态数组
if (oldCap > 0) {
//若数组容量达到MAXIMUM_CAPACITY 将临界值threshold赋值为Integer.MAX_VALUE 即不再扩容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//反之则二倍扩容
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//此处标记 后文会用到
//若数组是初始态数组 但通过构造函数指定了容量（经过tableSizeFor方法处理后暂存于临界值threshold） 则将容量初始化为临界值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//若数组是初始态数组 但未通过构造函数指定临界值 则将数组容量初始化为16 并通过DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY计算临界值
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//以上的情况中 只有走标记处分支的情况下 newThr == 0才会成立
//该分支用于为临界值threshold赋真正的值做准备（暂存于newThr）
//若经标记处分支初始化的容量<MAXIMUM_CAPACITY 且float ft = (float)newCap * loadFactor<MAXIMUM_CAPACITY 将ft作为新临界值赋值给newThr
//反之将Integer.MAX_VALUE作为新临界值赋值给newThr
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//将新临界值newThr赋值给临界值变量threshold
threshold = newThr;
//开始扩容
@SuppressWarnings({"rawtypes","unchecked"})
HashMap.Node<K,V>[] newTab = (HashMap.Node<K,V>[])new HashMap.Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
HashMap.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 HashMap.TreeNode)
((HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
HashMap.Node<K,V> loHead = null, loTail = null;
HashMap.Node<K,V> hiHead = null, hiTail = null;
HashMap.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;
}关于树化函数treeifyBin
//树化
final void treeifyBin(HashMap.Node<K,V>[] tab, int hash) {
int n, index; HashMap.Node<K,V> e;
//table == null 或 table.length < MIN_TREEIFY_CAPACITY（默认为64）时 将先进行扩容 而不是树化
// 默认为64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
HashMap.TreeNode<K,V> hd = null, tl = null;
do {
HashMap.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);
}
}关于初始容量处理函数tableSizeFor
该函数的作用为：返回大于或等于传入的初始容量的最小2的n次方数
关于tableSizeFor可参照：
集合_HashMap_tableSizeFor_Mudrock__的博客-CSDN博客
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}