JDK1.8
源码:
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) {//如果旧的容量是大于0
if (oldCap >= MAXIMUM_CAPACITY) {//如果旧的容量超过最大容量,阈值设置为integer最大值,返回旧的数组
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)//容量扩充1倍
newThr = oldThr << 1; // double threshold //如果新的容量小于最大容量并且旧的容量大于等于初始化的容量16时,新的阈值扩充1倍
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
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) {//如果数组中对应的值不为null
oldTab[j] = null;//旧的数组对应值引用为null
if (e.next == null) //e指向的next为null,说明只有一个值,直接根据hash取模移到新的数组中
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)//如果是红黑树,走红黑树的逻辑
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//位置不变的链表 低位=0 头和尾
Node<K,V> loHead = null, loTail = null;
//位置变的链表 高位=0 头和尾
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {//判断对应的hash,属于位置不变还是需要变
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;//位置需要变的链表 位置为位置迁移(index+oldCap)
}
}
}
}
}
return newTab; //返回新的数组
}
链表是红黑树扩容
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
//不需要改变位置的红黑树
TreeNode<K,V> loHead = null, loTail = null;
//需要改变位置的红黑树
TreeNode<K,V> hiHead = null, hiTail = null;
//对应红黑树大小
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {//遍历链表进行分类
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {//不需要改变位置的红黑树不为null时
if (lc <= UNTREEIFY_THRESHOLD)//如果大小 小于等于6时,转换成普通的链表
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
//如果没有需要改变位置的,说明原先的红黑树数据结构没有改变,否则说明数据结构改变了,需要重新转换成对应的红黑树
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
//如果原先位置的没有数据,说明原先的红黑树数据结构没有改变,全部都需要移到新的位置,否则说明数据结构改变了,需要重新转换成对应的红黑树
hiHead.treeify(tab);
}
}
}
总结:
- 扩容元素的赋值,结合各种数据限定判断,比如最大值、默认值,正常情况下扩容后数组大小为原来的2倍,阈值也为原来的2倍
- 判断数组中每个值是否只有一个或者是红黑树或者是普通链表结构
- 如果只有一个值,直接赋值到新的数组对应的位置中
- 如果是红黑树,根据红黑树逻辑迁移到数组对应的位置中
- 如果是普通链表,迁移到数组对应的位置中
- 不管是红黑树还是普通链表,再迁移的时候,都会分为原来位置和需要迁移的位置,因为扩容是原来的2倍,并且取数组下标是hash & (数组大小-1),所以旧的数组中的元素在扩容后只会分为原先的位置和(原先的位置+旧的数组大小)两种位置
- 红黑树在最后赋值的时候,会判断大小是否小于等于6,如果小于等于6,转换成普通的链表,如果大于6,还需要判断原来的红黑树有没有拆分(原来位置和需要迁移的位置都有值),如果重新拆分了,需要重新转换成红黑树结构