HashMap 源碼分析

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

成都創新互聯專注為客戶提供全方位的互聯網綜合服務，包含不限于成都做網站、成都網站建設、霸州網絡推廣、重慶小程序開發公司、霸州網絡營銷、霸州企業策劃、霸州品牌公關、搜索引擎seo、人物專訪、企業宣傳片、企業代運營等，從售前售中售后，我們都將竭誠為您服務，您的肯定，是我們最大的嘉獎；成都創新互聯為所有大學生創業者提供霸州建站搭建服務，24小時服務熱線：13518219792，官方網址：vcdvsql.cn

1. 了解底層如何存儲數據的

2. HashMap 的幾個主要方法

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

4. HashMap 擴容機制是怎樣的

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

本文也將從以上幾個方面來展開敘述：

由于掘金后臺審核可能會由于某些原因造成文章發布延遲或者遺漏，如果感覺我寫的源碼分析文章還不錯，可以關注我，以后我每次更新文章就可以收到推送了。另外博主也是在努力進步中，所有文章如果有問題請盡管留言給我。我會及時改正。大家一起進步。

概述

為了方便下邊的敘述這里需要先對幾個常見的關于?HashMap?的知識點進行下概述：

1. HashMap?存儲數據是根據鍵值對存儲數據的，并且存儲多個數據時，數據的鍵不能相同，如果相同該鍵之前對應的值將被覆蓋。注意如果想要保證?HashMap?能夠正確的存儲數據，請確保作為鍵的類，已經正確覆寫了?equals()?方法。

2. HashMap?存儲數據的位置與添加數據的鍵的?hashCode()?返回值有關。所以在將元素使用 HashMap 存儲的時候請確保你已經按照要求重寫了?hashCode(）方法。這里說有關系代表最終的存儲位置不一定就是?hashCode?的返回值。

3. HashMap?最多只允許一條存儲數據的鍵為 null，可允許多條數據的值為 null。

4. HashMap?存儲數據的順序是不確定的，并且可能會因為擴容導致元素存儲位置改變。因此遍歷順序是不確定的。

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

了解 HashMap 底層如何存儲數據的

要想分析 HashMap 源碼，就必須在 JDK1.8 和 JDK1.7之間劃分一條線，因為在 JDK 1.8 后對于 HashMap 做了底層實現的改動。

JDK 1.7 之前的存儲結構

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

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

「拉鏈法」用專業點的名詞來說叫做鏈地址法。簡單來說，就是數組加鏈表的結合。在每個數組元素上存儲的都是一個鏈表。

我們之前說到不同的 key 可能經過 hash 運算可能會得到相同的地址，但是一個數組單位上只能存放一個元素，采用鏈地址法以后，如果遇到相同的 hash 值的 key 的時候，我們可以將它放到作為數組元素的鏈表上。待我們去取元素的時候通過 hash 運算的結果找到這個鏈表，再在鏈表中找到與 key 相同的節點，就能找到 key 相應的值了。

JDK1.7中新添加進來的元素總是放在數組相應的角標位置，而原來處于該角標的位置的節點作為 next 節點放到新節點的后邊。稍后通過源碼分析我們也能看到這一點。

JDK1.8中的存儲結構。

對于 JDK1.8 之后的HashMap底層在解決哈希沖突的時候，就不單單是使用數組加上單鏈表的組合了，因為當處理如果 hash 值沖突較多的情況下，鏈表的長度就會越來越長，此時通過單鏈表來尋找對應 Key 對應的 Value 的時候就會使得時間復雜度達到 O(n),因此在 JDK1.8 之后，在鏈表新增節點導致鏈表長度超過?TREEIFY_THRESHOLD = 8?的時候，就會在添加元素的同時將原來的單鏈表轉化為紅黑樹。

對數據結構很在行的讀者應該，知道紅黑樹是一種易于增刪改查的二叉樹，他對與數據的查詢的時間復雜度是?O(logn)?級別，所以利用紅黑樹的特點就可以更高效的對?HashMap?中的元素進行操作。

JDK1.8 對于HashMap 底層存儲結構優化在于：當鏈表新增節點導致鏈表長度超過8的時候，就會將原有的鏈表轉為紅黑樹來存儲數據。

關于 HashMap 源碼中提到的幾個重要概念

關于 HashMap 源碼中分析的文章一般都會提及幾個重要的概念：

重要參數

1. 哈希桶（buckets）：在 HashMap 的注釋里使用哈希桶來形象的表示數組中每個地址位置。注意這里并不是數組本身，數組是裝哈希桶的，他可以被稱為哈希表。

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

3. 加載因子(load factor)：加載因子是哈希表（散列表）在其容量自動增加之前被允許獲得的最大數量的度量。當哈希表中的條目數量超過負載因子和當前容量的乘積時，散列表就會被重新映射（即重建內部數據結構），重新創建的散列表容量大約是之前散列表哈系統桶數量的兩倍。默認加載因子（0.75）在時間和空間成本之間提供了良好的折衷。加載因子過大會導致很容易鏈表過長，加載因子很小又容易導致頻繁的擴容。所以不要輕易試著去改變這個默認值。

4. 擴容閾值（threshold）：其實在說加載因子的時候已經提到了擴容閾值了，擴容閾值 = 哈希表容量 * 加載因子。哈希表的鍵值對總數 = 所有哈希桶中所有鏈表節點數的加和，擴容閾值比較的是是鍵值對的個數而不是哈希表的數組中有多少個位置被占了。

5. 樹化閥值(TREEIFY_THRESHOLD)?：這個參數概念是在 JDK1.8后加入的，它的含義代表一個哈希桶中的節點個數大于該值（默認為8）的時候將會被轉為紅黑樹行存儲結構。

6. 非樹化閥值(UNTREEIFY_THRESHOLD)： 與樹化閾值相對應，表示當一個已經轉化為數形存儲結構的哈希桶中節點數量小于該值（默認為 6）的時候將再次改為單鏈表的格式存儲。導致這種操作的原因可能有刪除節點或者擴容。

7. 最小樹化容量(MIN_TREEIFY_CAPACITY): 經過上邊的介紹我們只知道，當鏈表的節點數超過8的時候就會轉化為樹化存儲，其實對于轉化還有一個要求就是哈希表的數量超過最小樹化容量的要求（默認要求是 64）,且為了避免進行擴容、樹形化選擇的沖突，這個值不能小于 4 * TREEIFY_THRESHOLD);在達到該有求之前優先選擇擴容。擴容因為因為容量的變化可能會使單鏈表的長度改變。

與這個幾個概念對應的在 ?HashMap 中幾個常亮量，由于上邊的介紹比較詳細了，下邊僅列出幾個變量的聲明：

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

對應的還有幾個全局變量：

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

基本存儲單元

HashMap 在 JDK 1.7 中只有?Entry?一種存儲單元，而在 JDK1.8 中由于有了紅黑樹的存在，就多了一種存儲單元，而?Entry?也隨之應景的改為名為 Node。我們先來看下單鏈表節點的表示方法 ：

/**??*?內部類?Node?實現基類的內部接口?Map.Entry<K,V>??*???*/?static?class?Node<K,V>?implements?Map.Entry<K,V>?{????//此值是在數組索引位置????final?int?hash;????//節點的鍵????final?K?key;????//節點的值????V?value;????//單鏈表中下一個節點????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;?}?????//節點的?hashCode?值通過?key?的哈希值和?value?的哈希值異或得到，沒發現在源碼中中有用到。????public?final?int?hashCode()?{????????return?Objects.hashCode(key)?^?Objects.hashCode(value);????}????//更新相同?key?對應的?Value?值????public?final?V?setValue(V?newValue)?{????????V?oldValue?=?value;????????value?=?newValue;????????return?oldValue;????}??//equals?方法，鍵值同時相同才節點才相同????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;????}?}?復制代碼

對于JDK1.8 新增的紅黑樹節點

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);????}????·········?}?復制代碼

HashMap 構造方法

HashMap?構造方法一共有三個：

• 可以指定期望初始容量和加載因子的構造函數，有了這兩個值，我們就可以算出上邊說到的?threshold?加載因子。其中加載因子不可以小于0，并沒有規定不可以大于 1，但是不能等于無窮.

大家可能疑惑?Float.isNaN()?其實 ?NaN 就是 not a number 的縮寫，我們知道在運算 1/0 的時候回拋出異常，但是如果我們的除數指定為浮點數 1/0.0f 的時候就不會拋出異常了。計算器運算出的結果可以當做一個極值也就是無窮大，無窮大不是個數所以 1/0.0f 返回結果是 Infinity 無窮,使用 Float.isNaN(）判斷將會返回 true。

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

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

//根據期望容量返回一個?>=?cap?的擴容閾值，并且這個閾值一定是?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;????//經過上述面的?或和位移?運算，?n?最終各位都是1?????//最終結果?+1?也就保證了返回的肯定是?2^n?????return?(n?<?0)???1?:?(n?>=?MAXIMUM_CAPACITY)???MAXIMUM_CAPACITY?:?n?+?1;?}?復制代碼

• 只指定初始容量的構造函數

這個就比較簡單了，將指定的期望初容量和默認加載因子傳遞給兩個參數構造方法。這里就不在贅述。

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

• 無參數構造函數

這也是我們最常用的一個構造函數，該方法初始化了加載因子為默認值，并沒有調動其他的構造方法，跟我們之前說的一樣，哈希表的大小以及其他參數都會在第一調用擴容函數的初始化為默認值。

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

• 傳入一個 Map 集合的構造參數

該方法解釋起來就比較麻煩了，因為他在初始化的時候就涉及了添加元素，擴容這兩大重要的方法。這里先把它掛起來，緊接著我們講完了擴容機制再回來看就好了。

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

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

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

JDK 1.7 中 hash 方法的實現：

這里提出一個概念擾動函數，我們知道Map 文中存放鍵值對的位置有鍵的 hash 值決定，但是鍵的 hashCode 函數返回值不一定滿足，哈希表長度的要求，所以在存儲元素之前需要對 key 的 hash 值進行一步擾動處理。下面我們JDK1.7 中的擾動函數：

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

JDK1.8 中 hash 函數的實現

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

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

進過上述的擾動函數只是得到了合適的 hash 值，但是還沒有確定在 Node[] 數組中的角標，在 JDK1.7中存在一個函數，JDK1.8中雖然沒有但是只是把這步運算放到了 put 函數中。我們就看下這個函數實現：

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

為了讓 hash 值能夠對應到現有數組中的位置，我們上篇文章講到一個方法為 取模運算，即?hash % length，得到結果作為角標位置。但是 HashMap 就厲害了，連這一步取模運算的都優化了。我們需要知道一個計算機對于2進制的運算是要快于10進制的，取模算是10進制的運算了，而位與運算就要更高效一些了。

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

小結

通過上邊的分析我們可以到如下結論：

• 在存儲元素之前，HashMap 會對 key 的 hashCode 返回值做進一步擾動函數處理，1.7 中擾動函數使用了 4次位運算 + 5次異或運算，1.8 中降低到 1次位運算 + 1次異或運算

• 擾動處理后的 hash 與 哈希表數組length -1 做位與運算得到最終元素儲存的哈希桶角標位置。

HashMap 的添加元素

敲黑板了，重點來了。對于理解 HashMap 源碼一方面要了解存儲的數據結構，另一方面也要了解具體是如何添加元素的。下面我們就來看下?put(K key, V value)?函數。

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

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

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

由于添加元素中設計邏輯有點復雜，這里引用一張圖來說明，理解

添加元素過程：

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

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

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

4. 如果索引位置的 key 不相同，則需要遍歷單鏈表，如果遍歷過如果有與 key 相同的節點，則保存索引，替換 Value；如果沒有相同節點，則在但單鏈表尾部插入新節點。這里操作與1.7不同，1.7新來的節點總是在數組索引位置，而之前的元素作為下個節點拼接到新節點尾部。

5. 如果插入節點后鏈表的長度大于樹化閾值，則需要將單鏈表轉為紅黑樹。

6. 成功插入節點后，判斷鍵值對個數是否大于擴容閾值，如果大于了則需要再次擴容。至此整個插入元素過程結束。

HashMap 的擴容過程

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

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

相信大家看到擴容的整個函數后對擴容機制應該有所了解了，整體分為兩部分：1. 尋找擴容后數組的大小以及新的擴容閾值，2. 將原有哈希表拷貝到新的哈希表中。

第一部分沒的說，但是第二部分我看的有點懵逼了，但是踩在巨人的肩膀上總是比較容易的，美團的大佬們早就寫過一些有關 HashMap 的源碼分析文章，給了我很大的幫助。在文章的最后我會放出參考鏈接。下面說下我的理解：

JDK 1.8 不像 JDK1.7中會重新計算每個節點在新哈希表中的位置，而是通過?(e.hash & oldCap) == 0是否等于0 就可以得出原來鏈表中的節點在新哈希表的位置。為什么可以這樣高效的得出新位置呢？

因為擴容是容量翻倍，所以原鏈表上的每個節點，可能存放新哈希表中在原來的下標位置， 或者擴容后的原位置偏移量為 oldCap 的位置上，下邊舉個例子 圖片和敘述來自 https://tech.meituan.com/java-hashmap.html：

圖（a）表示擴容前的key1和key2兩種key確定索引位置的示例，圖（b）表示擴容后key1和key2兩種key確定索引位置的示例，其中hash2是key1對應的哈希與高位運算結果。

元素在重新計算hash之后，因為n變為2倍，那么n-1的mask范圍在高位多1bit(紅色)，因此新的index就會發生這樣的變化：

所以在 JDK1.8 中擴容后，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成“原索引+oldCap

另外還需要注意的一點是 HashMap 在 1.7的時候擴容后，鏈表的節點順序會倒置，1.8則不會出現這種情況。

HashMap 其他添加元素的方法

上邊將構造函數的時候埋了個坑即使用：

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

構造函數構建 HashMap 的時候，在這個方法里，除了賦值了默認的加載因子，并沒有調用其他構造方法，而是通過批量添加元素的方法?putMapEntries?來構造了 HashMap。該方法為私有方法，真正批量添加的方法為putAll

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

//同樣第二參數代表是否初次創建?table???final?void?putMapEntries(Map<??extends?K,???extends?V>?m,?boolean?evict)?{????int?s?=?m.size();????if?(s?>?0)?{?????????//如果哈希表為空則初始化參數擴容閾值????????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)//構造方法沒有計算?threshold?默認為0?所以會走擴容函數????????????resize();?????????//將參數中的?map?鍵值對一次添加到?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);????????}????}?}?復制代碼

JDK1.8 中還新增了一個添加方法，該方法調用 putVal 且第4個參數傳了 true，代表只有哈希表中對應的key 的位置上元素為空的時候添加成功，否則返回原來 key 對應的 Value 值。

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

HashMap 查詢元素

分析了完了 put 函數后，接下來讓我們看下 get 函數，當然有 put 函數計算鍵值對在哈希表中位置的索引方法分析的鋪墊后，get 方法就顯得很容容易了。

1. 根據鍵值對的 key 去獲取對應的 Value

public?V?get(Object?key)?{????Node<K,V>?e;????//通過?getNode尋找?key?對應的?Value?如果沒找到，或者找到的結果為?null?就會返回null?否則會返回對應的?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;????//現根據?key?的?hash?值去找到對應的鏈表或者紅黑樹????if?((tab?=?table)?!=?null?&&?(n?=?tab.length)?>?0?&&????????(first?=?tab[(n?-?1)?&?hash])?!=?null)?{????????//?如果第一個節點就是那么直接返回????????if?(first.hash?==?hash?&&?//?always?check?first?node????????????((k?=?first.key)?==?key?||?(key?!=?null?&&?key.equals(k))))????????????return?first;?????????//如果?對應的位置為紅黑樹調用紅黑樹的方法去尋找節點???????????if?((e?=?first.next)?!=?null)?{????????????if?(first?instanceof?TreeNode)????????????????return?((TreeNode<K,V>)first).getTreeNode(hash,?key);?????????????//遍歷單鏈表找到對應的?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;?}?復制代碼

1. JDK 1.8新增 get 方法，在尋找 key 對應 Value 的時候如果沒找大則返回指定默認值

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

HashMap 的刪操作

HashMap?沒有?set?方法，如果想要修改對應 key 映射的 Value ，只需要再次調用?put?方法就可以了。我們來看下如何移除?HashMap?中對應的節點的方法：

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

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

這里有兩個參數需要我們提起注意：

• matchValue 如果這個值為 true 則表示只有當 Value 與第三個參數 Value 相同的時候才刪除對一個的節點

• movable 這個參數在紅黑樹中先刪除節點時候使用 true 表示刪除并其他數中的節點。

?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;????//判斷哈希表是否為空，長度是否大于0?對應的位置上是否有元素????if?((tab?=?table)?!=?null?&&?(n?=?tab.length)?>?0?&&????????(p?=?tab[index?=?(n?-?1)?&?hash])?!=?null)?{????????????????//?node?用來存放要移除的節點，?e?表示下個節點?k?，v?每個節點的鍵值????????Node<K,V>?node?=?null,?e;?K?k;?V?v;????????//如果第一個節點就是我們要找的直接賦值給?node????????if?(p.hash?==?hash?&&????????????((k?=?p.key)?==?key?||?(key?!=?null?&&?key.equals(k))))????????????node?=?p;????????else?if?((e?=?p.next)?!=?null)?{?????????????//?遍歷紅黑樹找到對應的節點????????????if?(p?instanceof?TreeNode)????????????????node?=?((TreeNode<K,V>)p).getTreeNode(hash,?key);????????????else?{?????????????????//遍歷對應的鏈表找到對應的節點????????????????do?{????????????????????if?(e.hash?==?hash?&&????????????????????????((k?=?e.key)?==?key?||?????????????????????????(key?!=?null?&&?key.equals(k))))?{????????????????????????node?=?e;????????????????????????break;????????????????????}????????????????????p?=?e;????????????????}?while?((e?=?e.next)?!=?null);????????????}????????}????????//?如果找到了節點????????//?!matchValue?是否不刪除節點????????//?(v?=?node.value)?==?value?||?????????????????????????????(value?!=?null?&&?value.equals(v)))?節點值是否相同，????????if?(node?!=?null?&&?(!matchValue?||?(v?=?node.value)?==?value?||?????????????????????????????(value?!=?null?&&?value.equals(v))))?{????????????//刪除節點?????????????????????????????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;?}?復制代碼

HashMap 的迭代器

我們都只我們知道 Map 和 Set 有多重迭代方式，對于 Map 遍歷方式這里不展開說了，因為我們要分析迭代器的源碼所以這里就給出一個使用迭代器遍歷的方法：

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

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

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

//?我們來看下?EntrySet?是一個?set?存儲的元素是?Map?的鍵值對?final?class?EntrySet?extends?AbstractSet<Map.Entry<K,V>>?{????//?size?放回?Map?中鍵值對個數????public?final?int?size()?????????????????{?return?size;?}????//清除鍵值對????public?final?void?clear()???????????????{?HashMap.this.clear();?}????//?獲取迭代器????public?final?Iterator<Map.Entry<K,V>>?iterator()?{????????return?new?EntryIterator();????}????????//通過?getNode?方法獲取對一個及對應?key?對應的節點?這里必須傳入????//?Map.Entry?鍵值對類型的對象?否則直接返回?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?方法?刪除節點????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;????}????...?}?復制代碼

//EntryIterator?繼承自?HashIterator?final?class?EntryIterator?extends?HashIterator????implements?Iterator<Map.Entry<K,V>>?{????//?這里可能是因為大家使用適配器的習慣添加了這個?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()?{?????????????//初始化操作數?Fast-fail??????????????expectedModCount?=?modCount;?????????????//?將?Map?中的哈希表賦值給?t?????????????Node<K,V>[]?t?=?table;?????????????current?=?next?=?null;?????????????index?=?0;?????????????//從table?第一個不為空的?index?開始獲取?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();??????????????//如果當前鏈表節點遍歷完了，則取哈希桶下一個不為null的鏈表頭????????????????if?((next?=?(current?=?e).next)?==?null?&&?(t?=?table)?!=?null)?{?????????????????do?{}?while?(index?<?t.length?&&?(next?=?t[index++])?==?null);?????????????}?????????????return?e;?????????}?????????//這里還是調用?removeNode?函數不在贅述?????????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;?????????}?????}?復制代碼

除了?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;?}?}?復制代碼

可以看出無論哪種迭代器都是通過，遍歷 table 表來獲取下個節點，來遍歷的，遍歷過程可以理解為一種深度優先遍歷，即優先遍歷鏈表節點（或者紅黑樹），然后在遍歷其他數組位置。

HashTable 的區別

面試的時候面試官總是問完 HashMap 后會問 HashTable 其實 HashTable 也算是比較古老的類了。翻看 HashTable 的源碼可以發現有如下區別：

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

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

3. HashMap?內部使用hash(Object key)擾動函數對 key 的?hashCode?進行擾動后作為?hash?值。HashTable?是直接使用 key 的?hashCode()?返回值作為 hash 值。

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

5. HashTable?取哈希桶下標是直接用模運算,擴容時新容量是原來的2倍+1。HashMap?在擴容的時候是原來的兩倍，且哈希桶的下標使用 &運算代替了取模。

最后

寫 HashMap 源碼分析的過程，可以說比?ArrayList?或者LinkedList源碼簡直不是一個級別的。個人能力有限，所以在學習的過程中，參考了很多前輩們的分析，也學到了很多東西。這很有用，經過這一波分析我覺得我對面試中的的 HashMap 面試題回答要比以前強很多。對于 HashMap的相關面試題集合

當前題目：帶你搞懂Java中HashMap源碼！
文章網址：http://vcdvsql.cn/article20/gghejo.html

成都網站建設公司_創新互聯，為您提供App開發、自適應網站、網站內鏈、手機網站建設、網站制作、網站建設

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯