本來今天想要重新整理一些hashMap的源碼閱讀解析文章的相關內容的叼风，后面發(fā)現(xiàn)網上關于HashMap的源碼解析已經有很多專業(yè)的分析了，在看了一遍源碼之后休蟹，我就直接整理一下HashMap相關的一些熱門面試題的答案吧沸枯。
在回答以下的面試題之前日矫，還是希望對HashMap有以下的一些很基礎性的認識。
- HashMap 允許Key绑榴、Value 同時為空
- 線程不安全
- HashMap是使用一個Node<K,V> tables數(shù)組哪轿，里面包含hash、key翔怎、value窃诉、Node next，存放數(shù)據(jù)赤套，存儲結構要么為鏈表飘痛，要么為紅黑樹。假設數(shù)組的索引為N容握，里面的Node進行put時宣脉，如果put之后該索引下的鏈表長度大于8，會根據(jù)判斷tables數(shù)組的長度是否大于64剔氏，才會轉換存儲結構為紅黑樹塑猖。否則只會執(zhí)行擴容。
4.進行pop時谈跛，如果該索引中存儲結構為紅黑樹羊苟，其存儲長度<=6，又會轉化為鏈表的數(shù)據(jù)結構存儲感憾。 - hashMap數(shù)組的初始化之后長度為16.
- 負載因子蜡励，默認為0.75，也可以自己設置吹菱。是時間和空間之間的權衡巍虫，后面會詳細說，這里需要知道鳍刷，如果我們數(shù)組初始化長度為12占遥，通過16負載因子的值得到12，當我們數(shù)組的長度超過12時输瓜，就需要進行擴容瓦胎，每次擴容都是2倍擴容。
面試的問題總結:
從以下幾點思路去入手分析:
size必須是2的整數(shù)次方原因
這個根據(jù)我有去看源碼的思路的理解是這樣的尤揣，在擴容時搔啊，每次都是new一個新的原來兩倍的數(shù)組長度大小的node<k,v>[]數(shù)組，然后再散列的把原來的數(shù)據(jù)加入新數(shù)組北戏。
在put的時候负芋，每一個key，都會對應到一個桶里面嗜愈，通過index = hash & (n-1)計算桶的索引旧蛾。設原來的數(shù)組為table莽龟，負載因子為默認的0.75，長度n為16.則當里面的數(shù)據(jù)量大于12時锨天，需要進行擴容毯盈。就會新建一個長度為16*2的數(shù)組為newTab。然后就會開始把原來數(shù)組tables里面的數(shù)據(jù)搬移到newTab病袄，假設tables的第i個索引搂赋，通過索引的計算公式: hash & n（n為數(shù)組長度） ,對比新舊數(shù)組會發(fā)現(xiàn)一個規(guī)律，當我們把tabsles[i]的node遷到newTab時益缠，里面的node數(shù)據(jù)要么在原來的i位置不變脑奠，要么就在i+n的位置，所以在put時這樣處理把左刽，根據(jù)該公式的值捺信，把tables的數(shù)據(jù)拆分成兩個鏈表L1以及L2酌媒，執(zhí)行一次tables[i]下面的元素遍歷欠痴，令newtab[i]=l1,newtab[i+n]=l2,這樣就會完成tables[i]位置上面所有node的遷移了/refresh，這就是為什么設置容量為什么要為2的整數(shù)次冪帶來的方便之處秒咨。resize的邏輯就是上面講的那樣喇辽。將table[i]處的Node拆分為兩個鏈表，這兩個鏈表再放到newtab[i]和newtab[i+n]位置
get方法的流程
內部會執(zhí)行一個getNode方法判斷的雨席，入?yún)⑹莻魅雓ey的hash計算后的一個整數(shù)類型hash以及key菩咨。內部流程如下:
- 根據(jù) (n-1) & hash的算法得到桶的索引(這個桶要詳細解釋的話，就是hashMap里面存放數(shù)據(jù)的table數(shù)組的某一個索引里面的包含的數(shù)據(jù)結構陡厘，初始化是有16個桶)抽米，獲取出的該桶里面的node。
- 匹配該node值是都是要找的key糙置，如果是則直接返回云茸。
3.否則，先判斷node是否為TreeNode谤饭，也就是紅黑樹類型的node标捺，如果是，則調用紅黑樹的getTreeNode去獲取里面的值揉抵。
4.如果不是亡容，執(zhí)行鏈表查找，直到找到冤今。
附上get(key)源碼
public V get(Object key) {
Node<K,V> e;
//hash：這個函數(shù)上面分析過了闺兢。返回key混淆后的hashCode
//注意getNode返回的類型是Node：當返回值為null時表示map中沒有對應的key，注意區(qū)分value為
//null：如果key對應的value為null的話戏罢，體現(xiàn)在getNode的返回值e.value為null屋谭，此時返回值也是
//null阱佛，也就是HashMap的get函數(shù)不能判斷map中是否有對應的key：get返回值為null時硕淑，可能不包
//含該key咕别，也可能該key的value為null！那么如何判斷map中是否包含某個key呢防嗡？見下面contains
//函數(shù)分析
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//(n-1)&hash：當前key可能在的桶索引所意，put操作時也是將Node存放在index=(n-1)&hash位置
//主要邏輯：如果table[index]處節(jié)點的key就是要找的key則直接返回該節(jié)點淮逊；
//否則：如果在table[index]位置進行搜索，搜索是否存在目標key的Node：這里的搜索又分兩種：
//鏈表搜索和紅黑樹搜索扶踊，具體紅黑樹的查找就不展開了泄鹏，紅黑樹是一種弱平衡(相對于AVL)BST，
//紅黑樹查找秧耗、刪除备籽、插入等操作都能夠保證在O(lon(n))時間復雜度內完成，紅黑樹原理不在本文
//范圍內分井，但是大家要知道紅黑樹的各種操作是可以實現(xiàn)的车猬，簡單點可以把紅黑樹理解為BST，
//BST的查找尺锚、插入珠闰、刪除等操作的實現(xiàn)在之前的博客中有java實現(xiàn)代碼，實際上紅黑樹就是一種平
//衡的BST
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;//一次就匹配到了瘫辩，直接返回伏嗜，否則進行搜索
if ((e = first.next) != null) {
if (first instanceof TreeNode)
//紅黑樹搜索/查找
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//鏈表搜索(查找)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;//找到了就返回
} while ((e = e.next) != null);
}
}
return null;//沒找到，返回null
}
put方法流程
具體流程如下: 內部會執(zhí)行一個putVal的方法伐厌，參數(shù)分別為( hash(key) , key , value , onlyIfAbsent,evict).會稍微復雜一點:
1.如果hashMap里面還未初始化承绸，則初始化resize();
- 如果通過索引定位算法 (n-1) & hash 找到的桶為null，則直接構建一個node挣轨，set進去军熏。
- 如果定位到的tabls[index]有元素了，先判斷該元素key是否與存入的key相等刃唐，享的則set進去羞迷，否則判斷是否為紅黑樹類型，使用紅黑樹的方式put進去putTreeVal画饥。
4.以上都不是衔瓮，則在該桶的位置開始遍歷鏈表，直到鏈表的末尾抖甘，查找是否存在該key热鞍，構建node。
5.判斷遍歷的次數(shù)，如果大于等于8個薇宠，則執(zhí)行是否進行轉為紅黑樹結構存儲的判斷偷办。 - 判斷當前的key是否已存在，存在則更新key澄港，并且有一個鉤子函數(shù)椒涯，未實現(xiàn)，然后會返回舊的key的value值回梧。
7.如果是第一次插入废岂，則會執(zhí)行到failfast機制，不會返回已存在的值狱意，此時也已經put進去了湖苞。
8.判斷當前的hashMap里面的數(shù)量是否大于負載因子計算后的值，需要進行擴容详囤。 - return null
見源碼如下:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//上面提到過HashMap是懶加載财骨，所有put的時候要先檢查table數(shù)組是否已經初始化了，
//沒有初始化得先初始化table數(shù)組藏姐，保證table數(shù)組一定初始化了
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;//這個函數(shù)后面有resize函數(shù)分析
//到這里表示table數(shù)組一定初始化了
//與上面get函數(shù)相同隆箩，指定key的Node，put在table數(shù)組的i=(n-1)&hash下標位置包各，get的時候
//也是從table數(shù)組的該位置搜索
if ((p = tab[i = (n - 1) & hash]) == null)
//如果i位置還沒有存儲元素摘仅，則把當前的key靶庙，value封裝為Node问畅，存儲在table[i]位置
tab[i] = newNode(hash, key, value, null);
else {
//如果table[i]位置已經有元素了，則接下來執(zhí)行的是：
//首先判斷鏈表或者二叉樹中時候已經存在key的鍵值對六荒，存在的話就更新它的value
//不存在的話把當前的key护姆，value插入到鏈表的末尾或者插入到紅黑樹中
//如果鏈表或者紅黑樹中已經存在Node.key等于key，則e指向該Node掏击，即
//e指向一個Node：該Node的key屬性與put時傳入的key參數(shù)相等的那個Node卵皂，后面會更新e.value
Node<K,V> e; K k;
//為什么get和put先判斷p.hash==hash,下面的if條件中去掉hash的比較也可以邏輯也正確？
//因為hash的比較是兩個整數(shù)的比較砚亭，比較的代價相對較小灯变，key是泛型，對象的比較比整數(shù)比較
//代價大捅膘，所以先比較hash添祸，hash相等在比較key
if (p.hash == hash &&//
((k = p.key) == key || (key != null && key.equals(k))))
e = p;//e指向一個Node：該Node的key屬性與put時傳入的key參數(shù)相等的那個Node
else if (p instanceof TreeNode)
//紅黑樹的插入操作，如果已經存在該key的TreeNode寻仗，則返回該TreeNode刃泌，否則返回null
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//table[i]處存放的是鏈表，接下來和TreeNode類似
//在遍歷鏈表過程中先判斷是key先前是否存在，如果存在則e指向該Node
//否則將該Node插入到鏈表末尾耙替，插入后判斷鏈表長度是否>=8亚侠，是的話要進行額外操作
//binCountt最后的值是鏈表的長度
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//遍歷到了鏈表最后一個元素,接下來執(zhí)行鏈表的插入操作，先封裝為Node再插入
//p指向的是鏈表最后一個節(jié)點俗扇，將待插入的Node置為p.next硝烂，就完成了單鏈表的插入
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//TREEIFY_THRESHOLD值是8， binCount>=7,然后又插入了一個新節(jié)點铜幽，
//鏈表長度>=8钢坦，這時要么進行擴容操作，要么把鏈表結構轉為紅黑樹結構
//我們接下會分析treeifyBin的源碼實現(xiàn)
treeifyBin(tab, hash);
break;
}
//當p不是指向鏈表末尾的時候：先判斷p.key是否等于key啥酱，等于的話表示當前key
//已經存在了爹凹，令e指向p，停止遍歷镶殷，最后會更新e的value禾酱；
//不等的話準備下次遍歷，令p=p.next绘趋，即p=e
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
//表示當前的key之前已經存在了颤陶，并且上面的邏輯保證:e.key一定等于key
//這是更新e.value就好
V oldValue = e.value;//保存oldvalue
//onlyIfAbsent默是false，evict為true
//onlyIfAbsent為true表示如果之前已經存在key這個鍵值對了陷遮，那么后面在put這個key
//時滓走，忽略這個操作，不更新先前的value帽馋，這里連接就好
if (!onlyIfAbsent || oldValue == null)
e.value = value;//更新e.value
//這個函數(shù)的默認實現(xiàn)是“空”搅方，即這個函數(shù)默認什么操作都不執(zhí)行，那為什么要有它呢绽族？
//這是個hook/鉤子函數(shù)姨涡，主要要在LinkedHashMap中，LinkedHashMap重寫了這個函數(shù)
//后面講解LinkedHashMap時會詳細講解
afterNodeAccess(e);
return oldValue;//返回舊的value
}
}
//如果是第一次插入key這個鍵吧慢，就會執(zhí)行到這里
++modCount;//failFast機制
//size保存的是當前HashMap中保存了多少個鍵值對涛漂，HashMap的size方法就是直接返回size
//之前說過，threshold保存的是當前table數(shù)組長度*loadfactor检诗，如果table數(shù)組中存儲的
//Node數(shù)量大于threshold匈仗，這時候會進行擴容，即將table數(shù)組的容量翻倍逢慌。后面會詳細講解
//resize方法
if (++size > threshold)
resize();
//這也是一個hook函數(shù)悠轩，作用和afterNodeAccess一樣
afterNodeInsertion(evict);
return null;
}
//將鏈表轉換為紅黑樹結構，在鏈表的插入操作后調用
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//MIN_TREEIFY_CAPACITY值是64,也就是當鏈表長度>8的時候涕癣，有兩種情況：
//如果table數(shù)組的長度<64,此時進行擴容操作
//如果table數(shù)組的長度>64哗蜈，此時進行鏈表轉紅黑樹結構的操作
//具體轉細節(jié)在面試中幾乎沒有問的前标，這里不細講了，
//大部同學認為鏈表長度>8一定會轉換成紅黑樹距潘，這是不對的Ａ读小！音比！
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
resize方法
該方法在初始化以及put的時候俭尖，需要擴容時這兩種情況下，會執(zhí)行該方法洞翩。
先判斷是否超過最大容量稽犁，此時會把擴容臨界點改為Integer的最大值，正常擴容的話會翻倍骚亿，使用位運算去擴容已亥，并重新計算擴容后的最大容量，擴容臨界值threshold也會*2
如果不擴容来屠，該值為空虑椎，會執(zhí)行初始化。
最后是對擴容時的處理俱笛，會新建一個容量為原來容量2倍的node數(shù)組捆姜，把原數(shù)組同索引下的同一個桶中，不管是紅黑樹還是鏈表結構迎膜，都按照(hash & N（該桶的數(shù)量）)得出的值泥技，如果該值為0，則放在鏈表L1(loTail)磕仅，否則L2（hiTail）上.遷移時珊豹，把L1數(shù)據(jù)放到table[i]上面，L2放到table[i+n(擴容前的長度)]上宽涌。
見源碼:
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;//保留擴容前數(shù)組引用
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//正常擴容：newCap = oldCap << 1
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//容量翻倍平夜，擴容后的threshold自然也是*2
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
//table數(shù)組初始化的時候會進入到這里
newCap = DEFAULT_INITIAL_CAPACITY;//默認容量
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//threshold
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;//更新threshold
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//擴容后的新數(shù)組
table = newTab;//執(zhí)行容量翻倍的新數(shù)組
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {//之后完成oldTab中Node遷移到table中去
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)//j這個桶位置只有一個元素，直接rehash到table數(shù)組
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//如果是紅黑樹：也是將紅黑樹拆分為兩個鏈表卸亮，這里主要看鏈表的拆分，兩者邏輯一樣
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//鏈表的拆分
Node<K,V> loHead = null, loTail = null;//第一個鏈表l1
Node<K,V> hiHead = null, hiTail = null;//第二個鏈表l2
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {//rehash到table[j]位置
//將當前node連接到l1上
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
//將當前node連接到l2上
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
//l1放到table[j]位置
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
//l1放到table[j+oldCap]位置
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
影響HashMap的性能因素（key的hashCode函數(shù)實現(xiàn)玩裙、loadFactor兼贸、初始容量）
key的hashCode函數(shù)實現(xiàn)，主要是因為該實現(xiàn)吃溅，可以將key的hashCode的高16位的隨機性與低16位進行異或運算溶诞，增強hash的隨機性減少hash&(n-1)的 隨機性(這個是計算桶的索引的算法)，即減小hash沖突决侈，提高HashMap的性能螺垢。
看源碼：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
loadFactor: 負載因子，決定桶的利用率。當size==桶的數(shù)量DEFAULT_LOAD_FACTOR的時候枉圃，這時HashMap要進行擴容操作功茴，也就是桶不能裝滿。DEFAULT_LOAD_FACTOR是衡量桶的利率:DEFAULT_LOAD_FACTOR較小時（桶的利用率較心跚住）,這時浪費的空間較多（因為只能存儲桶的數(shù)量DEFAULT_LOAD_FACTOR個元素坎穿，超過了就要進行擴容）,這種情況下往HashMap中put元素時發(fā)生沖突的概率也很小，所謂沖突指的是：多個元素被put到了同一個桶 中; 沖突小時（可以認為一個桶中只有一個元素）put返劲、get等HashMap的操作代價就很低玲昧，可以認為是O(1);桶的利用率較大的時候(DEFAULT_LOAD_FACTOR很大，注意可以大于1篮绿，因為沖突的元素是使用鏈表或者 紅黑樹連接起來的)空間利用率較高
HashMap key的hash值計算方法以及原因（見上面hash函數(shù)的分析）
HashMap內部存儲結構：Node數(shù)組+鏈表或紅黑樹
table[i]位置的鏈表什么時候會轉變成紅黑樹
table[i]位置的鏈表里面的node數(shù)量大于8并且整體容量大于64時孵延，會轉換為紅黑樹存儲結構
HashMap主要成員屬性：threshold(擴容的臨界值)、loadFactor(負載因子)亲配、HashMap的懶加載
HashMap的get方法能否判斷某個元素是否在map中
如果java程序對key不存在和存在但是值為null隙袁，判斷是一致的，那么可以使用該get判斷弃榨，不然還是使用containskey();
HashMap線程安全嗎菩收，哪些環(huán)節(jié)最有可能出問題，為什么鲸睛？
線程不安全娜饵，多線程情況下會導致hashmap鏈表閉環(huán)， 一旦進入了閉環(huán)get數(shù)據(jù)官辈，程序就會進入死循環(huán)箱舞，所以導致HashMap是非線程安全的。
HashMap中的hook函數(shù)（可以鏈接到LinkedHashMap講解拳亿，這可作為HashMap的延伸知識晴股，增加面試官對你的印象）
摘自以下博客:
http://www.reibang.com/p/8e668a010f43
線程不安全的hashMap: https://blog.csdn.net/V_Axis/article/details/78604505
