一、快速入門(mén)

示例：有一定基礎(chǔ)的小伙伴們可以選擇性的跳過(guò)該步驟

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

1.HashMap的常用方法

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

2.HashMap的幾個(gè)重要知識(shí)點(diǎn)

• HashMap是無(wú)序且不安全的數(shù)據(jù)結(jié)構(gòu)。
• HashMap 是以key–value對(duì)的形式存儲(chǔ)的，key值是唯一的（可以為null），一個(gè)key只能對(duì)應(yīng)著一個(gè)value，但是value是可以重復(fù)的。
• HashMap 如果再次添加相同的key值，它會(huì)覆蓋key值所對(duì)應(yīng)的內(nèi)容，這也是與HashSet不同的一點(diǎn)，Set通過(guò)add添加相同的對(duì)象，不會(huì)再添加到Set中去。
• HashMap 提供了get方法，通過(guò)key值取對(duì)應(yīng)的value值，但是HashSet只能通過(guò)迭代器Iterator來(lái)遍歷數(shù)據(jù)，找對(duì)象。

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

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

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

三、HashMap的容量與擴(kuò)容機(jī)制

1.HashMap的默認(rèn)負(fù)載因子

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

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

• 閾值(threshold) = 負(fù)載因子(loadFactor) x 容量(capacity) 根據(jù)HashMap的擴(kuò)容機(jī)制，他會(huì)保證容量(capacity)的值永遠(yuǎn)都是2的冪 為了保證負(fù)載因子x容量的結(jié)果是一個(gè)整數(shù)，這個(gè)值是0.75(4/3)比較合理，因?yàn)檫@個(gè)數(shù)和任何2的次冪乘積結(jié)果都是整數(shù)。
• 理論上來(lái)講，負(fù)載因子越大，導(dǎo)致哈希沖突的概率也就越大，負(fù)載因子越小，費(fèi)的空間也就越大,這是一個(gè)無(wú)法避免的利弊關(guān)系，所以通過(guò)一個(gè)簡(jiǎn)單的數(shù)學(xué)推理，可以測(cè)算出這個(gè)數(shù)值在0.75左右是比較合理的

2.HashMap的擴(kuò)容機(jī)制

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

閾值(threshold) = 負(fù)載因子(loadFactor) x 容量(capacity)
當(dāng)HashMap中table數(shù)組(也稱(chēng)為桶)長(zhǎng)度 >= 閾值(threshold) 就會(huì)自動(dòng)進(jìn)行擴(kuò)容。

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

問(wèn)題又來(lái)了，為什么計(jì)算擴(kuò)容后容量要采用位移運(yùn)算呢，怎么不直接乘以2呢？
這個(gè)問(wèn)題就比較簡(jiǎn)單了，因?yàn)閏pu畢竟它不支持乘法運(yùn)算，所有的乘法運(yùn)算它最終都是再指令層面轉(zhuǎn)化為了加法實(shí)現(xiàn)的，這樣效率很低，如果用位運(yùn)算的話(huà)對(duì)cpu來(lái)說(shuō)就非常的簡(jiǎn)潔高效。

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

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

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

老問(wèn)題又來(lái)了，為啥HashMap中初始化大小為什么是16呢？

首先我們看hashMap的源碼可知當(dāng)新put一個(gè)數(shù)據(jù)時(shí)會(huì)進(jìn)行計(jì)算位于table數(shù)組(也稱(chēng)為桶)中的下標(biāo)：

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

hahmap每次擴(kuò)容都是以 2的整數(shù)次冪進(jìn)行擴(kuò)容

因?yàn)槭菍⒍M(jìn)制進(jìn)行按位于，(16-1) 是 1111,末位是1，這樣也能保證計(jì)算后的index既可以是奇數(shù)也可以是偶數(shù)，并且只要傳進(jìn)來(lái)的key足夠分散，均勻那么按位于的時(shí)候獲得的index就會(huì)減少重復(fù)，這樣也就減少了hash的碰撞以及hashMap的查詢(xún)效率。

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

答案是肯定的。那為什么不是8,4呢？ 因?yàn)槭?或者4的話(huà)很容易導(dǎo)致map擴(kuò)容影響性能，如果分配的太大的話(huà)又會(huì)浪費(fèi)資源，所以就使用16作為初始大小。

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

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

五、HashMap存儲(chǔ)原理與存儲(chǔ)流程

1.HashMap存儲(chǔ)原理

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

2.HashMap存儲(chǔ)流程

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

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

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

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

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

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

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

六、jdk8中HashMap為什么要引入紅黑樹(shù)？

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

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

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

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

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

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

(4.)第四種就是該槽位儲(chǔ)存了一個(gè)紅黑樹(shù)的根節(jié)點(diǎn)TreeNode對(duì)象：
這個(gè)就很復(fù)雜了，本文章暫時(shí)不做過(guò)多的介紹（博主還沒(méi)整明白 =_=! ）

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

最新評(píng)論