HashMap擴容改進分析

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

是以處。