前言
本文源碼分析基于jdk1.8版本（持續(xù)更新中）
1疮绷、HashMap數(shù)據(jù)結(jié)構(gòu)與工作原理
這是基礎中的基礎，這個都不能掌握滩字，面試大概率要翻車。源碼自己看御吞，這里講流程麦箍。
在Jdk1.8中，HashMap數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表+紅黑樹陶珠，數(shù)組也叫做hash表挟裂，每條鏈表也叫做桶(bucket)，紅黑樹是為了提高查詢效率揍诽。
- 1诀蓉、hashmap這個數(shù)組也叫做hash桶(bucket)，
- 2暑脆、存放元素的時候會先根據(jù)key的hash值去計算元素下標渠啤，如果這個下標沒有元素，就創(chuàng)建一個Node節(jié)點放進去添吗；
- 3沥曹、如果數(shù)組下標有數(shù)據(jù)，先判斷key是否相同碟联，相同的話替換元素的value妓美；不同的話插在鏈表的尾節(jié)點。注意：同一個鏈表中的節(jié)點只是說數(shù)組下標相同鲤孵，但不一定是發(fā)生了hash沖突的壶栋，有可能hash值不同；
- 4普监、鏈表長度大于8贵试，且數(shù)組長度大于64，會把鏈表轉(zhuǎn)位紅黑樹凯正，紅黑樹本質(zhì)是一顆自平衡的二叉查找樹毙玻，查找時間復雜度為o(logn)；
- 5漆际、元素容量size超過閾值會擴容淆珊；
下面這張美團技術畫的圖可以很清晰的表達整個流程。
2奸汇、HashMap如何解決hash碰撞（hash沖突）的施符？
拉鏈法。當存儲元素出現(xiàn)hash沖突時擂找，意味著hash值相同的多個元素要存儲在數(shù)組中的同一個位置戳吝，這時候就通過一個單鏈表來解決，每次新增的元素插在尾節(jié)點贯涎。注意：在同一個鏈表中的元素不能給說明一定是沖突的听哭，有可能hash值不相同。
3塘雳、為什么數(shù)組容量必須是2^n（初始化和擴容）陆盘？
為了讓添加的元素均勻分布在HashMap的數(shù)組上，減少hash碰撞败明。
//put()隘马，計算存儲的元素的下標
//n是數(shù)組長度，默認16
i = hash & (n - 1)
這種求下標的做法和hash % n取模運算是一樣的妻顶，只是說&運算是操作的二進制數(shù)酸员，在計算效率上更高一些，反正源碼都很喜歡這種位運算讳嘱。
我們在計算下標的時候當然是希望盡可能讓元素分散到0～n-1位置幔嗦，這樣可以減少沖突，讓查詢效率更高沥潭。下面就來看一下HashMap是怎么做到的邀泉。
hash是int類型，轉(zhuǎn)換為2進制數(shù)是32位钝鸽，為了簡化呼渣，假設
hash=0101 0101，n-1= 15
這樣就可以限制&運算的結(jié)果在0000~1111之間寞埠，轉(zhuǎn)為10進制數(shù)就是0～15屁置，是不是和求余運算的結(jié)果一致？如果n=17仁连，n-1=0001 0000蓝角，這樣&運算結(jié)果的低位全為0，數(shù)組中有很多位置利用不到饭冬，這樣會出現(xiàn)大量的hash沖突使鹅。
結(jié)論：只有數(shù)組長度為2^n，才能保證n-1的低位的值全為1昌抠，這樣元素就可以更均勻的分散在數(shù)組上患朱。
4、擾動函數(shù)
為了散列效果更好炊苫，減少碰撞裁厅，減少沖突冰沙。
在上面的&運算中，盡管已經(jīng)讓元素更分散了执虹，但是還是存在一個問題拓挥，由于n-1的高位全為0，所以&運算的結(jié)果只和hash的低位有關袋励，這樣的話侥啤，發(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()方法，而是重寫了這個散列方法磺芭。有些同學可能不太看得懂這里的位運算赁炎，我就給大家拆解開來看一下。
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; //異或運算徘跪，相同為0甘邀，不同為1
return newHash;
}
這樣的話，大家應該能看懂了吧垮庐。下面借用一張圖來說明上面的計算松邪。
h >>> 16只保留了h的高16位，h ^ high是讓h的高16位與低16位做異或運算哨查，這樣高16位與低16位都參與了hash的運算逗抑，使hash值更加不確定 降低了hash碰撞的概率。
5寒亥、樹化的條件是什么邮府？
網(wǎng)上很多具有誤導性的文章說鏈表長度大于8就會轉(zhuǎn)為紅黑樹，實際上是錯誤的溉奕。樹化其實需要2個條件褂傀，鏈表長度 >=7且數(shù)組長度>= 64
6、HashMap擴容是怎么做的加勤？
擴容有3個觸發(fā)時機仙辟，一個是初始化，也就是第一次put()存放數(shù)據(jù)時鳄梅，另一個是存儲的元素數(shù)量大于閾值threshold時叠国；還有一個是樹化的時候（這一點很多人應該不知道），最后都是調(diào)用resize()方法完成擴容和數(shù)據(jù)遷移的戴尸。
如果你沒看過hashmap擴容實現(xiàn)粟焊，你猜擴容是怎么實現(xiàn)的？難道和ArrayList一樣，數(shù)組拷貝项棠，把元素照般到新的數(shù)組中相同的位置就好了悲雳？實際上不是的，原來數(shù)組中的元素在擴容后只有2種選擇沾乘，第一怜奖，在原來的位置浑测；第二翅阵，在原來位置基礎上再加上原來數(shù)組長度。這里先說結(jié)論迁央，后面再源碼分析掷匠。
再來回顧下，我們是通過如下方式計算元素下標的岖圈。記住一點讹语，&運算算法：2個都是1，結(jié)果才為1蜂科，否則為0顽决。
//n是數(shù)組長度，默認16
i = hash & (n - 1)
下面這幅圖是擴容前后A导匣、B元素的數(shù)組下標的計算過程（有區(qū)別的地方做了標示）才菠。在擴容前A、B的hash值不一樣贡定，但是&運算后的下標卻是一樣的赋访；擴容后發(fā)生了一個變化，就是n變成了2原來的2倍缓待，變成2倍可以用左移1位表示蚓耽，也就是從0000 1111(16)變成0001 1111(32)，那擴容后與運算旋炒，A在高位的第4位&運算結(jié)果為0步悠；B在高位的第4位&運算結(jié)果為1；也就是說A還是在原來的位置瘫镇，B在原來的位置(5),再往后移動16位鼎兽，也就是B移動到21了。
這里的思路很巧妙汇四，利用了移位運算和&運算接奈，
n-1的值擴容后會向左移一位，那只需要看看原來的hash值中和這個新增1相同位置的值是1還是0就好了通孽，是0的話下標沒變序宦，是1的話下標變成“原下標+oldCap"。
源碼解析
final Node<K,V>[] resize() {
// oldTab 指向舊的 table 表
Node<K,V>[] oldTab = table;
// oldCap 代表擴容前 table 表的數(shù)組長度背苦，oldTab 第一次添加元素的時候為 null
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 舊的擴容閾值
int oldThr = threshold;
// 初始化新的閾值和容量
int newCap, newThr = 0;
// 如果 oldCap > 0 則會將新容量擴大到原來的2倍互捌，擴容閾值也將擴大到原來閾值的兩倍
if (oldCap > 0) {
// 如果舊的容量已經(jīng)達到最大容量 2^30 那么就不在繼續(xù)擴容直接返回潘明，將擴容閾值設置到 Integer.MAX_VALUE，并不代表不能裝新元素秕噪，只是數(shù)組長度將不會變化
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}//新容量擴大到原來的2倍钳降，擴容閾值也將擴大到原來閾值的兩倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//oldThr 不為空，代表我們使用帶參數(shù)的構(gòu)造方法指定了加載因子并計算了
//初始初始閾值 會將擴容閾值 賦值給初始容量這里不再是期望容量腌巾，
//但是 >= 指定的期望容量
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else {
// 空參數(shù)構(gòu)造會走這里初始化容量遂填，和擴容閾值 分別是 16 和 12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果新的擴容閾值是0，對應的是當前 table 為空澈蝙，但是有閾值的情況
if (newThr == 0) {
//計算新的擴容閾值
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);
}
//更新全局擴容閾值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//使用新的容量創(chuàng)建新的哈希表的數(shù)組
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//如果老的數(shù)組不為空將進行重新插入操作否則直接返回
if (oldTab != null) {
//遍歷老數(shù)組中每個位置的鏈表或者紅黑樹重新計算節(jié)點位置吓坚，插入新數(shù)組
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;//用來存儲對應數(shù)組位置鏈表頭節(jié)點
//如果當前數(shù)組位置存在元素
if ((e = oldTab[j]) != null) {
// 釋放原來數(shù)組中的對應的空間
oldTab[j] = null;
// 如果鏈表只有一個節(jié)點，
//則使用新的數(shù)組長度計算節(jié)點位于新數(shù)組中的角標并插入
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)//如果當前節(jié)點為紅黑樹則需要進一步確定樹中節(jié)點位于新數(shù)組中的位置灯荧。
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//因為擴容是容量翻倍礁击，
//原鏈表上的每個節(jié)點 現(xiàn)在可能存放在原來的下標，即low位逗载，
//或者擴容后的下標哆窿，即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秧均，應該存放在低位，
//否則存放在高位（稍后有圖片說明）
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;
}
這一部分代碼量非常大，很多同學在這里迷失了链快，不過這里給大家寫了詳細的注釋誉己，可以幫助理解。這里其實分為2部分：
- 1.設置擴容后的數(shù)組大小
newCap和擴容后新的閾值newThr域蜗，都是擴大2倍巨双； - 2.擴容后原來數(shù)組數(shù)據(jù)的遷移，只有2種情況霉祸，要么原位置筑累，原來原位置+ oldCap
如果上面的代碼還沒有看懂，推薦一下這個視頻丝蹭，非常清晰
HashMap你不知道的小秘密
7慢宗、為什么加載因子為什么是 0.75？為什么樹化的條件是鏈表長度為8？為什么樹退化為鏈表長度為6镜沽？
簡單說下敏晤，為什么是 0.75而不是0.6，0.8缅茉。因為太小了會導致頻繁擴容resize嘴脾，數(shù)組空間利用率就不高；太大了的話蔬墩，雖然空間充分利用了译打，但是計算下標的時候沖突的概率就變大了。
別去分析了筹我，分析也意義不大扶平，這是大量數(shù)據(jù)計算后得出的一個在時間／空間上平衡（折衷）的方案帆离。
8蔬蕊、HashMap是否有序？
肯定不是啊哥谷，存放元素的時候是隨機的岸夯，所以無序。要有序的話们妥，可以選擇LinkedHashMap和TreeMap猜扮。建議面試的時候說一個就好，我喜歡說LinkedHashMap监婶。這個連環(huán)炮可以問出好多問題旅赢。
面試必備：LinkedHashMap源碼解析（JDK8）
9、HashMap是否線程安全惑惶？
線程不安全煮盼。多線程去put()的時候，有可能造成數(shù)據(jù)覆蓋带污，擴容的時候也可能會僵控。要做到線程安全，有這么一些方法：HashTable鱼冀、Collections.synchronizedMap()报破、ConcurrentHashMap。這里也是一個連環(huán)坑千绪，問這個問題的充易，一般希望你說一下ConcurrentHashMap原理，還會扯到多線程同步問題荸型，鎖機制盹靴，互斥鎖、自旋鎖、悲觀鎖鹉究、樂觀鎖宇立、等等。
ConcurrentHashMap基于JDK1.8源碼剖析
