基於hashmap 的擴容和樹形化全面分析

Posted on by

一、樹形化

//鏈表轉紅黑樹的閾值
static final int TREEIFY_THRESHOLD = 8;
//紅黑樹轉鏈表的閾值
static final int UNTREEIFY_THRESHOLD = 6;
/**
*最小樹形化容量閾值：即 當哈希表中的容量 > 該值時，才允許樹形化鏈表 （即 將鏈表 轉換成紅黑樹）
*否則，若桶內元素太多時，則直接擴容，而不是樹形化
*為瞭避免進行擴容、樹形化選擇的沖突，這個值不能小於 4 * TREEIFY_THRESHOLD
**/
static final int MIN_TREEIFY_CAPACITY = 64;

第一個和第二個變量沒有什麼問題，關鍵是第三個：是表示隻有在數組長度大於64的時候，才能樹形化列表嗎？

實際上，這兩個變量是應用於不同場景的。

鏈表長度大於8的時候就會調用treeifyBin方法轉化為紅黑樹，但是在treeifyBin方法內部卻有一個判斷，當隻有數組長度大於64的時候，才會進行樹形化，否則就隻是resize擴容。

為什麼呢？

因為鏈表過長而數組過短，會經常發生hash碰撞，這個時候樹形化其實是治標不治本，因為引起鏈表過長的根本原因是數組過短。執行樹形化之前，會先檢查數組長度，如果長度小於 64，則對數組進行擴容，而不是進行樹形化。

所以發生擴容的時候是在兩種情況下

超過閾值

鏈表長度超過8，但是數值長度不足64

二、擴容機制

hashmap內部創建過程

構造器（隻是初始化一下參數，也就代表著隻有添加數據的時候才會構建數組和鏈表）—調用put方法—put方法會調用resize方法（在數組為空或者超過閾值的時候，put方法調用resize方法）

hashmap是如何擴容的

1.hashmap中閾值threshold的設定

剛開始，閾值設定為空

當未聲明的hashmap的大小的時候，閾值設定就是默認大小16*默認負載因子0.75=12

當聲明hashmap的大小的時候，會先調用一個函數把閾值設定為剛剛大於設定值的2的次方（比如說設定的大小是1000，那閾值就是1024），然後在resize方法中，先把閾值賦給容量大小，然後在把容量大小*0.75在賦值給閾值。

代碼如下：

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;
            }
            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);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;

2.數據轉移

當數組為null的時候，會創建新的數組

當數組不為空，會把容量和閾值均*2，並創建一個容量為之前二倍的數組，然後把原有數組的數據都轉移到新數組。

假設擴容前的 table 大小為 2 的 N 次方，元素的 table 索引為其 hash 值的後 N 位確定

擴容後的 table 大小即為 2 的 N+1 次方，則其中元素的 table 索引為其 hash 值的後 N+1 位確定，比原來多瞭一位

轉移數據不在跟1.7一樣重新計算hash值（計算hash值耗時巨大），隻需要看索引中新增的是bit位是1還是0,

若為0則在新數組中與原來位置一樣，

若為1則在新 原位置+oldCap 即可。

三、容量計算公式

擴容是一個特別耗性能的操作，所以當程序員在使用 HashMap 的時候，估算 map 的大小，初始化的時候給一個大致的數值，避免 map 進行頻繁的擴容。

HashMap 的容量計算公式 ：size/0.75 +1 。

原理就是保證，閾值（數組長度*0.75）>實際容量

HashMap的最大容量為什麼是2的30次方(1左移30)?

在閱讀hashmap的源碼過程中，我看到瞭關於hashmap最大容量的限制，並產生瞭一絲疑問。

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

為啥最大容量是 1 << 30?

探究過程1 – 為什麼是30

首先是 << 這個操作符必須要理解，在一般情況下 1 << x 等於 2^x。這是左移操作符，對二進制進行左移。

來看1 << 30。它代表將1左移30位，也就是0010…0

來看這樣一段代碼：

public static void main(String[] args){
        for (int i = 30; i <= 33; i++) {
            System.out.println("1 << "+ i +" = "+(1 << i));
        }
        System.out.println("1 << -1 = " + (1 << -1));
}

輸出結果為：

1 << 30 = 1073741824
1 << 31 = -2147483648
1 << 32 = 1
1 << 33 = 2
1 << -1 = -2147483648

結果分析：

  • int類型是32位整型，占4個字節。
  • Java的原始類型裡沒有無符號類型。 –>所以首位是符號位 正數為0，負數為1
  • java中存放的是補碼，1左移31位的為 16進制的0x80000000代表的是-2147483648–>所以最大隻能是30

探究過程2 – 為什麼是 1 << 30

探究完1相信大傢對 為什麼是30有一點點瞭解。那為什麼是 1 << 30，而不是0x7fffffff即Integer.MAX_VALUE

我們首先看代碼的註釋

 /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

翻譯一下大概就是：如果構造函數傳入的值大於該數 ，那麼替換成該數。

ok，我們看看構造函數的調用：

public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

其中這一句：

if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;

看到這有很有疑問瞭，如果我要存的數目大於 MAXIMUM_CAPACITY，你還把我的容量縮小成 MAXIMUM_CAPACITY？？？

別急繼續看：在resize()方法中有一句：

if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
}

在這裡我們可以看到其實 hashmap的“最大容量“是Integer.MAX_VALUE;

總結

MAXIMUM_CAPACITY作為一個2的冪方中最大值，這個值的作用涉及的比較廣。其中有一點比較重要的是在hashmap中容量會確保是 2的k次方，即使你傳入的初始容量不是 2的k次方，tableSizeFor()方法也會將你的容量置為 2的k次方。這時候MAX_VALUE就代表瞭最大的容量值。

另外還有一點就是threshold，如果對hashmap有一點瞭解的人都會知道threshold = 初始容量 * 加載因子。也就是擴容的 門檻。相當於實際使用的容量。而擴容都是翻倍的擴容。那麼當容量到達MAXIMUM_CAPACITY，這時候再擴容就是 1 << 31 整型溢出。

所以Integer.MAX_VALUE作為最終的容量，但是是一個threshold的身份。以上為個人經驗，希望能給大傢一個參考，也希望大傢多多支持WalkonNet。

推薦閱讀：