HashMap 源碼分析
前幾篇分析了 ArrayList
, LinkedList
,Vector
,Stack
List 集合的源碼,Java 容器除了包含 List 集合外還包含著 Set 和 Map 兩個重要的集合類型。而 HashMap
則是最具有代表性的,也是我們最常使用到的 Map 集合。我們這篇文章就來試著分析下 HashMap
的源碼,由于 HashMap
底層涉及到太多方面,一篇文章總是不能面面俱到,所以我們可以帶著面試官常問的幾個問題去看源碼:
- 了解底層如何存儲數據的
- HashMap 的幾個主要方法
- HashMap 是如何確定元素存儲位置的以及如何處理哈希沖突的
- HashMap 擴容機制是怎樣的
- JDK 1.8 在擴容和解決哈希沖突上對 HashMap 源碼做了哪些改動?有什么好處?
本文也將從以上幾個方面來展開敘述:
由于掘金后臺審核可能會由于某些原因造成文章發布延遲或者遺漏,如果感覺我寫的源碼分析文章還不錯,可以關注我,以后我每次更新文章就可以收到推送了。另外博主也是在努力進步中,所有文章如果有問題請盡管留言給我。我會及時改正。大家一起進步。
概述
為了方便下邊的敘述這里需要先對幾個常見的關于 HashMap
的知識點進行下概述:
-
HashMap
存儲數據是根據鍵值對存儲數據的,并且存儲多個數據時,數據的鍵不能相同,如果相同該鍵之前對應的值將被覆蓋。注意如果想要保證HashMap
能夠正確的存儲數據,請確保作為鍵的類,已經正確覆寫了equals()
方法。 -
HashMap
存儲數據的位置與添加數據的鍵的hashCode()
返回值有關。所以在將元素使用 HashMap 存儲的時候請確保你已經按照要求重寫了hashCode()
方法。這里說有關系代表最終的存儲位置不一定就是hashCode
的返回值。 -
HashMap
最多只允許一條存儲數據的鍵為 null,可允許多條數據的值為 null。 -
HashMap
存儲數據的順序是不確定的,并且可能會因為擴容導致元素存儲位置改變。因此遍歷順序是不確定的。 -
HashMap
是線程不安全的,如果需要再多線程的情況下使用可以用Collections.synchronizedMap(Map map)
方法使HashMap
具有線程安全的能力,或者使用ConcurrentHashMap
。
了解 HashMap 底層如何存儲數據的
要想分析 HashMap 源碼,就必須在 JDK1.8 和 JDK1.7之間劃分一條線,因為在 JDK 1.8 后對于 HashMap 做了底層實現的改動。
JDK 1.7 之前的存儲結構
通過上篇文章搞懂 Java equals 和 hashCode 方法 我們以及對 hash 表有所了解,我們了解到及時 hashCode() 方法已經寫得很完美了,終究還是有可能導致 「hash碰撞」的,HashMap
作為使用 hash 值來決定元素存儲位置的集合也是需要處理 hash 沖突的。在1.7之前JDK采用「拉鏈法」來存儲數據,即數組和鏈表結合的方式:
「拉鏈法」用專業點的名詞來說叫做鏈地址法。簡單來說,就是數組加鏈表的結合。在每個數組元素上存儲的都是一個鏈表。
我們之前說到不同的 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 源碼中分析的文章一般都會提及幾個重要的概念:
重要參數
-
哈希桶(buckets):在 HashMap 的注釋里使用哈希桶來形象的表示數組中每個地址位置。注意這里并不是數組本身,數組是裝哈希桶的,他可以被稱為哈希表。
-
初始容量(initial capacity) : 這個很容易理解,就是哈希表中哈希桶初始的數量。如果我們沒有通過構造方法修改這個容量值默認為
DEFAULT_INITIAL_CAPACITY = 1<<4
即16。值得注意的是為了保證 HashMap 添加和查找的高效性,HashMap
的容量總是 2^n 的形式。 -
加載因子(load factor):加載因子是哈希表(散列表)在其容量自動增加之前被允許獲得的最大數量的度量。當哈希表中的條目數量超過負載因子和當前容量的乘積時,散列表就會被重新映射(即重建內部數據結構),重新創建的散列表容量大約是之前散列表哈系統桶數量的兩倍。默認加載因子(0.75)在時間和空間成本之間提供了良好的折衷。加載因子過大會導致很容易鏈表過長,加載因子很小又容易導致頻繁的擴容。所以不要輕易試著去改變這個默認值。
-
擴容閾值(threshold):其實在說加載因子的時候已經提到了擴容閾值了,擴容閾值 = 哈希表容量 * 加載因子。哈希表的鍵值對總數 = 所有哈希桶中所有鏈表節點數的加和,擴容閾值比較的是是鍵值對的個數而不是哈希表的數組中有多少個位置被占了。
-
樹化閥值(TREEIFY_THRESHOLD) :這個參數概念是在 JDK1.8后加入的,它的含義代表一個哈希桶中的節點個數大于該值(默認為8)的時候將會被轉為紅黑樹行存儲結構。
-
非樹化閥值(UNTREEIFY_THRESHOLD): 與樹化閾值相對應,表示當一個已經轉化為數形存儲結構的哈希桶中節點數量小于該值(默認為 6)的時候將再次改為單鏈表的格式存儲。導致這種操作的原因可能有刪除節點或者擴容。
-
最小樹化容量(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 新增的紅黑樹節點,這里不做展開敘述,有興趣的朋友可以查看 HashMap 在 JDK 1.8 后新增的紅黑樹結構這篇文章來了解一下 JDK1.8對于紅黑樹的操作。
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {TreeNode<K,V> parent; // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev; // needed to unlink next upon deletionboolean 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取模。我們根據圖片來看一個具體的例子:
圖片來自:https://tech.meituan.com/java-hashmap.html 侵刪。
小結
通過上邊的分析我們可以到如下結論:
- 在存儲元素之前,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 1sttreeifyBin(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所指節點 Valueif (e != null) { // existing mapping for keyV oldValue = e.value//保存原來的 Value 作為返回值// onlyIfAbsent 一般為 false 所以替換原來的 Valueif (!onlyIfAbsent || oldValue == null)e.value = value;//這個方法在 HashMap 中是空實現,在 LinkedHashMap 中有關系 afterNodeAccess(e);return oldValue;}}//操作數增加++modCount;//如果 size 大于擴容閾值則表示需要擴容if (++size > threshold)resize();afterNodeInsertion(evict);return null;
}
復制代碼
由于添加元素中設計邏輯有點復雜,這里引用一張圖來說明,理解
圖片來來自:https://tech.meituan.com/java-hashmap.html
添加元素過程:
- 如果
Node[] table
表為 null ,則表示是第一次添加元素,講構造函數也提到了,及時構造函數指定了期望初始容量,在第一次添加元素的時候也為空。這時候需要進行首次擴容過程。 - 計算對應的鍵值對在 table 表中的索引位置,通過
i = (n - 1) & hash
獲得。 - 判斷索引位置是否有元素如果沒有元素則直接插入到數組中。如果有元素且key 相同,則覆蓋 value 值,這里判斷是用的 equals 這就表示要正確的存儲元素,就必須按照業務要求覆寫 key 的 equals 方法,上篇文章我們也提及到了該方法重要性。
- 如果索引位置的 key 不相同,則需要遍歷單鏈表,如果遍歷過如果有與 key 相同的節點,則保存索引,替換 Value;如果沒有相同節點,則在但單鏈表尾部插入新節點。這里操作與1.7不同,1.7新來的節點總是在數組索引位置,而之前的元素作為下個節點拼接到新節點尾部。
- 如果插入節點后鏈表的長度大于樹化閾值,則需要將單鏈表轉為紅黑樹。
- 成功插入節點后,判斷鍵值對個數是否大于擴容閾值,如果大于了則需要再次擴容。至此整個插入元素過程結束。
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 thresholdnewCap = oldThr;else {// 空參數構造會走這里初始化容量,和擴容閾值 分別是 16 和 12newCap = 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_VALUEnewThr = (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;elseloTail.next = e;loTail = e;}//高位也是相同的邏輯else {if (hiTail == null)hiHead = e;elsehiTail.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確定索引位置的示例,其中hash1是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-sizefloat 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 方法就顯得很容容易了。
- 根據鍵值對的 key 去獲取對應的 Value
public V get(Object key) {Node<K,V> e;//通過 getNode尋找 key 對應的 Value 如果沒找到,或者找到的結果為 null 就會返回null 否則會返回對應的 Valuereturn (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;
}
復制代碼
- 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為truereturn 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;//如果第一個節點就是我們要找的直接賦值給 nodeif (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;elsep.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、valueMap.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 鍵值對類型的對象 否則直接返回 falsepublic 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 HashIteratorimplements 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 returnNode<K,V> current; // current entryint expectedModCount; // for fast-failint index; // current slotHashIterator() {//初始化操作數 Fast-fail expectedModCount = modCount;// 將 Map 中的哈希表賦值給 tNode<K,V>[] t = table;current = next = null;index = 0;//從table 第一個不為空的 index 開始獲取 entryif (t != null && size > 0) { // advance to first entrydo {} 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 HashIteratorimplements Iterator<K> {public final K next() { return nextNode().key; }
}final class ValueIterator extends HashIteratorimplements Iterator<V> {public final V next() { return nextNode().value; }
}
復制代碼
可以看出無論哪種迭代器都是通過,遍歷 table 表來獲取下個節點,來遍歷的,遍歷過程可以理解為一種深度優先遍歷,即優先遍歷鏈表節點(或者紅黑樹),然后在遍歷其他數組位置。
HashTable 的區別
面試的時候面試官總是問完 HashMap 后會問 HashTable 其實 HashTable 也算是比較古老的類了。翻看 HashTable 的源碼可以發現有如下區別:
-
HashMap
是線程不安全的,HashTable是線程安全的。 -
HashMap
允許 key 和 Vale 是 null,但是只允許一個 key 為 null,且這個元素存放在哈希表 0 角標位置。HashTable
不允許key、value 是 null -
HashMap
內部使用hash(Object key)
擾動函數對 key 的hashCode
進行擾動后作為hash
值。HashTable
是直接使用 key 的hashCode()
返回值作為 hash 值。 -
HashMap
默認容量為 2^4 且容量一定是 2^n ;HashTable
默認容量是11,不一定是 2^n -
HashTable
取哈希桶下標是直接用模運算,擴容時新容量是原來的2倍+1。HashMap
在擴容的時候是原來的兩倍,且哈希桶的下標使用 &運算代替了取模。
參考
- JDK 1.7 & 1.8 HashMap & HashTable 源碼
- 美團技術團隊博客 :Java 8系列之重新認識HashMap
- 美團大佬張旭童 :面試必備:HashMap源碼解析(JDK8)
- 張拭心 CSDN 博客 Java 集合深入理解(16):HashMap 主要特點和關鍵方法源碼解讀
- Carson_Ho CSDN 博客 Java源碼分析:關于 HashMap 1.8 的重大更新
- HashMap 源碼詳細分析(JDK1.8)
- 集合番@HashMap一文通(1.7版)
最后
寫 HashMap 源碼分析的過程,可以說比 ArrayList
或者LinkedList
源碼簡直不是一個級別的。個人能力有限,所以在學習的過程中,參考了很多前輩們的分析,也學到了很多東西。這很有用,經過這一波分析我覺得我對面試中的的 HashMap 面試題回答要比以前強很多。對于 HashMap的相關面試題集合番@HashMap一文通(1.7版) 這篇文章末尾較全面的總結。另外 HashMap 的多線程會導致循環鏈表的情況,大家可以參考 Java 8系列之重新認識HashMap 寫的非常好。大家可以原博客去查看。