HashMap 一直是非常常用的數(shù)據(jù)結(jié)構(gòu)魁瞪，也是面試中十分常問到的集合類型待笑，今天就來說說 HashMap丽柿。
但是為什么要專門說明是 Java8 的 HashMap 呢飞袋？我們都知道恰聘，Java8 有很多大的變化和改動(dòng)句各，如函數(shù)式編程等，而 HashMap 也有了一個(gè)比較大的變化晴叨。
先了解一下 Map
常見的Map類型有以下幾種：
HashMap：
- 哈希表的實(shí)現(xiàn)
- 無序
- 訪問速度快
- key不允許重復(fù)（只允許存在一個(gè)null key）
LinkedHashMap：
- 有序
- HashMap 子類
TreeMap：
- 紅黑樹的實(shí)現(xiàn)
- TreeMap 中保存的記錄會根據(jù) Key 排序（默認(rèn)為升序排序）凿宾，因此使用 Iterator 遍歷時(shí)得到的記錄是排過序的
- 因?yàn)樾枰判颍訲reeMap 中的 key 必須實(shí)現(xiàn) Comparable 接口兼蕊，否則會報(bào) ClassCastException 異常
- TreeMap 會按照其 key 的 compareTo 方法來判斷 key 是否重復(fù)
除了上面幾種以外菌湃，我們還可能看到過一個(gè)叫 Hashtable 的類：
Hashtable：
- 一個(gè)遺留類，線程安全遍略，與 HashMap 類似
- 當(dāng)不需要線程安全時(shí)惧所，選擇 HashMap 代替
- 當(dāng)需要線程安全時(shí)骤坐，使用 ConcurrentHashMap 代替
HashMap
我們現(xiàn)在來正式看一下 HashMap
首先先了解一下 HashMap 內(nèi)部的一些主要特點(diǎn)：
- 使用哈希表（散列表）來進(jìn)行數(shù)據(jù)存儲，并使用鏈地址法來解決沖突
- 當(dāng)鏈表長度大于等于 8 時(shí)下愈，將鏈表轉(zhuǎn)換為紅黑樹來存儲
- 每次進(jìn)行二次冪的擴(kuò)容纽绍，即擴(kuò)容為原容量的兩倍
字段
HashMap 有以下幾個(gè)字段：
- Node[] table：存儲數(shù)據(jù)的哈希表；初始長度 length = 16（
DEFAULT_INITIAL_CAPACITY）势似，擴(kuò)容時(shí)容量為原先的兩倍（n * 2） - final float loadFactor：負(fù)載因子拌夏，確定數(shù)組長度與當(dāng)前所能存儲的鍵值對最大值的關(guān)系；不建議輕易修改履因，除非情況特殊
- int threshold：所能容納的 key-value 對極限 障簿；threshold = length * Load factor，當(dāng)存在的鍵值對大于該值栅迄，則進(jìn)行擴(kuò)容
- int modCount：HashMap 結(jié)構(gòu)修改次數(shù)（例如每次 put 新值使則自增 1）
- int size：當(dāng)前 key-value 個(gè)數(shù)
值得一提的是站故，HashMap 中數(shù)組的初始大小為 16，這是為什么呢毅舆？這個(gè)我會在后面講 put 方法的時(shí)候說到西篓。
方法
hash(Object key)
我們都知道，Object 類的 hashCode 方法與 HashMap 息息相關(guān)憋活，因?yàn)?HashMap 便是通過 hashCode 來確定一個(gè) key 在數(shù)組中的存儲位置岂津。（這里大家都應(yīng)該了解一下 hashCode 與 equals 方法之間的關(guān)系與約定，這里就不多說了）
Java 8 之前的做法和現(xiàn)在的有所不同悦即，Java 8 對此進(jìn)行了改進(jìn)吮成，優(yōu)化了該算法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
值得注意的是，HashMap 并非直接使用 hashCode 作為哈希值辜梳，而是通過這里的 hash 方法對 hashCode 進(jìn)行一系列的移位和異或處理粱甫，這樣處理的目的是為了有效地避免哈希碰撞
我們可以看到，通過這樣的計(jì)算方式冗美，key 的 hash 值高 16 位不變魔种，低 16 位與高 16 位異或作為 key 的最終 hash 值析二；我們后面會知道粉洼，HashMap 通過 (n - 1) & hash 來決定元素的位置（其中 n 是當(dāng)前數(shù)組大小）
很顯然叶摄，這種計(jì)算方式?jīng)Q定了元素的位置只關(guān)系到低位的數(shù)值属韧，這樣會使得哈希碰撞出現(xiàn)的可能性增加，因此我們利用 hash 值高位與低位的異或處理來降低沖突的可能性蛤吓，使得元素的位置不單單取決于低位
put(K key, V value)
put 方法是 HashMap 里面一個(gè)十分核心的方法宵喂，關(guān)系到了 HashMap 對數(shù)據(jù)的存儲問題。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put 方法直接調(diào)用了 putVal 方法会傲，這里我為大家加上了注釋锅棕，可以配合下面的流程圖一步步感受：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
HashMap.Node<K, V>[] tab;
HashMap.Node<K, V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//初始化哈希表
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
//通過哈希值找到對應(yīng)的位置拙泽，如果該位置還沒有元素存在，直接插入
tab[i] = newNode(hash, key, value, null);
else {
HashMap.Node<K, V> e;
K k;
//如果該位置的元素的 key 與之相等裸燎，則直接到后面重新賦值
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof HashMap.TreeNode)
//如果當(dāng)前節(jié)點(diǎn)為樹節(jié)點(diǎn)顾瞻，則將元素插入紅黑樹中
e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
else {
//否則一步步遍歷鏈表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//插入元素到鏈尾
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
//元素個(gè)數(shù)大于等于 8，改造為紅黑樹
treeifyBin(tab, hash);
break;
}
//如果該位置的元素的 key 與之相等德绿，則重新賦值
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//前面當(dāng)哈希表中存在當(dāng)前key時(shí)對e進(jìn)行了賦值荷荤，這里統(tǒng)一對該key重新賦值更新
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//檢查是否超出 threshold 限制，是則進(jìn)行擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
主要的邏輯步驟在此：
有個(gè)值得注意的有趣的地方：在 Java 8 之前移稳，HashMap 插入數(shù)據(jù)時(shí)一直是插入到鏈表表頭蕴纳；而到了 Java 8 之后，則改為了尾部插入个粱。至于頭插入有什么缺點(diǎn)古毛，其中一個(gè)就是在并發(fā)的情況下因?yàn)椴迦攵M(jìn)行擴(kuò)容時(shí)可能會出現(xiàn)鏈表環(huán)而發(fā)生死循環(huán)；當(dāng)然几蜻，HashMap 設(shè)計(jì)出來本身就不是用于并發(fā)的情況的喇潘。
（1）HashMap 初始大小為何是 16
每當(dāng)插入一個(gè)元素時(shí)，我們都需要計(jì)算該值在數(shù)組中的位置梭稚，即p = tab[i = (n - 1) & hash]颖低。
當(dāng) n = 16 時(shí)，n - 1 = 15弧烤，二進(jìn)制為 1111忱屑，這時(shí)和 hash 作與運(yùn)算時(shí)，元素的位置完全取決與 hash 的大小
倘若不是 16暇昂，如 n = 10莺戒，n - 1 = 9，二進(jìn)制為 1001急波，這時(shí)作與運(yùn)算从铲，很容易出現(xiàn)重復(fù)值，如 1101 & 1001澄暮，1011 & 1001名段，1111 & 1001，結(jié)果都是一樣的泣懊，所以選擇 16 以及 每次擴(kuò)容都乘以二的原因也可想而知了
（2）懶加載
我們在 HashMap 的構(gòu)造函數(shù)中可以發(fā)現(xiàn)伸辟，哈希表 Node[] table 并沒有在一開始就完成初始化；觀察 put 方法可以發(fā)現(xiàn)：
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
當(dāng)發(fā)現(xiàn)哈希表為空或者長度為 0 時(shí)馍刮，會使用 resize 方法進(jìn)行初始化信夫，這里很顯然運(yùn)用了 lazy-load 原則，當(dāng)哈希表被首次使用時(shí)，才進(jìn)行初始化
（3）樹化
Java8 中静稻，HashMap 最大的變動(dòng)就是增加了樹化處理警没，當(dāng)鏈表中元素大于等于 8，這時(shí)有可能將鏈表改造為紅黑樹的數(shù)據(jù)結(jié)構(gòu)振湾，為什么我這里說可能呢?
final void treeifyBin(HashMap.Node<K,V>[] tab, int hash) {
int n, index; HashMap.Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
//......
}
我們可以觀察樹化處理的方法 treeifyBin惠奸，發(fā)現(xiàn)當(dāng)tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY為 true 時(shí)，只會進(jìn)行擴(kuò)容處理恰梢，而沒有進(jìn)行樹化佛南；MIN_TREEIFY_CAPACITY 規(guī)定了 HashMap 可以樹化的最小表容量為 64，這是因?yàn)楫?dāng)一開始哈希表容量較小是嵌言，哈希碰撞的幾率會比較大嗅回，而這個(gè)時(shí)候出現(xiàn)長鏈表的可能性會稍微大一些，這種原因下產(chǎn)生的長鏈表摧茴，我們應(yīng)該優(yōu)先選擇擴(kuò)容而避免這類不必要的樹化绵载。
那么，HashMap 為什么要進(jìn)行樹化呢苛白？我們都知道娃豹，鏈表的查詢效率大大低于數(shù)組，而當(dāng)過多的元素連成鏈表购裙，會大大降低查詢存取的性能懂版；同時(shí)，這也涉及到了一個(gè)安全問題躏率，一些代碼可以利用能夠造成哈希沖突的數(shù)據(jù)對系統(tǒng)進(jìn)行攻擊躯畴，這會導(dǎo)致服務(wù)端 CPU 被大量占用。
resize()
擴(kuò)容方法同樣是 HashMap 中十分核心的方法薇芝，同時(shí)也是比較耗性能的操作蓬抄。
我們都知道數(shù)組是無法自動(dòng)擴(kuò)容的，所以我們需要重新計(jì)算新的容量夯到，創(chuàng)建新的數(shù)組嚷缭，并將所有元素拷貝到新數(shù)組中，并釋放舊數(shù)組的數(shù)據(jù)耍贾。
與以往不同的是阅爽，Java8 規(guī)定了 HashMap 每次擴(kuò)容都為之前的兩倍（n*2），也正是因?yàn)槿绱吮普總€(gè)元素在數(shù)組中的新的索引位置只可能是兩種情況优床，一種為不變劝赔，一種為原位置 + 擴(kuò)容長度（即偏移值為擴(kuò)容長度大惺慕埂）；反觀 Java8 之前，每次擴(kuò)容需要重新計(jì)算每個(gè)值在數(shù)組中的索引位置杂伟，增加了性能消耗
接下來簡單給大家說明一下移层，上一段話是什么意思：
前面講 put 的時(shí)候我們知道每個(gè)元素在哈希表數(shù)組中的位置等于 (n - 1) & hash，其中 n 是當(dāng)前數(shù)組的大小赫粥，hash 則是前面講到的 hash 方法計(jì)算出來的哈希值
圖中我們可以看到观话，擴(kuò)容前 0001 0101 和 0000 0101 兩個(gè) hash 值最終的計(jì)算出來的數(shù)組中的位置都是 0000 0101，即為 5越平，此時(shí)數(shù)組大小為 0000 1111 + 1 即 16
擴(kuò)容后频蛔，數(shù)組從 16 擴(kuò)容為兩倍即 32（0001 1111），此時(shí)原先兩個(gè) hash 值計(jì)算出來的結(jié)果分別為 0001 0101 和 0000 0101 即 21 和 5秦叛，兩個(gè)數(shù)之間剛好相差 16晦溪，即數(shù)組的擴(kuò)容大小
這個(gè)其實(shí)很容易理解，數(shù)組擴(kuò)容為原來的兩倍后挣跋，n - 1 改變?yōu)?2n - 1三圆，即在原先的二進(jìn)制的最高位發(fā)生了變化
因此進(jìn)行 ＆ 運(yùn)算后，出來的結(jié)果只可能是兩種情況避咆，一種是毫無影響舟肉，一種為原位置 + 擴(kuò)容長度
那么源代碼中是如何判斷是這兩種情況的哪一種呢？我們前面說到查库，HashMap 中數(shù)組的大小始終為 16 的倍數(shù)路媚，因此 hash & n 和 hash & (2n - 1) 分別計(jì)算出來的值中高位是相等的
因此源碼中使用了一個(gè)非常簡單的方法（oldCap 是原數(shù)組的大小，即 n）
if ((e.hash & oldCap) == 0) {
...
} else {
...
}
當(dāng) e.hash & oldCap 等于 0 時(shí)樊销，元素位置不變磷籍，當(dāng)非 0 時(shí)，位置為原位置 + 擴(kuò)容長度
get(Object key)
了解了 HashMap 的存儲機(jī)制后现柠，get 方法也很好理解了
final HashMap.Node<K,V> getNode(int hash, Object key) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
//檢查當(dāng)前位置的第一個(gè)元素院领，如果正好是該元素，則直接返回
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
//否則檢查是否為樹節(jié)點(diǎn)够吩，則調(diào)用 getTreeNode 方法獲取樹節(jié)點(diǎn)
if (first instanceof HashMap.TreeNode)
return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
//遍歷整個(gè)鏈表比然，尋找目標(biāo)元素
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
主要就四步：
- 哈希表是否為空或者目標(biāo)位置是否存在元素
- 是否為第一個(gè)元素
- 如果是樹節(jié)點(diǎn)，尋找目標(biāo)樹節(jié)點(diǎn)
- 如果是鏈表結(jié)點(diǎn)周循，遍歷鏈表尋找目標(biāo)結(jié)點(diǎn)
