注:行尾注释是为了方便调试jdk源码
resize源码注释
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
上述的未知语言翻译成人话
首先,如果当前的哈希表 table 为 null,表示哈希表尚未进行初始化,需要根据 threshold 字段中的初始容量目标分配空间,这个初始容量目标决定了哈希表的初始大小。
否则,如果哈希表 table 已经存在,表示需要对哈希表进行扩容。由于HashMap使用的是2的幂次扩容,每个哈希桶中的元素要么保持在相同的索引位置,要么以2的幂次偏移移动到新的哈希表中。(英语渣渣,只能翻译成这样了!)
流程简述
流程:进行一些边界判断之后,创建新tab,遍历原tab,逐个节点判断类型(普通节点,链表,红黑树,)进行放入
图片链接
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 && // 边界判断:原数组长度大于等于初始化长度16,并且原数组长度扩大1倍也小于2^30次方
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold // 阈值扩大一倍
}
else if (oldThr > 0) // initial capacity was placed in threshold 旧阈值大于0
newCap = oldThr; // 旧阈值大于0,则直接将新容量=旧阈值
else { // zero initial threshold signifies using defaults 旧阈值等于0
newCap = DEFAULT_INITIAL_CAPACITY; // 说明没有进行初始化 , 将新容量赋值为初始化容量
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 新阈值 = 16* 加载因子
}
if (newThr == 0) { // 新阈值 = 0
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE); // 边界值判断,正常情况下newThr = newCap * 加载因子
}
threshold = newThr; // 新阈值来啦
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 创建新的table
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; //loHead:下标不变情况下的链表头 loTail:下标不变情况下的链表尾 /*这个下标是指hash索引.*/
Node<K,V> hiHead = null, hiTail = null; //hiHead:下标改变情况下的链表头 hiTail:下标改变情况下的链表尾
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { // 由于1.8采用的是原来两倍的扩容策略,所以不需要像1.7那样重新计算hash,扩容后的元素不是在原来的位置,就是在原来的位置的2次幂位置,所以只需要看hash新增的bite 是1还是0
if (loTail == null) // 是bite是0,在原来位置。
loHead = e; // 1.8按顺序添加,不是1.7头添加。
else
loTail.next = e;
loTail = e; // 链表尾索引移到e
}
else { // bite是1,索引变成原索引+oldCap
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead; // hash索引不变的情况下,将后来的链表头放到新数组的原容量索引位置, 挂上去
}
if (hiTail != null) { // tail->null
hiTail.next = null;
newTab[j + oldCap] = hiHead; // hash索引改变情况下,在新数组中的索引位置变为 /*原索引位置 + 原容量*/
}
}
}
}
}
return newTab;
}