在講解HashMap之前，我們先說一說HashMap中一些比較重要的算法，這個(gè)是我們理解HashMap源碼的關(guān)鍵。
一. 哈?；?/h2>
1.1 用位運(yùn)算實(shí)現(xiàn)哈?；?/h3>
我們知道HashMap是基于哈希表實(shí)現(xiàn)的，而且是鏈地址法實(shí)現(xiàn)的哈希表(即數(shù)組加鏈表的形式)。
哈希表的關(guān)鍵是哈?；?，就是將很大的哈希值轉(zhuǎn)化成變成一定區(qū)間范圍內(nèi)的值，在上一章中我們采用了取余%操作來實(shí)現(xiàn)哈?；?。但是我們知道取余%是非常耗費(fèi)性能的，盡量不要使用這種方式，那怎么實(shí)現(xiàn)高效率的哈?；兀?/p>
我們知道兩個(gè)數(shù)最快的運(yùn)算方式是位運(yùn)算，那么怎么樣使用位運(yùn)算將較大的哈希值hashCode變成一定區(qū)間范圍內(nèi)的值呢？
那就使用&運(yùn)算。我們知道如果有一個(gè)數(shù)它的高位都是0.低位都是1，即0b000011111...這種形式。它與任何一個(gè)數(shù)進(jìn)行&運(yùn)算，得到的結(jié)果值都不可能大于這個(gè)數(shù)。例如0b111 & 0b1010111010010 = 0b010。因?yàn)?amp;運(yùn)算只有兩位都是1才是1，否則就是0.
那怎么得到0b000011111...這種形式的數(shù)?
有一個(gè)非常簡單的方法，如果一個(gè)數(shù)是2的冪數(shù)，即0b0001000...這種形式，例如 2、4、8、16、32等等。這個(gè)數(shù)減一得到的數(shù)就是0b000011111...這種形式。例如8-1 =7(0b111)。
這個(gè)就解釋了為什么HashMap數(shù)組的長度必須是2的冪數(shù)，因?yàn)檫@樣就可以使用&運(yùn)算的方式實(shí)現(xiàn)哈?；?。即 (table.length - 1) & hashCode。
這個(gè)也是一個(gè)公式，即 任何一個(gè)數(shù)x % 2^n都可以轉(zhuǎn)成 數(shù)x & (2^n - 1)。也就是說數(shù)x對2^n進(jìn)行取余，本質(zhì)上是返回?cái)?shù)x 低n位二進(jìn)制數(shù)。這個(gè)很重要，對我們理解resize()方法由很大幫助，具體請看后面對resize()方法的詳解。
1.2 哈希值高位失效問題
但是這里還是有個(gè)問題，那就是哈希值hashCode高位失效。
因?yàn)?amp;運(yùn)算導(dǎo)致哈希值hashCode的高位不管是0或者1，與0相與結(jié)果都是0，會導(dǎo)致很多不同的哈希值hashCode只要低位是相等的，那么哈?；?即相與操作)得到的值是一樣的。
它們會存到同一個(gè)鏈表中，導(dǎo)致哈希表中有的數(shù)組存放的鏈表很長，有的卻是為空，很影響哈希表的效率。
怎么處理hashCode高位失效問題呢？就要用到HashMap中一個(gè)靜態(tài)方法int hash(Object key)。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
看到這種表達(dá)式，一定很懵逼，一步一步分析它的作用。
先看一下它是怎么處理的,h表示key值的哈希值。h >>> 16表示右移16位，我們知道一個(gè)int整形有32位，右移16位表示丟棄高16位的數(shù)據(jù)，因?yàn)槎甲兂筛?6位都變成0了，然后再和原來的h值進(jìn)行異或^。
要知道一個(gè)事實(shí)就是異或^0，每一位保持不變。0b101 ^ 0b000 = 0b101。h ^ (h >>> 16)得到的結(jié)果我們知道高16位是不變的，低16位才可能發(fā)生改變，而且它的改變是與高16位數(shù)有關(guān)的，這樣就將高16位的數(shù)據(jù)也利用起來，減緩了高位失效。
三. 數(shù)組長度
根據(jù)上一節(jié)我們知道，HashMap中數(shù)組的長度必須是2的冪數(shù)。
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
我們知道當(dāng)哈希表元素的個(gè)數(shù)超出哈希表閾值(即數(shù)組長度*負(fù)載因子),就要進(jìn)行數(shù)組擴(kuò)容，而根據(jù)上一節(jié)我們知道，HashMap中數(shù)組的長度必須是2的冪數(shù)。
所以這個(gè)方法就是返回一個(gè)與cap最近的2的冪數(shù)。
怎樣返回一個(gè)與cap最近的2的冪數(shù)呢？有一個(gè)簡單地方法。
int n = 1; while (n < cap) n <<= 1;
這個(gè)實(shí)現(xiàn)方式很容易理解，因?yàn)閚開始值是1，而n <<= 1得到的值一定也是2的冪數(shù),然后利用循環(huán)，找出比cap大(包括等于)的數(shù)。
這種方式簡單易懂,以前HashMap就是用這種方式計(jì)算的，但是可能覺得兩個(gè)數(shù)判斷大小很耗時(shí)間或者循環(huán)比較耗時(shí)間，所以使用了上面這種全新的算法(我只想說mmp)
上面這種算法理解起來就比較麻煩了。
- 首先我們確定一個(gè)事實(shí)，一個(gè)不是0正整數(shù)，它可以表示0b0001XXX這種形式，我們就用0b1000做示范。
- 第一步 n |= n >>> 1 即 0b1000 | 0b0100 = 0b1100
- 第二步 n |= n >>> 2 即 0b1100 | 0b0011 = 0b1111
- 第三步 n |= n >>> 4 即 0b1111 | 0b0000 = 0b1111
不知道大家看出來什么規(guī)律了么？
- 第一步將n右移一位，再與n相或，它的作用就是將n從0b0001XXX變成0b00011XX形式。
- 再看第二步，n右移兩位，那么就是將n從0b00011XX變成0b0001111形式。
- 第三步時(shí)，發(fā)現(xiàn)值沒有變化，那是因?yàn)槲覀円呀?jīng)將n完成轉(zhuǎn)換成0b0001111...形式。
- 因?yàn)閕nt是32位的，所以需要n |= n >>> 16才能確保覆蓋整個(gè)整數(shù)范圍,最后我們再使用n = n+1,將n從0b0001XXX變成0b0010000形式(也就是2的冪數(shù))
還有個(gè)疑惑，這里為什么要n = cap - 1，因?yàn)榘凑瘴覀兊倪壿?，直接使用cap也可以啊。
這就考慮的一個(gè)邊界問題了，如果cap就是2的冪數(shù)，比如是8(即0b1000)，按照算法我們將它變成0b1111形式，最后再加1，就變成了16(即0b10000),那么就就對了，因?yàn)榕c8最近2的冪數(shù)應(yīng)該就是8，與9最近2的冪數(shù)才是16。所以這里先cap - 1將8變成7(0b111)，最后結(jié)果還是8。
最后n >= MAXIMUM_CAPACITY判斷條件，是因?yàn)镠ashMap 數(shù)組最大長度是1 << 30，所以要判斷最大值。
四. 數(shù)組擴(kuò)容
數(shù)組擴(kuò)容對于基于數(shù)組實(shí)現(xiàn)的集合都是很重要的方法，比如ArrayList和HashMap。而HashMap的數(shù)組擴(kuò)容就更加麻煩，它涉及到再哈希的問題。
因?yàn)閿U(kuò)容后的數(shù)組長度與原來數(shù)組長度是不一樣的，那么哈?；蟮玫降南聵?biāo)值也有可能是不一樣的。
4.1 再哈希問題新算法
HashMap的數(shù)組擴(kuò)容是通過resize()方法實(shí)現(xiàn)的，這個(gè)方法最重要的就是將老數(shù)組中全部鍵值對存放到新數(shù)組中。也就是再哈希問題
一種簡單的方法，就是先遍歷老數(shù)組，獲取對應(yīng)鏈表，再遍歷鏈表，得到每個(gè)鍵值對，然后對鍵值對的key進(jìn)行新數(shù)組的哈?；?，得到一個(gè)下標(biāo)值，然后進(jìn)行處理。看一看以前版本jdk是怎么處理這個(gè)問題的。
// jdk老版本進(jìn)行重新哈希化的算法
// 將HashMap中的全部元素都添加到newTable中
void transfer(Entry[] newTable) {
// HashMap老的哈希表
Entry[] src = table;
// 新的哈希表長度
int newCapacity = newTable.length;
// 遍歷老的哈希表
for (int j = 0; j < src.length; j++) {
// 得到j(luò)下標(biāo)處的鏈表
Entry<K, V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K, V> next = e.next;
// 得到新的哈?；南聵?biāo)值
int i = indexFor(e.hash, newCapacity);
// 將元素e插入到鏈表的表頭
e.next = newTable[i];
newTable[i] = e;
// 將next賦值給e，遍歷老的鏈表
e = next;
} while (e != null);
}
}
}
老版本代碼邏輯比較簡單：
- 遍歷老的哈希表，得到鏈表頭元素e，以及下一個(gè)元素next，并求出新的哈希化下標(biāo)值i。
- 將e插入新的哈希表i下標(biāo)位置鏈表的表頭。通過公式e.next = newTable[i]，newTable[i] = e來實(shí)現(xiàn)
- 將next賦值給e，循環(huán)遍歷老的鏈表
這種實(shí)現(xiàn)方式簡單明了，容易讓人理解。但是有個(gè)問題，就是得到的新鏈表和老鏈表是反向的，因?yàn)槲覀儽闅v老鏈表是從頭到尾的，但是插入新鏈表卻是從頭插入。
jdk1.8對再哈希問題提供了全新的算法。我們知道HashMap集合數(shù)組長度必須是2的冪數(shù)(2^n)， 而且每次擴(kuò)容老數(shù)組的一倍，即2^(n+1)。
- 集合中數(shù)組數(shù)量是2的冪數(shù)2^n即0b00010000..這種形式，進(jìn)行哈希化，就是用一個(gè)數(shù)x & (2^n - 1) 返回的就是數(shù)x低位的二進(jìn)制數(shù)(即低n位的二進(jìn)制數(shù))
例如 長度是4(2^2) 0b00100，那么3(2^2 - 1) 0b00011。
數(shù)x分別是3 0b00011 7 0b00111 15 0b01111，它們 & 3 得到都是3，也就是它們在低位(低2位)的表現(xiàn)形式。
- HashMap集合進(jìn)行數(shù)組擴(kuò)容時(shí)，得到新數(shù)組長度就是2^(n+1)，對新數(shù)組進(jìn)行哈?；?，就變成了 數(shù)x & (2^ (n + 1) - 1), 返回的是數(shù)x低n+1位的二進(jìn)制數(shù)。
這個(gè)時(shí)候我們發(fā)現(xiàn)與擴(kuò)容前相比，哈?；南聵?biāo)值低n位是不變的，有可能改變的是就是第n+1位(從低往高數(shù))。
- 如果第n+1位是0，那么新的哈?；牡玫降南聵?biāo)值和原來的是一樣的。
- 如果第n+1位是1，那么新得到的下標(biāo)值與原來相比，要加上 2^n (即原數(shù)組長度)。
例如 長度就從4(2^2) 變成了8(2^3) 0b01000, 那么7(2^3 - 1) 0b00111。
數(shù)x分別是3 0b00011 7 0b00111 15 0b01111，它們 & 7 得到的分別是 3，7， 7，也就是它們在低位(低3位)的表現(xiàn)形式。
注意 第n+1位對應(yīng)的數(shù)是2^n, 比如說第3(2+1)位對應(yīng)的數(shù)是4(2^2)，即0b100.
因此我們發(fā)現(xiàn)對新數(shù)組進(jìn)行哈?；?，有了更好的方式，不需要使用數(shù)x & (2^(n+1) - 1)得到新的下標(biāo)值。變成判斷數(shù)x的第n+1位(從低往高數(shù))是0還是1。
判斷數(shù)x的第n+1位是0還是1，也有個(gè)很簡單的方式。就是用數(shù)x & 2^n ,因?yàn)?^n 只有第n+1位是1，其他位置都是0。那么它與任何數(shù)相&只有兩個(gè)結(jié)果，0表示數(shù)x第n+1是0，1表示數(shù)x第n+1位是1.而2^n就是老數(shù)組的長度。
4.2 再哈希新算法代碼實(shí)現(xiàn)
先遍歷老數(shù)組，用j表示數(shù)組下標(biāo)，獲取下標(biāo)j對應(yīng)位置的鏈表e，如果鏈表e不為null，那么下標(biāo)j就是鏈表e中鍵值對對應(yīng)的哈希值。
根據(jù)鏈表中元素的數(shù)量分為兩種情況：
- 鏈表元素?cái)?shù)量為1
if (e.next == null) newTab[e.hash & (newCap - 1)] = e;
當(dāng)e.next為null，那么鏈表只有一個(gè)元素。發(fā)現(xiàn)這里使用了e.hash & (newCap - 1)計(jì)算新的下標(biāo)值，然后直接將e賦值到這個(gè)位置。這時(shí)我們就有兩個(gè)疑惑了。
- 為什么沒有用新的方式計(jì)算下標(biāo)值呢？這里其實(shí)是可以用新的計(jì)算方式的,例如：
int newIndex = (e.hash & oldCap) == 0 ? j : j + oldCap;
newTab[newIndex] = e;
這個(gè)得到的newIndex值與e.hash & (newCap - 1)得到的值是一樣的，而且計(jì)算起來更加麻煩，這里就不用這種方式。
- 為什么直接將e賦值給newTab數(shù)組，難道不怕newTab數(shù)組該位置已經(jīng)有了元素，而導(dǎo)致被覆蓋情況么?
既然源碼這么寫的，那么就不可能出現(xiàn)覆蓋情況，這時(shí)為什么呢?
我們說過新數(shù)組和老數(shù)組哈?；玫降闹抵挥幸粋€(gè)位會可能不一樣，也就是說新數(shù)組哈?；玫降南聵?biāo)值，要么與老數(shù)組哈?；玫降闹狄粯樱词抢蠑?shù)組哈?；玫降闹导由侠蠑?shù)組的長度。
也就是說老數(shù)組鏈表中的元素會被分配到這個(gè)兩個(gè)位置的鏈表中，而當(dāng)前位置鏈表長度為1，它只能分配到一個(gè)位置，不會發(fā)生覆蓋情況。
- 鏈表元素?cái)?shù)量不為1
else {
// loHead表示放入當(dāng)前j位置鏈表的鏈表頭，loTail表示鏈表尾，
// 因?yàn)镹ode是單向鏈表，所以要用鏈表尾變量，將鍵值對插入到鏈表尾
Node<K,V> loHead = null, loTail = null;
// loHead表示放入當(dāng)前j+oldCap位置鏈表的鏈表頭，loTail表示鏈表尾，
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// (e.hash & oldCap) == 0 表示對n+1位是0，那么它在新數(shù)組中的哈?；蟮闹岛驮瓉淼囊粯? // 將元素放入loHead鏈表中
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循環(huán)遍歷這個(gè)鏈表
} while ((e = next) != null);
// 將鏈表放到新數(shù)組對應(yīng)位置。
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
那么這個(gè)鏈表就可能分為兩個(gè)鏈表，放到本下標(biāo)j位置，以及j+ oldCap下標(biāo)位置。
所以我們要?jiǎng)?chuàng)建兩個(gè)變量loHead和hiHead表示這兩個(gè)鏈表，但是如果我們要保持鏈表的順序不變，就還要?jiǎng)?chuàng)建兩個(gè)變量loTail和hiTail表示鏈表尾，這樣遍歷鏈表的時(shí)候，就可以向新鏈表 鏈表尾插入元素，保證新鏈表的順序和老鏈表一樣。
具體步驟：
- 通過while循環(huán)遍歷鏈表。
- 然后用(e.hash & oldCap) == 0 判斷式，決定鏈表中的元素插入到那個(gè)鏈表中。
- 將兩個(gè)鏈表放入新數(shù)組對應(yīng)位置。
4.3 resize()方法詳解
final Node<K,V>[] resize() {
// 使用oldTab表示原來的數(shù)組
Node<K,V>[] oldTab = table;
// oldCap表示老數(shù)組的長度， oldThr表示老的閾值
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
// newCap表示新數(shù)組的長度， newThr表示新的閾值
int newCap, newThr = 0;
// oldCap > 0表示table數(shù)組已經(jīng)創(chuàng)建了
if (oldCap > 0) {
// 老數(shù)組長度已經(jīng)最大容量了，那么就不能進(jìn)行數(shù)組擴(kuò)容，直接返回老數(shù)組
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 對老數(shù)組長度進(jìn)行2倍擴(kuò)容。
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0)
// table數(shù)組還沒有創(chuàng)建，threshold代表的是數(shù)組的長度，所以賦值給新數(shù)組的長度
newCap = oldThr;
else {
// table數(shù)組還沒有創(chuàng)建，且threshold為0，只有一種情況，那就是使用默認(rèn)無參構(gòu)造函數(shù)創(chuàng)建的Map集合
// 所以使用默認(rèn)的初始數(shù)組長度DEFAULT_INITIAL_CAPACITY(16)
newCap = DEFAULT_INITIAL_CAPACITY;
// 這時(shí)可以直接計(jì)算出它的閾值， 即默認(rèn)數(shù)組長度 16 * 默認(rèn)負(fù)載因子 0.75f
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
// 因?yàn)樾碌臄?shù)組長度newCap可能很大，所以要考慮超過最大容量上限問題，
// 如果出現(xiàn)那樣的情況，那么新的閾值就是int型最大值Integer.MAX_VALUE
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 將新閾值賦值給threshold
threshold = newThr;
// 根據(jù)新的數(shù)組長度創(chuàng)建新的數(shù)組newTab，并將它賦值給table
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 如果老數(shù)組不為空，那么就要將老數(shù)組中鍵值對元素遷移到新數(shù)組newTab中。
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 這個(gè)是紅黑樹節(jié)點(diǎn)
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// loHead表示放入當(dāng)前j位置鏈表的鏈表頭，loTail表示鏈表尾，
// 因?yàn)镹ode是單向鏈表，所以要用鏈表尾變量，將鍵值對插入到鏈表尾
Node<K,V> loHead = null, loTail = null;
// loHead表示放入當(dāng)前j+oldCap位置鏈表的鏈表頭，loTail表示鏈表尾，
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// (e.hash & oldCap) == 0 表示對n+1位是0，那么它在新數(shù)組中的哈?；蟮闹岛驮瓉淼囊粯? // 將元素放入loHead鏈表中
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循環(huán)遍歷這個(gè)鏈表
} while ((e = next) != null);
// 將鏈表放到新數(shù)組對應(yīng)位置。
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
這個(gè)方法返回?cái)U(kuò)容之后的新數(shù)組，主要可能進(jìn)行那個(gè)步驟，創(chuàng)建符合長度的新數(shù)組，確定新的閾值threshold，將老數(shù)組中元素移到新數(shù)組中。
這個(gè)還分為三種情況：
- 老數(shù)組存在，一般是將老數(shù)組進(jìn)行兩倍擴(kuò)容，但是如果老數(shù)組長度已經(jīng)是最大容量MAXIMUM_CAPACITY，不能再擴(kuò)容了，那么就直接返回老數(shù)組。
- 老數(shù)組不存在，那么閾值threshold就是新數(shù)組的長度，還有一種特殊情況，就是threshold也是0。那么它是HashMap空參構(gòu)造函數(shù)創(chuàng)建的，特殊處理。
- 將老數(shù)組元素移動(dòng)到新數(shù)組，這個(gè)在再哈希過程詳細(xì)說了。
未完待續(xù)
