本來想先在專欄里簡單的說一下二叉樹，紅黑樹的內(nèi)容后再說HashMap的桅狠，但看到評論區(qū)里不斷的出現(xiàn)HashMap這個詞讼载，怕大家等得著急，本篇文章就先說說HashMap吧中跌，前面講ArrayList和LinkedList時把源碼說得很細(xì)，只要理解了這兩塊內(nèi)容菇篡，本篇內(nèi)容也很好理解漩符，先來看看HashMap在Map這個大家族中的位置。
上圖中驱还，白色部分是接口嗜暴，黃色部分是要重點了解的，最好是看一遍源碼议蟆，綠色部分已經(jīng)過時闷沥，不常用了，但是面試中可能會問到咐容。這里先簡單的說一下這幾個Map舆逃，TreeMap是基于樹的實現(xiàn)，HashMap，HashTable路狮，ConcurrentHashMap是基于hash表的實現(xiàn)虫啥，下文我們會介紹hash表。HashTable和HashMap在代碼實現(xiàn)上奄妨，基本上是一樣的涂籽，和Vector與Arraylist的區(qū)別大體上差不多，一個是線程安全的砸抛，一個非線程安全评雌，忘記了的朋友可以去看這篇文章，傳送門：Arraylist與Vector的區(qū)別直焙。ConcurrentHashMap也是線程安全的景东，但性能比HashTable好很多，HashTable是鎖整個Map對象箕般，而ConcurrentHashMap是鎖Map的部分結(jié)構(gòu)耐薯，LinkedHashMap后續(xù)會單獨開文講解。
Map其實很簡單丝里，就是一個key曲初，對應(yīng)一個value。本章我們重點了解HashMap杯聚，話不多說臼婆，上代碼：
執(zhí)行構(gòu)造函數(shù)，當(dāng)我們看到這個new幌绍，第一反應(yīng)應(yīng)該是這貨又在堆內(nèi)存里開辟了一塊空間颁褂。
構(gòu)造函數(shù)如下：
似乎簡單，就是初始化了一個負(fù)載因子
負(fù)載因子默認(rèn)為0.75f傀广，這個負(fù)載因子后續(xù)會詳說颁独。
嘿嘿，又看到了傳說中的數(shù)組伪冰，數(shù)組里原對象是Node誓酒，來看一下Node是什么鬼
其實很簡單，一些屬性贮聂，一個key靠柑，一個value，用來保存我們往Map里放入的數(shù)據(jù)吓懈，next用來標(biāo)記Node節(jié)點的下一個元素歼冰。目前還沒有任何代碼用到Node，我們只能從成員變量入手了
這兩個就不多說了吧耻警，一個是邏輯長度隔嫡，一個是修改次數(shù)甸怕，ArrayList，LinkedList也有這兩個屬性畔勤，老規(guī)矩蕾各，我們來畫一畫
HashMap我們就初始化好了，成員變量table數(shù)組默認(rèn)為null庆揪，size默認(rèn)為0式曲，負(fù)載因子為0.75f，初始化完成缸榛，往里添加元素吝羞，來看一下put的源碼
就一行代碼，調(diào)用了putVal方法内颗，其中key是傳進(jìn)來的“張三”這個字符串對象钧排，value是“張三”這個Person對象，調(diào)用了一個方法hash()均澳，再看一下
看到了熟悉的hashCode恨溜，我們在前面的文章里已經(jīng)強調(diào)過很多次了，重寫equals方法的時候找前，一定要重寫hashCode方法糟袁，因為key是基于hashCode來處理的。繼續(xù)看putVal方法
resize方法比較復(fù)雜躺盛，這兒就不完全貼出來了项戴，當(dāng)放入第一個元素時，會觸發(fā)resize方法的以下關(guān)鍵代碼
再看這個DEFAULT_INITIAL_CAPACITY是什么東東
又是傳說中的移位運算符槽惫，1 << 4 其實就是相當(dāng)于16周叮。
恩，這句是關(guān)鍵界斜，當(dāng)我們放入第一個元素時仿耽，如果底層數(shù)組還是null，系統(tǒng)會初始化一個長度為16的Node數(shù)組各薇，像極了ArrayList的初始化氓仲。
最后返回new出來的數(shù)組，繼續(xù)畫圖得糜，由于篇幅有限，下圖中省略了部分?jǐn)?shù)組內(nèi)容晰洒，注意朝抖，雖然數(shù)組長度為16，但邏輯長度size依然是0
繼續(xù)執(zhí)行下圖中putVal方法里的紅框內(nèi)容
if ((p = tab[i = (n - 1) & hash]) == null)
? ? tab[i] = newNode(hash, key, value, null);
這段代碼初學(xué)者可能看起來比較費勁谍珊，我們重寫一下以便初學(xué)者能更好的理解治宣，這兩段代碼等同，下面是重寫后的代碼，清晰了很多
i = (n - 1) & hash;//hash是傳過來的侮邀，其中n是底層數(shù)組的長度坏怪，用&運算符計算出i的值
p = tab[i];//用計算出來的i的值作為下標(biāo)從數(shù)組中元素
if(p == null){//如果這個元素為null，用key,value構(gòu)造一個Node對象放入數(shù)組下標(biāo)為i的位置
? ? tab[i] = newNode(hash, key, value, null);
}
這個hash值是字符串“張三”這個對象的hashCode方法與hashMap提供hash()方法共同計算出來的結(jié)果绊茧，其中n是數(shù)組的長度铝宵，目前數(shù)組長度為16，不管這個hash的值是多少华畏，經(jīng)過(n - 1) & hash計算出來的i 的值一定在n-1之間鹏秋。剛好是底層數(shù)組的合法下標(biāo)，用i這個下標(biāo)值去底層數(shù)組里去取值亡笑，如果為null侣夷，創(chuàng)建一個Node放到數(shù)組下標(biāo)為i的位置。這里的“張三”計算出來的i的值為2仑乌，繼續(xù)畫圖
繼續(xù)添加元素“李四”百拓，“王五”，“趙六”晰甚，一切正常衙传，key：“李四”經(jīng)過(n - 1) & hash算出來在數(shù)組下標(biāo)位置為1，“王五”為7压汪，“趙六”為9粪牲，添加完成后如下圖
上圖更趨近于堆內(nèi)存中的樣子，但看起來比較復(fù)雜止剖，我們簡化一下
上圖是簡化后的堆內(nèi)存圖腺阳。繼續(xù)往里添加“孫七”，通過(n - 1) & hash計算“孫七”這個key時計算出來的下標(biāo)值是1穿香，而數(shù)組下標(biāo)1這個位置目前已經(jīng)被“李四”給占了亭引，產(chǎn)生了沖突。相信大家在看本文的過程中也有這樣的疑惑皮获，萬一計算出來的下標(biāo)值i重了怎么辦焙蚓？我們來看一看HashMap是怎么解決沖突的。
上圖中紅框里就是沖突的處理洒宝，這一句是關(guān)鍵
p.next=newNode(hash,key,value,null);
也就是說new一個新的Node對象并把當(dāng)前Node的next引用指向該對象购公，也就是說原來該位置上只有一個元素對象，現(xiàn)在轉(zhuǎn)成了單向鏈表雁歌，繼續(xù)畫圖
繼續(xù)添加其它元素宏浩，添加完成后如下
到這里，我們的元素就添加完了靠瞎。我們debug看一下
大框里的內(nèi)容是鏈表的體現(xiàn)比庄，小框里的內(nèi)容是單元素的體現(xiàn)求妹。
紅框中還有兩行比較重要的代碼
if (binCount >= TREEIFY_THRESHOLD - 1) //當(dāng)binCount>=TREEIFY_THRESHOLD-1
? ? ? treeifyBin(tab, hash);//把鏈表轉(zhuǎn)化為紅黑樹
再看看TREEIFY_THRESHOLD的值
當(dāng)鏈表長度到8時，將鏈表轉(zhuǎn)化為紅黑樹來處理佳窑，由于樹相關(guān)的內(nèi)容本專欄還未講解制恍，紅黑樹的內(nèi)容這里就不深入了。樹在內(nèi)存中的樣子我們還是畫個圖簡單的了解一下
在JDK1.7及以前的版本中神凑，HashMap里是沒有紅黑樹的實現(xiàn)的净神，在JDK1.8中加入了紅黑樹是為了防止哈希表碰撞攻擊，當(dāng)鏈表鏈長度為8時耙厚，及時轉(zhuǎn)成紅黑樹强挫，提高map的效率。在面試過程中薛躬，能說出這一點俯渤，面試官會對你加分不少。
注：本章所講的移位運算符（如：“<<”）型宝、位運算符（如：“&”）八匠，紅黑樹、哈希表碰撞攻擊等趴酣，這里不做詳解梨树，大家有興趣的話請在評論區(qū)留言，響應(yīng)的人多的話岖寞，會單獨開文講解抡四。
思考下面代碼：
hash方法的實現(xiàn)：
在put放入元素時，HashMap又自己寫了一個hash方法來計算hash值仗谆，大家想想看指巡，為什么不用key本身的hashCode方法，而是又處理了一下隶垮？
本文到這里先告一個段落藻雪，先做一個小結(jié)。
HashMap的最底層是數(shù)組來實現(xiàn)的狸吞，數(shù)組里的元素可能為null勉耀，也有可能是單個對象，還有可能是單向鏈表或是紅黑樹蹋偏。
文中的resize在底層數(shù)組為null的時候會初始化一個數(shù)組便斥，不為null的情況下會去擴(kuò)容底層數(shù)組，并會重排底層數(shù)組里的元素威始。
轉(zhuǎn)載出自：https://zhuanlan.zhihu.com/p/28501879
