HashMap源碼實現分析 一、前言 HashMap 顧名思義，就是用hash表的原理實現的Map介面容器對象，那什麼又是hash表呢。 我們對數組都很熟悉，數組是一個占用連續記憶體的數據結構，學過C的朋友對這一點影響肯定更為深刻。既然是一段連續的記憶體，數組的特點就顯而易見了，一旦你知道要查第幾個數據 ...
HashMap源碼實現分析
一、前言
HashMap 顧名思義，就是用hash表的原理實現的Map介面容器對象，那什麼又是hash表呢。
我們對數組都很熟悉，數組是一個占用連續記憶體的數據結構，學過C的朋友對這一點影響肯定更為深刻。既然是一段連續的記憶體，數組的特點就顯而易見了，一旦你知道要查第幾個數據，時間複雜度就是O(1),但是對於插入操作就很困難；還有一種數據結構你也一定很熟悉，那就是鏈表，鏈表由一組指向（單向或者雙向）的節點連接的數據結構，它的特點是記憶體不連續，查找困難，但是插入刪除都很容易。
那有沒有一種查找容易，插入刪除查找都容易的數據結構呢， 沒錯，它就是hash表。
本篇，我們就來討論：
- HashMap的數據結構實現方式
- HashMap是怎麼做到為get、put操作提供穩定的時間複雜度的
- HashMap什麼時候從單節點轉成鏈表又是什麼時候從鏈表轉成紅黑樹
- HashMap初始化時為什麼要給自定義的初始容量。
- HashMap如何保證容量始終是2的冪
- HashMap為何要保證容量始終是2的冪
- HashMap的hash值如何計算
- HashMap為什麼是線程不安全的
要瞭解HashMap 最好的方式就是看源碼，本篇內容基於Jdk1.8HashMap源碼。
二、HashMap的基本要素
磨刀不誤砍柴功，想瞭解HashMap的原理，必然繞不過HashMap源碼中的以下幾個變數：
- DEFAULT_INITIAL_CAPACITY： 初始容量 1<<4也就是16
- MAXIMUM_CAPACITY：最大容量 1<<30。
- DEFAULT_LOAD_FACTOR：負載因數，預設是0.75。什麼意思呢，比如說你定義了一個初始容量為16的HashMap，當你不斷向裡面添加元素後，最多到初始容量的0.75，HashMap就會觸發擴容操作。
- threshold：下一個觸發擴容操作的閾值，threshold = CAPACITY * LOAD_FACTOR。
- TREEIFY_THRESHOLD：鏈表轉紅黑樹閾值，預設為8，超過8就會執行鏈表轉紅黑樹方法，但是註意轉紅黑樹方法中會判斷當前size是否大於64，只有大於64才轉紅黑樹，否則執行resize()操作。
- UNTREEIFY_THRESHOLD： 紅黑樹轉鏈表閾值，預設為6，顧名思義，紅黑樹節點小於6就會轉成鏈表。
- Node<K, V> implements Map.Entry<K, V> HashMap存放數據的基本單位，裡面存有hash值、key、value、next。
- Node<K, V>[] table：存放Node節點的數組，HashMap最底層數組，數組元素可以為單節點Node、多節點鏈表、多節點紅黑樹。
以上內容，有個印象就好，不必每個都記得。但這些概念對理解HashMap至關重要。
三、正文
3.1 HashMap 數據結構
HashMap的數據結構很簡單，它是一個Node類型的數組，每個元素可以為單節點、多節點鏈表、多節點紅黑樹。關鍵的問題是，這麼簡單的結構怎麼實現的put、get都很快？ 什麼時候從單節點轉成鏈表又是什麼時候從鏈表轉成紅黑樹？
3.1.1 HashMap如何實現put、get操作時間複雜度為O(1)~O(n)?
我們知道，查找一個數組的元素，當我們不知道index的時候，複雜度是很高的，但是當我們知道index的時候，這個複雜度就是O(1)級別的。HashMap使用的就是這個原理。
對於get操作，首先根據key計算出hash值，而這個hash值執行操作(n - 1) & hash後就是它所在的index，在最好的情況下，該index恰好只有一個節點且hash值和key的hash值相同，那麼時間複雜度就是O(1)，當該節點為鏈表或者紅黑樹時，時間複雜度會上升，但是由於HashMap的優化（鏈表長度、紅黑樹長度相對於HashMap容量不會過長，過長會觸發resize操作），所以最壞的情況也就是O(n),可能還會小於這個值。
對於put操作，我們知道，數組插入元素的成本是高昂的，HashMap巧妙的使用鏈表和紅黑樹代替了數組插入元素需要移動後續元素的消耗。這樣在最好的情況下，插入一個元素，該index位置恰好沒有元素的話，時間複雜度就是O(1),當該位置有元素且為鏈表或者紅黑樹的情況下，時間複雜度會上升，但是最壞的情況下也就是O(n)。
3.1.2 HashMap什麼時候從單節點轉成鏈表又是什麼時候從鏈表轉成紅黑樹？
單節點轉鏈表很簡單，當根據新加入的值計算出來的index處有元素時，若元素為單節點，則從節點轉為鏈表。
鏈表轉紅黑樹有兩個條件：
-
鏈表長度大於TREEIFY_THRESHOLD，預設閾值是8
-
HashMap長度大於64
當同時滿足這兩個條件，那麼就會觸發鏈表轉紅黑樹的操作。
3.2 HashMap初始化時為什麼要給自定義的初始容量？
為啥前輩們都要求定義一個HashMap的時候一定要使用構造函數HashMap(int initialCapacity)指定初始容量呢？
在阿裡的《Java開發手冊》中是這樣說明的：
- 【推薦】集合初始化時，指定集合初始值大小。
說明：HashMap 使用 HashMap(int initialCapacity) 初始化，
正例：initialCapacity = (需要存儲的元素個數 / 負載因數) + 1。註意負載因數（即 loader
factor）預設為 0.75，如果暫時無法確定初始值大小，請設置為 16（即預設值）。
反例：HashMap 需要放置 1024 個元素，由於沒有設置容量初始大小，隨著元素不斷增加，容
量 7 次被迫擴大，resize 需要重建 hash 表，嚴重影響性能。
這個問題在HashMap源碼中是顯而易見的，每次put函數中都會檢查當前size是否大於threshold，如果大於就會進行擴容，新容量是原來容量的二倍。那麼問題就來了，當你要存大量數據到HashMap中而又不指定初始容量的話，擴容會被一次接一次的觸發，非常消耗性能。
而初始容量和負載因數給多少好呢，日常開發中如無必要不建議動負載因數，而是根據要使用的HashMap大小確定初始容量，這也不是說為了避免擴容初始容量給的越大越好， 越大申請的記憶體就越大，如果你沒有這麼多數據去存，又會造成hash值過於離散。
3.3 HashMap如何保證容量始終是2的冪
HashMap使用方法tableSizeFor()來保證無論你給值是什麼，返回的一定是2的冪：
static final int tableSizeFor(int cap)
{
int n = cap - 1; // 作用：保證當cap為2的冪時，返回原值而不是二倍，如8 返回8 而不是16
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
首先我們來看操作：
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16
假設 n=01000000, n |= n >>> 1後 n=01100000，n |= n >>> 2後n=01111000,n |= n >>> 4;後n=01111111,我們可以發現，上述5步操作可以將一個32位數第一位為1的後面所有位全變為1。這樣再執行n + 1操作後，該數就必為2的冪次方了。如01111111+1 = 10000000。
那又為什麼要保證一定是2的冪次方呢？不是不行嗎？
3.3.1 HashMap為何要保證容量始終是2的冪
說到這個問題不得不說執行put()方法時，是如何根據hash值在table中定位。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
{
......
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
......
可以看到，它使用了一個 (n - 1) & hash的操作，n為當前hashmap的容量，而容量一定為2的冪次方，n-1的二進位低位都為1，舉例：16=0000000000010000，15=0000000000001111，這樣的處理好處在於，當執行(n - 1) & hash的操作時，元素的位置僅取決於低位而與高位無關（這種無關性隨著HashMap容量的增大而減小），這個邏輯優點是，無論你的hash值有多大，我都鎖定了你的取值範圍小於當前容量，這樣做避免了hash值過於離散的情況，而當HashMap擴容時又可以同時增大hash值的取值範圍，缺點是增加了hash碰撞的可能性，為瞭解決這個問題HashMap修改了hash值的計算方法來增加低位的hash複雜度。
3.3.2 HashMap計算hash值
不廢話，直接上源碼：
static final int hash(Object key)
{
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
hash方法用 key的hash值異或上key的hash值的高16位，為什麼要這樣做呢？
首先，h>>>16 的值高16位都為0，這樣h^(h>>>16)時，高16位的值不會有任何變化，但是低16位的值混雜了key的高16位的值，從而增加了hash值的複雜度，進一步減少了hash值一樣的概率。
3.4 HashMap為什麼是線程不安全的
在Jdk1.7中，造成HashMap線程不安全的原因之一是transfer函數，該函數使用頭查法在多線程的情況下很容易出現閉環鏈表從而導致死迴圈，同時還有數據丟失的問題，Jdk1.8中沒有transfer函數而是在resize函數中完成了HashMap擴容或者初始化操作，resize採用尾插法很好的解決了閉環鏈表的問題，但是依舊避免不了數據覆蓋的問題。
在HashMap的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;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
......
在執行完 if ((tab = table) == null || (n = tab.length) == 0)判斷且為true的情況下，會直接進行賦值，但是在多線程的環境下，當兩個線程同時完成判斷，線程1剛賦值完，線程2再進行賦值，就造成了數據覆蓋的問題。
這隻是最簡單的現象，我們要想線程安全，首先要有多線程安全的處理邏輯，很明顯HashMap是沒有這樣的邏輯的，那麼很多為單線程設計的邏輯就很大可能出問題，所以HashMap為什麼是線程不安全的？它本身設計就不支持多線程下的操作，所以不該有此問。
如果想要線程安全的使用基於hash表的map，可以使用ConcurrentHashMap，該實現get操作是無鎖的，put操作也是分段鎖，性能很好。
所以說術業有專攻，每個容器的實現都有它對應的優缺點。我們需要學會的是分析面對的每一種情況，合理的使用不同的容器去解決問題。
HashMap基本的原理和對應實現就說到這裡了，更深入的話題如：紅黑樹插入節點、平衡紅黑樹、遍歷紅黑樹，可以直接看紅黑樹對應的原理和實現。
需要源碼註釋的請戳這裡源碼解析
公眾號：良許Linux
