基于hashmap擴(kuò)容和樹形化的示例分析

這篇文章將為大家詳細(xì)講解有關(guān)基于hashmap擴(kuò)容和樹形化的示例分析，小編覺得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

一、樹形化

//鏈表轉(zhuǎn)紅黑樹的閾值
static final int TREEIFY_THRESHOLD = 8;
//紅黑樹轉(zhuǎn)鏈表的閾值
static final int UNTREEIFY_THRESHOLD = 6;
/**
*最小樹形化容量閾值：即 當(dāng)哈希表中的容量 > 該值時(shí)，才允許樹形化鏈表 （即 將鏈表 轉(zhuǎn)換成紅黑樹）
*否則，若桶內(nèi)元素太多時(shí)，則直接擴(kuò)容，而不是樹形化
*為了避免進(jìn)行擴(kuò)容、樹形化選擇的沖突，這個(gè)值不能小于 4 * TREEIFY_THRESHOLD
**/
static final int MIN_TREEIFY_CAPACITY = 64;

第一個(gè)和第二個(gè)變量沒有什么問題，關(guān)鍵是第三個(gè)：是表示只有在數(shù)組長度大于64的時(shí)候，才能樹形化列表嗎？

實(shí)際上，這兩個(gè)變量是應(yīng)用于不同場景的。

鏈表長度大于8的時(shí)候就會調(diào)用treeifyBin方法轉(zhuǎn)化為紅黑樹，但是在treeifyBin方法內(nèi)部卻有一個(gè)判斷，當(dāng)只有數(shù)組長度大于64的時(shí)候，才會進(jìn)行樹形化，否則就只是resize擴(kuò)容。

為什么呢？

因?yàn)殒湵磉^長而數(shù)組過短，會經(jīng)常發(fā)生hash碰撞，這個(gè)時(shí)候樹形化其實(shí)是治標(biāo)不治本，因?yàn)橐疰湵磉^長的根本原因是數(shù)組過短。執(zhí)行樹形化之前，會先檢查數(shù)組長度，如果長度小于 64，則對數(shù)組進(jìn)行擴(kuò)容，而不是進(jìn)行樹形化。

所以發(fā)生擴(kuò)容的時(shí)候是在兩種情況下

超過閾值

鏈表長度超過8，但是數(shù)值長度不足64

二、擴(kuò)容機(jī)制

hashmap內(nèi)部創(chuàng)建過程

構(gòu)造器（只是初始化一下參數(shù)，也就代表著只有添加數(shù)據(jù)的時(shí)候才會構(gòu)建數(shù)組和鏈表）—調(diào)用put方法—put方法會調(diào)用resize方法（在數(shù)組為空或者超過閾值的時(shí)候，put方法調(diào)用resize方法）

hashmap是如何擴(kuò)容的

1.hashmap中閾值threshold的設(shè)定

剛開始，閾值設(shè)定為空

當(dāng)未聲明的hashmap的大小的時(shí)候，閾值設(shè)定就是默認(rèn)大小16*默認(rèn)負(fù)載因子0.75=12

當(dāng)聲明hashmap的大小的時(shí)候，會先調(diào)用一個(gè)函數(shù)把閾值設(shè)定為剛剛大于設(shè)定值的2的次方（比如說設(shè)定的大小是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.數(shù)據(jù)轉(zhuǎn)移

當(dāng)數(shù)組為null的時(shí)候，會創(chuàng)建新的數(shù)組

當(dāng)數(shù)組不為空，會把容量和閾值均*2，并創(chuàng)建一個(gè)容量為之前二倍的數(shù)組，然后把原有數(shù)組的數(shù)據(jù)都轉(zhuǎn)移到新數(shù)組。

假設(shè)擴(kuò)容前的 table 大小為 2 的 N 次方，元素的 table 索引為其 hash 值的后 N 位確定

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

轉(zhuǎn)移數(shù)據(jù)不在跟1.7一樣重新計(jì)算hash值（計(jì)算hash值耗時(shí)巨大），只需要看索引中新增的是bit位是1還是0,

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

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

三、容量計(jì)算公式

擴(kuò)容是一個(gè)特別耗性能的操作，所以當(dāng)程序員在使用 HashMap 的時(shí)候，估算 map 的大小，初始化的時(shí)候給一個(gè)大致的數(shù)值，避免 map 進(jìn)行頻繁的擴(kuò)容。

HashMap 的容量計(jì)算公式 ：size/0.75 +1 。

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

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

在閱讀hashmap的源碼過程中，我看到了關(guān)于hashmap最大容量的限制，并產(chǎn)生了一絲疑問。

/**
     * 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

首先是 << 這個(gè)操作符必須要理解，在一般情況下 1 << x 等于 2^x。這是左移操作符，對二進(jìn)制進(jìn)行左移。

來看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));
}

輸出結(jié)果為：

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

結(jié)果分析：

• int類型是32位整型，占4個(gè)字節(jié)。

• Java的原始類型里沒有無符號類型。 -->所以首位是符號位 正數(shù)為0，負(fù)數(shù)為1

• java中存放的是補(bǔ)碼，1左移31位的為 16進(jìn)制的0x80000000代表的是-2147483648–>所以最大只能是30

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

探究完1相信大家對 為什么是30有一點(diǎn)點(diǎn)了解。那為什么是 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;

翻譯一下大概就是：如果構(gòu)造函數(shù)傳入的值大于該數(shù) ，那么替換成該數(shù)。

ok，我們看看構(gòu)造函數(shù)的調(diào)用：

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;

看到這有很有疑問了，如果我要存的數(shù)目大于 MAXIMUM_CAPACITY，你還把我的容量縮小成 MAXIMUM_CAPACITY？？？

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

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

在這里我們可以看到其實(shí) hashmap的“最大容量“是Integer.MAX_VALUE;

總結(jié)

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

另外還有一點(diǎn)就是threshold，如果對hashmap有一點(diǎn)了解的人都會知道threshold = 初始容量 * 加載因子。也就是擴(kuò)容的 門檻。相當(dāng)于實(shí)際使用的容量。而擴(kuò)容都是翻倍的擴(kuò)容。那么當(dāng)容量到達(dá)MAXIMUM_CAPACITY，這時(shí)候再擴(kuò)容就是 1 << 31 整型溢出。

所以Integer.MAX_VALUE作為最終的容量，但是是一個(gè)threshold的身份。

關(guān)于“基于hashmap擴(kuò)容和樹形化的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，使各位可以學(xué)到更多知識，如果覺得文章不錯(cuò)，請把它分享出去讓更多的人看到。