看完這篇還不懂HashMap的擴容機制，那我要哭了~-有解無憂

HashMap 發出的 Warning：這是《Java 程式員進階之路》專欄的第 56 篇，那天，小二垂頭喪氣地跑來給我訴苦，“老王，有個學弟小默問我‘ HashMap 的擴容機制’，我愣是支支吾吾講了半天，沒給他講明白，講到最后我內心都是崩潰的，差點哭出聲！”

我安慰了小二好一會，他激動的情緒才穩定下來，我給他說，HashMap 的擴容機制本來就很難理解，尤其是 JDK8 新增了紅黑樹之后，先基于 JDK7 講，再把紅黑樹那塊加上去就會容易理解很多，

小二這才恍然大悟，佩服地點了點頭，

HashMap 發出的呼聲：有 GitHub 賬號的小伙伴記得去安排一波 star 呀，《Java 程式員進階之路》開源教程目前在 GitHub 上有 244 個 star 了，準備沖 1000 了，求求各位了，

GitHub 地址：https://github.com/itwanger/toBeBetterJavaer
在線閱讀地址：https://itwanger.gitee.io/tobebetterjavaer

大家都知道，陣列一旦初始化后大小就無法改變了，所以就有了 ArrayList這種“動態陣列”，可以自動擴容，

HashMap 的底層用的也是陣列，向 HashMap 里不停地添加元素，當陣列無法裝載更多元素時，就需要對陣列進行擴容，以便裝入更多的元素，

當然了，陣列是無法自動擴容的，所以如果要擴容的話，就需要新建一個大的陣列，然后把小陣列的元素復制過去，

HashMap 的擴容是通過 resize 方法來實作的，JDK 8 中融入了紅黑樹，比較復雜，為了便于理解，就還使用 JDK 7 的原始碼，搞清楚了 JDK 7 的，我們后面再詳細說明 JDK 8 和 JDK 7 之間的區別，

resize 方法的原始碼：

// newCapacity為新的容量
void resize(int newCapacity) {
    // 小陣列，臨時過度下
    Entry[] oldTable = table;
    // 擴容前的容量
    int oldCapacity = oldTable.length;
    // MAXIMUM_CAPACITY 為最大容量，2 的 30 次方 = 1<<30
    if (oldCapacity == MAXIMUM_CAPACITY) {
        // 容量調整為 Integer 的最大值 0x7fffffff（十六進制）=2 的 31 次方-1
        threshold = Integer.MAX_VALUE;
        return;
    }

    // 初始化一個新的陣列（大容量）
    Entry[] newTable = new Entry[newCapacity];
    // 把小陣列的元素轉移到大陣列中
    transfer(newTable, initHashSeedAsNeeded(newCapacity));
    // 參考新的大陣列
    table = newTable;
    // 重新計算閾值
    threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}

代碼注釋里出現了左移（<<），這里簡單介紹一下：

a=39
b = a << 2

十進制 39 用 8 位的二進制來表示，就是 00100111，左移兩位后是 10011100（低位用 0 補上），再轉成十進制數就是 156，

移位運算通常可以用來代替乘法運算和除法運算，例如，將 0010011（39）左移兩位就是 10011100（156），剛好變成了原來的 4 倍，

實際上呢，二進制數左移后會變成原來的 2 倍、4 倍、8 倍，

transfer 方法用來轉移，將小陣列的元素拷貝到新的陣列中，

void transfer(Entry[] newTable, boolean rehash) {
    // 新的容量
    int newCapacity = newTable.length;
    // 遍歷小陣列
    for (Entry<K,V> e : table) {
        while(null != e) {
            // 拉鏈法，相同 key 上的不同值
            Entry<K,V> next = e.next;
            // 是否需要重新計算 hash
            if (rehash) {
                e.hash = null == e.key ? 0 : hash(e.key);
            }
            // 根據大陣列的容量，和鍵的 hash 計算元素在陣列中的下標
            int i = indexFor(e.hash, newCapacity);

            // 同一位置上的新元素被放在鏈表的頭部
            e.next = newTable[i];

            // 放在新的陣列上
            newTable[i] = e;

            // 鏈表上的下一個元素
            e = next;
        }
    }
}

e.next = newTable[i]，也就是使用了單鏈表的頭插入方式，同一位置上新元素總會被放在鏈表的頭部位置；這樣先放在一個索引上的元素侄訓被放到鏈表的尾部（如果發生了hash沖突的話），這一點和 JDK 8 有區別，

在舊陣列中同一個鏈表上的元素，通過重新計算索引位置后，有可能被放到了新陣列的不同位置上（仔細看下面的內容，會解釋清楚這一點），

假設 hash 演算法（之前的章節有講到，點擊鏈接再溫故一下）就是簡單的用鍵的哈希值（一個 int 值）和陣列大小取模（也就是 hashCode % table.length），

繼續假設：

陣列 table 的長度為 2
鍵的哈希值為 3、7、5

取模運算后，哈希沖突都到 table[1] 上了，因為余數為 1，那么擴容前的樣子如下圖所示，

小陣列的容量為 2， key 3、7、5 都在 table[1] 的鏈表上，

假設負載因子 loadFactor 為 1，也就是當元素的實際大小大于 table 的實際大小時進行擴容，

擴容后的大陣列的容量為 4，

key 3 取模（3%4）后是 3，放在 table[3] 上，
key 7 取模（7%4）后是 3，放在 table[3] 上的鏈表頭部，
key 5 取模（5%4）后是 1，放在 table[1] 上，

按照我們的預期，擴容后的 7 仍然應該在 3 這條鏈表的后面，但實際上呢？ 7 跑到 3 這條鏈表的頭部了，針對 JDK 7 中的這個情況，JDK 8 做了哪些優化呢？

看下面這張圖，

n 為 table 的長度，默認值為 16，

n-1 也就是二進制的 0000 1111（1X 2 0 2^0 20+1X 2 1 2^1 21+1X 2 2 2^2 22+1X 2 3 2^3 23=1+2+4+8=15）；
key1 哈希值的最后 8 位為 0000 0101
key2 哈希值的最后 8 位為 0001 0101（和 key1 不同）
做與運算后發生了哈希沖突，索引都在（0000 0101）上，

擴容后為 32，

n-1 也就是二進制的 0001 1111（1X 2 0 2^0 20+1X 2 1 2^1 21+1X 2 2 2^2 22+1X 2 3 2^3 23+1X 2 4 2^4 24=1+2+4+8+16=31），擴容前是 0000 1111，
key1 哈希值的低位為 0000 0101
key2 哈希值的低位為 0001 0101（和 key1 不同）
key1 做與運算后，索引為 0000 0101，
key2 做與運算后，索引為 0001 0101，

新的索引就會發生這樣的變化：

原來的索引是 5（0 0101）
原來的容量是 16
擴容后的容量是 32
擴容后的索引是 21（1 0101），也就是 5+16，也就是原來的索引+原來的容量

也就是說，JDK 8 不需要像 JDK 7 那樣重新計算 hash，只需要看原來的hash值新增的那個bit是1還是0就好了，是0的話就表示索引沒變，是1的話，索引就變成了“原索引+原來的容量”，

JDK 8 的這個設計非常巧妙，既省去了重新計算hash的時間，同時，由于新增的1 bit是0還是1是隨機的，因此擴容的程序，可以均勻地把之前的節點分散到新的位置上，

woc，只能說 HashMap 的作者 Doug Lea、Josh Bloch、Arthur van Hoff、Neal Gafter 真的強——的一筆，

JDK 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) {
        // 超過最大值就不再擴充了，就只好隨你碰撞去吧
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 沒超過最大值，就擴充為原來的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    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);
    }
    // 計算新的resize上限
    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) {
                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
                    // 鏈表優化重 hash 的代碼塊
                    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;
                    }
                }
            }
        }
    }
    return newTab;
}

參考鏈接：

https://zhuanlan.zhihu.com/p/21673805

Java 程式員進階之路，風趣幽默、通俗易懂，對 Java 初學者極度友好和舒適😘，內容包括但不限于 Java 語法、Java 集合框架、Java IO、Java 并發編程、Java 虛擬機等核心知識點，

https://github.com/itwanger/toBeBetterJavaer

轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/302829.html

標籤：其他

上一篇：Unity 之紋理型別匯入設定和壓縮格式介紹

下一篇：【游戲開發創新】上班通勤時間太長，做一個任意門，告別地鐵與塞車（Unity | 建模 | ShaderGraph | 搖桿 | 角色控制）