Java之HashMap解剖學
- 2019 年 10 月 8 日
- 筆記
「 做知識的搬運工，奮鬥在知識共享的道路上」 —— 23號老闆
文章部分內容摘自dreamcatcher-cx、feigeswjtu，在此鳴謝。
什麼是HashMap
在討論哈希表之前，我們先大概了解下其他數據結構在新增，查找等基礎操作執行性能
數組：採用一段連續的存儲單元來存儲數據。對於指定下標的查找，時間複雜度為O(1)；通過給定值進行查找，需要遍曆數組，逐一比對給定關鍵字和數組元素，時間複雜度為O(n)，當然，對於有序數組，則可採用二分查找，插值查找，斐波那契查找等方式，可將查找複雜度提高為O(logn)；對於一般的插入刪除操作，涉及到數組元素的移動，其平均複雜度也為O(n)
線性鏈表：對於鏈表的新增，刪除等操作（在找到指定操作位置後），僅需處理結點間的引用即可，時間複雜度為O(1)，而查找操作需要遍歷鏈表逐一進行比對，複雜度為O(n)
二叉樹：對一棵相對平衡的有序二叉樹，對其進行插入，查找，刪除等操作，平均複雜度均為O(logn)。
哈希表：相比上述幾種數據結構，在哈希表中進行添加，刪除，查找等操作，性能十分之高，不考慮哈希衝突的情況下，僅需一次定位即可完成，時間複雜度為O(1)，接下來我們就來看看哈希表是如何實現達到驚艷的常數階O(1)的。
我們知道，數據結構的物理存儲結構只有兩種：順序存儲結構和鏈式存儲結構（像棧，隊列，樹，圖等是從邏輯結構去抽象的，映射到記憶體中，也這兩種物理組織形式），而在上面我們提到過，在數組中根據下標查找某個元素，一次定位就可以達到，哈希表利用了這種特性，哈希表的主幹就是數組。
比如我們要新增或查找某個元素，我們通過把當前元素的關鍵字 通過某個函數映射到數組中的某個位置，通過數組下標一次定位就可完成操作。
存儲位置 = f(關鍵字)
其中，這個函數f一般稱為哈希函數，這個函數的設計好壞會直接影響到哈希表的優劣。舉個例子，比如我們要在哈希表中執行插入操作：
查找操作同理，先通過哈希函數計算出實際存儲地址，然後從數組中對應地址取出即可。
哈希衝突
然而萬事無完美，如果兩個不同的元素，通過哈希函數得出的實際存儲地址相同怎麼辦？也就是說，當我們對某個元素進行哈希運算，得到一個存儲地址，然後要進行插入的時候，發現已經被其他元素佔用了，其實這就是所謂的哈希衝突，也叫哈希碰撞。前面我們提到過，哈希函數的設計至關重要，好的哈希函數會儘可能地保證 計算簡單和散列地址分布均勻,但是，我們需要清楚的是，數組是一塊連續的固定長度的記憶體空間，再好的哈希函數也不能保證得到的存儲地址絕對不發生衝突。那麼哈希衝突如何解決呢？哈希衝突的解決方案有多種:開放定址法（發生衝突，繼續尋找下一塊未被佔用的存儲地址），再散列函數法，鏈地址法，而HashMap即是採用了鏈地址法，也就是數組+鏈表的方式。
HashMap是基於哈希表的Map介面的非同步實現。此實現提供所有可選的映射操作，並允許使用null值和null鍵。此類不保證映射的順序，特別是它不保證該順序恆久不變。
HashMap的數據結構 在Java程式語言中，最基本的結構就是兩種，一個是數組，另外一個是模擬指針（引用），所有的數據結構都可以用這兩個基本結構來構造的，HashMap也不例外。HashMap實際上是一個「鏈表散列」的數據結構，即數組和鏈表的結合體。
文字描述永遠要配上圖才能更好的講解數據結構，HashMap的結構圖如下。
從上圖中可以看出，HashMap底層就是一個數組結構，數組中的每一項又是一個鏈表或者紅黑樹。 當新建一個HashMap的時候，就會初始化一個數組。
下面先通過大概看下HashMap的核心成員。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { // 默認容量，默認為16，必須是2的冪 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 最大容量，值是2^30 static final int MAXIMUM_CAPACITY = 1 << 30 // 裝載因子，默認的裝載因子是0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 解決衝突的數據結構由鏈錶轉換成樹的閾值，默認為8 static final int TREEIFY_THRESHOLD = 8; // 解決衝突的數據結構由樹轉換成鏈表的閾值，默認為6 static final int UNTREEIFY_THRESHOLD = 6; /* 當桶中的bin被樹化時最小的hash表容量。 * 如果沒有達到這個閾值，即hash表容量小於MIN_TREEIFY_CAPACITY，當桶中bin的數量太多時會執行resize擴容操作。 * 這個MIN_TREEIFY_CAPACITY的值至少是TREEIFY_THRESHOLD的4倍。 */ static final int MIN_TREEIFY_CAPACITY = 64; static class Node<K,V> implements Map.Entry<K,V> { //... } // 存儲數據的數組 transient Node<K,V>[] table; // 遍歷的容器 transient Set<Map.Entry<K,V>> entrySet; // Map中KEY-VALUE的數量 transient int size; /** * 結構性變更的次數。 * 結構性變更是指map的元素數量的變化，比如rehash操作。 * 用於HashMap快速失敗操作，比如在遍歷時發生了結構性變更，就會拋出ConcurrentModificationException。 */ transient int modCount; // 下次resize的操作的size值。 int threshold; // 負載因子，resize後容量的大小會增加現有size * loadFactor final float loadFactor; }
HashMap的初始化
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // 其他值都是默認值 }
通過源碼可以看出初始化時並沒有初始化數組table，那隻能在put操作時放入了，為什麼要這樣做？估計是避免初始化了HashMap之後不使用反而佔用記憶體吧，哈哈哈。
HashMap的存儲操作
public V put(K key, V value) { return putVal(hash(key), key, value, false, true); }
下面我們詳細講一下HashMap是如何確定數組索引的位置、進行put操作的詳細過程以及擴容機制(resize)
hash計算，確定數組索引位置
不管增加、刪除、查找鍵值對，定位到哈希桶數組的位置都是很關鍵的第一步。前面說過HashMap的數據結構是數組和鏈表的結合，所以我們當然希望這個HashMap裡面的元素位置盡量分布均勻些，盡量使得每個位置上的元素數量只有一個，那麼當我們用hash演算法求得這個位置的時候，馬上就可以知道對應位置的元素就是我們要的，不用遍歷鏈表，大大優化了查詢的效率。HashMap定位數組索引位置，直接決定了hash方法的離散性能。
看下源碼的實現:
static final int hash(Object key) { //jdk1.8 int h; // h = key.hashCode() 為第一步 取hashCode值 // h ^ (h >>> 16) 為第二步 高位參與運算 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
通過hashCode()的高16位異或低16位實現的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度、功效、品質來考慮的，這麼做可以在數組table的length比較小的時候，也能保證考慮到高低Bit都參與到Hash的計算中，同時不會有太大的開銷。
大家都知道上面程式碼里的key.hashCode()函數調用的是key鍵值類型自帶的哈希函數，返回int型散列值。 理論上散列值是一個int型，如果直接拿散列值作為下標訪問HashMap主數組的話，考慮到2進位32位帶符號的int表值範圍從‑2147483648到2147483648。前後加起來大概40億的映射空間。
只要哈希函數映射得比較均勻鬆散，一般應用是很難出現碰撞的。但問題是一個40億長度的數組，記憶體是放不下的。你想，HashMap擴容之前的數組初始大小才16。所以這個散列值是不能直接拿來用的。用之前還要先做對數組的長度取模運算，得到的餘數才能用來訪問數組下標。源碼中模運算是在這個indexFor( )函數里完成。
bucketIndex = indexFor(hash, table.length); //indexFor的程式碼也很簡單，就是把散列值和數組長度做一個"與"操作， static int indexFor(int h, int length) { return h & (length-1); }
順便說一下，這也正好解釋了為什么HashMap的數組長度要取2的整次冪。因為這樣（數組長度‑1）正好相當於一個「低位掩碼」。「與」操作的結果就是散列值的高位全部歸零，只保留低位值，用來做數組下標訪問。以初始長度16為例，16‑1=15。2進位表示是00000000 0000000000001111。和某散列值做「與」操作如下，結果就是截取了最低的四位值。
10100101 11000100 00100101 & 00000000 00000000 00001111 ---------------------------------- 00000000 00000000 00000101 //高位全部歸零，只保留末四位
但這時候問題就來了，這樣就算我的散列值分布再鬆散，要是只取最後幾位的話，碰撞也會很嚴重。更要命的是如果散列本身做得不好，分布上成等差數列的漏洞，恰好使最後幾個低位呈現規律性重複，就無比蛋疼。這時候「擾動函數」的價值就出來了，說到這大家應該都明白了，看下圖。
右位移16位，正好是32bit的一半，自己的高半區和低半區做異或，就是為了混合原始哈希碼的高位和低位，以此來加大低位的隨機性。而且混合後的低位摻雜了高位的部分特徵，這樣高位的資訊也被變相保留下來。
putVal方法
HashMap的put方法執行過程可以通過下圖來理解，自己有興趣可以去對比源碼更清楚地研究學習。
源碼以及解釋如下:
// 真正的put操作 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沒有初始化，或者初始化的大小為0，進行resize操作 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 如果hash值對應的桶內沒有數據，直接生成結點並且把結點放入桶中 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); // 如果hash值對應的桶內有數據解決衝突，再放入桶中 else { Node<K,V> e; K k; //判斷put的元素和已經存在的元素是相同(hash一致，並且equals返回true) if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // put的元素和已經存在的元素是不相同(hash一致，並且equals返回true) // 如果桶內元素的類型是TreeNode，也就是解決hash解決衝突用的樹型結構，把元素放入樹種 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 桶內元素的類型不是TreeNode，而是鏈表時，把數據放入鏈表的最後一個元素上 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 如果鏈表的長度大於轉換為樹的閾值(TREEIFY_THRESHOLD)，將存儲元素的數據結構變更為樹 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 如果查已經存在key，停止遍歷 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 已經存在元素時 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 如果K-V數量大於閾值，進行resize操作 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
擴容機制
HashMap的擴容機制用的很巧妙，以最小的性能來完成擴容。 擴容後的容量就變成了變成了之前容量的2倍，初始容量為16，所以經過rehash之後，元素的位置要麼是在原位置，要麼是在原位置再向高下標移動上次容量次數的位置，也就是說如果上次容量是16，下次擴容後容量變成了16+16，如果一個元素在下標為7的位置，下次擴容時，要不還在7的位置，要不在7+16的位置。
我們下面來解釋一下Java8的擴容機制是怎麼做到的？ n為table的長度，圖（a）表示擴容前的key1和key2兩種key確定索引位置的示例，圖（b）表示擴容後key1和key2兩種key確定索引位置的示例，其中hash1是key1對應的哈希與高位運算結果。
元素在重新計算hash之後，因為n變為2倍，那麼n-1的mask範圍在高位多1bit(紅色)，因此新的index就會發生這樣的變化：
因此，我們在擴充HashMap的時候，不需要像JDK1.7的實現那樣重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就好了，是0的話索引沒變，是1的話索引變成「原索引+oldCap」，可以看看下圖為16擴充為32的resize示意圖：
而hash值的高位是否為1，只需要和擴容後的長度做與操作就可以了，因為擴容後的長度為2的次冪，所以高位必為1，低位必為0，如10000這種形式，源碼中有e.hash & oldCap來做到這個邏輯。
這個設計確實非常的巧妙，既省去了重新計算hash值的時間，而且同時，由於新增的1bit是0還是1可以認為是隨機的，因此resize的過程，均勻的把之前的衝突的節點分散到新的bucket了。這一塊就是JDK1.8新增的優化點。有一點注意區別，JDK1.7中rehash的時候，舊鏈表遷移新鏈表的時候，如果在新表的數組索引位置相同，則鏈表元素會倒置，但是從上圖可以看出，JDK1.8不會倒置。 下面是JDK1.8的resize源碼，寫的很贊，如下:
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; // 計算新的容量值和下一次要擴展的容量 if (oldCap > 0) { // 超過最大值就不再擴充了，就只好隨你碰撞去吧 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 } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 計算新的resize上限 if (newThr == 0) { float ft = (float)newCap * loadFactor; 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) { // 把每個bucket都移動到新的buckets中 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; //如果位置上沒有元素，直接為null if ((e = oldTab[j]) != null) { oldTab[j] = null; //如果只有一個元素，新的hash計算後放入新的數組中 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 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; //hash碰撞後高位為0，放入低Hash值的鏈表中 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } //hash碰撞後高位為1，放入高Hash值的鏈表中 else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 低hash值的鏈表放入數組的原始位置 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // 高hash值的鏈表放入數組的原始位置 + 原始容量 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
HashMap的數組長度一定保持2的次冪，比如16的二進位表示為 10000，那麼length-1就是15，二進位為01111，同理擴容後的數組長度為32，二進位表示為100000，length-1為31，二進位表示為011111。從下圖可以我們也能看到這樣會保證低位全為1，而擴容後只有一位差異，也就是多出了最左位的1，這樣在通過 h&(length-1)的時候，只要h對應的最左邊的那一個差異位為0，就能保證得到的新的數組索引和老數組索引一致(大大減少了之前已經散列良好的老數組的數據位置重新調換)，個人理解。
還有，數組長度保持2的次冪，length-1的低位都為1，會使得獲得的數組索引index更加均勻，比如：
我們看到，上面的&運算，高位是不會對結果產生影響的（hash函數採用各種位運算可能也是為了使得低位更加散列），我們只關注低位bit，如果低位全部為1，那麼對於h低位部分來說，任何一位的變化都會對結果產生影響，也就是說，要得到index=21這個存儲位置，h的低位只有這一種組合。這也是數組長度設計為必須為2的次冪的原因。
如果不是2的次冪，也就是低位不是全為1此時，要使得index=21，h的低位部分不再具有唯一性了，哈希衝突的幾率會變的更大，同時，index對應的這個bit位無論如何不會等於1了，而對應的那些數組位置也就被白白浪費了。
