一、概述
在上一篇文章中陕习，我們分析了HashMap中增刪改查的流程，但這是遠(yuǎn)遠(yuǎn)不夠的址愿，所以在本文中该镣，我們將根據(jù)一些常見(jiàn)問(wèn)題并結(jié)合源碼來(lái)進(jìn)行更具體的分析。
二响谓、常見(jiàn)問(wèn)題
- HashMap的數(shù)組長(zhǎng)度為什么必須是2的冪损合？
- HashMap的默認(rèn)負(fù)載因子是多少，作用是什么娘纷？
- HashMap的默認(rèn)負(fù)載因子為什么是0.75嫁审？
- HashMax數(shù)組最大長(zhǎng)度是多少？
- 什么叫做Hash碰撞赖晶？
- HashMap何時(shí)擴(kuò)容律适？
- Jdk 1.8為什么加入了紅黑樹(shù)？
- 什么時(shí)候由鏈表轉(zhuǎn)為紅黑樹(shù)？
三擦耀、問(wèn)題解析
- HashMap的數(shù)組長(zhǎng)度為什么必須是2的冪棉圈？
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
通過(guò)上面的源碼注釋中，就已經(jīng)寫(xiě)明了：必須是 2 的冪眷蜓，這是為什么分瘾？源碼也不是我們寫(xiě)的，我們也不知道吁系，不過(guò)我們根據(jù)數(shù)組的長(zhǎng)度的使用來(lái)進(jìn)行分析德召，在HashMap的putVal方法中，有這樣一段代碼：
n = (tab = resize()).length;
p = tab[i = (n - 1) & hash]
這里的n為數(shù)組的長(zhǎng)度汽纤，p為計(jì)算出來(lái)的下標(biāo)上岗，下標(biāo)通過(guò)(16-1) & hash 進(jìn)行計(jì)算的。就是15&hash蕴坪，我們反向來(lái)思考問(wèn)題肴掷，如果數(shù)組長(zhǎng)度為15呢？我們來(lái)看下圖：
可以看到背传，當(dāng)數(shù)組長(zhǎng)度為15時(shí)呆瞻，通過(guò)&運(yùn)算，最終計(jì)算出來(lái)的下標(biāo)為：0径玖，2痴脾，4，6梳星，8赞赖，10，12冤灾，14前域，且均發(fā)生了哈希碰撞。那這時(shí)候數(shù)組的1 3 5 7 9 11 位置上不就存不上數(shù)據(jù)了嘛韵吨。
接下來(lái)我們?cè)倏串?dāng)數(shù)組長(zhǎng)度為2的冪次方時(shí)的結(jié)果：我們用2的3次方话侄，長(zhǎng)度為8舉例
可以看到，當(dāng)長(zhǎng)度為2的冪時(shí)学赛，最終算出的下標(biāo)是均勻分布的年堆，并沒(méi)有發(fā)生哈希碰撞。
細(xì)心的人可以發(fā)現(xiàn)盏浇，當(dāng)數(shù)組長(zhǎng)度不為2的冪時(shí)变丧，二進(jìn)制的最后一位總是為0，這就導(dǎo)致不管hash為多少绢掰，最終算出來(lái)總是雙數(shù)痒蓬，進(jìn)而導(dǎo)致了數(shù)組分布不均童擎，有些位置永遠(yuǎn)用不到。
所以：數(shù)組長(zhǎng)度為2的冪攻晒，是為了減少哈希碰撞顾复，是數(shù)組分布更均勻。
- HashMap的默認(rèn)負(fù)載因子是多少鲁捏，作用是什么芯砸？
static final float DEFAULT_LOAD_FACTOR = 0.75f;
newCap = DEFAULT_INITIAL_CAPACITY;
float ft = (float)newCap * loadFactor;
默認(rèn)的加載因子為0.75，它與HashMap的擴(kuò)容機(jī)制相關(guān)给梅，當(dāng)數(shù)組長(zhǎng)度大于16*0.75=12時(shí)假丧，數(shù)組就會(huì)擴(kuò)容，并不是到達(dá)16時(shí)才會(huì)擴(kuò)容动羽。它決定了HashMap擴(kuò)容的時(shí)機(jī)包帚。
- HashMap的默認(rèn)負(fù)載因子為什么是0.75？
上面提到了數(shù)組擴(kuò)容是由 長(zhǎng)度加載因子运吓，得到一個(gè)閾值渴邦，當(dāng)長(zhǎng)度達(dá)到這個(gè)閾值時(shí)就會(huì)擴(kuò)容，如果加載因子為1拘哨，那就是161,即數(shù)組長(zhǎng)度達(dá)到16時(shí)才會(huì)擴(kuò)容谋梭，但是這樣會(huì)犧牲時(shí)間效率，如果加載因子0.5時(shí)宅静，那么長(zhǎng)度為8時(shí)就擴(kuò)容了章蚣，此時(shí)就會(huì)導(dǎo)致數(shù)組中空間利用率降低站欺，所以0.75是一個(gè)比較合適的值姨夹。
- HashMax數(shù)組最大長(zhǎng)度是多少？
static final int MAXIMUM_CAPACITY = 1 << 30;
HashMap數(shù)組最大長(zhǎng)度為：2的30次冪矾策，1073741824
- 什么叫做Hash碰撞磷账？
在HashMap中，Hash碰撞就是指計(jì)算出的hash值相同贾虽。
- HashMap何時(shí)擴(kuò)容逃糟？
n = (tab = resize()).length; //629行
if (++size > threshold)
resize(); //663行
在HashMap中，擴(kuò)容由resize()方法完成蓬豁，
在首次調(diào)用put時(shí)绰咽，會(huì)執(zhí)行resize()方法初始化，put之后判斷數(shù)量是否大于閾值地粪，如果大于閾值則擴(kuò)容取募，
后續(xù)調(diào)用會(huì)直接存入數(shù)據(jù)，然后再判斷數(shù)量是否大于閾值蟆技，如果大于閾值則擴(kuò)容玩敏，
當(dāng)數(shù)組長(zhǎng)度大于加載因子*數(shù)組長(zhǎng)度時(shí)斗忌，則會(huì)擴(kuò)容。
- Jdk 1.8為什么加入了紅黑樹(shù)旺聚？
再Jdk1.7中织阳，HashMap是通過(guò)數(shù)組+鏈表實(shí)現(xiàn)的，Jdk1.8中加入了紅黑樹(shù)砰粹，只有當(dāng)數(shù)組中鏈表的長(zhǎng)度大于8時(shí)唧躲，才會(huì)轉(zhuǎn)為紅黑樹(shù)，紅黑樹(shù)相比于鏈表在插入和刪除的操作上伸眶，要比鏈表更快惊窖，如果說(shuō)鏈表長(zhǎng)度為100時(shí)，那么HashMap要循環(huán)99次才能找到最后一個(gè)節(jié)點(diǎn)厘贼，再執(zhí)行插入操作界酒，刪除同理。
- 什么時(shí)候由鏈表轉(zhuǎn)為紅黑樹(shù)嘴秸？
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) 64
resize();
當(dāng)鏈表的長(zhǎng)度大于8時(shí)執(zhí)行樹(shù)化的方法毁欣，隨后如果數(shù)組長(zhǎng)度小于64時(shí)，則會(huì)擴(kuò)容岳掐，反之轉(zhuǎn)換為紅黑樹(shù)凭疮。
所以 當(dāng)鏈表長(zhǎng)度大于8時(shí) 且 數(shù)組長(zhǎng)度小于64時(shí)才會(huì)將鏈表轉(zhuǎn)為紅黑樹(shù)。
