HashMap 源碼分析

前幾篇分析了?ArrayList?，?LinkedList?，Vector?，Stack??List 集合的源碼，Java 容器除了包含 List 集合外還包含著 Set 和 Map 兩個(gè)重要的集合類(lèi)型。而?HashMap?則是最具有代表性的，也是我們最常使用到的 Map 集合。我們這篇文章就來(lái)試著分析下?HashMap?的源碼，由于?HashMap?底層涉及到太多方面，一篇文章總是不能面面俱到，所以我們可以帶著面試官常問(wèn)的幾個(gè)問(wèn)題去看源碼：

成都創(chuàng)新互聯(lián)專(zhuān)注為客戶(hù)提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都做網(wǎng)站、成都網(wǎng)站建設(shè)、霸州網(wǎng)絡(luò)推廣、重慶小程序開(kāi)發(fā)公司、霸州網(wǎng)絡(luò)營(yíng)銷(xiāo)、霸州企業(yè)策劃、霸州品牌公關(guān)、搜索引擎seo、人物專(zhuān)訪、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等，從售前售中售后，我們都將竭誠(chéng)為您服務(wù)，您的肯定，是我們最大的嘉獎(jiǎng)；成都創(chuàng)新互聯(lián)為所有大學(xué)生創(chuàng)業(yè)者提供霸州建站搭建服務(wù)，24小時(shí)服務(wù)熱線：13518219792，官方網(wǎng)址：chinadenli.net

1. 了解底層如何存儲(chǔ)數(shù)據(jù)的

2. HashMap 的幾個(gè)主要方法

3. HashMap 是如何確定元素存儲(chǔ)位置的以及如何處理哈希沖突的

4. HashMap 擴(kuò)容機(jī)制是怎樣的

5. JDK 1.8 在擴(kuò)容和解決哈希沖突上對(duì) HashMap 源碼做了哪些改動(dòng)？有什么好處?

本文也將從以上幾個(gè)方面來(lái)展開(kāi)敘述：

由于掘金后臺(tái)審核可能會(huì)由于某些原因造成文章發(fā)布延遲或者遺漏，如果感覺(jué)我寫(xiě)的源碼分析文章還不錯(cuò)，可以關(guān)注我，以后我每次更新文章就可以收到推送了。另外博主也是在努力進(jìn)步中，所有文章如果有問(wèn)題請(qǐng)盡管留言給我。我會(huì)及時(shí)改正。大家一起進(jìn)步。

概述

為了方便下邊的敘述這里需要先對(duì)幾個(gè)常見(jiàn)的關(guān)于?HashMap?的知識(shí)點(diǎn)進(jìn)行下概述：

1. HashMap?存儲(chǔ)數(shù)據(jù)是根據(jù)鍵值對(duì)存儲(chǔ)數(shù)據(jù)的，并且存儲(chǔ)多個(gè)數(shù)據(jù)時(shí)，數(shù)據(jù)的鍵不能相同，如果相同該鍵之前對(duì)應(yīng)的值將被覆蓋。注意如果想要保證?HashMap?能夠正確的存儲(chǔ)數(shù)據(jù)，請(qǐng)確保作為鍵的類(lèi)，已經(jīng)正確覆寫(xiě)了?equals()?方法。

2. HashMap?存儲(chǔ)數(shù)據(jù)的位置與添加數(shù)據(jù)的鍵的?hashCode()?返回值有關(guān)。所以在將元素使用 HashMap 存儲(chǔ)的時(shí)候請(qǐng)確保你已經(jīng)按照要求重寫(xiě)了?hashCode(）方法。這里說(shuō)有關(guān)系代表最終的存儲(chǔ)位置不一定就是?hashCode?的返回值。

3. HashMap?最多只允許一條存儲(chǔ)數(shù)據(jù)的鍵為 null，可允許多條數(shù)據(jù)的值為 null。

4. HashMap?存儲(chǔ)數(shù)據(jù)的順序是不確定的，并且可能會(huì)因?yàn)閿U(kuò)容導(dǎo)致元素存儲(chǔ)位置改變。因此遍歷順序是不確定的。

5. HashMap?是線程不安全的，如果需要再多線程的情況下使用可以用?Collections.synchronizedMap(Map map)?方法使?HashMap?具有線程安全的能力，或者使用?ConcurrentHashMap。

了解 HashMap 底層如何存儲(chǔ)數(shù)據(jù)的

要想分析 HashMap 源碼，就必須在 JDK1.8 和 JDK1.7之間劃分一條線，因?yàn)樵?JDK 1.8 后對(duì)于 HashMap 做了底層實(shí)現(xiàn)的改動(dòng)。

JDK 1.7 之前的存儲(chǔ)結(jié)構(gòu)

我們了解到及時(shí) hashCode() 方法已經(jīng)寫(xiě)得很完美了，終究還是有可能導(dǎo)致 「hash碰撞」的，HashMap?作為使用 hash 值來(lái)決定元素存儲(chǔ)位置的集合也是需要處理 hash 沖突的。在1.7之前JDK采用「拉鏈法」來(lái)存儲(chǔ)數(shù)據(jù)，即數(shù)組和鏈表結(jié)合的方式：

cdn.xitu.io/2018/4/7/1629e3892dcbf24d?imageView2/0/w/1280/h/960/format/webp/ignore-error/1">

「拉鏈法」用專(zhuān)業(yè)點(diǎn)的名詞來(lái)說(shuō)叫做鏈地址法。簡(jiǎn)單來(lái)說(shuō)，就是數(shù)組加鏈表的結(jié)合。在每個(gè)數(shù)組元素上存儲(chǔ)的都是一個(gè)鏈表。

我們之前說(shuō)到不同的 key 可能經(jīng)過(guò) hash 運(yùn)算可能會(huì)得到相同的地址，但是一個(gè)數(shù)組單位上只能存放一個(gè)元素，采用鏈地址法以后，如果遇到相同的 hash 值的 key 的時(shí)候，我們可以將它放到作為數(shù)組元素的鏈表上。待我們?nèi)ト≡氐臅r(shí)候通過(guò) hash 運(yùn)算的結(jié)果找到這個(gè)鏈表，再在鏈表中找到與 key 相同的節(jié)點(diǎn)，就能找到 key 相應(yīng)的值了。

JDK1.7中新添加進(jìn)來(lái)的元素總是放在數(shù)組相應(yīng)的角標(biāo)位置，而原來(lái)處于該角標(biāo)的位置的節(jié)點(diǎn)作為 next 節(jié)點(diǎn)放到新節(jié)點(diǎn)的后邊。稍后通過(guò)源碼分析我們也能看到這一點(diǎn)。

JDK1.8中的存儲(chǔ)結(jié)構(gòu)。

對(duì)于 JDK1.8 之后的HashMap底層在解決哈希沖突的時(shí)候，就不單單是使用數(shù)組加上單鏈表的組合了，因?yàn)楫?dāng)處理如果 hash 值沖突較多的情況下，鏈表的長(zhǎng)度就會(huì)越來(lái)越長(zhǎng)，此時(shí)通過(guò)單鏈表來(lái)尋找對(duì)應(yīng) Key 對(duì)應(yīng)的 Value 的時(shí)候就會(huì)使得時(shí)間復(fù)雜度達(dá)到 O(n),因此在 JDK1.8 之后，在鏈表新增節(jié)點(diǎn)導(dǎo)致鏈表長(zhǎng)度超過(guò)?TREEIFY_THRESHOLD = 8?的時(shí)候，就會(huì)在添加元素的同時(shí)將原來(lái)的單鏈表轉(zhuǎn)化為紅黑樹(shù)。

對(duì)數(shù)據(jù)結(jié)構(gòu)很在行的讀者應(yīng)該，知道紅黑樹(shù)是一種易于增刪改查的二叉樹(shù)，他對(duì)與數(shù)據(jù)的查詢(xún)的時(shí)間復(fù)雜度是?O(logn)?級(jí)別，所以利用紅黑樹(shù)的特點(diǎn)就可以更高效的對(duì)?HashMap?中的元素進(jìn)行操作。

JDK1.8 對(duì)于HashMap 底層存儲(chǔ)結(jié)構(gòu)優(yōu)化在于：當(dāng)鏈表新增節(jié)點(diǎn)導(dǎo)致鏈表長(zhǎng)度超過(guò)8的時(shí)候，就會(huì)將原有的鏈表轉(zhuǎn)為紅黑樹(shù)來(lái)存儲(chǔ)數(shù)據(jù)。

關(guān)于 HashMap 源碼中提到的幾個(gè)重要概念

關(guān)于 HashMap 源碼中分析的文章一般都會(huì)提及幾個(gè)重要的概念：

重要參數(shù)

1. 哈希桶（buckets）：在 HashMap 的注釋里使用哈希桶來(lái)形象的表示數(shù)組中每個(gè)地址位置。注意這里并不是數(shù)組本身，數(shù)組是裝哈希桶的，他可以被稱(chēng)為哈希表。

2. 初始容量(initial capacity)?: 這個(gè)很容易理解，就是哈希表中哈希桶初始的數(shù)量。如果我們沒(méi)有通過(guò)構(gòu)造方法修改這個(gè)容量值默認(rèn)為DEFAULT_INITIAL_CAPACITY = 1<<4?即16。值得注意的是為了保證 HashMap 添加和查找的高效性，HashMap?的容量總是 ?2^n 的形式。

3. 加載因子(load factor)：加載因子是哈希表（散列表）在其容量自動(dòng)增加之前被允許獲得的最大數(shù)量的度量。當(dāng)哈希表中的條目數(shù)量超過(guò)負(fù)載因子和當(dāng)前容量的乘積時(shí)，散列表就會(huì)被重新映射（即重建內(nèi)部數(shù)據(jù)結(jié)構(gòu)），重新創(chuàng)建的散列表容量大約是之前散列表哈系統(tǒng)桶數(shù)量的兩倍。默認(rèn)加載因子（0.75）在時(shí)間和空間成本之間提供了良好的折衷。加載因子過(guò)大會(huì)導(dǎo)致很容易鏈表過(guò)長(zhǎng)，加載因子很小又容易導(dǎo)致頻繁的擴(kuò)容。所以不要輕易試著去改變這個(gè)默認(rèn)值。

4. 擴(kuò)容閾值（threshold）：其實(shí)在說(shuō)加載因子的時(shí)候已經(jīng)提到了擴(kuò)容閾值了，擴(kuò)容閾值 = 哈希表容量 * 加載因子。哈希表的鍵值對(duì)總數(shù) = 所有哈希桶中所有鏈表節(jié)點(diǎn)數(shù)的加和，擴(kuò)容閾值比較的是是鍵值對(duì)的個(gè)數(shù)而不是哈希表的數(shù)組中有多少個(gè)位置被占了。

5. 樹(shù)化閥值(TREEIFY_THRESHOLD)?：這個(gè)參數(shù)概念是在 JDK1.8后加入的，它的含義代表一個(gè)哈希桶中的節(jié)點(diǎn)個(gè)數(shù)大于該值（默認(rèn)為8）的時(shí)候?qū)?huì)被轉(zhuǎn)為紅黑樹(shù)行存儲(chǔ)結(jié)構(gòu)。

6. 非樹(shù)化閥值(UNTREEIFY_THRESHOLD)： 與樹(shù)化閾值相對(duì)應(yīng)，表示當(dāng)一個(gè)已經(jīng)轉(zhuǎn)化為數(shù)形存儲(chǔ)結(jié)構(gòu)的哈希桶中節(jié)點(diǎn)數(shù)量小于該值（默認(rèn)為 6）的時(shí)候?qū)⒃俅胃臑閱捂湵淼母袷酱鎯?chǔ)。導(dǎo)致這種操作的原因可能有刪除節(jié)點(diǎn)或者擴(kuò)容。

7. 最小樹(shù)化容量(MIN_TREEIFY_CAPACITY): 經(jīng)過(guò)上邊的介紹我們只知道，當(dāng)鏈表的節(jié)點(diǎn)數(shù)超過(guò)8的時(shí)候就會(huì)轉(zhuǎn)化為樹(shù)化存儲(chǔ)，其實(shí)對(duì)于轉(zhuǎn)化還有一個(gè)要求就是哈希表的數(shù)量超過(guò)最小樹(shù)化容量的要求（默認(rèn)要求是 64）,且為了避免進(jìn)行擴(kuò)容、樹(shù)形化選擇的沖突，這個(gè)值不能小于 4 * TREEIFY_THRESHOLD);在達(dá)到該有求之前優(yōu)先選擇擴(kuò)容。擴(kuò)容因?yàn)橐驗(yàn)槿萘康淖兓赡軙?huì)使單鏈表的長(zhǎng)度改變。

與這個(gè)幾個(gè)概念對(duì)應(yīng)的在 ?HashMap 中幾個(gè)常亮量，由于上邊的介紹比較詳細(xì)了，下邊僅列出幾個(gè)變量的聲明：

/*默認(rèn)初始容量*/?static?final?int?DEFAULT_INITIAL_CAPACITY?=?1?<<?4;?//?aka?16?/*最大存儲(chǔ)容量*/?static?final?int?MAXIMUM_CAPACITY?=?1?<<?30;?/*默認(rèn)加載因子*/?static?final?float?DEFAULT_LOAD_FACTOR?=?0.75f;?/*默認(rèn)樹(shù)化閾值*/?static?final?int?TREEIFY_THRESHOLD?=?8;?/*默認(rèn)非樹(shù)化閾值*/?static?final?int?UNTREEIFY_THRESHOLD?=?6;?/*默認(rèn)最小樹(shù)化容量*/?static?final?int?MIN_TREEIFY_CAPACITY?=?64;?復(fù)制代碼

對(duì)應(yīng)的還有幾個(gè)全局變量：

//?擴(kuò)容閾值?=?容量?x?加載因子?int?threshold;?//存儲(chǔ)哈希桶的數(shù)組，哈希桶中裝的是一個(gè)單鏈表或一顆紅黑樹(shù)，長(zhǎng)度一定是?2^n?transient?Node<K,V>[]?table;??????//?HashMap中存儲(chǔ)的鍵值對(duì)的數(shù)量注意這里是鍵值對(duì)的個(gè)數(shù)而不是數(shù)組的長(zhǎng)度?transient?int?size;????//所有鍵值對(duì)的Set集合?區(qū)分于?table?可以調(diào)用?entrySet(）得到該集合?transient?Set<Map.Entry<K,V>>?entrySet;????//操作數(shù)記錄?為了多線程操作時(shí)?Fast-fail?機(jī)制?transient?int?modCount;?復(fù)制代碼

基本存儲(chǔ)單元

HashMap 在 JDK 1.7 中只有?Entry?一種存儲(chǔ)單元，而在 JDK1.8 中由于有了紅黑樹(shù)的存在，就多了一種存儲(chǔ)單元，而?Entry?也隨之應(yīng)景的改為名為 Node。我們先來(lái)看下單鏈表節(jié)點(diǎn)的表示方法 ：

/**??*?內(nèi)部類(lèi)?Node?實(shí)現(xiàn)基類(lèi)的內(nèi)部接口?Map.Entry<K,V>??*???*/?static?class?Node<K,V>?implements?Map.Entry<K,V>?{????//此值是在數(shù)組索引位置????final?int?hash;????//節(jié)點(diǎn)的鍵????final?K?key;????//節(jié)點(diǎn)的值????V?value;????//單鏈表中下一個(gè)節(jié)點(diǎn)????Node<K,V>?next;?????????Node(int?hash,?K?key,?V?value,?Node<K,V>?next)?{????????this.hash?=?hash;????????this.key?=?key;????????this.value?=?value;????????this.next?=?next;????}????public?final?K?getKey()????????{?return?key;?}????public?final?V?getValue()??????{?return?value;?}????public?final?String?toString()?{?return?key?+?"="?+?value;?}?????//節(jié)點(diǎn)的?hashCode?值通過(guò)?key?的哈希值和?value?的哈希值異或得到，沒(méi)發(fā)現(xiàn)在源碼中中有用到。????public?final?int?hashCode()?{????????return?Objects.hashCode(key)?^?Objects.hashCode(value);????}????//更新相同?key?對(duì)應(yīng)的?Value?值????public?final?V?setValue(V?newValue)?{????????V?oldValue?=?value;????????value?=?newValue;????????return?oldValue;????}??//equals?方法，鍵值同時(shí)相同才節(jié)點(diǎn)才相同????public?final?boolean?equals(Object?o)?{????????if?(o?==?this)????????????return?true;????????if?(o?instanceof?Map.Entry)?{????????????Map.Entry<?,?>?e?=?(Map.Entry<?,?>)o;????????????if?(Objects.equals(key,?e.getKey())?&&????????????????Objects.equals(value,?e.getValue()))????????????????return?true;????????}????????return?false;????}?}?復(fù)制代碼

對(duì)于JDK1.8 新增的紅黑樹(shù)節(jié)點(diǎn)

static?final?class?TreeNode<K,V>?extends?LinkedHashMap.Entry<K,V>?{????TreeNode<K,V>?parent;??//?red-black?tree?links????TreeNode<K,V>?left;????TreeNode<K,V>?right;????TreeNode<K,V>?prev;????//?needed?to?unlink?next?upon?deletion????boolean?red;????TreeNode(int?hash,?K?key,?V?val,?Node<K,V>?next)?{????????super(hash,?key,?val,?next);????}????·········?}?復(fù)制代碼

HashMap 構(gòu)造方法

HashMap?構(gòu)造方法一共有三個(gè)：

• 可以指定期望初始容量和加載因子的構(gòu)造函數(shù)，有了這兩個(gè)值，我們就可以算出上邊說(shuō)到的?threshold?加載因子。其中加載因子不可以小于0，并沒(méi)有規(guī)定不可以大于 1，但是不能等于無(wú)窮.

大家可能疑惑?Float.isNaN()?其實(shí) ?NaN 就是 not a number 的縮寫(xiě)，我們知道在運(yùn)算 1/0 的時(shí)候回拋出異常，但是如果我們的除數(shù)指定為浮點(diǎn)數(shù) 1/0.0f 的時(shí)候就不會(huì)拋出異常了。計(jì)算器運(yùn)算出的結(jié)果可以當(dāng)做一個(gè)極值也就是無(wú)窮大，無(wú)窮大不是個(gè)數(shù)所以 1/0.0f 返回結(jié)果是 Infinity 無(wú)窮,使用 Float.isNaN(）判斷將會(huì)返回 true。

?public?HashMap(int?initialCapacity,?float?loadFactor)?{?????//?指定期望初始容量小于0將會(huì)拋出非法參數(shù)異常????if?(initialCapacity?<?0)????????throw?new?IllegalArgumentException("Illegal?initial?capacity:?"?+???????????????????????????????????????????initialCapacity);????//?期望初始容量不可以大于最大值?2^30??實(shí)際上我們也不會(huì)用到這么大的容量??????????????????????????????????????????if?(initialCapacity?>?MAXIMUM_CAPACITY)????????initialCapacity?=?MAXIMUM_CAPACITY;???//?加載因子必須大于0?不能為無(wú)窮大???????if?(loadFactor?<=?0?||?Float.isNaN(loadFactor))????????throw?new?IllegalArgumentException("Illegal?load?factor:?"?+???????????????????????????????????????????loadFactor);????this.loadFactor?=?loadFactor;//初始化全局加載因子變量????this.threshold?=?tableSizeFor(initialCapacity);//根據(jù)初始容量計(jì)算計(jì)算擴(kuò)容閾值?}?復(fù)制代碼

咦？不是說(shuō)好擴(kuò)容閾值 = 哈希表容量 * 加載因子么？為什么還要用到下邊這個(gè)方法呢？我們之前說(shuō)了參數(shù)?initialCapacity?只是期望容量，不知道大家發(fā)現(xiàn)沒(méi)我們這個(gè)構(gòu)造函數(shù)并沒(méi)有初始化?Node<K,V>[] table?，事實(shí)上真正指定哈希表容量總是在第一次添加元素的時(shí)候，這點(diǎn)和 ArrayList 的機(jī)制有所不同。等我們說(shuō)到擴(kuò)容機(jī)制的時(shí)候我們就可以看到相關(guān)代碼了。

//根據(jù)期望容量返回一個(gè)?>=?cap?的擴(kuò)容閾值，并且這個(gè)閾值一定是?2^n??static?final?int?tableSizeFor(int?cap)?{????int?n?=?cap?-?1;????n?|=?n?>>>?1;????n?|=?n?>>>?2;????n?|=?n?>>>?4;????n?|=?n?>>>?8;????n?|=?n?>>>?16;????//經(jīng)過(guò)上述面的?或和位移?運(yùn)算，?n?最終各位都是1?????//最終結(jié)果?+1?也就保證了返回的肯定是?2^n?????return?(n?<?0)???1?:?(n?>=?MAXIMUM_CAPACITY)???MAXIMUM_CAPACITY?:?n?+?1;?}?復(fù)制代碼

• 只指定初始容量的構(gòu)造函數(shù)

這個(gè)就比較簡(jiǎn)單了，將指定的期望初容量和默認(rèn)加載因子傳遞給兩個(gè)參數(shù)構(gòu)造方法。這里就不在贅述。

public?HashMap(int?initialCapacity)?{????this(initialCapacity,?DEFAULT_LOAD_FACTOR);?}?復(fù)制代碼

• 無(wú)參數(shù)構(gòu)造函數(shù)

這也是我們最常用的一個(gè)構(gòu)造函數(shù)，該方法初始化了加載因子為默認(rèn)值，并沒(méi)有調(diào)動(dòng)其他的構(gòu)造方法，跟我們之前說(shuō)的一樣，哈希表的大小以及其他參數(shù)都會(huì)在第一調(diào)用擴(kuò)容函數(shù)的初始化為默認(rèn)值。

public?HashMap()?{????this.loadFactor?=?DEFAULT_LOAD_FACTOR;?//?all?other?fields?defaulted?}?復(fù)制代碼

• 傳入一個(gè) Map 集合的構(gòu)造參數(shù)

該方法解釋起來(lái)就比較麻煩了，因?yàn)樗诔跏蓟臅r(shí)候就涉及了添加元素，擴(kuò)容這兩大重要的方法。這里先把它掛起來(lái)，緊接著我們講完了擴(kuò)容機(jī)制再回來(lái)看就好了。

public?HashMap(Map<??extends?K,???extends?V>?m)?{????this.loadFactor?=?DEFAULT_LOAD_FACTOR;????putMapEntries(m,?false);?}?復(fù)制代碼

HashMap 如何確定添加元素的位置

在分析?HashMap?添加元素的方法之前，我們需要先來(lái)了解下，如何確定元素在?HashMap?中的位置的。我們知道?HashMap?底層是哈希表，哈希表依靠 hash 值去確定元素存儲(chǔ)位置。HashMap?在 JDK 1.7 和 JDK1.8中采用的 hash 方法并不是完全相同。我們現(xiàn)在看下

JDK 1.7 中 hash 方法的實(shí)現(xiàn)：

這里提出一個(gè)概念擾動(dòng)函數(shù)，我們知道Map 文中存放鍵值對(duì)的位置有鍵的 hash 值決定，但是鍵的 hashCode 函數(shù)返回值不一定滿(mǎn)足，哈希表長(zhǎng)度的要求，所以在存儲(chǔ)元素之前需要對(duì) key 的 hash 值進(jìn)行一步擾動(dòng)處理。下面我們JDK1.7 中的擾動(dòng)函數(shù)：

//4次位運(yùn)算?+?5次異或運(yùn)算??//這種算法可以防止低位不變，高位變化時(shí)，造成的?hash?沖突?static?final?int?hash(Object?k)?{????int?h?=?0;????h?^=?k.hashCode();?????h?^=?(h?>>>?20)?^?(h?>>>?12);????return?h?^?(h?>>>?7)?^?(h?>>>?4);?}?復(fù)制代碼

JDK1.8 中 hash 函數(shù)的實(shí)現(xiàn)

JDK1.8中再次優(yōu)化了這個(gè)哈希函數(shù)，把 key 的 hashCode 方法返回值右移16位，即丟棄低16位，高16位全為0 ，然后在于 hashCode 返回值做異或運(yùn)算，即高 16 位與低 16 位進(jìn)行異或運(yùn)算，這么做可以在數(shù)組 table 的 length 比較小的時(shí)候，也能保證考慮到高低Bit都參與到 hash 的計(jì)算中，同時(shí)不會(huì)有太大的開(kāi)銷(xiāo)，擾動(dòng)處理次數(shù)也從 4次位運(yùn)算 + 5次異或運(yùn)算 降低到 1次位運(yùn)算 + 1次異或運(yùn)算

static?final?int?hash(Object?key)?{?????int?h;?????return?(key?==?null)???0?:?(h?=?key.hashCode())?^?(h?>>>?16);?}?復(fù)制代碼

進(jìn)過(guò)上述的擾動(dòng)函數(shù)只是得到了合適的 hash 值，但是還沒(méi)有確定在 Node[] 數(shù)組中的角標(biāo)，在 JDK1.7中存在一個(gè)函數(shù)，JDK1.8中雖然沒(méi)有但是只是把這步運(yùn)算放到了 put 函數(shù)中。我們就看下這個(gè)函數(shù)實(shí)現(xiàn)：

static?int?indexFor(int?h,?int?length)?{??????return?h?&?(length-1);??//?取模運(yùn)算?}?復(fù)制代碼

為了讓 hash 值能夠?qū)?yīng)到現(xiàn)有數(shù)組中的位置，我們上篇文章講到一個(gè)方法為 取模運(yùn)算，即?hash % length，得到結(jié)果作為角標(biāo)位置。但是 HashMap 就厲害了，連這一步取模運(yùn)算的都優(yōu)化了。我們需要知道一個(gè)計(jì)算機(jī)對(duì)于2進(jìn)制的運(yùn)算是要快于10進(jìn)制的，取模算是10進(jìn)制的運(yùn)算了，而位與運(yùn)算就要更高效一些了。

我們知道?HashMap?底層數(shù)組的長(zhǎng)度總是 2^n ,轉(zhuǎn)為二進(jìn)制總是 1000 即1后邊多個(gè)0的情況。此時(shí)一個(gè)數(shù)與 2^n 取模，等價(jià)于 一個(gè)數(shù)與 2^n - 1做位與運(yùn)算。而 JDK ?中就使用h & (length-1)?運(yùn)算替代了對(duì) length取模。我們根據(jù)圖片來(lái)看一個(gè)具體的例子：

小結(jié)

通過(guò)上邊的分析我們可以到如下結(jié)論：

• 在存儲(chǔ)元素之前，HashMap 會(huì)對(duì) key 的 hashCode 返回值做進(jìn)一步擾動(dòng)函數(shù)處理，1.7 中擾動(dòng)函數(shù)使用了 4次位運(yùn)算 + 5次異或運(yùn)算，1.8 中降低到 1次位運(yùn)算 + 1次異或運(yùn)算

• 擾動(dòng)處理后的 hash 與 哈希表數(shù)組length -1 做位與運(yùn)算得到最終元素儲(chǔ)存的哈希桶角標(biāo)位置。

HashMap 的添加元素

敲黑板了，重點(diǎn)來(lái)了。對(duì)于理解 HashMap 源碼一方面要了解存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)，另一方面也要了解具體是如何添加元素的。下面我們就來(lái)看下?put(K key, V value)?函數(shù)。

//?可以看到具體的添加行為在?putVal?方法中進(jìn)行?public?V?put(K?key,?V?value)?{????return?putVal(hash(key),?key,?value,?false,?true);?}?復(fù)制代碼

對(duì)于 putVal 前三個(gè)參數(shù)很好理解，第4個(gè)參數(shù) onlyIfAbsent 表示只有當(dāng)對(duì)應(yīng) key 的位置為空的時(shí)候替換元素，一般傳 false，在 JDK1.8中新增方法?public V putIfAbsent(K key, V value)?傳 true，第 5 個(gè)參數(shù) evict 如果是 false。那么表示是在初始化時(shí)調(diào)用的:

?final?V?putVal(int?hash,?K?key,?V?value,?boolean?onlyIfAbsent,???????????????boolean?evict)?{???????????????????Node<K,V>[]?tab;?Node<K,V>?p;?int?n,?i;????//如果是第一添加元素?table?=?null?則需要擴(kuò)容????if?((tab?=?table)?==?null?||?(n?=?tab.length)?==?0)????????n?=?(tab?=?resize()).length;//?n?表示擴(kuò)容后數(shù)組的長(zhǎng)度????//??i?=?(n?-?1)?&?hash?即上邊講得元素存儲(chǔ)在?map?中的數(shù)組角標(biāo)計(jì)算????//?如果對(duì)應(yīng)數(shù)組沒(méi)有元素沒(méi)發(fā)生?hash?碰撞?則直接賦值給數(shù)組中?index?位置???????if?((p?=?tab[i?=?(n?-?1)?&?hash])?==?null)????????tab[i]?=?newNode(hash,?key,?value,?null);????else?{//?發(fā)生?hash?碰撞了????????Node<K,V>?e;?K?k;?????????//如果對(duì)應(yīng)位置有已經(jīng)有元素了?且?key?是相同的則覆蓋元素????????if?(p.hash?==?hash?&&????????????((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))????????????e?=?p;????????else?if?(p?instanceof?TreeNode)//如果添加當(dāng)前節(jié)點(diǎn)已經(jīng)為紅黑樹(shù)，則需要轉(zhuǎn)為紅黑樹(shù)中的節(jié)點(diǎn)????????????e?=?((TreeNode<K,V>)p).putTreeVal(this,?tab,?hash,?key,?value);????????else?{//?hash?值計(jì)算出的數(shù)組索引相同，但?key?并不同的時(shí)候，????????//?循環(huán)整個(gè)單鏈表????????????for?(int?binCount?=?0;?;?++binCount)?{????????????????if?((e?=?p.next)?==?null)?{//遍歷到尾部?????????????????????//?創(chuàng)建新的節(jié)點(diǎn)，拼接到鏈表尾部????????????????????p.next?=?newNode(hash,?key,?value,?null);?????????????//?如果添加后?bitCount?大于等于樹(shù)化閾值后進(jìn)行哈希桶樹(shù)化操作????????????????????if?(binCount?>=?TREEIFY_THRESHOLD?-?1)?//?-1?for?1st????????????????????????treeifyBin(tab,?hash);????????????????????break;????????????????}????????????????//如果遍歷過(guò)程中找到鏈表中有個(gè)節(jié)點(diǎn)的?key?與?當(dāng)前要插入元素的?key?相同，此時(shí)?e?所指的節(jié)點(diǎn)為需要替換?Value?的節(jié)點(diǎn)，并結(jié)束循環(huán)????????????????if?(e.hash?==?hash?&&????????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))????????????????????break;????????????????//移動(dòng)指針????????????????????p?=?e;????????????}????????}????????//如果循環(huán)完后?e!=null?代表需要替換e所指節(jié)點(diǎn)?Value????????if?(e?!=?null)?{?//?existing?mapping?for?key????????????V?oldValue?=?e.value//保存原來(lái)的?Value?作為返回值????????????//?onlyIfAbsent?一般為?false?所以替換原來(lái)的?Value????????????if?(!onlyIfAbsent?||?oldValue?==?null)????????????????e.value?=?value;?????????????//這個(gè)方法在?HashMap?中是空實(shí)現(xiàn)，在?LinkedHashMap?中有關(guān)系???????????????afterNodeAccess(e);????????????return?oldValue;????????}????}????//操作數(shù)增加????++modCount;????//如果?size?大于擴(kuò)容閾值則表示需要擴(kuò)容????if?(++size?>?threshold)????????resize();????afterNodeInsertion(evict);????return?null;?}?復(fù)制代碼

由于添加元素中設(shè)計(jì)邏輯有點(diǎn)復(fù)雜，這里引用一張圖來(lái)說(shuō)明，理解

添加元素過(guò)程：

1. 如果?Node[] table?表為 null ,則表示是第一次添加元素，講構(gòu)造函數(shù)也提到了，及時(shí)構(gòu)造函數(shù)指定了期望初始容量，在第一次添加元素的時(shí)候也為空。這時(shí)候需要進(jìn)行首次擴(kuò)容過(guò)程。

2. 計(jì)算對(duì)應(yīng)的鍵值對(duì)在 table 表中的索引位置，通過(guò)i = (n - 1) & hash?獲得。

3. 判斷索引位置是否有元素如果沒(méi)有元素則直接插入到數(shù)組中。如果有元素且key 相同，則覆蓋 value 值，這里判斷是用的 equals 這就表示要正確的存儲(chǔ)元素，就必須按照業(yè)務(wù)要求覆寫(xiě) key 的 equals 方法，上篇文章我們也提及到了該方法重要性。

4. 如果索引位置的 key 不相同，則需要遍歷單鏈表，如果遍歷過(guò)如果有與 key 相同的節(jié)點(diǎn)，則保存索引，替換 Value；如果沒(méi)有相同節(jié)點(diǎn)，則在但單鏈表尾部插入新節(jié)點(diǎn)。這里操作與1.7不同，1.7新來(lái)的節(jié)點(diǎn)總是在數(shù)組索引位置，而之前的元素作為下個(gè)節(jié)點(diǎn)拼接到新節(jié)點(diǎn)尾部。

5. 如果插入節(jié)點(diǎn)后鏈表的長(zhǎng)度大于樹(shù)化閾值，則需要將單鏈表轉(zhuǎn)為紅黑樹(shù)。

6. 成功插入節(jié)點(diǎn)后，判斷鍵值對(duì)個(gè)數(shù)是否大于擴(kuò)容閾值，如果大于了則需要再次擴(kuò)容。至此整個(gè)插入元素過(guò)程結(jié)束。

HashMap 的擴(kuò)容過(guò)程

在上邊說(shuō)明 HashMap 的 putVal 方法時(shí)候，多次提到了擴(kuò)容函數(shù)，擴(kuò)容函數(shù)也是我們理解 HashMap 源碼的重中之重。所以再次敲黑板~

final?Node<K,V>[]?resize()?{????//?oldTab?指向舊的?table?表????Node<K,V>[]?oldTab?=?table;????//?oldCap?代表擴(kuò)容前?table?表的數(shù)組長(zhǎng)度，oldTab?第一次添加元素的時(shí)候?yàn)?null?????int?oldCap?=?(oldTab?==?null)???0?:?oldTab.length;????//?舊的擴(kuò)容閾值????int?oldThr?=?threshold;????//?初始化新的閾值和容量????int?newCap,?newThr?=?0;????//?如果?oldCap?>?0?則會(huì)將新容量擴(kuò)大到原來(lái)的2倍，擴(kuò)容閾值也將擴(kuò)大到原來(lái)閾值的兩倍????if?(oldCap?>?0)?{????????//?如果舊的容量已經(jīng)達(dá)到最大容量?2^30?那么就不在繼續(xù)擴(kuò)容直接返回，將擴(kuò)容閾值設(shè)置到?Integer.MAX_VALUE，并不代表不能裝新元素，只是數(shù)組長(zhǎng)度將不會(huì)變化????????if?(oldCap?>=?MAXIMUM_CAPACITY)?{????????????threshold?=?Integer.MAX_VALUE;????????????return?oldTab;????????}//新容量擴(kuò)大到原來(lái)的2倍，擴(kuò)容閾值也將擴(kuò)大到原來(lái)閾值的兩倍????????else?if?((newCap?=?oldCap?<<?1)?<?MAXIMUM_CAPACITY?&&?????????????????oldCap?>=?DEFAULT_INITIAL_CAPACITY)????????????newThr?=?oldThr?<<?1;?//?double?threshold????}????//oldThr?不為空，代表我們使用帶參數(shù)的構(gòu)造方法指定了加載因子并計(jì)算了????//初始初始閾值?會(huì)將擴(kuò)容閾值?賦值給初始容量這里不再是期望容量，????//但是?>=?指定的期望容量????else?if?(oldThr?>?0)?//?initial?capacity?was?placed?in?threshold????????newCap?=?oldThr;????else?{?????????//?空參數(shù)構(gòu)造會(huì)走這里初始化容量，和擴(kuò)容閾值?分別是?16?和?12????????newCap?=?DEFAULT_INITIAL_CAPACITY;????????newThr?=?(int)(DEFAULT_LOAD_FACTOR?*?DEFAULT_INITIAL_CAPACITY);????}????//如果新的擴(kuò)容閾值是0，對(duì)應(yīng)的是當(dāng)前?table?為空，但是有閾值的情況????if?(newThr?==?0)?{?????????//計(jì)算新的擴(kuò)容閾值????????float?ft?=?(float)newCap?*?loadFactor;????????//?如果新的容量不大于?2^30?且?ft?不大于?2^30?的時(shí)候賦值給?newThr?????????//否則?使用?Integer.MAX_VALUE????????newThr?=?(newCap?<?MAXIMUM_CAPACITY?&&?ft?<?(float)MAXIMUM_CAPACITY????????????????????(int)ft?:?Integer.MAX_VALUE);????}????//更新全局?jǐn)U容閾值????threshold?=?newThr;????@SuppressWarnings({"rawtypes","unchecked"})?????//使用新的容量創(chuàng)建新的哈希表的數(shù)組????Node<K,V>[]?newTab?=?(Node<K,V>[])new?Node[newCap];????table?=?newTab;????//如果老的數(shù)組不為空將進(jìn)行重新插入操作否則直接返回????if?(oldTab?!=?null)?{?????????//遍歷老數(shù)組中每個(gè)位置的鏈表或者紅黑樹(shù)重新計(jì)算節(jié)點(diǎn)位置，插入新數(shù)組????????for?(int?j?=?0;?j?<?oldCap;?++j)?{????????????Node<K,V>?e;//用來(lái)存儲(chǔ)對(duì)應(yīng)數(shù)組位置鏈表頭節(jié)點(diǎn)????????????//如果當(dāng)前數(shù)組位置存在元素????????????if?((e?=?oldTab[j])?!=?null)?{?????????????????//?釋放原來(lái)數(shù)組中的對(duì)應(yīng)的空間????????????????oldTab[j]?=?null;????????????????//?如果鏈表只有一個(gè)節(jié)點(diǎn)，????????????????//則使用新的數(shù)組長(zhǎng)度計(jì)算節(jié)點(diǎn)位于新數(shù)組中的角標(biāo)并插入????????????????if?(e.next?==?null)????????????????????newTab[e.hash?&?(newCap?-?1)]?=?e;????????????????else?if?(e?instanceof?TreeNode)//如果當(dāng)前節(jié)點(diǎn)為紅黑樹(shù)則需要進(jìn)一步確定樹(shù)中節(jié)點(diǎn)位于新數(shù)組中的位置。????????????????????((TreeNode<K,V>)e).split(this,?newTab,?j,?oldCap);????????????????else?{?//?preserve?order????????????????????//因?yàn)閿U(kuò)容是容量翻倍，????????????????????//原鏈表上的每個(gè)節(jié)點(diǎn)?現(xiàn)在可能存放在原來(lái)的下標(biāo)，即low位，????????????????????//或者擴(kuò)容后的下標(biāo)，即high位???????????????//低位鏈表的頭結(jié)點(diǎn)、尾節(jié)點(diǎn)???????????????Node<K,V>?loHead?=?null,?loTail?=?null;???????????????//高位鏈表的頭節(jié)點(diǎn)、尾節(jié)點(diǎn)???????????????Node<K,V>?hiHead?=?null,?hiTail?=?null;???????????????Node<K,V>?next;//用來(lái)存放原鏈表中的節(jié)點(diǎn)???????????????do?{???????????????????next?=?e.next;???????????????????//?利用哈希值?&?舊的容量，可以得到哈希值去模后，???????????????????//是大于等于?oldCap?還是小于?oldCap，???????????????????//等于?0?代表小于?oldCap，應(yīng)該存放在低位，???????????????????//否則存放在高位（稍后有圖片說(shuō)明）???????????????????if?((e.hash?&?oldCap)?==?0)?{???????????????????????//給頭尾節(jié)點(diǎn)指針賦值???????????????????????if?(loTail?==?null)???????????????????????????loHead?=?e;???????????????????????else???????????????????????????loTail.next?=?e;???????????????????????loTail?=?e;???????????????????}//高位也是相同的邏輯???????????????????else?{???????????????????????if?(hiTail?==?null)???????????????????????????hiHead?=?e;???????????????????????else???????????????????????????hiTail.next?=?e;???????????????????????hiTail?=?e;???????????????????}//循環(huán)直到鏈表結(jié)束???????????????}?while?((e?=?next)?!=?null);???????????????//將低位鏈表存放在原index處，???????????????if?(loTail?!=?null)?{???????????????????loTail.next?=?null;???????????????????newTab[j]?=?loHead;???????????????}???????????????//將高位鏈表存放在新index處???????????????if?(hiTail?!=?null)?{???????????????????hiTail.next?=?null;???????????????????newTab[j?+?oldCap]?=?hiHead;???????????????}????????????}????????}????}????return?newTab;?}?復(fù)制代碼

相信大家看到擴(kuò)容的整個(gè)函數(shù)后對(duì)擴(kuò)容機(jī)制應(yīng)該有所了解了，整體分為兩部分：1. 尋找擴(kuò)容后數(shù)組的大小以及新的擴(kuò)容閾值，2. 將原有哈希表拷貝到新的哈希表中。

第一部分沒(méi)的說(shuō)，但是第二部分我看的有點(diǎn)懵逼了，但是踩在巨人的肩膀上總是比較容易的，美團(tuán)的大佬們?cè)缇蛯?xiě)過(guò)一些有關(guān) HashMap 的源碼分析文章，給了我很大的幫助。在文章的最后我會(huì)放出參考鏈接。下面說(shuō)下我的理解：

JDK 1.8 不像 JDK1.7中會(huì)重新計(jì)算每個(gè)節(jié)點(diǎn)在新哈希表中的位置，而是通過(guò)?(e.hash & oldCap) == 0是否等于0 就可以得出原來(lái)鏈表中的節(jié)點(diǎn)在新哈希表的位置。為什么可以這樣高效的得出新位置呢？

因?yàn)閿U(kuò)容是容量翻倍，所以原鏈表上的每個(gè)節(jié)點(diǎn)，可能存放新哈希表中在原來(lái)的下標(biāo)位置， 或者擴(kuò)容后的原位置偏移量為 oldCap 的位置上，下邊舉個(gè)例子 圖片和敘述來(lái)自 https://tech.meituan.com/java-hashmap.html：

圖（a）表示擴(kuò)容前的key1和key2兩種key確定索引位置的示例，圖（b）表示擴(kuò)容后key1和key2兩種key確定索引位置的示例，其中hash2是key1對(duì)應(yīng)的哈希與高位運(yùn)算結(jié)果。

元素在重新計(jì)算hash之后，因?yàn)閚變?yōu)?倍，那么n-1的mask范圍在高位多1bit(紅色)，因此新的index就會(huì)發(fā)生這樣的變化：

所以在 JDK1.8 中擴(kuò)容后，只需要看看原來(lái)的hash值新增的那個(gè)bit是1還是0就好了，是0的話索引沒(méi)變，是1的話索引變成“原索引+oldCap

另外還需要注意的一點(diǎn)是 HashMap 在 1.7的時(shí)候擴(kuò)容后，鏈表的節(jié)點(diǎn)順序會(huì)倒置，1.8則不會(huì)出現(xiàn)這種情況。

HashMap 其他添加元素的方法

上邊將構(gòu)造函數(shù)的時(shí)候埋了個(gè)坑即使用：

public?HashMap(Map<??extends?K,???extends?V>?m)?{????this.loadFactor?=?DEFAULT_LOAD_FACTOR;????putMapEntries(m,?false);?}?復(fù)制代碼

構(gòu)造函數(shù)構(gòu)建 HashMap 的時(shí)候，在這個(gè)方法里，除了賦值了默認(rèn)的加載因子，并沒(méi)有調(diào)用其他構(gòu)造方法，而是通過(guò)批量添加元素的方法?putMapEntries?來(lái)構(gòu)造了 HashMap。該方法為私有方法，真正批量添加的方法為putAll

public?void?putAll(Map<??extends?K,???extends?V>?m)?{????putMapEntries(m,?true);?}?復(fù)制代碼

//同樣第二參數(shù)代表是否初次創(chuàng)建?table???final?void?putMapEntries(Map<??extends?K,???extends?V>?m,?boolean?evict)?{????int?s?=?m.size();????if?(s?>?0)?{?????????//如果哈希表為空則初始化參數(shù)擴(kuò)容閾值????????if?(table?==?null)?{?//?pre-size????????????float?ft?=?((float)s?/?loadFactor)?+?1.0F;????????????int?t?=?((ft?<?(float)MAXIMUM_CAPACITY)???????????????????????(int)ft?:?MAXIMUM_CAPACITY);????????????if?(t?>?threshold)????????????????threshold?=?tableSizeFor(t);????????}????????else?if?(s?>?threshold)//構(gòu)造方法沒(méi)有計(jì)算?threshold?默認(rèn)為0?所以會(huì)走擴(kuò)容函數(shù)????????????resize();?????????//將參數(shù)中的?map?鍵值對(duì)一次添加到?HashMap?中????????for?(Map.Entry<??extends?K,???extends?V>?e?:?m.entrySet())?{????????????K?key?=?e.getKey();????????????V?value?=?e.getValue();????????????putVal(hash(key),?key,?value,?false,?evict);????????}????}?}?復(fù)制代碼

JDK1.8 中還新增了一個(gè)添加方法，該方法調(diào)用 putVal 且第4個(gè)參數(shù)傳了 true，代表只有哈希表中對(duì)應(yīng)的key 的位置上元素為空的時(shí)候添加成功，否則返回原來(lái) key 對(duì)應(yīng)的 Value 值。

@Override?public?V?putIfAbsent(K?key,?V?value)?{????return?putVal(hash(key),?key,?value,?true,?true);?}?復(fù)制代碼

HashMap 查詢(xún)?cè)?/h3>

分析了完了 put 函數(shù)后，接下來(lái)讓我們看下 get 函數(shù)，當(dāng)然有 put 函數(shù)計(jì)算鍵值對(duì)在哈希表中位置的索引方法分析的鋪墊后，get 方法就顯得很容容易了。

1. 根據(jù)鍵值對(duì)的 key 去獲取對(duì)應(yīng)的 Value

public?V?get(Object?key)?{????Node<K,V>?e;????//通過(guò)?getNode尋找?key?對(duì)應(yīng)的?Value?如果沒(méi)找到，或者找到的結(jié)果為?null?就會(huì)返回null?否則會(huì)返回對(duì)應(yīng)的?Value????return?(e?=?getNode(hash(key),?key))?==?null???null?:?e.value;?}?final?Node<K,V>?getNode(int?hash,?Object?key)?{????Node<K,V>[]?tab;?Node<K,V>?first,?e;?int?n;?K?k;????//現(xiàn)根據(jù)?key?的?hash?值去找到對(duì)應(yīng)的鏈表或者紅黑樹(shù)????if?((tab?=?table)?!=?null?&&?(n?=?tab.length)?>?0?&&????????(first?=?tab[(n?-?1)?&?hash])?!=?null)?{????????//?如果第一個(gè)節(jié)點(diǎn)就是那么直接返回????????if?(first.hash?==?hash?&&?//?always?check?first?node????????????((k?=?first.key)?==?key?||?(key?!=?null?&&?key.equals(k))))????????????return?first;?????????//如果?對(duì)應(yīng)的位置為紅黑樹(shù)調(diào)用紅黑樹(shù)的方法去尋找節(jié)點(diǎn)???????????if?((e?=?first.next)?!=?null)?{????????????if?(first?instanceof?TreeNode)????????????????return?((TreeNode<K,V>)first).getTreeNode(hash,?key);?????????????//遍歷單鏈表找到對(duì)應(yīng)的?key?和?Value???????????????do?{????????????????if?(e.hash?==?hash?&&????????????????????((k?=?e.key)?==?key?||?(key?!=?null?&&?key.equals(k))))????????????????????return?e;????????????}?while?((e?=?e.next)?!=?null);????????}????}????return?null;?}?復(fù)制代碼

1. JDK 1.8新增 get 方法，在尋找 key 對(duì)應(yīng) Value 的時(shí)候如果沒(méi)找大則返回指定默認(rèn)值

@Override?public?V?getOrDefault(Object?key,?V?defaultValue)?{????Node<K,V>?e;????return?(e?=?getNode(hash(key),?key))?==?null???defaultValue?:?e.value;?}?復(fù)制代碼

HashMap 的刪操作

HashMap?沒(méi)有?set?方法，如果想要修改對(duì)應(yīng) key 映射的 Value ，只需要再次調(diào)用?put?方法就可以了。我們來(lái)看下如何移除?HashMap?中對(duì)應(yīng)的節(jié)點(diǎn)的方法：

?public?V?remove(Object?key)?{????Node<K,V>?e;????return?(e?=?removeNode(hash(key),?key,?null,?false,?true))?==?null??????????null?:?e.value;?}?復(fù)制代碼

@Override?public?boolean?remove(Object?key,?Object?value)?{????//這里傳入了value?同時(shí)matchValue為true????return?removeNode(hash(key),?key,?value,?true,?true)?!=?null;?}?復(fù)制代碼

這里有兩個(gè)參數(shù)需要我們提起注意：

• matchValue 如果這個(gè)值為 true 則表示只有當(dāng) Value 與第三個(gè)參數(shù) Value 相同的時(shí)候才刪除對(duì)一個(gè)的節(jié)點(diǎn)

• movable 這個(gè)參數(shù)在紅黑樹(shù)中先刪除節(jié)點(diǎn)時(shí)候使用 true 表示刪除并其他數(shù)中的節(jié)點(diǎn)。

?final?Node<K,V>?removeNode(int?hash,?Object?key,?Object?value,????????????????????????????????boolean?matchValue,?boolean?movable)?{????Node<K,V>[]?tab;?Node<K,V>?p;?int?n,?index;????//判斷哈希表是否為空，長(zhǎng)度是否大于0?對(duì)應(yīng)的位置上是否有元素????if?((tab?=?table)?!=?null?&&?(n?=?tab.length)?>?0?&&????????(p?=?tab[index?=?(n?-?1)?&?hash])?!=?null)?{????????????????//?node?用來(lái)存放要移除的節(jié)點(diǎn)，?e?表示下個(gè)節(jié)點(diǎn)?k?，v?每個(gè)節(jié)點(diǎn)的鍵值????????Node<K,V>?node?=?null,?e;?K?k;?V?v;????????//如果第一個(gè)節(jié)點(diǎn)就是我們要找的直接賦值給?node????????if?(p.hash?==?hash?&&????????????((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))????????????node?=?p;????????else?if?((e?=?p.next)?!=?null)?{?????????????//?遍歷紅黑樹(shù)找到對(duì)應(yīng)的節(jié)點(diǎn)????????????if?(p?instanceof?TreeNode)????????????????node?=?((TreeNode<K,V>)p).getTreeNode(hash,?key);????????????else?{?????????????????//遍歷對(duì)應(yīng)的鏈表找到對(duì)應(yīng)的節(jié)點(diǎn)????????????????do?{????????????????????if?(e.hash?==?hash?&&????????????????????????((k?=?e.key)?==?key?||?????????????????????????(key?!=?null?&&?key.equals(k))))?{????????????????????????node?=?e;????????????????????????break;????????????????????}????????????????????p?=?e;????????????????}?while?((e?=?e.next)?!=?null);????????????}????????}????????//?如果找到了節(jié)點(diǎn)????????//?!matchValue?是否不刪除節(jié)點(diǎn)????????//?(v?=?node.value)?==?value?||?????????????????????????????(value?!=?null?&&?value.equals(v)))?節(jié)點(diǎn)值是否相同，????????if?(node?!=?null?&&?(!matchValue?||?(v?=?node.value)?==?value?||?????????????????????????????(value?!=?null?&&?value.equals(v))))?{????????????//刪除節(jié)點(diǎn)?????????????????????????????if?(node?instanceof?TreeNode)????????????????((TreeNode<K,V>)node).removeTreeNode(this,?tab,?movable);????????????else?if?(node?==?p)????????????????tab[index]?=?node.next;????????????else????????????????p.next?=?node.next;????????????++modCount;????????????--size;????????????afterNodeRemoval(node);????????????return?node;????????}????}????return?null;?}?復(fù)制代碼

HashMap 的迭代器

我們都只我們知道 Map 和 Set 有多重迭代方式，對(duì)于 Map 遍歷方式這里不展開(kāi)說(shuō)了，因?yàn)槲覀円治龅鞯脑创a所以這里就給出一個(gè)使用迭代器遍歷的方法：

public?void?test(){?????Map<String,?Integer>?map?=?new?HashMap<>();??????????...??????????Set<Map.Entry<String,?Integer>>?entrySet?=?map.entrySet();??????????//通過(guò)迭代器：先獲得?key-value?對(duì)（Entry）的Iterator，再循環(huán)遍歷????????Iterator?iter1?=?entrySet.iterator();?????while?(iter1.hasNext())?{?????//?遍歷時(shí)，需先獲取entry，再分別獲取key、value?????Map.Entry?entry?=?(Map.Entry)?iter1.next();?????System.out.print((String)?entry.getKey());?????System.out.println((Integer)?entry.getValue());?????}?}?復(fù)制代碼

通過(guò)上述遍歷過(guò)程我們可以使用?map.entrySet()?獲取之前我們最初提及的?entrySet

public?Set<Map.Entry<K,V>>?entrySet()?{????Set<Map.Entry<K,V>>?es;????return?(es?=?entrySet)?==?null???(entrySet?=?new?EntrySet())?:?es;?}?復(fù)制代碼

//?我們來(lái)看下?EntrySet?是一個(gè)?set?存儲(chǔ)的元素是?Map?的鍵值對(duì)?final?class?EntrySet?extends?AbstractSet<Map.Entry<K,V>>?{????//?size?放回?Map?中鍵值對(duì)個(gè)數(shù)????public?final?int?size()?????????????????{?return?size;?}????//清除鍵值對(duì)????public?final?void?clear()???????????????{?HashMap.this.clear();?}????//?獲取迭代器????public?final?Iterator<Map.Entry<K,V>>?iterator()?{????????return?new?EntryIterator();????}????????//通過(guò)?getNode?方法獲取對(duì)一個(gè)及對(duì)應(yīng)?key?對(duì)應(yīng)的節(jié)點(diǎn)?這里必須傳入????//?Map.Entry?鍵值對(duì)類(lèi)型的對(duì)象?否則直接返回?false????public?final?boolean?contains(Object?o)?{????????if?(!(o?instanceof?Map.Entry))????????????return?false;????????Map.Entry<?,?>?e?=?(Map.Entry<?,?>)?o;????????Object?key?=?e.getKey();????????Node<K,V>?candidate?=?getNode(hash(key),?key);????????return?candidate?!=?null?&&?candidate.equals(e);????}????//?滴啊用之前講得?removeNode?方法?刪除節(jié)點(diǎn)????public?final?boolean?remove(Object?o)?{????????if?(o?instanceof?Map.Entry)?{????????????Map.Entry<?,?>?e?=?(Map.Entry<?,?>)?o;????????????Object?key?=?e.getKey();????????????Object?value?=?e.getValue();????????????return?removeNode(hash(key),?key,?value,?true,?true)?!=?null;????????}????????return?false;????}????...?}?復(fù)制代碼

//EntryIterator?繼承自?HashIterator?final?class?EntryIterator?extends?HashIterator????implements?Iterator<Map.Entry<K,V>>?{????//?這里可能是因?yàn)榇蠹沂褂眠m配器的習(xí)慣添加了這個(gè)?next?方法????public?final?Map.Entry<K,V>?next()?{?return?nextNode();?}?}?????abstract?class?HashIterator?{?????????Node<K,V>?next;????????//?next?entry?to?return?????????Node<K,V>?current;?????//?current?entry?????????int?expectedModCount;??//?for?fast-fail?????????int?index;?????????????//?current?slot?????????HashIterator()?{?????????????//初始化操作數(shù)?Fast-fail??????????????expectedModCount?=?modCount;?????????????//?將?Map?中的哈希表賦值給?t?????????????Node<K,V>[]?t?=?table;?????????????current?=?next?=?null;?????????????index?=?0;?????????????//從table?第一個(gè)不為空的?index?開(kāi)始獲取?entry?????????????if?(t?!=?null?&&?size?>?0)?{?//?advance?to?first?entry?????????????????do?{}?while?(index?<?t.length?&&?(next?=?t[index++])?==?null);?????????????}?????????}??????????????????public?final?boolean?hasNext()?{?????????????return?next?!=?null;?????????}?????????final?Node<K,V>?nextNode()?{?????????????Node<K,V>[]?t;?????????????Node<K,V>?e?=?next;?????????????if?(modCount?!=?expectedModCount)?????????????????throw?new?ConcurrentModificationException();?????????????if?(e?==?null)?????????????????throw?new?NoSuchElementException();??????????????//如果當(dāng)前鏈表節(jié)點(diǎn)遍歷完了，則取哈希桶下一個(gè)不為null的鏈表頭????????????????if?((next?=?(current?=?e).next)?==?null?&&?(t?=?table)?!=?null)?{?????????????????do?{}?while?(index?<?t.length?&&?(next?=?t[index++])?==?null);?????????????}?????????????return?e;?????????}?????????//這里還是調(diào)用?removeNode?函數(shù)不在贅述?????????public?final?void?remove()?{?????????????Node<K,V>?p?=?current;?????????????if?(p?==?null)?????????????????throw?new?IllegalStateException();?????????????if?(modCount?!=?expectedModCount)?????????????????throw?new?ConcurrentModificationException();?????????????current?=?null;?????????????K?key?=?p.key;?????????????removeNode(hash(key),?key,?null,?false,?false);?????????????expectedModCount?=?modCount;?????????}?????}?復(fù)制代碼

除了?EntryIterator?以外還有?KeyIterator?和?ValueIterator?也都繼承了HashIterator?也代表了 HashMap 的三種不同的迭代器遍歷方式。

?final?class?KeyIterator?extends?HashIterator????implements?Iterator<K>?{????public?final?K?next()?{?return?nextNode().key;?}?}?final?class?ValueIterator?extends?HashIterator????implements?Iterator<V>?{????public?final?V?next()?{?return?nextNode().value;?}?}?復(fù)制代碼

可以看出無(wú)論哪種迭代器都是通過(guò)，遍歷 table 表來(lái)獲取下個(gè)節(jié)點(diǎn)，來(lái)遍歷的，遍歷過(guò)程可以理解為一種深度優(yōu)先遍歷，即優(yōu)先遍歷鏈表節(jié)點(diǎn)（或者紅黑樹(shù)），然后在遍歷其他數(shù)組位置。

HashTable 的區(qū)別

面試的時(shí)候面試官總是問(wèn)完 HashMap 后會(huì)問(wèn) HashTable 其實(shí) HashTable 也算是比較古老的類(lèi)了。翻看 HashTable 的源碼可以發(fā)現(xiàn)有如下區(qū)別：

1. HashMap?是線程不安全的，HashTable是線程安全的。

2. HashMap?允許 key 和 Vale 是 null，但是只允許一個(gè) key 為 null,且這個(gè)元素存放在哈希表 0 角標(biāo)位置。?HashTable?不允許key、value 是 null

3. HashMap?內(nèi)部使用hash(Object key)擾動(dòng)函數(shù)對(duì) key 的?hashCode?進(jìn)行擾動(dòng)后作為?hash?值。HashTable?是直接使用 key 的?hashCode()?返回值作為 hash 值。

4. HashMap默認(rèn)容量為 2^4 且容量一定是 2^n ;?HashTable?默認(rèn)容量是11,不一定是 2^n

5. HashTable?取哈希桶下標(biāo)是直接用模運(yùn)算,擴(kuò)容時(shí)新容量是原來(lái)的2倍+1。HashMap?在擴(kuò)容的時(shí)候是原來(lái)的兩倍，且哈希桶的下標(biāo)使用 &運(yùn)算代替了取模。

最后

寫(xiě) HashMap 源碼分析的過(guò)程，可以說(shuō)比?ArrayList?或者LinkedList源碼簡(jiǎn)直不是一個(gè)級(jí)別的。個(gè)人能力有限，所以在學(xué)習(xí)的過(guò)程中，參考了很多前輩們的分析，也學(xué)到了很多東西。這很有用，經(jīng)過(guò)這一波分析我覺(jué)得我對(duì)面試中的的 HashMap 面試題回答要比以前強(qiáng)很多。對(duì)于 HashMap的相關(guān)面試題集合

當(dāng)前題目：帶你搞懂Java中HashMap源碼！
文章網(wǎng)址：http://chinadenli.net/article20/gghejo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App開(kāi)發(fā)、自適應(yīng)網(wǎng)站、網(wǎng)站內(nèi)鏈、手機(jī)網(wǎng)站建設(shè)、網(wǎng)站制作、網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)