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