上文講到HashMap的增加方法，現(xiàn)在繼續(xù)

上文鏈接

HashMap在上一篇源碼分析的文章中，如果使用put的時(shí)候如果元素?cái)?shù)量超過(guò)threshold就會(huì)調(diào)用resize進(jìn)行擴(kuò)容

1.擴(kuò)容機(jī)制

想要了解HashMap的擴(kuò)容機(jī)制你要有這兩個(gè)問(wèn)題

• 1.什么時(shí)候才需要擴(kuò)容

• 2.HashMap的擴(kuò)容是什么

在添加元素的時(shí)候如果超過(guò)threshold設(shè)置的閥值點(diǎn)就會(huì)進(jìn)行擴(kuò)容，簡(jiǎn)單的來(lái)說(shuō)就是一個(gè)水壺容量是二升，然后這個(gè)時(shí)候已經(jīng)滿了但是你還要繼續(xù)加水，咋辦？換個(gè)大的。所以HashMap的擴(kuò)容就和你這個(gè)水壺一樣，水已經(jīng)滿了那我就在換個(gè)大的水壺繼續(xù)加水。不過(guò)在你換水壺的時(shí)候是有很多條件的。

在我看這個(gè)resize的源碼的時(shí)候我也是一臉懵逼，最后請(qǐng)教了大佬得到的回答是因?yàn)?.8加入了紅黑樹(shù)比較麻煩可以看一下1.7的，然后我有去網(wǎng)上看了一下別人寫(xiě)的文章基本上都是基于1.7的resize。所以這里就看1.7的resize來(lái)分析。

來(lái)看JDK1.7中resize的實(shí)現(xiàn)。

復(fù)制操作是調(diào)用的transfer方法

在1.7中的resize結(jié)合一下我們的小例子可以這樣理解，去超市買(mǎi)一個(gè)大一點(diǎn)的水壺，然后把以前水壺里面的水給倒進(jìn)新的水壺里面。再把我們當(dāng)前的水壺的容量替換掉，告訴別人我的容量更大了。（強(qiáng)行比喻哈哈哈哈哈）

1.7中的resize就是這么簡(jiǎn)單，那我們?cè)诳匆幌?.8中的resize(),這樣再看就不會(huì)一臉懵逼了

我在這里把1.8的resize方法分為兩部分

• 1.計(jì)算新的newCap(新的容量)和newThr(新閥值點(diǎn))

• 2.復(fù)制新的數(shù)組

第一部分

第二部分

對(duì)比一下1.7

• 1.7元素不需要更換位置。1.8元素的位置要么是在原位置，要么是在原位置再移動(dòng)2次冪的位置

• 不需要像1.7一樣重新計(jì)算hash

2.刪除

刪除的話就是首先先找到元素的位置，如果是鏈表就遍歷鏈表找到元素之后刪除。如果是用紅黑樹(shù)就遍歷樹(shù)然后找到之后做刪除，樹(shù)小于6的時(shí)候要轉(zhuǎn)鏈表。

刪除方法：

調(diào)用removeNode：

3.查找元素

查找方法，通過(guò)元素的Key找到Value。

調(diào)用getNode()方法

看完可以知道邏輯是先通過(guò)Key計(jì)算出索引的位置，然后先檢查第一個(gè)節(jié)點(diǎn)看看是否是我們要的節(jié)點(diǎn)，如果不是在去查看是否死紅黑樹(shù)和鏈表。

4.遍歷

我們通過(guò)下面幾個(gè)例子來(lái)演示一下HashMap怎么遍歷

1.分別遍歷Key和Values

2.迭代

 Iterator<Map.Entry<String, Object>> iterator = map.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<String, Object> mapEntry = iterator.next();
            System.out.println(mapEntry.getKey() + '====' + mapEntry.getValue());
        }

3.獲取 key 集合

4.獲取Entry 集合，遍歷Entry 集合

	Set<Map.Entry<String, Object>> entrySet = map.entrySet();
        for (Map.Entry<String, Object> entry : entrySet) {
            System.out.println(entry.getKey() + '====' + entry.getValue());
        }

對(duì)比來(lái)說(shuō)使用迭代的方式是最好的，也可以在迭代的時(shí)候?qū)系脑剡M(jìn)行刪除

總結(jié)

基于JDK1.8的HashMap是由數(shù)組+鏈表+紅黑樹(shù)組成，當(dāng)鏈表長(zhǎng)度超過(guò) 8 時(shí)會(huì)自動(dòng)轉(zhuǎn)換成紅黑樹(shù)，當(dāng)紅黑樹(shù)節(jié)點(diǎn)個(gè)數(shù)小于 6 時(shí)，又會(huì)轉(zhuǎn)化成鏈表。相對(duì)于早期版本的 JDK HashMap 實(shí)現(xiàn)，新增了紅黑樹(shù)作為底層數(shù)據(jù)結(jié)構(gòu)，在數(shù)據(jù)量較大且哈希碰撞較多時(shí)，能夠極大的增加檢索的效率。HashMap并不是線程安全的，支持K和V為null ,k重復(fù)會(huì)覆蓋，V可以重復(fù)，還有一點(diǎn)HashMap遍歷的數(shù)據(jù)不是有序的是無(wú)序的