HashMap 作為最常用的集合類之一滤淳，有必要深入淺出的了解一下贤徒。這篇文章會(huì)深入到 HashMap 源碼醉蚁，刨析它的存儲(chǔ)結(jié)構(gòu)以及工作機(jī)制睛琳。
1. HashMap 的存儲(chǔ)結(jié)構(gòu)
HashMap 的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)是一個(gè) Node<K,V> 數(shù)組盒蟆，在（Java 7 中是 Entry<K,V> 數(shù)組，但結(jié)構(gòu)相同）
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
// 數(shù)組
transient Node<K,V>[] table;
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
// 鏈表
Node<K,V> next;
....
}
.....
}
存儲(chǔ)結(jié)構(gòu)主要是****數(shù)組加鏈表****师骗，像下面的圖历等。
2. HashMap 的 put()
在 Java 8 中 HashMap 的 put 方法如下，我已經(jīng)詳細(xì)注釋了重要代碼辟癌。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// 計(jì)算哈希值 與（&）寒屯、非（~）、或（|）黍少、異或（^）
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 如果數(shù)組為空寡夹，進(jìn)行 resize() 初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 如果計(jì)算的位置上Node不存在，直接創(chuàng)建節(jié)點(diǎn)插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 如果計(jì)算的位置上Node 存在厂置，鏈表處理
Node<K,V> e; K k;
// 如果 hash 值菩掏，k 值完全相同，直接覆蓋
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果 index 位置元素已經(jīng)存在昵济，且是紅黑樹(shù)
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 如果這次要放入的值不存在
for (int binCount = 0; ; ++binCount) {
// 尾插法
if ((e = p.next) == null) {
// 找到節(jié)點(diǎn)鏈表中next為空的節(jié)點(diǎn)智绸，創(chuàng)建新的節(jié)點(diǎn)插入
p.next = newNode(hash, key, value, null);
// 如果節(jié)點(diǎn)鏈表中數(shù)量超過(guò)TREEIFY_THRESHOLD（8）個(gè)，轉(zhuǎn)化為紅黑樹(shù)
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果節(jié)點(diǎn)鏈表中有發(fā)現(xiàn)已有相同key
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果節(jié)點(diǎn) e 有值访忿，放入數(shù)組 table[]
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 當(dāng)前大小大于臨界大小瞧栗，擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
舉個(gè)例子，如果 put 的 key 為字母 a醉顽，當(dāng)前 HashMap 容量是初始容量 16沼溜，計(jì)算出位置是 1平挑。
# int hash = key.hashCode()
# hash = hash ^ (hash >>> 16)
# 公式 index = (n - 1) & hash // n 是容量
hash HEX(97) = 0110 0001
n-1 HEX(15) = 0000 1111
--------------------------
結(jié)果 = 0000 0001
# 計(jì)算得到位置是 1
總結(jié) HashMap put 過(guò)程游添。
-
計(jì)算 key 的 hash 值系草。
計(jì)算方式是
(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 檢查當(dāng)前數(shù)組是否為空，為空需要進(jìn)行初始化唆涝，初始化容量是 16 找都，負(fù)載因子默認(rèn) 0.75。
-
計(jì)算 key 在數(shù)組中的坐標(biāo)廊酣。
計(jì)算方式：
(容量 - 1) & hash.因?yàn)槿萘靠偸?的次方能耻，所以-1的值的二進(jìn)制總是全1。方便與 hash 值進(jìn)行與運(yùn)算亡驰。
-
如果計(jì)算出的坐標(biāo)元素為空晓猛，創(chuàng)建節(jié)點(diǎn)加入，put 結(jié)束凡辱。
- 如果當(dāng)前數(shù)組容量大于負(fù)載因子設(shè)置的容量戒职，進(jìn)行擴(kuò)容。
-
如果計(jì)算出的坐標(biāo)元素有值透乾。
如果坐標(biāo)上的元素值和要加入的值 key 完全一樣洪燥，覆蓋原有值。
如果坐標(biāo)上的元素是紅黑樹(shù)乳乌，把要加入的值和 key 加入到紅黑樹(shù)捧韵。
-
如果坐標(biāo)上的元素和要加入的元素不同（尾插法增加）。
如果 next 節(jié)點(diǎn)為空汉操，把要加入的值和 key 加入 next 節(jié)點(diǎn)再来。
-
如果 next 節(jié)點(diǎn)不為空，循環(huán)查看 next 節(jié)點(diǎn)磷瘤。
如果發(fā)現(xiàn)有 next 節(jié)點(diǎn)的 key 和要加入的 key 一樣其弊，對(duì)應(yīng)的值替換為新值。
如果循環(huán) next 節(jié)點(diǎn)查找超過(guò)8層還不為空膀斋，把這個(gè)位置元素轉(zhuǎn)換為紅黑樹(shù)梭伐。
3. HashMap 的 get()
在 Java 8 中 get 方法源碼如下，我已經(jīng)做了注釋說(shuō)明仰担。
public V get(Object key) {
Node<K,V> e;
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;
// 只有在存儲(chǔ)數(shù)組已經(jīng)存在的情況下進(jìn)入這個(gè) if
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// first 是獲取的坐標(biāo)上元素
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
// key 相同糊识，說(shuō)明first是想要的元素，返回
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
// 如果是紅黑樹(shù)摔蓝，從紅黑樹(shù)中查找結(jié)果
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 循環(huán)遍歷查找
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
get 方法流程總結(jié)赂苗。
- 計(jì)算 key 的 hash 值。
- 如果存儲(chǔ)數(shù)組不為空贮尉，且計(jì)算得到的位置上的元素不為空拌滋。繼續(xù)，否則猜谚，返回 Null败砂。
- 如果獲取到的元素的 key 值相等，說(shuō)明查找到了昌犹，返回元素。
- 如果獲取到的元素的 key 值不相等斜姥，查找 next 節(jié)點(diǎn)的元素。
- 如果元素是紅黑樹(shù)铸敏，在紅黑樹(shù)中查找。
- 不是紅黑樹(shù)杈笔，遍歷 next 節(jié)點(diǎn)查找，找到則返回桩撮。
4. HashMap 的 Hash 規(guī)則
- 計(jì)算 hash 值 int hash = key.hashCode()。
- 與或上 hash 值無(wú)符號(hào)右移16 位店量。 hash = hash ^ (hash >>> 16)。
- 位置計(jì)算公式
index = (n - 1) & hash融师，其中n是容量。
這里可能會(huì)有同學(xué)對(duì) hash ^ (hash >>> 16) 有疑惑旱爆，很好奇為什么這里要拿 hash 值異或上 hash 值無(wú)符號(hào)右移 16 位呢舀射？下面通過(guò)一個(gè)例子演示其中道理所在。
假設(shè) hash 值是 0001 0100 1100 0010 0110 0001 0010 0000怀伦，當(dāng)前容量是 16脆烟。
hash = 0001 0100 1100 0010 0110 0001 0010 0000 ---
| 與或計(jì)算
hash >>> 16 = 0000 0000 0000 0000 0001 0100 1100 0010 ---
------------------------------------------------------
hash 結(jié)果 = 0001 0100 1100 0010 0111 0101 1110 0100 ---
| & 與運(yùn)算
容量 -1 = 0000 0000 0000 0000 0000 0000 0000 1111 ---
------------------------------------------------------
# 得到位置 = 0000 0000 0000 0000 0000 0000 0000 0100 得到位置是 4
如果又新增一個(gè)數(shù)據(jù)，得到 hash 值是 0100 0000 1110 0010 1010 0010 0001 0000 房待，容量還是16邢羔，計(jì)算他的位置應(yīng)該是什么呢？
hash = 0100 0000 1110 0010 1010 0010 0001 0000 ---
| 與或計(jì)算
hash >>> 16 = 0000 0000 0000 0000 0001 0100 1100 0010 ---
------------------------------------------------------
hash 結(jié)果 = 0100 0000 1110 0010 1011 0110 1101 0010 ---
| & 與運(yùn)算
容量 -1 = 0000 0000 0000 0000 0000 0000 0000 1111 ---
------------------------------------------------------
# 得到位置 = 0000 0000 0000 0000 0000 0000 0000 0010 得到位置是 2
上面兩個(gè)例子桑孩，得到位置一個(gè)是 4拜鹤，一個(gè)是 2，上面只是我隨便輸入的兩個(gè)二進(jìn)制數(shù)流椒，那么這兩個(gè)數(shù)如果不經(jīng)過(guò) hash ^ (hash >>> 16) 運(yùn)算敏簿，位置會(huì)有什么變化呢？
hash = 0001 0100 1100 0010 0110 0001 0010 0000
容量 -1 = 0000 0000 0000 0000 0000 0000 0000 1111
------------------------------------------------------
結(jié)果 = 0000 0000 0000 0000 0000 0000 0000 0000
# 得到位置是 0
hash = 0100 0000 1110 0010 1010 0010 0001 0000
容量 -1 = 0000 0000 0000 0000 0000 0000 0000 1111
------------------------------------------------------
結(jié)果 = 0000 0000 0000 0000 0000 0000 0000 0000
# 得到位置是 0
可以發(fā)現(xiàn)位置都是 0 ，沖突概率提高了惯裕∥率可見(jiàn) hash ^ (hash >>> 16) 讓數(shù)據(jù)的 hash 值的高 16 位與低 16 位進(jìn)行與或混合，可以減少低位相同時(shí)數(shù)據(jù)插入沖突的概率轻猖。
5. HashMap 的初始化大小
-
初始化大小是 16帆吻，為什么是 16 呢域那？
這可能是因?yàn)槊看螖U(kuò)容都是 2 倍咙边。而選擇 2 的次方值 16 作為初始容量，有利于擴(kuò)容時(shí)重新 Hash 計(jì)算位置次员。為什么是 16 我想是一個(gè)經(jīng)驗(yàn)值败许，理論上說(shuō)只要是 2 的次方都沒(méi)有問(wèn)題。
6. HashMap 的擴(kuò)容方式
負(fù)載因子是多少淑蔚？負(fù)載因子是 0.75市殷。
擴(kuò)容方式是什么？看源碼說(shuō)明刹衫。
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
// 現(xiàn)有容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 現(xiàn)有擴(kuò)容閥值
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
// 如果當(dāng)前長(zhǎng)度已經(jīng)大于最大容量醋寝。結(jié)束擴(kuò)容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 如果擴(kuò)大兩倍之后小于最大容量，且現(xiàn)有容量大于等于初始容量音羞，就擴(kuò)大兩倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
// 擴(kuò)容閥值擴(kuò)大為兩倍
newThr = oldThr << 1; // double threshold
}
// 當(dāng)前容量 = 0 嗅绰，但是當(dāng)前記錄容量 > 0 搀继，獲取當(dāng)前記錄容量叽躯。
else if (oldThr > 0) // initial capacity was placed in threshold
// 進(jìn)入這里，說(shuō)明是通過(guò)指定容量和負(fù)載因子的構(gòu)造函數(shù)
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 進(jìn)入這里說(shuō)明是通過(guò)無(wú)參構(gòu)造
// 新的容量
newCap = DEFAULT_INITIAL_CAPACITY;
// 新的閥值
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
// 計(jì)算擴(kuò)容閥值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 如果 oldTab != null制圈，說(shuō)明是擴(kuò)容鲸鹦，否則是初始化馋嗜，直接返回
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 如果當(dāng)前元素 next節(jié)點(diǎn)沒(méi)有元素葛菇，當(dāng)前元素重新計(jì)算位置直接放入
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 如果當(dāng)前節(jié)點(diǎn)是紅黑樹(shù)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// == 0 ，位置不變
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// e.hash & oldCap != 0 ,位置變?yōu)椋何恢?擴(kuò)容前容量
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
擴(kuò)容時(shí)候怎么重新確定元素在數(shù)組中的位置，我們看到是由 if ((e.hash & oldCap) == 0) 確定的莺债。
hash HEX(97) = 0110 0001
n HEX(16) = 0001 0000
--------------------------
結(jié)果 = 0000 0000
# e.hash & oldCap = 0 計(jì)算得到位置還是擴(kuò)容前位置
hash HEX(17) = 0001 0001
n HEX(16) = 0001 0000
--------------------------
結(jié)果 = 0001 0000
# e.hash & oldCap != 0 計(jì)算得到位置是擴(kuò)容前位置+擴(kuò)容前容量
通過(guò)上面的分析也可以看出齐邦，只有在每次容量都是2的次方的情況下才能使用 if ((e.hash & oldCap) == 0) 判斷擴(kuò)容后的位置。
7. HashMap 中的紅黑樹(shù)
HashMap 在 Java 8 中的實(shí)現(xiàn)增加了紅黑樹(shù)我纪，當(dāng)鏈表節(jié)點(diǎn)達(dá)到 8 個(gè)的時(shí)候浅悉，會(huì)把鏈表轉(zhuǎn)換成紅黑樹(shù)券犁，低于 6 個(gè)的時(shí)候族操，會(huì)退回鏈表。究其原因是因?yàn)楫?dāng)節(jié)點(diǎn)過(guò)多時(shí)泼舱，使用紅黑樹(shù)可以更高效的查找到節(jié)點(diǎn)娇昙。畢竟紅黑樹(shù)是一種二叉查找樹(shù)笤妙。
-
節(jié)點(diǎn)個(gè)數(shù)是多少的時(shí)候，鏈表會(huì)轉(zhuǎn)變成紅黑樹(shù)股毫。
鏈表節(jié)點(diǎn)個(gè)數(shù)大于等于 8 時(shí)铃诬，鏈表會(huì)轉(zhuǎn)換成樹(shù)結(jié)構(gòu)。
-
節(jié)點(diǎn)個(gè)數(shù)是多少的時(shí)候兵志，紅黑樹(shù)會(huì)退回鏈表想罕。
節(jié)點(diǎn)個(gè)數(shù)小于等于 6 時(shí)霉涨，樹(shù)會(huì)轉(zhuǎn)變成鏈表嵌纲。
-
為什么轉(zhuǎn)變條件 8 和 6 有一個(gè)差值腥沽。
如果沒(méi)有差值，都是 8 师溅，那么如果頻繁的插入刪除元素墓臭，鏈表個(gè)數(shù)又剛好在 8 徘徊妖谴，那么就會(huì)頻繁的發(fā)生鏈表轉(zhuǎn)樹(shù)膝舅，樹(shù)轉(zhuǎn)鏈表。
8. 為啥容量都是2的冪洼滚？
容量是2的冪時(shí)遥巴，key 的 hash 值然后 & (容量-1) 確定位置時(shí)碰撞概率會(huì)比較低享幽，因?yàn)槿萘繛?2 的冪時(shí)，減 1 之后的二進(jìn)制數(shù)為全1摆霉，這樣與運(yùn)算的結(jié)果就等于 hasｈ值后面與 1 進(jìn)行與運(yùn)算的幾位斯入。
下面是個(gè)例子。
hash HEX(97) = 0110 0001
n-1 HEX(15) = 0000 1111
--------------------------
結(jié)果 = 0000 0001
# 計(jì)算得到位置是 1
hash HEX(99) = 0110 0011
n-1 HEX(15) = 0000 1111
--------------------------
結(jié)果 = 0000 0011
# 計(jì)算得到位置是 3
hash HEX(101) = 0110 0101
n-1 HEX(15) = 0000 1111
--------------------------
結(jié)果 = 0000 0101
# 計(jì)算得到位置是 5
如果是其他的容量值增蹭，假設(shè)是9滋迈，進(jìn)行與運(yùn)算結(jié)果碰撞的概率就比較大饼灿。
hash HEX(97) = 0110 0001
n-1 HEX(09) = 0000 1001
--------------------------
結(jié)果 = 0000 0001
# 計(jì)算得到位置是 1
hash HEX(99) = 0110 0011
n-1 HEX(09) = 0000 1001
--------------------------
結(jié)果 = 0000 0001
# 計(jì)算得到位置是 1
hash HEX(101) = 0110 0101
n-1 HEX(09) = 0000 1001
--------------------------
結(jié)果 = 0000 0001
# 計(jì)算得到位置是 1
另外碍彭，每次都是 2 的冪也可以讓 HashMap 擴(kuò)容時(shí)可以方便的重新計(jì)算位置悼潭。
hash HEX(97) = 0110 0001
n-1 HEX(15) = 0000 1111
--------------------------
結(jié)果 = 0000 0001
# 計(jì)算得到位置是 1
hash HEX(97) = 0110 0001
n-1 HEX(31) = 0001 1111
--------------------------
結(jié)果 = 0000 0001
# 計(jì)算得到位置是 1
9. 快速失斀⑼省（fail—fast）
HashMap 遍歷使用的是一種快速失敗機(jī)制，它是 Java 非安全集合中的一種普遍機(jī)制略就，這種機(jī)制可以讓集合在遍歷時(shí)表牢，如果有線程對(duì)集合進(jìn)行了修改掖疮、刪除、增加操作恼布，會(huì)觸發(fā)并發(fā)修改異常折汞。
它的實(shí)現(xiàn)機(jī)制是在遍歷前保存一份 modCount 盖腿，在每次獲取下一個(gè)要遍歷的元素時(shí)會(huì)對(duì)比當(dāng)前的 modCount 和保存的 modCount 是否相等。
快速失敗也可以看作是一種安全機(jī)制鸟款，這樣在多線程操作不安全的集合時(shí)，由于快速失敗的機(jī)制组哩，會(huì)拋出異常伶贰。
10. 線程安全的 Map
-
使用 Collections.synchronizedMap(Map) 創(chuàng)建線程安全的 Map.
實(shí)現(xiàn)原理：有一個(gè)變量
final Object mutex;罐栈，操作方法都加了這個(gè)synchronized (mutex)排它鎖荠诬。 使用 Hashtable
使用 ConcurrentHashMap
<完>
這篇文章到這里就結(jié)束了，如果你覺(jué)得文章不錯(cuò)可以關(guān)注我的公眾號(hào)望迎。 公眾號(hào)滿載干貨凌外，童叟無(wú)欺康辑。
也可以訪問(wèn)我的個(gè)人網(wǎng)站:https://www.wdbyte.com
[圖片上傳失敗...(image-84f936-1585702855127)]
