前言
本文源碼分析基于jdk1.8版本（持續(xù)更新中）
1、HashMap數(shù)據(jù)結(jié)構(gòu)與工作原理
這是基礎(chǔ)中的基礎(chǔ)，這個(gè)都不能掌握，面試大概率要翻車。源碼自己看，這里講流程。
在Jdk1.8中，HashMap數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表+紅黑樹，數(shù)組也叫做hash表，每條鏈表也叫做桶(bucket)，紅黑樹是為了提高查詢效率。
- 1、hashmap這個(gè)數(shù)組也叫做hash桶(bucket)，
- 2、存放元素的時(shí)候會(huì)先根據(jù)key的hash值去計(jì)算元素下標(biāo)，如果這個(gè)下標(biāo)沒有元素，就創(chuàng)建一個(gè)Node節(jié)點(diǎn)放進(jìn)去；
- 3、如果數(shù)組下標(biāo)有數(shù)據(jù)，先判斷key是否相同，相同的話替換元素的value；不同的話插在鏈表的尾節(jié)點(diǎn)。注意：同一個(gè)鏈表中的節(jié)點(diǎn)只是說數(shù)組下標(biāo)相同，但不一定是發(fā)生了hash沖突的，有可能hash值不同；
- 4、鏈表長(zhǎng)度大于8，且數(shù)組長(zhǎng)度大于64，會(huì)把鏈表轉(zhuǎn)位紅黑樹，紅黑樹本質(zhì)是一顆自平衡的二叉查找樹，查找時(shí)間復(fù)雜度為o(logn)；
- 5、元素容量size超過閾值會(huì)擴(kuò)容；
下面這張美團(tuán)技術(shù)畫的圖可以很清晰的表達(dá)整個(gè)流程。
2、HashMap如何解決hash碰撞（hash沖突）的？
拉鏈法。當(dāng)存儲(chǔ)元素出現(xiàn)hash沖突時(shí)，意味著hash值相同的多個(gè)元素要存儲(chǔ)在數(shù)組中的同一個(gè)位置，這時(shí)候就通過一個(gè)單鏈表來解決，每次新增的元素插在尾節(jié)點(diǎn)。注意：在同一個(gè)鏈表中的元素不能給說明一定是沖突的，有可能hash值不相同。
3、為什么數(shù)組容量必須是2^n（初始化和擴(kuò)容）？
為了讓添加的元素均勻分布在HashMap的數(shù)組上，減少hash碰撞。
//put()，計(jì)算存儲(chǔ)的元素的下標(biāo)
//n是數(shù)組長(zhǎng)度，默認(rèn)16
i = hash & (n - 1)
這種求下標(biāo)的做法和hash % n取模運(yùn)算是一樣的，只是說&運(yùn)算是操作的二進(jìn)制數(shù)，在計(jì)算效率上更高一些，反正源碼都很喜歡這種位運(yùn)算。
我們?cè)谟?jì)算下標(biāo)的時(shí)候當(dāng)然是希望盡可能讓元素分散到0～n-1位置，這樣可以減少?zèng)_突，讓查詢效率更高。下面就來看一下HashMap是怎么做到的。
hash是int類型，轉(zhuǎn)換為2進(jìn)制數(shù)是32位，為了簡(jiǎn)化，假設(shè)
hash=0101 0101，n-1= 15
這樣就可以限制&運(yùn)算的結(jié)果在0000~1111之間，轉(zhuǎn)為10進(jìn)制數(shù)就是0～15，是不是和求余運(yùn)算的結(jié)果一致？如果n=17，n-1=0001 0000，這樣&運(yùn)算結(jié)果的低位全為0，數(shù)組中有很多位置利用不到，這樣會(huì)出現(xiàn)大量的hash沖突。
結(jié)論：只有數(shù)組長(zhǎng)度為2^n，才能保證n-1的低位的值全為1，這樣元素就可以更均勻的分散在數(shù)組上。
4、擾動(dòng)函數(shù)
為了散列效果更好，減少碰撞，減少?zèng)_突。
在上面的&運(yùn)算中，盡管已經(jīng)讓元素更分散了，但是還是存在一個(gè)問題，由于n-1的高位全為0，所以&運(yùn)算的結(jié)果只和hash的低位有關(guān)，這樣的話，發(fā)生hash沖突的次數(shù)會(huì)比較多。但是我們看HashMap源碼，會(huì)發(fā)現(xiàn)已經(jīng)通過重寫hash方法優(yōu)化了這一點(diǎn)。
//計(jì)算key的hash值
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這里并沒有直接使用Object的hashCode()方法，而是重寫了這個(gè)散列方法。有些同學(xué)可能不太看得懂這里的位運(yùn)算，我就給大家拆解開來看一下。
static int hash2(Object key) {
if ((key == null)) return 0;
int h = key.hashCode(); //計(jì)算hash值
int high = h >>> 16; //右移16位,那就只保留了h的高16位
int newHash = h ^ high; //異或運(yùn)算，相同為0，不同為1
return newHash;
}
這樣的話，大家應(yīng)該能看懂了吧。下面借用一張圖來說明上面的計(jì)算。
h >>> 16只保留了h的高16位，h ^ high是讓h的高16位與低16位做異或運(yùn)算，這樣高16位與低16位都參與了hash的運(yùn)算，使hash值更加不確定 降低了hash碰撞的概率。
5、樹化的條件是什么？
網(wǎng)上很多具有誤導(dǎo)性的文章說鏈表長(zhǎng)度大于8就會(huì)轉(zhuǎn)為紅黑樹，實(shí)際上是錯(cuò)誤的。樹化其實(shí)需要2個(gè)條件，鏈表長(zhǎng)度 >=7且數(shù)組長(zhǎng)度>= 64
6、HashMap擴(kuò)容是怎么做的？
擴(kuò)容有3個(gè)觸發(fā)時(shí)機(jī)，一個(gè)是初始化，也就是第一次put()存放數(shù)據(jù)時(shí)，另一個(gè)是存儲(chǔ)的元素?cái)?shù)量大于閾值threshold時(shí)；還有一個(gè)是樹化的時(shí)候（這一點(diǎn)很多人應(yīng)該不知道），最后都是調(diào)用resize()方法完成擴(kuò)容和數(shù)據(jù)遷移的。
如果你沒看過hashmap擴(kuò)容實(shí)現(xiàn)，你猜擴(kuò)容是怎么實(shí)現(xiàn)的？難道和ArrayList一樣，數(shù)組拷貝，把元素照般到新的數(shù)組中相同的位置就好了？實(shí)際上不是的，原來數(shù)組中的元素在擴(kuò)容后只有2種選擇，第一，在原來的位置；第二，在原來位置基礎(chǔ)上再加上原來數(shù)組長(zhǎng)度。這里先說結(jié)論，后面再源碼分析。
再來回顧下，我們是通過如下方式計(jì)算元素下標(biāo)的。記住一點(diǎn)，&運(yùn)算算法：2個(gè)都是1，結(jié)果才為1，否則為0。
//n是數(shù)組長(zhǎng)度，默認(rèn)16
i = hash & (n - 1)
下面這幅圖是擴(kuò)容前后A、B元素的數(shù)組下標(biāo)的計(jì)算過程（有區(qū)別的地方做了標(biāo)示）。在擴(kuò)容前A、B的hash值不一樣，但是&運(yùn)算后的下標(biāo)卻是一樣的；擴(kuò)容后發(fā)生了一個(gè)變化，就是n變成了2原來的2倍，變成2倍可以用左移1位表示，也就是從0000 1111(16)變成0001 1111(32)，那擴(kuò)容后與運(yùn)算，A在高位的第4位&運(yùn)算結(jié)果為0；B在高位的第4位&運(yùn)算結(jié)果為1；也就是說A還是在原來的位置，B在原來的位置(5),再往后移動(dòng)16位，也就是B移動(dòng)到21了。
這里的思路很巧妙，利用了移位運(yùn)算和&運(yùn)算，
n-1的值擴(kuò)容后會(huì)向左移一位，那只需要看看原來的hash值中和這個(gè)新增1相同位置的值是1還是0就好了，是0的話下標(biāo)沒變，是1的話下標(biāo)變成“原下標(biāo)+oldCap"。
源碼解析
final Node<K,V>[] resize() {
// oldTab 指向舊的 table 表
Node<K,V>[] oldTab = table;
// oldCap 代表擴(kuò)容前 table 表的數(shù)組長(zhǎng)度，oldTab 第一次添加元素的時(shí)候?yàn)?null
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 舊的擴(kuò)容閾值
int oldThr = threshold;
// 初始化新的閾值和容量
int newCap, newThr = 0;
// 如果 oldCap > 0 則會(huì)將新容量擴(kuò)大到原來的2倍，擴(kuò)容閾值也將擴(kuò)大到原來閾值的兩倍
if (oldCap > 0) {
// 如果舊的容量已經(jīng)達(dá)到最大容量 2^30 那么就不在繼續(xù)擴(kuò)容直接返回，將擴(kuò)容閾值設(shè)置到 Integer.MAX_VALUE，并不代表不能裝新元素，只是數(shù)組長(zhǎng)度將不會(huì)變化
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}//新容量擴(kuò)大到原來的2倍，擴(kuò)容閾值也將擴(kuò)大到原來閾值的兩倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//oldThr 不為空，代表我們使用帶參數(shù)的構(gòu)造方法指定了加載因子并計(jì)算了
//初始初始閾值 會(huì)將擴(kuò)容閾值 賦值給初始容量這里不再是期望容量，
//但是 >= 指定的期望容量
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else {
// 空參數(shù)構(gòu)造會(huì)走這里初始化容量，和擴(kuò)容閾值 分別是 16 和 12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果新的擴(kuò)容閾值是0，對(duì)應(yīng)的是當(dāng)前 table 為空，但是有閾值的情況
if (newThr == 0) {
//計(jì)算新的擴(kuò)容閾值
float ft = (float)newCap * loadFactor;
// 如果新的容量不大于 2^30 且 ft 不大于 2^30 的時(shí)候賦值給 newThr
//否則 使用 Integer.MAX_VALUE
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//更新全局?jǐn)U容閾值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//使用新的容量創(chuàng)建新的哈希表的數(shù)組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//如果老的數(shù)組不為空將進(jìn)行重新插入操作否則直接返回
if (oldTab != null) {
//遍歷老數(shù)組中每個(gè)位置的鏈表或者紅黑樹重新計(jì)算節(jié)點(diǎn)位置，插入新數(shù)組
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;//用來存儲(chǔ)對(duì)應(yīng)數(shù)組位置鏈表頭節(jié)點(diǎn)
//如果當(dāng)前數(shù)組位置存在元素
if ((e = oldTab[j]) != null) {
// 釋放原來數(shù)組中的對(duì)應(yīng)的空間
oldTab[j] = null;
// 如果鏈表只有一個(gè)節(jié)點(diǎn)，
//則使用新的數(shù)組長(zhǎng)度計(jì)算節(jié)點(diǎn)位于新數(shù)組中的角標(biāo)并插入
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)//如果當(dāng)前節(jié)點(diǎn)為紅黑樹則需要進(jìn)一步確定樹中節(jié)點(diǎn)位于新數(shù)組中的位置。
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//因?yàn)閿U(kuò)容是容量翻倍，
//原鏈表上的每個(gè)節(jié)點(diǎn) 現(xiàn)在可能存放在原來的下標(biāo)，即low位，
//或者擴(kuò)容后的下標(biāo)，即high位
//低位鏈表的頭結(jié)點(diǎn)、尾節(jié)點(diǎn)
Node<K,V> loHead = null, loTail = null;
//高位鏈表的頭節(jié)點(diǎn)、尾節(jié)點(diǎn)
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;//用來存放原鏈表中的節(jié)點(diǎn)
do {
next = e.next;
// 利用哈希值 & 舊的容量，可以得到哈希值去模后，
//是大于等于 oldCap 還是小于 oldCap，
//等于 0 代表小于 oldCap，應(yīng)該存放在低位，
//否則存放在高位（稍后有圖片說明）
if ((e.hash & oldCap) == 0) {
//給頭尾節(jié)點(diǎn)指針賦值
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}//高位也是相同的邏輯
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}//循環(huán)直到鏈表結(jié)束
} while ((e = next) != null);
//1.將低位鏈表存放在原index處，
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//2.將高位鏈表存放在新index處，也就是原來index+原來的數(shù)組長(zhǎng)度
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
return newTab;
}
這一部分代碼量非常大，很多同學(xué)在這里迷失了，不過這里給大家寫了詳細(xì)的注釋，可以幫助理解。這里其實(shí)分為2部分：
- 1.設(shè)置擴(kuò)容后的數(shù)組大小
newCap和擴(kuò)容后新的閾值newThr，都是擴(kuò)大2倍； - 2.擴(kuò)容后原來數(shù)組數(shù)據(jù)的遷移，只有2種情況，要么原位置，原來原位置+ oldCap
如果上面的代碼還沒有看懂，推薦一下這個(gè)視頻，非常清晰
HashMap你不知道的小秘密
7、為什么加載因子為什么是 0.75？為什么樹化的條件是鏈表長(zhǎng)度為8？為什么樹退化為鏈表長(zhǎng)度為6？
簡(jiǎn)單說下，為什么是 0.75而不是0.6，0.8。因?yàn)樘×藭?huì)導(dǎo)致頻繁擴(kuò)容resize，數(shù)組空間利用率就不高；太大了的話，雖然空間充分利用了，但是計(jì)算下標(biāo)的時(shí)候沖突的概率就變大了。
別去分析了，分析也意義不大，這是大量數(shù)據(jù)計(jì)算后得出的一個(gè)在時(shí)間／空間上平衡（折衷）的方案。
8、HashMap是否有序？
肯定不是啊，存放元素的時(shí)候是隨機(jī)的，所以無序。要有序的話，可以選擇LinkedHashMap和TreeMap。建議面試的時(shí)候說一個(gè)就好，我喜歡說LinkedHashMap。這個(gè)連環(huán)炮可以問出好多問題。
面試必備：LinkedHashMap源碼解析（JDK8）
9、HashMap是否線程安全？
線程不安全。多線程去put()的時(shí)候，有可能造成數(shù)據(jù)覆蓋，擴(kuò)容的時(shí)候也可能會(huì)。要做到線程安全，有這么一些方法：HashTable、Collections.synchronizedMap()、ConcurrentHashMap。這里也是一個(gè)連環(huán)坑，問這個(gè)問題的，一般希望你說一下ConcurrentHashMap原理，還會(huì)扯到多線程同步問題，鎖機(jī)制，互斥鎖、自旋鎖、悲觀鎖、樂觀鎖、等等。
ConcurrentHashMap基于JDK1.8源碼剖析
