簡(jiǎn)介
HashMap在工作中使用頻率最高的用于映射(鍵值對(duì))處理的數(shù)據(jù)類(lèi)型蠢箩。本文主要通過(guò)JDK1.8版本腰池，深入探討HashMap的結(jié)構(gòu)實(shí)現(xiàn)和功能原理。
功能實(shí)現(xiàn)
一忙芒、傳統(tǒng) HashMap 的缺點(diǎn)
JDK 1.8 以前 HashMap 的實(shí)現(xiàn)是 數(shù)組+鏈表示弓，即使哈希函數(shù)取得再好，也很難達(dá)到元素百分百均勻分布呵萨。
當(dāng) HashMap 中有大量的元素都存放到同一個(gè)桶中時(shí)奏属，這個(gè)桶下有一條長(zhǎng)長(zhǎng)的鏈表，這個(gè)時(shí)候 HashMap 就相當(dāng)于一個(gè)單鏈表潮峦，假如單鏈表有 n 個(gè)元素囱皿，遍歷的時(shí)間復(fù)雜度就是 O(n)，完全失去了它的優(yōu)勢(shì)忱嘹。
二嘱腥、JDK1.8實(shí)現(xiàn)
JDK1.8版本中HashMap是數(shù)組+鏈表+紅黑樹(shù)（查找時(shí)間復(fù)雜度為 O(logn)）實(shí)現(xiàn)的。
由于HashMap就是使用哈希表來(lái)存儲(chǔ)的拘悦，當(dāng)兩個(gè)hash值算出同一個(gè)index時(shí)齿兔，就出現(xiàn)了“hash沖突”——兩個(gè)鍵值對(duì)要被插在同一個(gè)bucket里了。
常見(jiàn)解法有兩種：
①開(kāi)放式hash map：用一個(gè)bucket數(shù)組作為骨干础米，然后每個(gè)bucket上掛著一個(gè)鏈表來(lái)存放hash一樣的鍵值對(duì)分苇。有變種不用鏈表而用例如說(shuō)二叉樹(shù)的，反正只要是“開(kāi)放”的屁桑、可以添加元素的數(shù)據(jù)結(jié)構(gòu)就行医寿；
②封閉式hash map：bucket數(shù)組就是主體了，沖突的話就線性向后在數(shù)組里找下一個(gè)空的bucket插入蘑斧；查找操作亦然靖秩。java.util.HashMap用的是開(kāi)放式設(shè)計(jì)。Hash沖突越多越影響訪問(wèn)效率竖瘾，所以要盡量避免沟突。
三、HashMap的原理-哈希表
哈希表的本質(zhì)是一個(gè)數(shù)組准浴，數(shù)組中每一個(gè)元素稱為一個(gè)箱子(bin)事扭，箱子中存放的是鍵值對(duì)。
1乐横、哈希表的存儲(chǔ)過(guò)程如下:
根據(jù) key 計(jì)算出它的哈希值 h求橄。
假設(shè)箱子的個(gè)數(shù)為 n今野，那么這個(gè)鍵值對(duì)應(yīng)該放在第 (h % n) 個(gè)箱子中。
如果該箱子中已經(jīng)有了鍵值對(duì)罐农，就使用開(kāi)放尋址法或者拉鏈法解決沖突条霜。
在使用拉鏈法解決哈希沖突時(shí)，每個(gè)箱子其實(shí)是一個(gè)鏈表涵亏，屬于同一個(gè)箱子的所有鍵值對(duì)都會(huì)排列在鏈表中宰睡。
1.1、負(fù)載因子(load factor)
它用來(lái)衡量哈希表的 空/滿 程度气筋，一定程度上也可以體現(xiàn)查詢的效率拆内，計(jì)算公式為:
負(fù)載因子 = 總鍵值對(duì)數(shù) / 箱子個(gè)數(shù)
源碼：
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
threshold = capacity * loadFactor
1.1.1、為啥負(fù)載因子（DEFAULT_LOAD_FACTOR）默認(rèn)為0.75
源碼文檔
HashMap實(shí)例有兩個(gè)參數(shù)會(huì)影響其性能:初始容量和負(fù)載因子宠默。
（1）容量是哈希表中的桶數(shù)麸恍，初始容量就是創(chuàng)建哈希表時(shí)的容量。
（2）負(fù)載系數(shù)是在哈希表的容量自動(dòng)增加之前搀矫，允許哈希表填滿的度量抹沪。
當(dāng)哈希表中的條目數(shù)量超過(guò)負(fù)載因子和當(dāng)前容量的乘積時(shí)，哈希表就會(huì)被重新哈希(也就是說(shuō)瓤球，重新構(gòu)建內(nèi)部數(shù)據(jù)結(jié)構(gòu))融欧，這樣哈希表的桶數(shù)大約是原來(lái)的兩倍。
（3）一般來(lái)說(shuō)卦羡，默認(rèn)的負(fù)載因子(.75)在時(shí)間和空間成本之間提供了很好的權(quán)衡噪馏。較高的值減少了空間開(kāi)銷(xiāo)，但增加了查找成本(反映在HashMap類(lèi)的大多數(shù)操作中虹茶，包括get和put)逝薪。在設(shè)置映射的初始容量時(shí)，應(yīng)該考慮映射中的期望條目數(shù)及其負(fù)載因子蝴罪，以最小化重哈希操作的數(shù)量。如果初始容量大于條目的最大數(shù)量除以負(fù)載系數(shù)步清，則不會(huì)發(fā)生重哈希操作要门。
如果要將許多映射存儲(chǔ)在HashMap實(shí)例中，那么使用足夠大的容量創(chuàng)建映射將使映射存儲(chǔ)得比根據(jù)需要執(zhí)行自動(dòng)重哈希更有效廓啊。
注意欢搜，使用具有相同hashCode()的多個(gè)鍵肯定會(huì)降低任何哈希表的性能。為了改善影響谴轮，當(dāng)鍵具有可比性時(shí)炒瘟，該類(lèi)可以使用鍵之間的比較順序來(lái)幫助打破關(guān)系。
文檔說(shuō)的主要是：
1第步、負(fù)載因子越大疮装，意味著哈希表越滿缘琅，越容易導(dǎo)致沖突，性能也就越低廓推。負(fù)載因子越小刷袍，越容易導(dǎo)致擴(kuò)容，性能也就越低樊展。因此呻纹，一般來(lái)說(shuō)，當(dāng)負(fù)載因子大于某個(gè)常數(shù)(可能是 1专缠，或者 0.75 等)時(shí)雷酪，哈希表將自動(dòng)擴(kuò)容。
2涝婉、哈希表在自動(dòng)擴(kuò)容時(shí)太闺，一般會(huì)創(chuàng)建兩倍于原來(lái)個(gè)數(shù)的箱子，因此即使 key 的哈希值不變嘁圈，對(duì)箱子個(gè)數(shù)取余的結(jié)果也會(huì)發(fā)生改變省骂，因此所有鍵值對(duì)的存放位置都有可能發(fā)生改變，這個(gè)過(guò)程也稱為重哈希(rehash)最住。
3钞澳、哈希表的擴(kuò)容并不總是能夠有效解決負(fù)載因子過(guò)大的問(wèn)題。假設(shè)所有 key 的哈希值都一樣涨缚，那么即使擴(kuò)容以后他們的位置也不會(huì)變化轧粟。雖然負(fù)載因子會(huì)降低，但實(shí)際存儲(chǔ)在每個(gè)箱子中的鏈表長(zhǎng)度并不發(fā)生改變脓魏，因此也就不能提高哈希表的查詢性能兰吟。
1.2、初始值和最大容量
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
默認(rèn)情況下茂翔，HashMap 初始容量是16混蔼，即2的4次方，最大容量1 << 30;
基于以上總結(jié)珊燎，發(fā)現(xiàn)哈希表的兩個(gè)問(wèn)題:
1惭嚣、如果哈希表中本來(lái)箱子就比較多，擴(kuò)容時(shí)需要重新哈希并移動(dòng)數(shù)據(jù)悔政，性能影響較大晚吞。
2、如果哈希函數(shù)設(shè)計(jì)不合理谋国，哈希表在極端情況下會(huì)變成線性表槽地，性能極低。
2、具體實(shí)現(xiàn)
首先需要清楚HashMap數(shù)據(jù)底層具體存儲(chǔ)的是什么?
根據(jù)源碼捌蚊，HashMap類(lèi)中有一個(gè)字段集畅， Node[] table字段，即哈希桶數(shù)組逢勾，明顯它是一個(gè)Node的數(shù)組牡整。
我們來(lái)看Node是什么。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
從源碼可以看出：Node是HashMap的一個(gè)內(nèi)部類(lèi)溺拱，實(shí)現(xiàn)了Map.Entry接口逃贝，本質(zhì)是就是一個(gè)映射(鍵值對(duì))。當(dāng)我們通過(guò)hashMap.put(key迫摔，value);時(shí)沐扳，Node存儲(chǔ)的就是我們put的k-v鍵值對(duì)。每put一次就把node存儲(chǔ)到bucket數(shù)組中
示意圖如下：
2.1句占、確定哈希桶數(shù)組索引位置
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// h = key.hashCode() : 取hashCode值
// h ^ (h >>> 16) :高位參與運(yùn)算
//tab[i = (n - 1) & hash]: 取模運(yùn)算【這段代碼是在下面的put（）方法里面】
這段代碼為啥要這樣寫(xiě)沪摄，可以參考【位運(yùn)算（java8 HashMap）】
2.2、put()方法
當(dāng)我們通過(guò)下面的代碼添加值的時(shí)候
Map<String, String> map = new HashMap<String, String>();
map.put("key1", "value2");
map.put("key2", "value2");
具體會(huì)由HashMap的put()方法進(jìn)行處理纱烘，下面就是HashMap的put()方法源碼
public V put(K key, V value) {
// 對(duì)key的hashCode()做hash
return putVal(hash(key), key, value, false, true);
}
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為空或者tab長(zhǎng)度為0
if ((tab = table) == null || (n = tab.length) == 0)
//執(zhí)行resize()進(jìn)行擴(kuò)容
n = (tab = resize()).length;
// ②：根據(jù)鍵值key計(jì)算hash值得到插入的哈希數(shù)組索引i杨拐，并對(duì)null做處理
if ((p = tab[i = (n - 1) & hash]) == null)
//null的話說(shuō)明tab中index位置沒(méi)有node，那么就可以直接創(chuàng)建node添加到數(shù)組中
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// ③：節(jié)點(diǎn)key存在擂啥，直接覆蓋value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//覆蓋value
e = p;
// ④：判斷該鏈表為紅黑樹(shù)哄陶，如果是紅黑樹(shù)，則直接在樹(shù)中插入鍵值對(duì)
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// ⑤該鏈為鏈表則遍歷table[i]哺壶，判斷鏈表長(zhǎng)度是否大于8屋吨，大于8的話把鏈表轉(zhuǎn)換為紅黑樹(shù)，
//在紅黑樹(shù)中執(zhí)行插入操作山宾，否則進(jìn)行鏈表的插入操作至扰；
//遍歷過(guò)程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//鏈表長(zhǎng)度大于8轉(zhuǎn)換為紅黑樹(shù)進(jìn)行處理
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//遍歷過(guò)程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// ⑥：超過(guò)最大容量 就擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
static final int TREEIFY_THRESHOLD = 8;
從上面的源碼可以總結(jié)出HashMap的put()方法的執(zhí)行流程：
①.判斷哈希桶數(shù)組table[i]是否為空或length為0，否則執(zhí)行resize()進(jìn)行擴(kuò)容资锰；
②.根據(jù)鍵值key計(jì)算hash值得到插入的哈希數(shù)組索引i敢课，如果table[i]==null，直接新建節(jié)點(diǎn)添加台妆，轉(zhuǎn)向⑥翎猛，如果table[i]不為空，轉(zhuǎn)向③接剩；
③.判斷table[i]的元素，也就是Node節(jié)點(diǎn)中的hash值是否與要添加的key的hash值相等萨咳，并且Node節(jié)點(diǎn)中的key與要添加的key是否相等懊缺，也就是是hashCode以及equals，如果相同直接覆蓋value，如果僅僅是hash值一樣鹃两，key不一樣遗座，那么轉(zhuǎn)向④；
④.判斷table[i] 是否為treeNode俊扳，即table[i] 是否是紅黑樹(shù)途蒋，如果是紅黑樹(shù)，則直接在樹(shù)中插入鍵值對(duì)馋记，否則轉(zhuǎn)向⑤号坡；
⑤.遍歷table[i]，判斷鏈表長(zhǎng)度是否大于8梯醒，大于8的話把鏈表轉(zhuǎn)換為紅黑樹(shù)宽堆，在紅黑樹(shù)中執(zhí)行插入操作，否則進(jìn)行鏈表的插入操作茸习；遍歷過(guò)程中若發(fā)現(xiàn)key已經(jīng)存在直接覆蓋value即可畜隶；
⑥.插入成功后，判斷實(shí)際存在的鍵值對(duì)數(shù)量size是否超多了最大容量threshold号胚，如果超過(guò)籽慢，進(jìn)行擴(kuò)容。
2.3猫胁、get()方法
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;
//①tab不為空并且tab.length不為0箱亿，tab[i]也不為空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果hash和key都一樣，直接從哈希數(shù)組桶中獲取value值
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//②如果hash一樣杜漠，但是key不一樣极景，則從紅黑樹(shù)或者鏈表中查找
if ((e = first.next) != null) {
//如果是紅黑樹(shù)，則到紅黑樹(shù)中查找
if (first instanceof TreeNode)
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;
}
從上面的源碼可以總結(jié)出HashMap的get()方法的執(zhí)行流程：
①.判斷哈希桶數(shù)組tab[i]是否為空或length為0驾茴，根據(jù)鍵值key計(jì)算hash值得到查找的哈希數(shù)組索引i盼樟，如果tab[i]==null，轉(zhuǎn)向⑤锈至；否則轉(zhuǎn)向②
②.判斷tab[i]的元素晨缴，也就是Node節(jié)點(diǎn)中的hash值是否與要查找的key的hash值相等，并且Node節(jié)點(diǎn)中的key與要查找的key是否相等峡捡，也就是hashCode以及equals击碗，如果相同則return node<k,v>，如果僅僅是hash值一樣们拙，key不一樣稍途，那么轉(zhuǎn)向③；
③.判斷table[i] 是否為treeNode砚婆，即table[i] 是否是紅黑樹(shù)械拍，如果是紅黑樹(shù)，則直接在樹(shù)中查找鍵值對(duì)，否則轉(zhuǎn)向④坷虑；
④從鏈表中查找甲馋，首先遍歷tab[i]，根據(jù)hashCode以及equals查找到Node<k,v>迄损；如果查不到轉(zhuǎn)向⑤定躏；
⑤.如果查不到return null。
2.4芹敌、HashMap 在 JDK 1.8 中新增的數(shù)據(jù)結(jié)構(gòu) – 紅黑樹(shù)
2.4.1鏈表樹(shù)化痊远、紅黑樹(shù)鏈化與拆分
源碼：
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
//一個(gè)桶的樹(shù)化閾值
//當(dāng)桶中元素個(gè)數(shù)超過(guò)這個(gè)值時(shí)，需要使用紅黑樹(shù)節(jié)點(diǎn)替換鏈表節(jié)點(diǎn)
//這個(gè)值必須為 8党窜，要不然頻繁轉(zhuǎn)換效率也不高
static final int TREEIFY_THRESHOLD = 8;
//一個(gè)樹(shù)的鏈表還原閾值
//當(dāng)擴(kuò)容時(shí)拗引，桶中元素個(gè)數(shù)小于這個(gè)值，就會(huì)把樹(shù)形的桶元素 還原（切分）為鏈表結(jié)構(gòu)
//這個(gè)值應(yīng)該比上面那個(gè)小幌衣，至少為 6矾削，避免頻繁轉(zhuǎn)換
static final int UNTREEIFY_THRESHOLD = 6;
//哈希表的最小樹(shù)形化容量
//當(dāng)哈希表中的容量大于這個(gè)值時(shí)，表中的桶才能進(jìn)行樹(shù)形化
//否則桶內(nèi)元素太多時(shí)會(huì)擴(kuò)容豁护，而不是樹(shù)形化
//為了避免進(jìn)行擴(kuò)容哼凯、樹(shù)形化選擇的沖突，這個(gè)值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 將普通節(jié)點(diǎn)鏈表轉(zhuǎn)換成樹(shù)形節(jié)點(diǎn)鏈表
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 桶數(shù)組容量小于 MIN_TREEIFY_CAPACITY楚里，優(yōu)先進(jìn)行擴(kuò)容而不是樹(shù)化
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
// hd 為頭節(jié)點(diǎn)（head）断部，tl 為尾節(jié)點(diǎn)（tail）
TreeNode<K,V> hd = null, tl = null;
do {
// 將普通節(jié)點(diǎn)替換成樹(shù)形節(jié)點(diǎn)
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); // 將普通鏈表轉(zhuǎn)成由樹(shù)形節(jié)點(diǎn)鏈表
if ((tab[index] = hd) != null)
// 將樹(shù)形鏈表轉(zhuǎn)換成紅黑樹(shù)
hd.treeify(tab);
}
}
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
可以看到TreeNode有父親、左右孩子班缎、前一個(gè)元素的節(jié)點(diǎn)蝴光，還有個(gè)顏色值。
另外由于它繼承自 LinkedHashMap.Entry
紅黑樹(shù)的三個(gè)關(guān)鍵參數(shù)TREEIFY_THRESHOLD达址、UNTREEIFY_THRESHOLD 蔑祟、MIN_TREEIFY_CAPACITY
擴(kuò)展
（1）為啥當(dāng)桶中元素個(gè)數(shù)超過(guò)8時(shí)，需要使用紅黑樹(shù)節(jié)點(diǎn)替換鏈表節(jié)點(diǎn)沉唠？
（2）為啥桶中元素個(gè)數(shù)小于6疆虚，就會(huì)把樹(shù)形的桶元素 還原（切分）為鏈表結(jié)構(gòu)？
（3）哈希表的最小樹(shù)形化容量為64满葛？
1径簿、因?yàn)榧t黑樹(shù)的平均查找長(zhǎng)度是log(n)，長(zhǎng)度為8的時(shí)候嘀韧，平均查找長(zhǎng)度為3篇亭，如果繼續(xù)使用鏈表，平均查找長(zhǎng)度為8/2=4锄贷，這才有轉(zhuǎn)換為樹(shù)的必要暗赶。
2鄙币、鏈表長(zhǎng)度如果是小于等于6肃叶，6/2=3蹂随，雖然速度也很快的，但是轉(zhuǎn)化為樹(shù)結(jié)構(gòu)和生成樹(shù)的時(shí)間并不會(huì)太短因惭。
選擇6和8岳锁，中間有個(gè)差值7可以有效防止鏈表和樹(shù)頻繁轉(zhuǎn)換。假設(shè)一下蹦魔，如果設(shè)計(jì)成鏈表個(gè)數(shù)超過(guò)8則鏈表轉(zhuǎn)換成樹(shù)結(jié)構(gòu)激率，鏈表個(gè)數(shù)小于8則樹(shù)結(jié)構(gòu)轉(zhuǎn)換成鏈表，如果一個(gè)HashMap不停的插入勿决、刪除元素乒躺，鏈表個(gè)數(shù)在8左右徘徊，就會(huì)頻繁的發(fā)生樹(shù)轉(zhuǎn)鏈表低缩、鏈表轉(zhuǎn)樹(shù)嘉冒，效率會(huì)很低。
3咆繁、當(dāng)桶數(shù)組容量比較小時(shí)讳推，鍵值對(duì)節(jié)點(diǎn) hash 的碰撞率可能會(huì)比較高，進(jìn)而導(dǎo)致鏈表長(zhǎng)度較長(zhǎng)玩般。這個(gè)時(shí)候應(yīng)該優(yōu)先擴(kuò)容银觅，而不是立馬樹(shù)化。畢竟高碰撞率是因?yàn)橥皵?shù)組容量較小引起的坏为，這個(gè)是主因究驴。容量小時(shí)，優(yōu)先擴(kuò)容可以避免一些列的不必要的樹(shù)化過(guò)程匀伏。同時(shí)洒忧，桶容量較小時(shí)，擴(kuò)容會(huì)比較頻繁帘撰，擴(kuò)容時(shí)需要拆分紅黑樹(shù)并重新映射跑慕。所以在桶容量比較小的情況下，將長(zhǎng)鏈表轉(zhuǎn)成紅黑樹(shù)是一件吃力不討好的事摧找。
HashMap 在設(shè)計(jì)之初，并沒(méi)有考慮到以后會(huì)引入紅黑樹(shù)進(jìn)行優(yōu)化堡牡。所以并沒(méi)有像 TreeMap 那樣抒抬，要求鍵類(lèi)實(shí)現(xiàn) comparable 接口或提供相應(yīng)的比較器。但由于樹(shù)化過(guò)程需要比較兩個(gè)鍵對(duì)象的大小晤柄，在鍵類(lèi)沒(méi)有實(shí)現(xiàn) comparable 接口的情況下擦剑，怎么比較鍵與鍵之間的大小了就成了一個(gè)棘手的問(wèn)題。為了解決這個(gè)問(wèn)題芥颈，HashMap 是做了三步處理惠勒，確保可以比較出兩個(gè)鍵的大小爬坑，如下：
- 比較鍵與鍵之間 hash 的大小纠屋，如果 hash 相同，繼續(xù)往下比較
- 檢測(cè)鍵類(lèi)是否實(shí)現(xiàn)了 Comparable 接口盾计，如果實(shí)現(xiàn)調(diào)用 compareTo 方法進(jìn)行比較
- 如果仍未比較出大小售担，就需要進(jìn)行仲裁了，仲裁方法為 tieBreakOrder
tie break 是網(wǎng)球術(shù)語(yǔ)闯估，可以理解為加時(shí)賽的意思灼舍，起這個(gè)名字還是挺有意思的。
通過(guò)上面三次比較涨薪，最終就可以比較出孰大孰小骑素。比較出大小后就可以構(gòu)造紅黑樹(shù)了，最終構(gòu)造出的紅黑樹(shù)如下：
橙色的箭頭表示 TreeNode 的 next 引用刚夺。由于空間有限献丑，prev 引用未畫(huà)出∠拦茫可以看出创橄，鏈表轉(zhuǎn)成紅黑樹(shù)后，原鏈表的順序仍然會(huì)被引用仍被保留了（紅黑樹(shù)的根節(jié)點(diǎn)會(huì)被移動(dòng)到鏈表的第一位）莽红，我們?nèi)匀豢梢园幢闅v鏈表的方式去遍歷上面的紅黑樹(shù)妥畏。這樣的結(jié)構(gòu)為后面紅黑樹(shù)的切分以及紅黑樹(shù)轉(zhuǎn)成鏈表做好了鋪墊，我們繼續(xù)往下分析安吁。
紅黑樹(shù)拆分
擴(kuò)容后醉蚁，普通節(jié)點(diǎn)需要重新映射，紅黑樹(shù)節(jié)點(diǎn)也不例外鬼店。按照一般的思路网棍，我們可以先把紅黑樹(shù)轉(zhuǎn)成鏈表推穷，之后再重新映射鏈表即可绳瘟。這種處理方式是大家比較容易想到的，但這樣做會(huì)損失一定的效率耕突。不同于上面的處理方式炉爆，如上節(jié)所說(shuō)含滴，在將普通鏈表轉(zhuǎn)成紅黑樹(shù)時(shí)辐棒，HashMap 通過(guò)兩個(gè)額外的引用 next 和 prev 保留了原鏈表的節(jié)點(diǎn)順序寡夹。這樣再對(duì)紅黑樹(shù)進(jìn)行重新映射時(shí)，完全可以按照映射鏈表的方式進(jìn)行桨菜。這樣就避免了將紅黑樹(shù)轉(zhuǎn)成鏈表后再進(jìn)行映射豁状，無(wú)形中提高了效率。
以上就是紅黑樹(shù)拆分的邏輯倒得，下面看一下具體實(shí)現(xiàn)吧：
// 紅黑樹(shù)轉(zhuǎn)鏈表閾值
static final int UNTREEIFY_THRESHOLD = 6;
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
/*
* 紅黑樹(shù)節(jié)點(diǎn)仍然保留了 next 引用，故仍可以按鏈表方式遍歷紅黑樹(shù)夭禽。
* 下面的循環(huán)是對(duì)紅黑樹(shù)節(jié)點(diǎn)進(jìn)行分組霞掺，與上面類(lèi)似
*/
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
// 如果 loHead 不為空，且鏈表長(zhǎng)度小于等于 6讹躯，則將紅黑樹(shù)轉(zhuǎn)成鏈表
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
/*
* hiHead == null 時(shí)菩彬，表明擴(kuò)容后，
* 所有節(jié)點(diǎn)仍在原位置潮梯，樹(shù)結(jié)構(gòu)不變骗灶，無(wú)需重新樹(shù)化
*/
if (hiHead != null)
loHead.treeify(tab);
}
}
// 與上面類(lèi)似
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
從源碼上可以看得出，重新映射紅黑樹(shù)的邏輯和重新映射鏈表的邏輯基本一致秉馏。不同的地方在于耙旦，重新映射后，會(huì)將紅黑樹(shù)拆分成兩條由 TreeNode 組成的鏈表萝究。如果鏈表長(zhǎng)度小于 UNTREEIFY_THRESHOLD（6）免都，則將鏈表轉(zhuǎn)換成普通鏈表。否則根據(jù)條件重新將 TreeNode 鏈表樹(shù)化帆竹。舉個(gè)例子說(shuō)明一下绕娘，假設(shè)擴(kuò)容后，重新映射上圖的紅黑樹(shù)栽连，映射結(jié)果如下：
紅黑樹(shù)鏈化
前面說(shuō)過(guò)险领，紅黑樹(shù)中仍然保留了原鏈表節(jié)點(diǎn)順序。有了這個(gè)前提秒紧，再將紅黑樹(shù)轉(zhuǎn)成鏈表就簡(jiǎn)單多了绢陌，僅需將 TreeNode 鏈表轉(zhuǎn)成 Node 類(lèi)型的鏈表即可。相關(guān)代碼如下：
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
// 遍歷 TreeNode 鏈表噩茄，并用 Node 替換
for (Node<K,V> q = this; q != null; q = q.next) {
// 替換節(jié)點(diǎn)類(lèi)型
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
return new Node<>(p.hash, p.key, p.value, next);
}
2.5下面、死循環(huán)
在多線程使用場(chǎng)景中，應(yīng)該盡量避免使用線程不安全的HashMap绩聘，而使用線程安全的ConcurrentHashMap沥割。那么為什么說(shuō)HashMap是線程不安全的耗啦，下面舉例子說(shuō)明在并發(fā)的多線程使用場(chǎng)景中使用HashMap可能造成死循環(huán)。代碼例子如下(便于理解机杜，仍然使用JDK1.7的環(huán)境)：
public class HashMapInfiniteLoop {
private static HashMap<Integer,String> map = new HashMap<Integer,String>(2帜讲，0.75f);
public static void main(String[] args) {
map.put(5， "C");
new Thread("Thread1") {
public void run() {
map.put(7, "B");
System.out.println(map);
};
}.start();
new Thread("Thread2") {
public void run() {
map.put(3, "A);
System.out.println(map);
};
}.start();
}
}
其中椒拗，map初始化為一個(gè)長(zhǎng)度為2的數(shù)組似将，loadFactor=0.75，threshold=2*0.75=1蚀苛，也就是說(shuō)當(dāng)put第二個(gè)key的時(shí)候在验，map就需要進(jìn)行resize。
通過(guò)設(shè)置斷點(diǎn)讓線程1和線程2同時(shí)debug到transfer方法(3.3小節(jié)代碼塊)的首行堵未。注意此時(shí)兩個(gè)線程已經(jīng)成功添加數(shù)據(jù)腋舌。放開(kāi)thread1的斷點(diǎn)至transfer方法的“Entry next = e.next;” 這一行；然后放開(kāi)線程2的的斷點(diǎn)渗蟹，讓線程2進(jìn)行resize块饺。結(jié)果如下圖。
注意雌芽，Thread1的 e 指向了key(3)授艰，而next指向了key(7)，其在線程二rehash后世落，指向了線程二重組后的鏈表淮腾。
線程一被調(diào)度回來(lái)執(zhí)行，先是執(zhí)行 newTalbe[i] = e岛心， 然后是e = next来破，導(dǎo)致了e指向了key(7)，而下一次循環(huán)的next = e.next導(dǎo)致了next指向了key(3)忘古。
e.next = newTable[i] 導(dǎo)致 key(3).next 指向了 key(7)徘禁。注意：此時(shí)的key(7).next 已經(jīng)指向了key(3)， 環(huán)形鏈表就這樣出現(xiàn)了髓堪。
于是送朱，當(dāng)我們用線程一調(diào)用map.get(11)時(shí)，悲劇就出現(xiàn)了——Infinite Loop干旁。
2.6驶沼、其他細(xì)節(jié)
前面的內(nèi)容分析了 HashMap 的常用操作及相關(guān)的源碼，本節(jié)內(nèi)容再補(bǔ)充一點(diǎn)其他方面的東西争群。
被 transient 所修飾 table 變量
如果大家細(xì)心閱讀 HashMap 的源碼回怜，會(huì)發(fā)現(xiàn)桶數(shù)組 table 被申明為 transient。transient 表示易變的意思换薄，在 Java 中玉雾，被該關(guān)鍵字修飾的變量不會(huì)被默認(rèn)的序列化機(jī)制序列化翔试。我們?cè)倩氐皆创a中，考慮一個(gè)問(wèn)題：桶數(shù)組 table 是 HashMap 底層重要的數(shù)據(jù)結(jié)構(gòu)复旬，不序列化的話垦缅，別人還怎么還原呢？
這里簡(jiǎn)單說(shuō)明一下吧驹碍，HashMap 并沒(méi)有使用默認(rèn)的序列化機(jī)制壁涎，而是通過(guò)實(shí)現(xiàn)readObject/writeObject兩個(gè)方法自定義了序列化的內(nèi)容。這樣做是有原因的志秃，試問(wèn)一句怔球，HashMap 中存儲(chǔ)的內(nèi)容是什么？不用說(shuō)洽损，大家也知道是鍵值對(duì)庞溜。所以只要我們把鍵值對(duì)序列化了，我們就可以根據(jù)鍵值對(duì)數(shù)據(jù)重建 HashMap碑定。有的朋友可能會(huì)想，序列化 table 不是可以一步到位又官，后面直接還原不就行了嗎延刘？這樣一想，倒也是合理六敬。但序列化 talbe 存在著兩個(gè)問(wèn)題：
table 多數(shù)情況下是無(wú)法被存滿的碘赖，序列化未使用的部分，浪費(fèi)空間
同一個(gè)鍵值對(duì)在不同 JVM 下外构，所處的桶位置可能是不同的普泡，在不同的 JVM 下反序列化 table 可能會(huì)發(fā)生錯(cuò)誤。
以上兩個(gè)問(wèn)題中审编，第一個(gè)問(wèn)題比較好理解撼班，第二個(gè)問(wèn)題解釋一下。HashMap 的get/put/remove等方法第一步就是根據(jù) hash 找到鍵所在的桶位置垒酬，但如果鍵沒(méi)有覆寫(xiě) hashCode 方法砰嘁，計(jì)算 hash 時(shí)最終調(diào)用 Object 中的 hashCode 方法。但 Object 中的 hashCode 方法是 native 型的勘究，不同的 JVM 下矮湘，可能會(huì)有不同的實(shí)現(xiàn)，產(chǎn)生的 hash 可能也是不一樣的口糕。也就是說(shuō)同一個(gè)鍵在不同平臺(tái)下可能會(huì)產(chǎn)生不同的 hash缅阳，此時(shí)再對(duì)在同一個(gè) table 繼續(xù)操作，就會(huì)出現(xiàn)問(wèn)題景描。
綜上所述十办，大家應(yīng)該能明白 HashMap 不序列化 table 的原因了秀撇。
參考
關(guān)于hashMap的一些按位與計(jì)算的問(wèn)題
Java 8系列之重新認(rèn)識(shí)HashMap
HashMap 源碼詳細(xì)分析(JDK1.8)
