HashMap定義

說(shuō)的專業(yè)一點(diǎn)，HashMap是常用的用于存儲(chǔ)key-value鍵值對(duì)數(shù)據(jù)的一個(gè)集合魄鸦，底層是基于對(duì)Map的接口實(shí)現(xiàn)宴杀。每一個(gè)鍵值對(duì)又叫Entry，這些Entry分散的存儲(chǔ)在一個(gè)由數(shù)組和鏈表組成的集合中拾因。當(dāng)然在Java8中旺罢，Entry變成了Node。

說(shuō)的通俗一點(diǎn)绢记，就像你去住酒店主经，你下單提供了你的手機(jī)號(hào)，然后到酒店了給你一個(gè)房卡庭惜，你知道了你的房號(hào)之后再根據(jù)這個(gè)房號(hào)去找對(duì)應(yīng)的房間一樣罩驻。

房號(hào)就是key，房間里就是value护赊。你通過(guò)手機(jī)號(hào)下單到酒店給你房號(hào)可以理解為對(duì)key哈希的過(guò)程惠遏。你找的過(guò)程就是HashMap根據(jù)key取到對(duì)應(yīng)value的過(guò)程

HashMap底層結(jié)構(gòu)

table數(shù)組

首先我們要知道，我們存在HashMap中的數(shù)據(jù)最終是存了什么地方骏啰，就是如下的結(jié)構(gòu)节吮。

transient HashMap.Node<K, V>[] table;

可能有人看到transient有些陌生，被這個(gè)關(guān)鍵字修飾的變量將不會(huì)被序列化判耕。簡(jiǎn)單來(lái)說(shuō)透绩，就是序列化之后這個(gè)字段的值就會(huì)被干掉，用于一些不需要傳遞給第三方的字段壁熄。

例如一個(gè)矩形帚豪，在本地使用的時(shí)候，有長(zhǎng)草丧、寬和面積三個(gè)屬性狸臣，但是你要把這個(gè)對(duì)象給第三方用，但是由于面積可以通過(guò)另外兩個(gè)屬性推導(dǎo)出來(lái)昌执，這個(gè)key就不需要傳遞給第三方了烛亦。

這種情況就可以用transient關(guān)鍵字修飾诈泼。總的來(lái)說(shuō)就是煤禽，被transient修飾的變量將不再參與序列化铐达。

Node節(jié)點(diǎn)

下面是Node節(jié)點(diǎn)的定義。

static class Node<K, V> implements Entry<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
                
            ......

        public final V getValue() {
            return value;
        }
  
        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
  
            ......
    }

上面的代碼省略了一些Getter和Setter檬果，結(jié)構(gòu)還是非常清晰和簡(jiǎn)單娶桦。可以看到這個(gè)節(jié)點(diǎn)存儲(chǔ)了下一個(gè)節(jié)點(diǎn)的對(duì)象的引用汁汗，形成了一個(gè)鏈表的結(jié)構(gòu)衷畦。

為什么要用鏈表？用數(shù)組不行嗎知牌？剛剛上面提到過(guò)祈争，這個(gè)集合是由鏈表和數(shù)組組成的。因?yàn)樵偻昝赖膆ash算法都有可能產(chǎn)生哈希沖突角寸，所以兩個(gè)不同key的元素可以被放在同一個(gè)地方菩混。

而單用數(shù)組明顯不能滿足這個(gè)需求，而在數(shù)組的槽位上存一個(gè)鏈表就可以解決這個(gè)問(wèn)題扁藕。

HashMap的使用

上面簡(jiǎn)單了解了HashMap的定義和基本的底層數(shù)據(jù)結(jié)構(gòu)沮峡，接下來(lái)通過(guò)HashMap在平常開發(fā)中的使用來(lái)具體看看怎么實(shí)現(xiàn)的。

Map<String, String> map = new HashMap<>();

map.put("搜索關(guān)注公眾號(hào)", "SH的全棧筆記"); // 設(shè)置值
map.get("搜索關(guān)注公眾號(hào)");               // SH的全棧筆記 

賦值

put函數(shù)

上面的Put方法亿柑，我們傳入了兩個(gè)參數(shù)邢疙，Key和Value，函數(shù)的定義如下望薄。

public V put(K key, V value) {
 return this.putVal(hash(key), key, value, false, true);
}

應(yīng)該跟大多數(shù)人YY的put方法差不多疟游，put方法再調(diào)用了putVal 方法。

首先經(jīng)過(guò)了hash之后的key痕支，是一個(gè)整型的hashcode颁虐，其次是我們傳入的key和value。最后兩個(gè)布爾值卧须，后面會(huì)提到另绩。

首先一進(jìn)入putVal就會(huì)聲明存放數(shù)據(jù)的table，如果這個(gè)HashMap是首次設(shè)置值花嘶，就會(huì)被初始化一個(gè)默認(rèn)size的table笋籽，且所有元素的初始值都是NULL，下面是初始化這塊的核心代碼察绷，我省略掉了一些無(wú)關(guān)的變量聲明干签。

有趣的是津辩，初始化調(diào)用的是resize方法拆撼。

Node<K,V>[] tab; 
int n;
if ((tab = table) == null || (n = tab.length) == 0) {
  n = (tab = resize()).length;
}

newCap = 16; // 默認(rèn)容量
newThr = 12; // 默認(rèn)閾值

默認(rèn)值為啥是16

上面初始化table的默認(rèn)size給的是16容劳，當(dāng)然我們也可以自己定義，但是建議是最好是2的冪闸度。有的朋（杠）友（精）就要問(wèn)了竭贩，為什么是16呢？我13莺禁，14不他不香嗎留量？我們接下來(lái)就要分析為什么不香。

當(dāng)我們放元素進(jìn)入map的時(shí)候哟冬，它是如何確定元素在table數(shù)組中的位置的呢楼熄？我們拿搜索關(guān)注公眾號(hào)這個(gè)key舉例。

hash = (h = key.hashCode()) ^ h >>> 16
p = tab[i = n - 1 & hash]

可以看到浩峡，是將hash之后key和數(shù)組的length-1做與運(yùn)算得到了一個(gè)數(shù)組下標(biāo)可岂。而且，hash值的二進(jìn)制的位數(shù)翰灾，大多數(shù)情況下都會(huì)比table的長(zhǎng)度的二進(jìn)制位數(shù)多缕粹。換句話說(shuō)，與運(yùn)算之后得到的數(shù)組下標(biāo)index完全取決于hash值的后幾位纸淮。

16 // n   10000
15 // n-1 1111
14 //     1110
13 //     1101
12 //     1100
11 //     1011
10 //     1010

從13平斩、14的二進(jìn)制值可以看出來(lái)，存在0和1在二進(jìn)制位數(shù)上分布不均勻的情況咽块，這樣一來(lái)就會(huì)造成一個(gè)問(wèn)題绘面，那就是會(huì)存在某些不同的hash值經(jīng)過(guò)與運(yùn)算得到的值是一樣的。這樣就會(huì)導(dǎo)致hash到的index不均勻侈沪，換句話說(shuō)有些index可能永遠(yuǎn)都不會(huì)被hash到飒货，而有些index也被頻繁的hash到。

本來(lái)hash算法是要求計(jì)算的結(jié)果要均勻分布的峭竣，但是上述的結(jié)果明顯不符合均勻分布的要求塘辅。用n-1而不用n也是因?yàn)橥瑯拥牡览怼Ｈ绻@個(gè)值是2的冪皆撩，那么2的冪的值-1的所有二進(jìn)制位數(shù)都是1扣墩，這樣有利于hash計(jì)算的均勻分布。

綜上所述扛吞，不一定是16呻惕，2的冪都可以，16只是一個(gè)經(jīng)驗(yàn)值滥比。

自動(dòng)擴(kuò)容

除了size亚脆，初始化的時(shí)候還會(huì)設(shè)定一個(gè)閾值，值為12盲泛，newThr = 12濒持，這里需要提到一個(gè)概念負(fù)載因子键耕，HashMap的實(shí)現(xiàn)里默認(rèn)給的是0.75。

public HashMap() {
  this.loadFactor = 0.75F; // 12/16=0.75
}

負(fù)載因子是用來(lái)干嘛的呢柑营？最開始我們提到了屈雄，最開始存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)是數(shù)組，這種基礎(chǔ)結(jié)構(gòu)是有size設(shè)定的官套。當(dāng)我們不停的往map里存數(shù)據(jù)的時(shí)候酒奶，總會(huì)存滿，當(dāng)元素快存滿的時(shí)候奶赔，我們就需要擴(kuò)大map的容量惋嚎，來(lái)容納更多的元素，這就需要一個(gè)自動(dòng)擴(kuò)容的機(jī)制了站刑。

不是擴(kuò)容彈匣瘸彤，想啥呢

在當(dāng)數(shù)據(jù)量大于超過(guò)設(shè)定的閾值的時(shí)候（容量*負(fù)載因子），自動(dòng)對(duì)map進(jìn)行擴(kuò)容笛钝，以存放更多的數(shù)據(jù)质况。

自動(dòng)擴(kuò)容做了什么事情呢？總結(jié)來(lái)說(shuō)就是兩件事玻靡。

• 創(chuàng)建新的數(shù)組结榄，大小是原來(lái)數(shù)組的一倍。
• 將元素rehash到新的數(shù)組

為什么要rehash呢囤捻？上面我們提到過(guò)了臼朗，當(dāng)元素被放進(jìn)map時(shí)，確認(rèn)下標(biāo)的方法是table的長(zhǎng)度-1和hash值做與運(yùn)算蝎土，現(xiàn)在table的長(zhǎng)度發(fā)生了變化视哑，那么自然而然，元素獲取下標(biāo)的運(yùn)算結(jié)果也就跟之前的不一樣了誊涯， 所以需要將老的map中的元素再按照新的table長(zhǎng)度rehash到擴(kuò)容后的table中挡毅。

所以在當(dāng)你對(duì)性能有一定要求，且你知道你創(chuàng)建map的時(shí)候size的時(shí)候暴构，可以指定size跪呈，這樣一來(lái)就不會(huì)因?yàn)閿?shù)據(jù)量持續(xù)的增大而去頻繁的自動(dòng)擴(kuò)容了

put的過(guò)程中到底發(fā)生了什么

了解了底層數(shù)據(jù)結(jié)構(gòu)和自動(dòng)擴(kuò)容機(jī)制，接下來(lái)我們來(lái)看一下put過(guò)程中究竟發(fā)生了什么取逾。我們上面說(shuō)過(guò)了耗绿，會(huì)通過(guò)數(shù)組的長(zhǎng)度-1和hash值與運(yùn)算得到一個(gè)數(shù)組下標(biāo)。

如果該位置沒有元素砾隅，那么就很簡(jiǎn)單误阻，直接新建一個(gè)節(jié)點(diǎn)即可然后放置在數(shù)據(jù)的具體位置即可。

tab[i] = this.newNode(hash, key, value, (HashMap.Node)null);

但是如果該下標(biāo)已經(jīng)有元素了，這種情況HashMap是怎么處理的呢究反？這也要看情況寻定。

• 如果是跟當(dāng)前槽位相同的key，就直接覆蓋奴紧。這就是我們修改某個(gè)key的值會(huì)發(fā)生的情況特姐。那HashMap怎么來(lái)判斷是不是同一個(gè)key呢晶丘？就像下面這樣黍氮。p就是當(dāng)前槽位上已經(jīng)有的元素，如果新浅浮、老元素的key的hashCode和值都相同且key不為空沫浆，那么就能證明這兩個(gè)key是相同的，那么此時(shí)只需要覆蓋即可滚秩。

  p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))

• 而如果p是TreeNode的實(shí)例专执，那么就代表當(dāng)前槽位已經(jīng)是一個(gè)紅黑樹了，此時(shí)只需要往這個(gè)樹里putTreeVal即可郁油。至于為什么是紅黑樹本股，哪兒來(lái)的紅黑樹，下面馬上就要講到了桐腌。

• 最后一種情況就是拄显，既不是已經(jīng)存在的元素也不是TreeNode的實(shí)例，也不是紅黑樹案站。這種情況下躬审，它就是一個(gè)普通的Node。你可以理解為鏈表蟆盐，如果hash沖突了承边，就把這個(gè)Node放到該位置的鏈表末尾。Java8之前采用的頭插法石挂，而Java8換成了尾插法博助，至于為什么要換，后面會(huì)講痹愚。

當(dāng)該位置的鏈表中的元素超過(guò)了TREEIFY_THRESHOLD所設(shè)置的數(shù)量時(shí)翔始，就會(huì)觸發(fā)樹化，將其轉(zhuǎn)化為紅黑樹里伯。Java8里給的默認(rèn)值是8城瞎。

為啥要轉(zhuǎn)化成紅黑樹

首先我們要知道為什么要樹化。當(dāng)大量的數(shù)據(jù)放入Map中疾瓮，Hash沖突會(huì)越來(lái)越多脖镀，某些位置就會(huì)出現(xiàn)一個(gè)很長(zhǎng)的鏈表的情況。這種情況下，查詢時(shí)間復(fù)雜度是O(n) 蜒灰，刪除的時(shí)間復(fù)雜度也是O(n)弦蹂，查詢、刪除的效率會(huì)大大降低强窖。而同樣的數(shù)據(jù)情況下凸椿，平衡二叉樹的時(shí)間復(fù)雜度都是O(logn)。

有的朋（杠）友（精）看到這個(gè)小標(biāo)題不樂(lè)意了翅溺，怎么就直接用紅黑樹了脑漫？我用二叉查找樹它不香嗎？

不了解二叉查找樹的咙崎，我把它的特點(diǎn)列在了下面优幸。

• 左子樹上的所有節(jié)點(diǎn)的值都小于根節(jié)點(diǎn)的值

• 右子樹上的所有節(jié)點(diǎn)的值都大于根節(jié)點(diǎn)的值

再精簡(jiǎn)一下就是，左小右大

但是褪猛，如果數(shù)據(jù)大量的趨近于有序网杆，例如所有的節(jié)點(diǎn)都比根節(jié)點(diǎn)大，那這個(gè)時(shí)候二叉查找樹就退化成了鏈表伊滋，查詢效率就會(huì)急劇下降碳却。看到這是不是覺得有點(diǎn)不對(duì)笑旺，我才從鏈表樹化昼浦，你這又給我退化成了鏈表荔茬？

朋友看到這又不樂(lè)意了君账，好好好，就算二叉查找樹不行输吏，那AVL樹它也不行物舒？用了AVL樹就不會(huì)出現(xiàn)上面所描述的效率急劇退化的情況了不是嗎色洞？

的確是這樣，AVL也可以叫平衡二叉搜索樹冠胯。AVL樹會(huì)在其有退化成鏈表的趨勢(shì)的時(shí)候（左右子樹的高度差超過(guò)某個(gè)閾值）調(diào)整樹的結(jié)構(gòu)火诸，也就是通過(guò)左旋和右旋來(lái)使其左右子樹的高度盡量平衡。

OK荠察，OK置蜀，就算你解釋清楚了為什么要樹化，那為什么一定要用紅黑樹悉盆？

具體的細(xì)節(jié)也就不在這里贅述盯荤，不知不覺已經(jīng)寫了這么多了，直接說(shuō)結(jié)論吧焕盟。AVL樹的查找速度更快秋秤，但是相應(yīng)的插入和修改的速度較慢。而紅黑樹則在插入和修改操作較為密集的時(shí)候表現(xiàn)更好。

而總結(jié)我們?nèi)粘５腍ashMap使用灼卢，大多數(shù)情況下插入和修改應(yīng)該是比查找更頻繁一些的绍哎。而在這種情況下，紅黑樹的綜合表現(xiàn)會(huì)更好一些鞋真。

至于紅黑樹的相關(guān)細(xì)節(jié)崇堰，涉及的東西還是挺多，我之后會(huì)單獨(dú)拿一個(gè)篇幅來(lái)講涩咖。

為什么要用尾插法

我們目前用的最多的是Java8海诲，在Java8中采用的是尾插法，Java8之前采用的是頭插法抠藕。

那為什么后面又變成了尾插法呢饿肺？放心蒋困，肯定不是設(shè)計(jì)者閑的蛋疼盾似，沒事來(lái)改個(gè)設(shè)計(jì)。這樣做一定是有一定的道理的雪标。在解釋這個(gè)問(wèn)題之前零院，我們先來(lái)看看，如果采取頭插法在多線程下的情況下會(huì)出現(xiàn)什么問(wèn)題村刨。

我們講過(guò)告抄，假設(shè)數(shù)組中index=1的位置已經(jīng)有了元素A，之后又有元素B被分配到了index=1的位置嵌牺。那么在下標(biāo)為1的槽位上的鏈表就變成了B -> A打洼。

此時(shí)再分配了一個(gè)新元素C，鏈表又被更新成了C -> B -> A逆粹。這也是為什么叫頭插法募疮，新的元素會(huì)被放在鏈表的頭節(jié)點(diǎn)，因?yàn)楫?dāng)時(shí)設(shè)計(jì)的時(shí)候考慮到后被放入map的元素被訪問(wèn)的可能性更大僻弹。

上面講到了在當(dāng)不停的往map中放置元素后阿浓，超過(guò)了設(shè)定的閾值，就會(huì)觸發(fā)自動(dòng)擴(kuò)容蹋绽。此時(shí)會(huì)觸發(fā)兩個(gè)操作芭毙，一是創(chuàng)建一個(gè)容量為之前兩倍的底層數(shù)組，并且將老的數(shù)組中的元素rehash到新的數(shù)組中卸耘。

而由于數(shù)組的長(zhǎng)度發(fā)生了變化退敦，這就導(dǎo)致了元素的rehash結(jié)果跟之前在老數(shù)組中的位置不一樣。

首先我們來(lái)模擬一下rehash的過(guò)程蚣抗，假設(shè)新的數(shù)組中下標(biāo)為2的槽位是空的侈百。

• 首先元素C，被放置在了其他位置。

• 然后元素B设哗，被rehash到了下標(biāo)為2的槽位唱捣， 至此都沒有問(wèn)題。

• 最后元素A网梢，同樣被rehash到了下標(biāo)為2的槽位震缭，此時(shí)鏈表變成了A -> B。到這就有問(wèn)題了战虏，最開始B的next指向的是A節(jié)點(diǎn)拣宰。但是rehash之后A的next又指向B，看到這你應(yīng)該就能明白發(fā)生了什么烦感。

我看到很多的對(duì)JDK1.7版的HashMap在多線程的情況下擴(kuò)容會(huì)出現(xiàn)死鎖的解釋都只到了環(huán)形鏈表巡社。但是其實(shí)就算是環(huán)形鏈表，只要找到了對(duì)應(yīng)的元素手趣，就會(huì)直接退出循環(huán)的邏輯晌该，也不會(huì)造成死循環(huán)。

實(shí)際情況是绿渣，當(dāng)自動(dòng)擴(kuò)容形成了環(huán)形鏈表后朝群，當(dāng)你去Get了一個(gè)在entry鏈上不存在的元素時(shí)，就會(huì)出現(xiàn)死循環(huán)的情況中符。

取值

上面聊了給HashMap賦值的大概過(guò)程姜胖，接下來(lái)聊一下從HashMap獲取值會(huì)發(fā)生什么。get方法的開始淀散，跟put一樣很簡(jiǎn)單右莱。

public V get(Object key) {
  Node<K,V> e;
  return (e = getNode(hash(key), key)) == null ? null : e.value;
}

可以看到，取值的核心操作是getNode來(lái)負(fù)責(zé)完成的档插。

首先第一件事就是去check的第一個(gè)元素是不是當(dāng)前查找的元素慢蜓。

如果不是，而且當(dāng)前槽位已經(jīng)被樹化成了紅黑樹阀捅，就走紅黑樹的getTreeNode方法胀瞪。

如果還沒有被樹化，只是普通的鏈表饲鄙，則順著next一路找下去凄诞。

由于get方法邏輯和實(shí)現(xiàn)都比較容易理解，就不貼太多源碼了忍级。

結(jié)尾

由于最近太忙了帆谍，工作和生活中的事都巨多，這篇文章是幾周利用零零散散的時(shí)間寫出來(lái)的轴咱，如果有什么問(wèn)題汛蝙，歡迎大家在評(píng)論區(qū)討論烈涮。

好了以上就是本篇博客的全部?jī)?nèi)容了，如果你覺得這篇文章對(duì)你有幫助窖剑，還麻煩點(diǎn)個(gè)贊坚洽，關(guān)個(gè)注，分個(gè)享西土，留個(gè)言讶舰。

歡迎微信搜索關(guān)注【SH的全棧筆記】，查看更多相關(guān)文章

拜了個(gè)拜

image