一、快速入門

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

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

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里的值得數(shù)量：-------------------》.size()； ----------------------》返回int類型
//
//  HashMap顯示當前已存的key：---------------------》 .keySet()；-------------------》返回Key的類型數(shù)組。
//
//  Hashmap顯示所有的key和value：-----------------》.entrySet())；------------------》返回Key=Value類型數(shù)組。
//
//  Hashmap添加另一個同一類型的map：--------------》.putAll(map)； -----------------》(參數(shù)為另一個同一類型的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是無序且不安全的數(shù)據(jù)結(jié)構(gòu)。
• HashMap 是以key–value對的形式存儲的，key值是唯一的（可以為null），一個key只能對應著一個value，但是value是可以重復的。
• HashMap 如果再次添加相同的key值，它會覆蓋key值所對應的內(nèi)容，這也是與HashSet不同的一點，Set通過add添加相同的對象，不會再添加到Set中去。
• HashMap 提供了get方法，通過key值取對應的value值，但是HashSet只能通過迭代器Iterator來遍歷數(shù)據(jù)，找對象。

二、JDK7與JDK8的HashMap區(qū)別

既然講HashMap，那就不得不說一下JDK7與JDK8（及jdk8以后）的HashMap有什么區(qū)別：

• jdk8中添加了紅黑樹，當鏈表長度大于等于8的時候鏈表會變成紅黑樹
• 鏈表新節(jié)點插入鏈表的順序不同（jdk7是插入頭結(jié)點，jdk8因為要把鏈表變?yōu)榧t 黑樹所以采用插入尾節(jié)點）
• hash算法簡化 ( jdk8 )
• resize的邏輯修改（jdk7會出現(xiàn)死循環(huán)，jdk8不會）

三、HashMap的容量與擴容機制

1.HashMap的默認負載因子

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

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

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

2.HashMap的擴容機制

寫數(shù)據(jù)之后會可能觸發(fā)擴容，HashMap結(jié)構(gòu)內(nèi)，我記得有一個記錄當前數(shù)據(jù)量的字段，這個數(shù)據(jù)量字段到達擴容閾值的話，它就會觸發(fā)擴容的操作

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

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

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

3.HashMap中散列表數(shù)組初始長度

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

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

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

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

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

hahmap每次擴容都是以 2的整數(shù)次冪進行擴容

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

那么到了這里你也許會問？ 那么就然16可以，是不是只要是2的整數(shù)次冪就可以呢？

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

四、HashMap的結(jié)構(gòu)

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

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

1.HashMap存儲原理

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

2.HashMap存儲流程

前面尋址算法都是一樣的，根據(jù)key的hashcode經(jīng)過高低位異或之后的值，再按位與 &(table.lingth - 1),得到一個數(shù)組下標，然后根據(jù)這個數(shù)組下標內(nèi)的狀況，狀況不同，然后情況也不同，大概分為了4種狀態(tài)：

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

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

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

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

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

其次第二種情況就是根節(jié)點在向下探測過程中發(fā)現(xiàn)TreeNode中key與當前put的key完全一致，然后就也是一次repleace操作，替換value。

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

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

七、擴容后的新table數(shù)組，那老數(shù)組中的這個數(shù)據(jù)怎么遷移呢

遷移其實就是挨個桶位推進遷移，就是一個桶位一個桶位的處理，主要還是看當前處理桶位的數(shù)據(jù)狀態(tài)把，這里也是分了大概四種狀態(tài)：
這四種的遷移規(guī)則都不太一樣

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

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

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

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

到此這篇關于HashMap底層實現(xiàn)原理詳解的文章就介紹到這了,更多相關HashMap底層實現(xiàn)原理內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！