HashMap 源碼分析
前幾篇分析了
ArrayList
LinkedList
Vector
Stack
HashMap
HashMap
HashMap
- 了解底層如何存儲資料的
- HashMap 的幾個主要方法
- HashMap 是如何确定元素存儲位置的以及如何處理哈希沖突的
- HashMap 擴容機制是怎樣的
- JDK 1.8 在擴容和解決哈希沖突上對 HashMap 源碼做了哪些改動？有什麼好處?
本文也将從以上幾個方面來展開叙述：
由于掘金背景稽核可能會由于某些原因造成文章釋出延遲或者遺漏，如果感覺我寫的源碼分析文章還不錯，可以關注我，以後我每次更新文章就可以收到推送了。另外部落客也是在努力進步中，所有文章如果有問題請盡管留言給我。我會及時改正。大家一起進步。
概述
為了友善下邊的叙述這裡需要先對幾個常見的關于
HashMap
的知識點進行下概述：
-
HashMap
HashMap
equals()
-
HashMap
hashCode()
hashCode(）
hashCode
-
HashMap
-
HashMap
-
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采用「拉鍊法」來存儲資料，即數組和連結清單結合的方式：
「拉鍊法」用專業點的名詞來說叫做鍊位址法。簡單來說，就是數組加連結清單的結合。在每個數組元素上存儲的都是一個連結清單。
我們之前說到不同的 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
HashMap
- 加載因子(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 新增的紅黑樹節點
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
大家可能疑惑 Float.isNaN()
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; } 複制代碼 由于添加元素中設計邏輯有點複雜，這裡引用一張圖來說明，了解
添加元素過程：
- 如果
Node[] table
- 計算對應的鍵值對在 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 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确定索引位置的示例，其中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-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 方法就顯得很容容易了。
- 根據鍵值對的 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; } 複制代碼 - 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 的源碼可以發現有如下差別：
-
HashMap
-
HashMap
HashTable
-
HashMap
hash(Object key)
hashCode
hash
HashTable
hashCode()
-
HashMap
HashTable
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)