HashMap查漏補缺

HashMap 是面試的釘子戶了，網上分析的文章也有很多，相信大家對于原理已經爛俗于心了。但最近在看源碼時，發現其中一些實作細節其實不太好了解，是以決定以問答的形式在這裡記錄一下，寫的時候盡量把原因說明白，希望對大家有幫助

容量和 size 分别指什麼？

容量并不是指 HashMap 所能存儲的鍵值對數量，而是其内部的 table 數組的大小，而 size 是指目前已存儲的鍵值對的數量。table 是一個 Entry 數組。 table 的每一個節點都連着一個連結清單或者紅黑樹。

初始容量可以随意設定嗎？

可以，但是 HashMap 内部會你設定的 initialCapacity 轉換為大于等于它的最小的2的n次方。比如 20 轉為 32，32 轉為 32等。如果不設定，則為預設值16。需要注意的是，在 Java 8的源碼中，并沒有在構造方法直接建立數組。而是先将處理後的容量值賦給 threshold，在第一次存儲鍵值對時再根據這個值建立數組。

為什麼内部要将容量轉換為 2 的n次方？

這樣可以提高取餘的效率。為了防止連結清單過長，要保證鍵值對在數組中盡可能均勻分布，是以在計算出 key 的 hash 值之後，需要對數組的容量進行取餘，餘數即為鍵值對在 table 中的 index。 對于計算機而言，二進制位運算的效率高于取餘(%)操作。而如果容量是 2 的 n 次方的話，hash 值對其取餘就等同于 hash 值和容量值減1進行按位與(&)操作：

// capacity 為 2 的 n 次方的話，下面兩個操作結果相同
hash & (capacity -1)
等同于
hash % capacity
           

那為什麼兩種操作等同呢？ 我們以2進制的思維想一下，如果一個數是 2 的 n 次方，那它的二進制就是從右往左 n 位都為0，n+1 位為1。比如2的3次方就是 1000。這個數的倍數也滿足從右往左 n 位都為0，取餘的時候抛棄倍數，就等同于将 n+1 位及其往左的所有位歸0，剩下的 n 位就代表餘數。換句話說，一個數對2的 n 次方取餘，就是要取這個數二進制的最低 n 位。 2 的 n 次方減1的結果就是 n 位1，進行與操作後就得到了最低 n 位。

如何将一個值轉換為大于等于它的最小的2的 n 次方？

我們先假設一個二進制數 cap，cap 的二進制有 a 位(不算前面高位的0)，那麼，大于它的最小的2的次方就是2的 a 次方。2 的 a 次方減一的結果就是 n 位1，那我們隻要将 cap 的全部 2 進制位變為1，再加1就能得到結果。而為了防止 cap 本身就是2的 n 次方，我們在計算之前先将 cap 自減。

如何将二進制位都變成1呢？下面是源碼：

static final int tableSizeFor(int cap) {
    int n = cap - 1; //這一步是為了避免 cap 剛好為2的 n 次方
    n |= n >>> 1; //保證前2位是1
    n |= n >>> 2; //保證前4位是1
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
           

下面的描述中 n 的位數都不包括前面補位的0。

|= 這個符号不常見，a |= b 就是 a = a|b 的意思。代碼中先将 n 無符号右移1位，由于n 的第1位肯定是1，移位後第2位是1，

|

操作後前2位就保證是1了。第二步右移了2位再進行

|

操作，保證了前4位是1，後面的計算類似，由于 n 最多有32位，是以一直操作到右移16為止。這樣就将 n 的所有2進制位都變成了1，最後自增傳回。

hash 值是如何計算的

hash 值并沒有直接傳回 hashcode 的傳回值，而是進行了一些處理。 前面提到過，hash 值算出來後需要進行取餘操作，影響取餘結果的是 hash 值的低 n 位。如果低 n 位是固定的或者集中在幾個值，那麼取餘的結果容易相同，導緻 hash 碰撞的發生。由于 hashcode 函數可以被重寫，重寫者可能無意識地就寫了一個壞的 hash 函數，導緻上面這種情況發生。

為了避免這種情況，HashMap 将 hash 值先向右移位，再進行或操作，這樣就使高位的值和低位的值融合成一個新的值，保證取餘結果受每一個二進制位的影響。Java 7和 Java 8的原理都一樣，但源碼有細微出入，可能是 因為 Java 經過統計發現移位一次就夠了吧。

//Java 7
static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}
//Java 8
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
           

擴容後元素如何進行移動

為了防止元素增多後，連結清單越來越長，HashMap 會在元素個數達到門檻值後進行擴容，新的容量為舊容量的2倍。 容量變化後，每個元素用 hash 值取餘的結果也會随之變化，需要在數組中重新排列。以前同一條連結清單上的元素，擴容後可能存在不同的連結清單上。

在 Java 7 中，重新排列實作得簡單粗暴，直接用 hash 根據新容量算出下标，然後設定到新數組中，即相當于将元素重新put 了一次。但在 Java 8中，作者發現沒必要重新插入，因為重新計算後，新的下标隻可能有兩種情況，要麼是原來的值，要麼是原來的值加舊容量。比如容量為16的數組擴容到32，下标為1的元素重新計算後，下标隻可能為1或17。

這個怎麼了解呢？重提一下之前的一句話，一個數對2的 n 次方取餘，就是要取這個數二進制的最低 n 位。當容量為16時，取餘是取最後4位的值，而擴容到32後，取餘變成取最後5位的值。這裡增加的1位如果為0，那麼餘數就沒變，如果為1，那麼餘數就增加了16。如何取增加的這一位的值呢？直接和16進行與操作即可。16的二進制是10000，與操作後如果結果為0，即表示高位為0，否則為1。

根據這個原理，我們隻需要将原來的連結清單分成兩條新鍊放到對應的位置即可，下面是具體步驟：

1. 周遊舊數組，如果元素的 next 為空，直接取餘後放到新數組；
2. 如果元素後面連了一個連結清單，那麼建立兩條連結清單，暫且成為 hi 鍊和 lo 鍊；
3. 周遊連結清單，計算每個元素的 hash 值和舊容量與操作的結果，結果為0則将其放入 lo 鍊末端，不為0放入 hi 鍊末端；
4. 将兩條鍊的 head 放到新數組中，其中 loHead 放到原來的位置，hiHead 放到原來的下标加上舊容量處；
5. 如果是紅黑樹，進行和上面類似的操作，隻是将兩條連結清單換成兩棵樹。

了解原理後看代碼就很簡單了：

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;
            Node<K,V> hiHead = null, hiTail = null;
            Node<K,V> next;
            do {
                next = e.next;
                if ((e.hash & oldCap) == 0) { //結果為0，表示下标沒變，放入 lo 鍊
                    if (loTail == null)
                        loHead = e;
                    else
                        loTail.next = e;
                    loTail = e;
                }
                else { //結果為0，表示下标要加上舊容量，放入 hi 鍊
                    if (hiTail == null)
                        hiHead = e;
                    else
                        hiTail.next = e;
                    hiTail = e;
                }
            } while ((e = next) != null);
            if (loTail != null) { //lo 鍊放在原來的下标處
                loTail.next = null;
                newTab[j] = loHead;
            }
            if (hiTail != null) { //hi 鍊放在原來的下标 加舊容量處
                hiTail.next = null;
                newTab[j + oldCap] = hiHead;
            }
        }
    }
}
           

最後 需要這份HashMap源碼解析進階學習視訊的可以加Android進階群免費擷取；701740775。請備注csdn