基于hashmap 的擴容和樹形化全面分析
一、樹形化
//鏈表轉(zhuǎn)紅黑樹的閾值 static final int TREEIFY_THRESHOLD = 8; //紅黑樹轉(zhuǎn)鏈表的閾值 static final int UNTREEIFY_THRESHOLD = 6; /** *最小樹形化容量閾值：即 當哈希表中的容量 > 該值時，才允許樹形化鏈表 （即 將鏈表 轉(zhuǎn)換成紅黑樹） *否則，若桶內(nèi)元素太多時，則直接擴容，而不是樹形化 *為了避免進行擴容、樹形化選擇的沖突，這個值不能小于 4 * TREEIFY_THRESHOLD **/ static final int MIN_TREEIFY_CAPACITY = 64;
第一個和第二個變量沒有什么問題，關(guān)鍵是第三個：是表示只有在數(shù)組長度大于64的時候，才能樹形化列表嗎？
實際上，這兩個變量是應用于不同場景的。
鏈表長度大于8的時候就會調(diào)用treeifyBin方法轉(zhuǎn)化為紅黑樹，但是在treeifyBin方法內(nèi)部卻有一個判斷，當只有數(shù)組長度大于64的時候，才會進行樹形化，否則就只是resize擴容。
為什么呢？
因為鏈表過長而數(shù)組過短，會經(jīng)常發(fā)生hash碰撞，這個時候樹形化其實是治標不治本，因為引起鏈表過長的根本原因是數(shù)組過短。執(zhí)行樹形化之前，會先檢查數(shù)組長度，如果長度小于 64，則對數(shù)組進行擴容，而不是進行樹形化。
所以發(fā)生擴容的時候是在兩種情況下
超過閾值
鏈表長度超過8，但是數(shù)值長度不足64
二、擴容機制
hashmap內(nèi)部創(chuàng)建過程
構(gòu)造器（只是初始化一下參數(shù)，也就代表著只有添加數(shù)據(jù)的時候才會構(gòu)建數(shù)組和鏈表）—調(diào)用put方法—put方法會調(diào)用resize方法（在數(shù)組為空或者超過閾值的時候，put方法調(diào)用resize方法）
hashmap是如何擴容的
1.hashmap中閾值threshold的設定
剛開始，閾值設定為空
當未聲明的hashmap的大小的時候，閾值設定就是默認大小16*默認負載因子0.75=12
當聲明hashmap的大小的時候，會先調(diào)用一個函數(shù)把閾值設定為剛剛大于設定值的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.數(shù)據(jù)轉(zhuǎn)移
當數(shù)組為null的時候，會創(chuàng)建新的數(shù)組
當數(shù)組不為空，會把容量和閾值均*2，并創(chuàng)建一個容量為之前二倍的數(shù)組，然后把原有數(shù)組的數(shù)據(jù)都轉(zhuǎn)移到新數(shù)組。
假設擴容前的 table 大小為 2 的 N 次方，元素的 table 索引為其 hash 值的后 N 位確定
擴容后的 table 大小即為 2 的 N+1 次方，則其中元素的 table 索引為其 hash 值的后 N+1 位確定，比原來多了一位
轉(zhuǎn)移數(shù)據(jù)不在跟1.7一樣重新計算hash值（計算hash值耗時巨大），只需要看索引中新增的是bit位是1還是0,
若為0則在新數(shù)組中與原來位置一樣，
若為1則在新 原位置+oldCap 即可。
三、容量計算公式
擴容是一個特別耗性能的操作，所以當程序員在使用 HashMap 的時候，估算 map 的大小，初始化的時候給一個大致的數(shù)值，避免 map 進行頻繁的擴容。
HashMap 的容量計算公式 ：size/0.75 +1 。
原理就是保證，閾值（數(shù)組長度*0.75）>實際容量
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
首先是 << 這個操作符必須要理解，在一般情況下 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));
}
輸出結(jié)果為：
1 << 30 = 1073741824
1 << 31 = -2147483648
1 << 32 = 1
1 << 33 = 2
1 << -1 = -2147483648
結(jié)果分析：
- int類型是32位整型，占4個字節(jié)。
- Java的原始類型里沒有無符號類型。 -->所以首位是符號位 正數(shù)為0，負數(shù)為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;
翻譯一下大概就是：如果構(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;
}
在這里我們可以看到其實 hashmap的“最大容量“是Integer.MAX_VALUE;
總結(jié)
MAXIMUM_CAPACITY作為一個2的冪方中最大值，這個值的作用涉及的比較廣。其中有一點比較重要的是在hashmap中容量會確保是 2的k次方，即使你傳入的初始容量不是 2的k次方，tableSizeFor()方法也會將你的容量置為 2的k次方。這時候MAX_VALUE就代表了最大的容量值。
另外還有一點就是threshold，如果對hashmap有一點了解的人都會知道threshold = 初始容量 * 加載因子。也就是擴容的 門檻。相當于實際使用的容量。而擴容都是翻倍的擴容。那么當容量到達MAXIMUM_CAPACITY，這時候再擴容就是 1 << 31 整型溢出。
所以Integer.MAX_VALUE作為最終的容量，但是是一個threshold的身份。以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要介紹了SpringBoot解決跨域請求攔截代碼實例，在微服務開發(fā)中,一個系統(tǒng)包含多個微服務,會存在跨域請求的場景。 本文講解SpringBoot解決跨域請求攔截的問題。,需要的朋友可以參考下2019-06-06
在Java編程中,獲取堆棧信息對于調(diào)試和故障排除非常重要,Java提供了多種方式來獲取當前線程的堆棧信息,下面就跟隨小編一起學習一下常用的三種吧2024-03-03
這篇文章主要介紹了JSONObject與JSONArray的使用 的相關(guān)資料,需要的朋友可以參考下2016-06-06
這篇文章主要介紹了Java多線程編程安全退出線程方法介紹，具有一定參考價值，需要的朋友可以了解下。2017-10-10
這篇文章主要介紹了java中synchronized鎖的升級過程，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09
這篇文章主要介紹了java list 比較詳解及實例的相關(guān)資料,需要的朋友可以參考下2017-05-05
關(guān)于Java中攔截mybatis并輸出完整sql語句的方法
這篇文章主要介紹了關(guān)于Java中攔截mybatis并輸出完整sql語句的方法,假如項目中有很多很多的SQL我們不可能一一的去修改解決。這個時候我們就需要通過mybatis攔截SQL并且最終修改SQL,需要的朋友可以參考下2023-08-08
這篇文章主要介紹了Java語言描述MD5加密工具類實例代碼，具有一定借鑒價值，需要的朋友可以參考下。2017-12-12
這篇文章主要介紹了java數(shù)據(jù)類型與二進制詳細介紹的相關(guān)資料,這里對數(shù)據(jù)類型進行了一一介紹分析，并說明自動轉(zhuǎn)換和強制轉(zhuǎn)換，需要的朋友可以參考下2017-07-07
這篇文章主要給大家介紹了關(guān)于java中static關(guān)鍵詞的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-12-12