HashMap底層實現原理詳解

一、快速入門

示例：有一定基礎的小夥伴們可以選擇性的跳過該步驟

HashMap是Java程序員使用頻率最高的用於映射鍵值對(key和value)處理的數據類型。隨著JDK版本的跟新，JDK1.8對HashMap底層的實現進行瞭優化，列入引入紅黑樹的數據結構和擴容的優化等。本文結合JDK1.7和JDK1.8的區別，深入探討HashMap的數據結構實現和功能原理。
Java為數據結構中的映射定義瞭一個接口java.uti.Map，此接口主要有四個常用的實現類，分別是HashMap，LinkedHashMap，Hashtable，TreeMap，IdentityHashMap。本篇文章主要講解HashMap以及底層實現原理。

1.HashMap的常用方法

//  Hashmap存值：----------------------------------》 .put("key","value")； ----------》無返回值。
//
//  Hashmap取值：----------------------------------》 .get("key")；-------------------》 返回Value的類型。
//
//  Hashmap判斷map是否為空：-----------------------》 .isEmpty()； -------------------》返回boolean類型。
//
//  Hashmap判斷map中是否存在這個key：--------------》.containsKey("key")；------------》返回boolean類型。
//
//  Hashmap判斷map中是否含有value：----------------》.containsValue("value")；-------》返回boolean類型。
//
//  Hashmap刪除這個key值下的value：----------------》.remove("key")；-----------------》返回Value的類型。
//
//  Hashmap顯示所有的value值：---------------------》.values()； --------------------》返回Value的類型。
//
//  Hashmap顯示map裡的值得數量：-------------------》.size()； ----------------------》返回int類型
//
//  HashMap顯示當前已存的key：---------------------》 .keySet()；-------------------》返回Key的類型數組。
//
//  Hashmap顯示所有的key和value：-----------------》.entrySet())；------------------》返回Key=Value類型數組。
//
//  Hashmap添加另一個同一類型的map：--------------》.putAll(map)； -----------------》(參數為另一個同一類型的map)無返回值。
//
//  Hashmap刪除這個key和value：------------------》.remove("key", "value")；-------》(如果該key值下面對應的是該value值則刪除)返回boolean類型。
//
//  Hashmap替換這個key對應的value值(JDK8新增)：---》.replace("key","value")；-------》返回被替換掉的Value值的類型。
//
//  克隆Hashmap：-------------------------------》.clone()； ---------------------》返回object類型。
//
//  清空Hashmap：-------------------------------》.clear()； ---------------------》無返回值。

2.HashMap的幾個重要知識點

• HashMap是無序且不安全的數據結構。
• HashMap 是以key–value對的形式存儲的，key值是唯一的（可以為null），一個key隻能對應著一個value，但是value是可以重復的。
• HashMap 如果再次添加相同的key值，它會覆蓋key值所對應的內容，這也是與HashSet不同的一點，Set通過add添加相同的對象，不會再添加到Set中去。
• HashMap 提供瞭get方法，通過key值取對應的value值，但是HashSet隻能通過迭代器Iterator來遍歷數據，找對象。

二、JDK7與JDK8的HashMap區別

既然講HashMap，那就不得不說一下JDK7與JDK8（及jdk8以後）的HashMap有什麼區別：

• jdk8中添加瞭紅黑樹，當鏈表長度大於等於8的時候鏈表會變成紅黑樹
• 鏈表新節點插入鏈表的順序不同（jdk7是插入頭結點，jdk8因為要把鏈表變為紅 黑樹所以采用插入尾節點）
• hash算法簡化 ( jdk8 )
• resize的邏輯修改（jdk7會出現死循環，jdk8不會）

三、HashMap的容量與擴容機制

1.HashMap的默認負載因子

/**
  * The load factor used when none specified in constructor.
  */
 static final float DEFAULT_LOAD_FACTOR = 0.75f;
 /**
  *默認的負載因子是0.75f,也就是75% 負載因子的作用就是計算擴容閾值用，比如說使用
  *無參構造方法創建的HashMap 對象，他初始長度默認是16 閾值 = 當前長度 * 0.75 就
  *能算出閾值，當當前長度大於等於閾值的時候HashMap就會進行自動擴容
  */

面試的時候，面試官經常會問道一個問題：為什麼HashMap的默認負載因子是0.75，而不是0.5或者是整數1呢？
答案有兩種：

• 閾值(threshold) = 負載因子(loadFactor) x 容量(capacity) 根據HashMap的擴容機制，他會保證容量(capacity)的值永遠都是2的冪 為瞭保證負載因子x容量的結果是一個整數，這個值是0.75(4/3)比較合理，因為這個數和任何2的次冪乘積結果都是整數。
• 理論上來講，負載因子越大，導致哈希沖突的概率也就越大，負載因子越小，費的空間也就越大,這是一個無法避免的利弊關系，所以通過一個簡單的數學推理，可以測算出這個數值在0.75左右是比較合理的

2.HashMap的擴容機制

寫數據之後會可能觸發擴容，HashMap結構內，我記得有一個記錄當前數據量的字段，這個數據量字段到達擴容閾值的話，它就會觸發擴容的操作

閾值(threshold) = 負載因子(loadFactor) x 容量(capacity)
當HashMap中table數組(也稱為桶)長度 >= 閾值(threshold) 就會自動進行擴容。

擴容的規則是這樣的，因為table數組長度必須是2的次方數，擴容其實每次都是按照上一次tableSize位運算得到的就是做一次左移1位運算，
假設當前tableSize是16的話 16轉為二進制再向左移一位就得到瞭32 即 16 << 1 == 32 即擴容後的容量，也就是說擴容後的容量是當前
容量的兩倍，但記住HashMap的擴容是采用當前容量向左位移一位（newtableSize = tableSize << 1），得到的擴容後容量，而不是當前容量x2

問題又來瞭，為什麼計算擴容後容量要采用位移運算呢，怎麼不直接乘以2呢？
這個問題就比較簡單瞭，因為cpu畢竟它不支持乘法運算，所有的乘法運算它最終都是再指令層面轉化為瞭加法實現的，這樣效率很低，如果用位運算的話對cpu來說就非常的簡潔高效。

3.HashMap中散列表數組初始長度

 /**
  * The default initial capacity - MUST be a power of two.
  */
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

 /**
  * HashMap中散列表數組初始長度為 16 (1 << 4)
  * 創建HashMap的時候可以設置初始化容量和設置負載因子，
  * 但HashMap會自動優化設置的初始化容量參數，確保初始化
  * 容量始終為2的冪
  */

老問題又來瞭，為啥HashMap中初始化大小為什麼是16呢？

首先我們看hashMap的源碼可知當新put一個數據時會進行計算位於table數組(也稱為桶)中的下標：

int index =key.hashCode()&(length-1);

hahmap每次擴容都是以 2的整數次冪進行擴容

因為是將二進制進行按位於，(16-1) 是 1111,末位是1，這樣也能保證計算後的index既可以是奇數也可以是偶數，並且隻要傳進來的key足夠分散，均勻那麼按位於的時候獲得的index就會減少重復，這樣也就減少瞭hash的碰撞以及hashMap的查詢效率。

那麼到瞭這裡你也許會問？ 那麼就然16可以，是不是隻要是2的整數次冪就可以呢？

答案是肯定的。那為什麼不是8,4呢？ 因為是8或者4的話很容易導致map擴容影響性能，如果分配的太大的話又會浪費資源，所以就使用16作為初始大小。

四、HashMap的結構

JDK7與JDK8及以後的HashMap結構與存儲原理有所不同：
Jdk1.7：數組 + 鏈表 ( 當數組下標相同，則會在該下標下使用鏈表)
Jdk1.8：數組 + 鏈表 + 紅黑樹 (預值為8 如果鏈表長度 >=8則會把鏈表變成紅黑樹 )
Jdk1.7中鏈表新元素添加到鏈表的頭結點,先加到鏈表的頭節點,再移到數組下標位置
Jdk1.8中鏈表新元素添加到鏈表的尾結點
(數組通過下標索引查詢，所以查詢效率非常高，鏈表隻能挨個遍歷，效率非常低。jdk1.8及以
上版本引入瞭紅黑樹，當鏈表的長度大於或等於8的時候則會把鏈表變成紅黑樹，以提高查詢效率)

五、HashMap存儲原理與存儲流程

1.HashMap存儲原理

• 獲取到傳過來的key，調用hash算法獲取到hash值
• 獲取到hash值之後調用indexFor方法，通過獲取到的hash值以及數組的長度算
• 出數組的下標 (把哈希值和數組容量轉換為二進，再在數組容量范圍內與哈希值
• 進行一次與運算，同為1則1，不然則為0，得出數組的下標值，這樣可以保證計算出的數組下標不會大於當前數組容量)
• 把傳過來的key和value存到該數組下標當中。
• 如該數組下標下以及有值瞭，則使用鏈表，jdk7是把新增元素添加到頭部節點 jdk8則添加到尾部節點。

2.HashMap存儲流程

前面尋址算法都是一樣的，根據key的hashcode經過高低位異或之後的值，再按位與 &(table.lingth – 1),得到一個數組下標，然後根據這個數組下標內的狀況，狀況不同，然後情況也不同，大概分為瞭4種狀態：

( 1.)第一種就是數組下標下內容為空：
這種情況沒什麼好說的，為空據直接占有這個slot槽位就好瞭，然後把當前.put方法傳進來的key和value包裝成一個node對象,放到這個slot中就好瞭。

( 2.)第二種情況就是數組下標下內容不為空，但它引用的node還沒有鏈化：
這種情況下先要對比一下這個node對象的key與當前put對象的key是否完全.相等，如果完全相等的情況下，就行進行replace操作，把之前的槽位中node.下的value替換成新的value就可以瞭，否則的話這個put操作就是一個正兒.八經的hash沖突,這種情況在slot槽位後面追加一個node就可以瞭,用尾插法 ( 前面講過，jdk7是把新增元素添加到頭部節點，而jdk8則添加到尾部節點)。

( 3.)第三種就是該數組下標下內容已經被鏈化瞭：
這種情況和第二種情況處理很相似，首先也是迭代查找node，看看鏈表上中元素的key，與當前傳過來的key是否完全一致，如果完全一致的話還是repleace操作，用put過來的新value替換掉之前node中的value，否則的話就是一致迭代到鏈表尾節點也沒有匹配到完全一致的node，就和之前的一樣，把put進來數據包裝成node追加到鏈表的尾部，再檢查一下當前鏈表的長度，有沒有達到樹化閾值，如果達到瞭閾值就調用一個樹化方法，樹化操作都是在這個方法裡完成的。

( 4.)第四種情況就是沖突很嚴重的情況下，這個鏈表已經轉化成紅黑樹瞭：
紅黑樹就比較復雜 要將清楚這個紅黑樹還得從TreeNode說起 TreeNode繼承瞭Node結構，在Node基礎上加瞭幾個字段，分別是指向父節點parent字段，指向左子節點left字段，指向右子節點right字段，還有一個表示顏色的red字段，這就是TreeNode的基本結構，然後紅黑樹的插入操作，首先找到一個合適的插入點，就是找到插入節點的父節點，然後紅黑樹它又滿足二叉樹的所有特性，所以找這個父節點的操作和二叉樹排序是完全一致的，然後說一下這個二叉樹排序，其實就是二分查找算法映射出來的結構，就是一個倒立的二叉樹，然後每個節點都可以有自己的子節點，本且左節點小於但前節點，右節點大於當前節點，然後每次向下查找一層就能那個排除掉一半的數據，查找效率非常的高效，當查找的過程中也是分情況的。

首先第一種情況就是一直向下探測，直到查詢到左子樹或者右子樹位null，說明整個樹中，並沒有發現node鏈表中的key與當前put key一致的TreeNode,那此時探測節點就是插入父節點的所在瞭，然後就是判斷插入節點的hash值和父節點的hash值大小決定插入到父節點的左子樹還是右子樹。當然插入會打破平衡，還需要一個紅黑樹的平衡算法保持平衡。

其次第二種情況就是根節點在向下探測過程中發現TreeNode中key與當前put的key完全一致，然後就也是一次repleace操作，替換value。

六、jdk8中HashMap為什麼要引入紅黑樹？

其實主要就是為瞭解決jdk1.8以前hash沖突所導致的鏈化嚴重的問題，因為鏈表結構的查詢效率是非常低的，他不像數組，能通過索引快速找到想要的值，鏈表隻能挨個遍歷，當hash沖突非常嚴重的時候，鏈表過長的情況下，就會嚴重影響查詢性能，本身散列列表最理想的查詢效率為O(1)，當時鏈化後鏈化特別嚴重，他就會導致查詢退化為O(n)為瞭解決這個問題所以jdk8中的HashMap添加瞭紅黑樹來解決這個問題，當鏈表長度>=8的時候鏈表就會變成紅黑樹，紅黑樹其實就是一顆特殊的二叉排序樹嘛，這個時間復雜…反正就是要比列表強很多

七、擴容後的新table數組，那老數組中的這個數據怎麼遷移呢

遷移其實就是挨個桶位推進遷移，就是一個桶位一個桶位的處理，主要還是看當前處理桶位的數據狀態把，這裡也是分瞭大概四種狀態：
這四種的遷移規則都不太一樣

(1.)第一種就是數組下標下內容為空：
這種情況下就沒什麼可說的，不用做什麼處理。

( 2.)第二種情況就是數組下標下內容不為空，但它引用的node還沒有鏈化：
當slot它不為空，但它引用的node還沒有鏈化的時候，說明這個槽位它沒有發生過hash沖突，直接遷移就好瞭，根據新表的tableSize計算出他在新表的位置,然後存放進去就好瞭。

( 3.)第三種就是slot內儲存瞭一個鏈化的node：
當node中next字段它不為空，說明槽位發生過hash沖突，這個時候需要把當前槽位中保存的這個鏈表拆分成兩個鏈表，分別是高位鏈和低位鏈

(4.)第四種就是該槽位儲存瞭一個紅黑樹的根節點TreeNode對象：
這個就很復雜瞭，本文章暫時不做過多的介紹（博主還沒整明白 =_=! ）

到此這篇關於HashMap底層實現原理詳解的文章就介紹到這瞭,更多相關HashMap底層實現原理內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：

• JDK8中的HashMap初始化和擴容機制詳解
• 深入理解Java中的HashMap
• Java京東面試題之為什麼HashMap線程不安全
• Java詳細分析講解HashMap
• 解析HashMap中的put方法執行流程