HashMap在面試中經(jīng)常會(huì)被問到，一定會(huì)問到它的存儲(chǔ)結(jié)構(gòu)和實(shí)現(xiàn)原理，甚至可能還會(huì)問到一些源碼
今天就來看一下HashMap
首先得看一下HashMap的存儲(chǔ)結(jié)構(gòu)和底層實(shí)現(xiàn)原理
如上圖所示，HashMap底層是用數(shù)組+鏈表+紅黑樹實(shí)現(xiàn)的，其中紅黑樹是JDK1.8對HashMap優(yōu)化之后加入的，當(dāng)鏈表的長度大于8的時(shí)候會(huì)由鏈表結(jié)構(gòu)轉(zhuǎn)為紅黑樹，這些等下在看源碼分析的時(shí)候都可以看到具體的實(shí)現(xiàn)。
那為什么用這幾種數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)？
這種結(jié)構(gòu)在數(shù)據(jù)結(jié)構(gòu)上稱為散列鏈表，其中的數(shù)組就相當(dāng)于一個(gè)一個(gè)的桶(Bucket)，當(dāng)有數(shù)據(jù)準(zhǔn)備存進(jìn)去的時(shí)候，它會(huì)通過一定的散列算法去計(jì)算，盡可能的讓數(shù)據(jù)平均的命中到各個(gè)桶上面去，盡可能的避免哈希碰撞。如果發(fā)生哈希碰撞，就是不同的數(shù)據(jù)最后落到了同一個(gè)桶上的時(shí)候，就采用鏈表的方式來存儲(chǔ)，但是鏈表長度比較長了的時(shí)候，去存儲(chǔ)數(shù)據(jù)，讀取數(shù)據(jù)都需要不停的去遍歷循環(huán)，所以此時(shí)再采用鏈表結(jié)構(gòu)的話效率會(huì)明顯下降，所以JDK1.8之后做了優(yōu)化，當(dāng)鏈表的長度大于8的時(shí)候就由鏈表轉(zhuǎn)為紅黑樹來存儲(chǔ)。紅黑樹是平衡二叉樹的其中一種實(shí)現(xiàn)，它比普通的二叉樹表現(xiàn)更優(yōu)異，因?yàn)槠胀ǖ牟樵兌鏄湓谝欢l件下也可能會(huì)變成鏈表結(jié)構(gòu)，而紅黑樹它是平衡二叉樹的一種，它是通過左旋右旋變色等保持樹的平衡。
簡單的了解了HashMap的存儲(chǔ)結(jié)構(gòu)后，下面來講下HashMap其中三個(gè)方法的源碼
一、hash()方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這個(gè)方法里看似簡單，卻暗藏玄機(jī)。
它是拿到了key本身的hashCode后，又做了一次運(yùn)算，先將原來的hashCode無符號(hào)右位移16位，然后再將原來的hashCode異或(^)上這個(gè)位移后的值，最后得到一個(gè)值。
補(bǔ)充知識(shí)：
表示右移，如果該數(shù)為正，則高位補(bǔ)0，若為負(fù)數(shù)，則高位補(bǔ)1。
表示無符號(hào)右移，也叫邏輯右移，即若該數(shù)為正，則高位補(bǔ)0，而若該數(shù)為負(fù)數(shù)，則右移后高位同樣補(bǔ)0。
^ 表示異或運(yùn)算，每個(gè)位相同為0，不同為1
比如：
0 ^ 1 得 1
1 ^ 1 得 0
0 ^ 0 得 0
1 ^ 0 得 1
那為什么要無符號(hào)右移16位后做異或運(yùn)算？key本身的hashCode直接拿來用不好嗎？
我們做一個(gè)簡單演練
將h無符號(hào)右移16為相當(dāng)于將高區(qū)16位移動(dòng)到了低區(qū)的16位，再與原h(huán)ashcode做異或運(yùn)算，可以將高低位二進(jìn)制特征混合起來
從上文可知高區(qū)的16位與原h(huán)ashcode相比沒有發(fā)生變化，低區(qū)的16位發(fā)生了變化
我們可知通過上面(h = key.hashCode()) ^ (h >>> 16)進(jìn)行運(yùn)算可以把高區(qū)與低區(qū)的二進(jìn)制特征混合到低區(qū)，那么為什么要這么做呢？
我們都知道重新計(jì)算出的新哈希值在后面將會(huì)參與hashmap中數(shù)組槽位的計(jì)算，計(jì)算公式：(n - 1) & hash，假如這時(shí)數(shù)組槽位有16個(gè)，則槽位計(jì)算如下：
仔細(xì)觀察上文不難發(fā)現(xiàn)，高區(qū)的16位很有可能會(huì)被數(shù)組槽位數(shù)的二進(jìn)制碼鎖屏蔽，如果我們不做剛才移位異或運(yùn)算，那么在計(jì)算槽位時(shí)將丟失高區(qū)特征
也許你可能會(huì)說，即使丟失了高區(qū)特征不同hashcode也可以計(jì)算出不同的槽位來，但是細(xì)想當(dāng)兩個(gè)哈希碼很接近時(shí)，那么這高區(qū)的一點(diǎn)點(diǎn)差異就可能導(dǎo)致一次哈希碰撞，所以這也是將性能做到極致的一種體現(xiàn)
使用異或運(yùn)算的原因
異或運(yùn)算能更好的保留各部分的特征，如果采用&運(yùn)算計(jì)算出來的值會(huì)向1靠攏，采用|運(yùn)算計(jì)算出來的值會(huì)向0靠攏
為什么槽位數(shù)必須使用2^n
1、為了讓哈希后的結(jié)果更加均勻
這個(gè)原因我們繼續(xù)用上面的例子來說明
假如槽位數(shù)不是16，而是17，則槽位計(jì)算公式變成：(17 - 1) & hash
從上文可以看出，計(jì)算結(jié)果將會(huì)大大趨同，hashcode參加&運(yùn)算后被更多位的0屏蔽，計(jì)算結(jié)果只剩下兩種0和16，這對于hashmap來說是一種災(zāi)難
2、可以通過位運(yùn)算e.hash & (newCap - 1)來計(jì)算，a % (2^n) 等價(jià)于 a & (2^n - 1) ，位運(yùn)算的運(yùn)算效率高于算術(shù)運(yùn)算，原因是算術(shù)運(yùn)算還是會(huì)被轉(zhuǎn)化為位運(yùn)算
說了這么多點(diǎn)，上面提到的所有問題，最終目的還是為了讓哈希后的結(jié)果更均勻的分部，減少哈希碰撞，提升hashmap的運(yùn)行效率
二、put()方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
這個(gè)沒什么好講的，調(diào)用了下邊的putVal()方法
三、putVal()方法
這個(gè)方法很重要，是往hashMap里put值的核心邏輯，下邊源碼里的每一行我都進(jìn)行了注釋
/**
* 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是不是為空,如果為空,則將容量進(jìn)行初始化,也就是說,初始換操作不是在new HashMap()的時(shí)候進(jìn)行的,而是在第一次put的時(shí)候進(jìn)行的
*/
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/**
* 初始化操作以后,根據(jù)當(dāng)前key的哈希值算出最終命中到哪個(gè)桶上去，并且這個(gè)桶上如果沒有元素的話,則直接new一個(gè)新節(jié)點(diǎn)放進(jìn)去
*/
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;
/** 先判斷一下這個(gè)桶里的第一個(gè)Node元素的key是不是和即將要存的key值相同，如果相同,則
*把當(dāng)前桶里第一個(gè)Node元素賦值給e,這個(gè)else的最下邊進(jìn)行了判斷，如果e!=null就執(zhí)行把
* 新value進(jìn)行替換的操作
*/
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果和桶里第一個(gè)Node的key不相同,則判斷當(dāng)前節(jié)點(diǎn)是不是TreeNode(紅黑樹),如果是,則進(jìn)
//行紅黑樹的插入
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);
//判斷元素個(gè)數(shù)是不是大于等于8
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//轉(zhuǎn)換成紅黑樹
treeifyBin(tab, hash);
break;
}
/**
* 如果在遍歷的時(shí)候，發(fā)現(xiàn)key值相同（就是key已經(jīng)存在了）就什么都不做跳出循環(huán)。因?yàn)樵谏线卐 = p.next的時(shí)候，已經(jīng)記錄e的Node值了，而下邊進(jìn)行了判斷，如果e!=null就執(zhí)行把新value進(jìn)行替換的操作
*/
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//把當(dāng)前下標(biāo)賦值給p并進(jìn)行下一次循環(huán)
p = e;
}
}
/**
只要e不為空,說明要插入的key已經(jīng)存在了,覆蓋舊的value值,然后返回原來oldValue
因?yàn)橹皇翘鎿Q了舊的value值，并沒有插入新的元素，所以不需要下邊的擴(kuò)容判斷，直接
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)到了需要擴(kuò)充的閾值了,如果到了,則進(jìn)行擴(kuò)充
* 如果上一步已經(jīng)判斷key是存在的，只是替換了value值，并沒有插入新的元素，所以不需要判斷
* 擴(kuò)容，不會(huì)走這一步的
*/
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
hashMap中還有其他的一些方法在此就不挨個(gè)來說了
可以在下方進(jìn)行評論，一起學(xué)習(xí)進(jìn)步
