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

一、樹形化

//鏈表轉紅黑樹的閾值
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。

推薦閱讀: