在看本文之前财异，強(qiáng)烈建議去讀下我的上一篇文章HashMap的hash機(jī)制詳解 劳跃，有了這個(gè)基礎(chǔ)后本文才更容易理解。
在分析源碼之前邑闲，這里對(duì)整個(gè)HashMap機(jī)制大致做下介紹算行，HashMap還是基于hash表的數(shù)據(jù)結(jié)構(gòu)，解決hash碰撞用的也是拉鏈法监憎，不同的是纱意，java8不只是一個(gè)簡(jiǎn)單的鏈表了婶溯，鏈表長度如果過長會(huì)變成紅黑樹鲸阔。而且和普通固定大小的hash表不同，HashMap需要?jiǎng)討B(tài)擴(kuò)容迄委。所以我們閱讀源碼時(shí)要重點(diǎn)關(guān)注：如何初始化褐筛，何時(shí)擴(kuò)容，擴(kuò)容時(shí)要考慮哪些叙身，解決hash碰撞時(shí)何時(shí)變成紅黑樹渔扎，何時(shí)又會(huì)重新變成鏈表等等。
特殊屬性
首先看下HashMap有哪些關(guān)鍵屬性：
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
/**
* 數(shù)組初始化大小為16
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
*數(shù)組最大容量
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 擴(kuò)容因子信轿，如果目前數(shù)組已使用空間占用總空間的比例達(dá)到或超過這個(gè)值就要擴(kuò)容
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
*鏈表的長度超過這個(gè)值就會(huì)轉(zhuǎn)換成紅黑樹
*/
static final int TREEIFY_THRESHOLD = 8;
/**
*紅黑樹的節(jié)點(diǎn)數(shù)量小于或等于這個(gè)值就要退化到鏈表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
//真正存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
//Hash表真正存儲(chǔ)數(shù)據(jù)的數(shù)組
transient Node<K,V>[] table;
//如果總節(jié)點(diǎn)數(shù)量達(dá)到這個(gè)值就要擴(kuò)容
int threshold;
}
初始化
public HashMap(int initialCapacity, float loadFactor) {
//此處省略一堆檢查校驗(yàn)
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
public HashMap(int initialCapacity) {
//初始大小默認(rèn)16晃痴，擴(kuò)容因子為0.75
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
//默認(rèn)0.75f
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
可以看到整個(gè)初始化其實(shí)就是確定兩個(gè)值，初始容量以及擴(kuò)容因子,另外計(jì)算了真正需要擴(kuò)容的那個(gè)閾值：threshhold
這里大家注意财忽，沒有對(duì)數(shù)組table進(jìn)行任何實(shí)例化操作倘核，沒有真正申請(qǐng)任何空間。
增加（碰撞解決）
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
這里首先是通過hash方法重新計(jì)算了key的hash值：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
至于這個(gè)方法為什么這么寫即彪，可以參考我的上一篇文章：HashMap的hash機(jī)制詳解
然后就是真正的putVal()方法紧唱，由于方法本身比較長，這里不一次性貼出整個(gè)方法源碼，我們一段一段來分析：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//省略其他代碼
}
這里首先判斷了當(dāng)前table數(shù)組是否為空漏益，空了要去開始擴(kuò)容蛹锰，之所以要做這個(gè)判斷是因?yàn)?上一步初始化時(shí)，HashMap并沒有真正申請(qǐng)任何空間绰疤，所以這里是利用了擴(kuò)容方法resize()順帶初始化table數(shù)組了铜犬。
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//省略代碼
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//省略代碼
}
這里大家注意i=(n-1)&hash的計(jì)算，這個(gè)就是根據(jù)hash值來確定當(dāng)前value放置在table數(shù)組的哪個(gè)位置上轻庆，為什么這么算還是參考我的上篇文章：HashMap的hash機(jī)制詳解翎苫。先判斷目標(biāo)位置有沒有被之前的元素占用，如果沒有直接放到該位置上榨了，否者就是下面要開始處理hash碰撞了煎谍。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//此處省略代碼
else {
Node<K,V> e; K k;
//此處的p就是產(chǎn)生hash碰撞位置的原有的數(shù)據(jù)，e用來存放被覆蓋的數(shù)據(jù)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) // 1
e = p;
else if (p instanceof TreeNode) // 2
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { // 3
//此處開始遍歷鏈表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null); //4
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//5
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) //6
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;
}
}
//此處省略代碼
hash碰撞頁分成好幾種情況龙屉，
- key完全相同 呐粘，這就是1號(hào)if對(duì)應(yīng)的情況，key完全相同時(shí)转捕，這里直接記錄了原來的值作岖，這里并沒有直接覆蓋
- key不同，但hash值相同五芝，而且由于此處hash碰撞次數(shù)太多痘儡，處理碰撞的鏈表已經(jīng)變成了紅黑樹，這是2號(hào)if對(duì)應(yīng)的情況枢步，這里直接將新的值插入到紅黑樹即可
- key不同沉删，但hash值相同，而且目前處理hash碰撞還是鏈表形態(tài)醉途，這里對(duì)應(yīng)3好else情況矾瑰，如果順利的話直接遍歷鏈表到尾節(jié)點(diǎn)，然后插入新的值（情況4）隘擎，插入新值后如果鏈表長度達(dá)到了TREEIFY_THRESHOLD（8）就會(huì)開始轉(zhuǎn)變成紅黑樹（情況5）殴穴，以上是理想情況，但還有一種情況货葬，如果和之前鏈表中某個(gè)節(jié)點(diǎn)的key相同呢（情況6）采幌？ 這個(gè)時(shí)候就不用繼續(xù)遍歷鏈表了，此時(shí)的e就指向了那個(gè)相同key的節(jié)點(diǎn)震桶。
上面我們處理了hash碰撞中key不相同的情況休傍，現(xiàn)在看看key相同怎么處理的：
//此處的e就是key相同時(shí)的舊值，會(huì)被新的value替代
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
可以看到?jīng)]有什么操作尼夺，只是在允許（HashMap可以設(shè)置不覆蓋同key的舊值）的情況下直接覆蓋舊值尊残，并返回新值炒瘸。
現(xiàn)在插入完成了，我們還需要判斷是否需要擴(kuò)容：
if (++size > threshold)
resize();
這里注意下寝衫，如果是同key的話顷扩，hashmap并沒有使用新的空間，只是覆蓋而已慰毅，上面已經(jīng)直接return oldValue了隘截，只有在插入了新的值的時(shí)候才會(huì)判斷擴(kuò)容。
擴(kuò)容
在分析源碼之前汹胃，大家先思考下：擴(kuò)容到底擴(kuò)的是哪部分婶芭？擴(kuò)容時(shí)如果是table+鏈表的結(jié)構(gòu)，擴(kuò)容后鏈表怎么辦着饥？如果是紅黑樹呢犀农？紅黑樹怎么辦？
確定要擴(kuò)多大
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) { // 1
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // 2 initial capacity was placed in threshold
newCap = oldThr;
else { // 3 zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
情況2是初始化時(shí)指定了threshold宰掉，這個(gè)情況比較少呵哨，我們重點(diǎn)關(guān)注情況3和情況1。
- 第一次擴(kuò)容（情況3）
之前初始化時(shí)我們還記得那時(shí)只是簡(jiǎn)單的確定了初始容量和擴(kuò)容因子轨奄，具體空間沒有申請(qǐng)孟害，我們第一次put的時(shí)候就會(huì)觸發(fā)這個(gè)擴(kuò)容機(jī)制，進(jìn)入到情況3中來挪拟。 - 后續(xù)擴(kuò)容（情況1）
后續(xù)正常擴(kuò)容一般都會(huì)進(jìn)入情況1挨务，超過最大MAXIMUM_CAPAXITY的情況也比較少，所以一般都會(huì)走
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1;
這樣容量翻倍玉组，擴(kuò)容threshold也翻倍谎柄。
申請(qǐng)新空間
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
這一步?jīng)]什么，直接new了一個(gè)新的數(shù)組
原有數(shù)據(jù)遷移
接下來我們要將原來數(shù)組中的數(shù)據(jù)遷移到新的數(shù)組中來
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
//省略代碼
}
}
可以看到球切，這里就是遍歷舊的數(shù)組中的每一個(gè)數(shù)據(jù)谷誓，然后放到新數(shù)組的合適位置上。
- 遷移沒有產(chǎn)生任何碰撞的數(shù)據(jù)
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
這里直接用新的容量重新計(jì)算了該元素在新數(shù)組中的位置
- 碰撞太多已經(jīng)轉(zhuǎn)變成紅黑樹的元素
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
這里對(duì)于紅黑樹的部分比較負(fù)責(zé)吨凑，本文就不做講解，有興趣的可以自己研究
- 碰撞后產(chǎn)生鏈表的元素
在看源碼之前户辱，我們先考慮一個(gè)問題：擴(kuò)容后所有元素的位置都需要重新計(jì)算嗎鸵钝？我們舉個(gè)例子說明：
原有容量為16，有兩個(gè)元素hash值分別為 e1: 2, e2:18,
2 &（16-1） = 2庐镐；
18 &（16-1） = 2恩商；
這兩個(gè)元素都放置在位置2上，現(xiàn)在擴(kuò)容一倍必逆，兩個(gè)元素如果重新計(jì)算位置的話
2 & (32 -1) = 2;
18 & (32 -1) = 18;
可以看到e1的位置還是不變的怠堪，e2的位置雖然變了揽乱，但只是在原有位置上增加了16而已，有了這個(gè)規(guī)律粟矿，我們就可以將鏈表上的元素分為兩種凰棉，一種在新數(shù)組位置不變newTab[j]上，一種在新數(shù)組 newTab[j+oldCap]上陌粹。接下來我們?cè)倏丛创a：
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;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
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;
}
}
理解上面說的再看源碼就很好理解了撒犀，就是將原本一條鏈表拆成了兩條，一條放置在newTab[j]上掏秩，一條放置在newTab[j+oldCap]上或舞。至于如何判斷一個(gè)元素是否是在原位置還是在新位置上，這里用了一個(gè)位運(yùn)算：
if ((e.hash & oldCap) == 0) {
如果等于0則在原位置蒙幻，否則就要放置在新位置映凳。
總結(jié)
到這里，hashmap基本就分析的差不多了邮破，剩下的get喷鸽，remove熔恢，update之類的操作也就沒有必要再多說了，有了上面的基礎(chǔ)一看就明白了，希望這篇文章對(duì)大家有幫助雹有，如果有理解不到位的，也請(qǐng)各位指正徘层。
