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
有識訓？希望老鐵們來個三連擊，給更多的人看到這篇文章
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/27112.html
標籤：Linux