HashMap在面試中經(jīng)常會被問到屹逛，一定會問到它的存儲結(jié)構(gòu)和實現(xiàn)原理刺下，甚至可能還會問到一些源碼
今天就來看一下HashMap
首先得看一下HashMap的存儲結(jié)構(gòu)和底層實現(xiàn)原理
如上圖所示，HashMap底層是用數(shù)組+鏈表+紅黑樹實現(xiàn)的瘦穆，其中紅黑樹是JDK1.8對HashMap優(yōu)化之后加入的闪湾，當(dāng)鏈表的長度大于8的時候會由鏈表結(jié)構(gòu)轉(zhuǎn)為紅黑樹早处，這些等下在看源碼分析的時候都可以看到具體的實現(xiàn)。
那為什么用這幾種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)椒丧？
這種結(jié)構(gòu)在數(shù)據(jù)結(jié)構(gòu)上稱為散列鏈表壹甥，其中的數(shù)組就相當(dāng)于一個一個的桶(Bucket)，當(dāng)有數(shù)據(jù)準(zhǔn)備存進去的時候壶熏，它會通過一定的散列算法去計算句柠，盡可能的讓數(shù)據(jù)平均的命中到各個桶上面去，盡可能的避免哈希碰撞棒假。如果發(fā)生哈希碰撞溯职，就是不同的數(shù)據(jù)最后落到了同一個桶上的時候，就采用鏈表的方式來存儲帽哑，但是鏈表長度比較長了的時候谜酒，去存儲數(shù)據(jù)，讀取數(shù)據(jù)都需要不停的去遍歷循環(huán)妻枕，所以此時再采用鏈表結(jié)構(gòu)的話效率會明顯下降僻族，所以JDK1.8之后做了優(yōu)化粘驰，當(dāng)鏈表的長度大于8的時候就由鏈表轉(zhuǎn)為紅黑樹來存儲。紅黑樹是平衡二叉樹的其中一種實現(xiàn)述么，它比普通的二叉樹表現(xiàn)更優(yōu)異晴氨，因為普通的查詢二叉樹在一定條件下也可能會變成鏈表結(jié)構(gòu)，而紅黑樹它是平衡二叉樹的一種碉输，它是通過左旋右旋變色等保持樹的平衡籽前。
簡單的了解了HashMap的存儲結(jié)構(gòu)后，下面來講下HashMap其中三個方法的源碼
一敷钾、hash()方法
這個方法里看似簡單枝哄，卻暗藏玄機。
它是拿到了key本身的hashCode后阻荒，又做了一次運算挠锥，先將原來的hashCode無符號右位移16位，然后再將原來的hashCode異或(^)上這個位移后的值侨赡，最后得到一個值蓖租。
補充知識：
表示右移，如果該數(shù)為正羊壹，則高位補0蓖宦，若為負數(shù)，則高位補1油猫。
表示無符號右移稠茂，也叫邏輯右移，即若該數(shù)為正情妖，則高位補0睬关，而若該數(shù)為負數(shù)，則右移后高位同樣補0毡证。
^ 表示異或運算电爹，每個位相同為0，不同為1
比如：
0 ^ 1 得 1
1 ^ 1 得 0
0 ^ 0 得 0
1 ^ 0 得 1
那為什么要無符號右移16位后做異或運算料睛？key本身的hashCode直接拿來用不好嗎丐箩？
我們做一個簡單演練
將h無符號右移16為相當(dāng)于將高區(qū)16位移動到了低區(qū)的16位，再與原h(huán)ashcode做異或運算秦效，可以將高低位二進制特征混合起來
從上文可知高區(qū)的16位與原h(huán)ashcode相比沒有發(fā)生變化雏蛮，低區(qū)的16位發(fā)生了變化
我們可知通過上面(h = key.hashCode()) ^ (h >>> 16)進行運算可以把高區(qū)與低區(qū)的二進制特征混合到低區(qū)，那么為什么要這么做呢阱州？
我們都知道重新計算出的新哈希值在后面將會參與hashmap中數(shù)組槽位的計算挑秉，計算公式：(n - 1) & hash，假如這時數(shù)組槽位有16個苔货，則槽位計算如下：
仔細觀察上文不難發(fā)現(xiàn)犀概，高區(qū)的16位很有可能會被數(shù)組槽位數(shù)的二進制碼鎖屏蔽立哑，如果我們不做剛才移位異或運算，那么在計算槽位時將丟失高區(qū)特征
也許你可能會說姻灶，即使丟失了高區(qū)特征不同hashcode也可以計算出不同的槽位來铛绰，但是細想當(dāng)兩個哈希碼很接近時，那么這高區(qū)的一點點差異就可能導(dǎo)致一次哈希碰撞产喉，所以這也是將性能做到極致的一種體現(xiàn)
使用異或運算的原因
異或運算能更好的保留各部分的特征捂掰，如果采用&運算計算出來的值會向1靠攏，采用|運算計算出來的值會向0靠攏
為什么槽位數(shù)必須使用2^n
1曾沈、為了讓哈希后的結(jié)果更加均勻
這個原因我們繼續(xù)用上面的例子來說明
假如槽位數(shù)不是16这嚣，而是17，則槽位計算公式變成：(17 - 1) & hash
從上文可以看出塞俱，計算結(jié)果將會大大趨同姐帚，hashcode參加&運算后被更多位的0屏蔽，計算結(jié)果只剩下兩種0和16障涯，這對于hashmap來說是一種災(zāi)難
2罐旗、可以通過位運算e.hash & (newCap - 1)來計算，a % (2^n) 等價于 a & (2^n - 1) 唯蝶，位運算的運算效率高于算術(shù)運算九秀，原因是算術(shù)運算還是會被轉(zhuǎn)化為位運算
說了這么多點，上面提到的所有問題生棍，最終目的還是為了讓哈希后的結(jié)果更均勻的分部颤霎，減少哈希碰撞，提升hashmap的運行效率
二涂滴、put()方法
這個沒什么好講的，調(diào)用了下邊的putVal()方法
三晴音、putVal()方法
這個方法很重要柔纵，是往hashMap里put值的核心邏輯，下邊源碼里的每一行我都進行了注釋
/Implements Map.put and related methods * * @param hash hash for keyput * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; /** * 判斷tab是不是為空,如果為空,則將容量進行初始化,也就是說,初始換操作不是在new HashMap()的時候進行的,而是在第一次put的時候進行的 */ if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; /** * 初始化操作以后,根據(jù)當(dāng)前key的哈希值算出最終命中到哪個桶上去锤躁，并且這個桶上如果沒有元素的話,則直接new一個新節(jié)點放進去 */ if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); /** * 如果對應(yīng)的桶上已經(jīng)有元素 */ else { Node<K,V> e; K k; /** 先判斷一下這個桶里的第一個Node元素的key是不是和即將要存的key值相同搁料，如果相同,則 *把當(dāng)前桶里第一個Node元素賦值給e,這個else的最下邊進行了判斷，如果e!=null就執(zhí)行把 * 新value進行替換的操作 */ if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //如果和桶里第一個Node的key不相同,則判斷當(dāng)前節(jié)點是不是TreeNode(紅黑樹),如果是,則進 //行紅黑樹的插入 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //如果不是紅黑樹,則循環(huán)鏈表系羞，把數(shù)據(jù)插入鏈表的最后邊 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //判斷元素個數(shù)是不是大于等于8 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st //轉(zhuǎn)換成紅黑樹 treeifyBin(tab, hash); break; } /** * 如果在遍歷的時候郭计，發(fā)現(xiàn)key值相同（就是key已經(jīng)存在了）就什么都不做跳出循環(huán)。因為在上邊e = p.next的時候椒振，已經(jīng)記錄e的Node值了昭伸，而下邊進行了判斷，如果e!=null就執(zhí)行把新value進行替換的操作 */ if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; //把當(dāng)前下標(biāo)賦值給p并進行下一次循環(huán) p = e; } } /** 只要e不為空,說明要插入的key已經(jīng)存在了,覆蓋舊的value值,然后返回原來oldValue 因為只是替換了舊的value值澎迎，并沒有插入新的元素庐杨，所以不需要下邊的擴容判斷选调，直接 return掉 */ if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; /** * 判斷容量是否已經(jīng)到了需要擴充的閾值了,如果到了,則進行擴充 * 如果上一步已經(jīng)判斷key是存在的，只是替換了value值灵份，并沒有插入新的元素仁堪，所以不需要判斷 * 擴容，不會走這一步的 */ if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
hashMap中還有其他的一些方法在此就不挨個來說了
可以在下方進行評論填渠，一起學(xué)習(xí)進步~
