HashMap扩容
JDK1.8以后对之前版本的HashMap扩容多线程场景下的死锁的问题进行了解决。采用高低位拆分转移方式,避免了链表的产生。
resize()方法扩容部分
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;
}
}
}
}
高低位拆分扩容
JDK8中设置了
Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null;
根据
(e.hash & oldCap) == 0
确定是高位还是低位,低位直接放在新hashtable的相同位置,高位则放在新hashtable的原位置+oldCap的位置,oldCap是原hashtable.length。
第一步:e指向key(3),next指向key(7),计算
(e.hash & oldCap) == 0)
不等于0,进入到高位判断;
第二步:e指向key(7),next指向key(5),计算
(e.hash & oldCap) == 0)
不等于0,进入到高位判断;
第三步:e指向key(5),next指向key(9),计算
(e.hash & oldCap) == 0)
等于0,进入到低位判断;
第四步:e指向key(9),next指向null,计算
(e.hash & oldCap) == 0)
等于0,进入到低位判断;
第五步:此时的e和next都已经指向null,所以判断
(loTail != null)
,此时lotail是key(9),hiTail是key(7);
第六步:把低位的数据移到新hashtable的相同索引处,把高位的数据移到新hashtable的
j + oldCap
所以处。