在講解HashMap之前柱恤，我們先說一說HashMap中一些比較重要的算法驮瞧，這個是我們理解HashMap源碼的關(guān)鍵叹括。
一. 哈希化
1.1 用位運算實現(xiàn)哈仙馨樱化
我們知道HashMap是基于哈希表實現(xiàn)的徘意，而且是鏈地址法實現(xiàn)的哈希表(即數(shù)組加鏈表的形式)。
哈希表的關(guān)鍵是哈闲郑化椎咧，就是將很大的哈希值轉(zhuǎn)化成變成一定區(qū)間范圍內(nèi)的值，在上一章中我們采用了取余%操作來實現(xiàn)哈希化的勤讽。但是我們知道取余%是非常耗費性能的蟋座，盡量不要使用這種方式，那怎么實現(xiàn)高效率的哈辖烹梗化呢向臀？
我們知道兩個數(shù)最快的運算方式是位運算，那么怎么樣使用位運算將較大的哈希值hashCode變成一定區(qū)間范圍內(nèi)的值呢诸狭？
那就使用&運算券膀。我們知道如果有一個數(shù)它的高位都是0.低位都是1，即0b000011111...這種形式驯遇。它與任何一個數(shù)進行&運算三娩，得到的結(jié)果值都不可能大于這個數(shù)。例如0b111 & 0b1010111010010 = 0b010妹懒。因為&運算只有兩位都是1才是1雀监，否則就是0.
那怎么得到0b000011111...這種形式的數(shù)?
有一個非常簡單的方法，如果一個數(shù)是2的冪數(shù)眨唬，即0b0001000...這種形式会前，例如 2、4匾竿、8瓦宜、16、32等等岭妖。這個數(shù)減一得到的數(shù)就是0b000011111...這種形式临庇。例如8-1 =7(0b111)。
這個就解釋了為什么HashMap數(shù)組的長度必須是2的冪數(shù)昵慌，因為這樣就可以使用&運算的方式實現(xiàn)哈霞俣幔化。即 (table.length - 1) & hashCode斋攀。
這個也是一個公式已卷，即 任何一個數(shù)x % 2^n都可以轉(zhuǎn)成 數(shù)x & (2^n - 1)。也就是說數(shù)x對2^n進行取余淳蔼，本質(zhì)上是返回數(shù)x 低n位二進制數(shù)侧蘸。這個很重要，對我們理解resize()方法由很大幫助鹉梨，具體請看后面對resize()方法的詳解讳癌。
1.2 哈希值高位失效問題
但是這里還是有個問題，那就是哈希值hashCode高位失效存皂。
因為&運算導(dǎo)致哈希值hashCode的高位不管是0或者1晌坤，與0相與結(jié)果都是0，會導(dǎo)致很多不同的哈希值hashCode只要低位是相等的，那么哈吓菡蹋化(即相與操作)得到的值是一樣的。
它們會存到同一個鏈表中猜憎，導(dǎo)致哈希表中有的數(shù)組存放的鏈表很長娩怎，有的卻是為空，很影響哈希表的效率胰柑。
怎么處理hashCode高位失效問題呢截亦？就要用到HashMap中一個靜態(tài)方法int hash(Object key)。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
看到這種表達式柬讨，一定很懵逼崩瓤，一步一步分析它的作用。
先看一下它是怎么處理的,h表示key值的哈希值踩官。h >>> 16表示右移16位却桶，我們知道一個int整形有32位，右移16位表示丟棄高16位的數(shù)據(jù)蔗牡，因為都變成高16位都變成0了颖系，然后再和原來的h值進行異或^。
要知道一個事實就是異或^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;
}
我們知道當哈希表元素的個數(shù)超出哈希表閾值(即數(shù)組長度*負載因子),就要進行數(shù)組擴容蛤签，而根據(jù)上一節(jié)我們知道，HashMap中數(shù)組的長度必須是2的冪數(shù)栅哀。
所以這個方法就是返回一個與cap最近的2的冪數(shù)震肮。
怎樣返回一個與cap最近的2的冪數(shù)呢？有一個簡單地方法留拾。
int n = 1; while (n < cap) n <<= 1;
這個實現(xiàn)方式很容易理解戳晌，因為n開始值是1，而n <<= 1得到的值一定也是2的冪數(shù),然后利用循環(huán)痴柔，找出比cap大(包括等于)的數(shù)沦偎。
這種方式簡單易懂,以前HashMap就是用這種方式計算的，但是可能覺得兩個數(shù)判斷大小很耗時間或者循環(huán)比較耗時間，所以使用了上面這種全新的算法(我只想說mmp)
上面這種算法理解起來就比較麻煩了豪嚎。
- 首先我們確定一個事實搔驼，一個不是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形式。
- 第三步時震檩，發(fā)現(xiàn)值沒有變化琢蛤，那是因為我們已經(jīng)將n完成轉(zhuǎn)換成0b0001111...形式。
- 因為int是32位的抛虏，所以需要n |= n >>> 16才能確保覆蓋整個整數(shù)范圍,最后我們再使用n = n+1,將n從0b0001XXX變成0b0010000形式(也就是2的冪數(shù))
還有個疑惑虐块，這里為什么要n = cap - 1，因為按照我們的邏輯嘉蕾，直接使用cap也可以啊贺奠。
這就考慮的一個邊界問題了，如果cap就是2的冪數(shù)错忱，比如是8(即0b1000)儡率，按照算法我們將它變成0b1111形式，最后再加1以清，就變成了16(即0b10000),那么就就對了儿普，因為與8最近2的冪數(shù)應(yīng)該就是8，與9最近2的冪數(shù)才是16掷倔。所以這里先cap - 1將8變成7(0b111)眉孩，最后結(jié)果還是8。
最后n >= MAXIMUM_CAPACITY判斷條件勒葱，是因為HashMap 數(shù)組最大長度是1 << 30浪汪，所以要判斷最大值。
四. 數(shù)組擴容
數(shù)組擴容對于基于數(shù)組實現(xiàn)的集合都是很重要的方法凛虽，比如ArrayList和HashMap死遭。而HashMap的數(shù)組擴容就更加麻煩，它涉及到再哈希的問題凯旋。
因為擴容后的數(shù)組長度與原來數(shù)組長度是不一樣的呀潭，那么哈隙っ裕化之后得到的下標值也有可能是不一樣的。
4.1 再哈希問題新算法
HashMap的數(shù)組擴容是通過resize()方法實現(xiàn)的钠署，這個方法最重要的就是將老數(shù)組中全部鍵值對存放到新數(shù)組中糠聪。也就是再哈希問題
一種簡單的方法，就是先遍歷老數(shù)組谐鼎，獲取對應(yīng)鏈表舰蟆，再遍歷鏈表，得到每個鍵值對该面，然后對鍵值對的key進行新數(shù)組的哈县裁纾化信卡，得到一個下標值隔缀，然后進行處理“剑看一看以前版本jdk是怎么處理這個問題的猾瘸。
// jdk老版本進行重新哈希化的算法
// 將HashMap中的全部元素都添加到newTable中
void transfer(Entry[] newTable) {
// HashMap老的哈希表
Entry[] src = table;
// 新的哈希表長度
int newCapacity = newTable.length;
// 遍歷老的哈希表
for (int j = 0; j < src.length; j++) {
// 得到j(luò)下標處的鏈表
Entry<K, V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K, V> next = e.next;
// 得到新的哈隙埃化的下標值
int i = indexFor(e.hash, newCapacity);
// 將元素e插入到鏈表的表頭
e.next = newTable[i];
newTable[i] = e;
// 將next賦值給e牵触，遍歷老的鏈表
e = next;
} while (e != null);
}
}
}
老版本代碼邏輯比較簡單：
- 遍歷老的哈希表，得到鏈表頭元素e咐低，以及下一個元素next揽思，并求出新的哈希化下標值i见擦。
- 將e插入新的哈希表i下標位置鏈表的表頭钉汗。通過公式e.next = newTable[i]，newTable[i] = e來實現(xiàn)
- 將next賦值給e鲤屡，循環(huán)遍歷老的鏈表
這種實現(xiàn)方式簡單明了损痰，容易讓人理解。但是有個問題酒来，就是得到的新鏈表和老鏈表是反向的卢未，因為我們遍歷老鏈表是從頭到尾的，但是插入新鏈表卻是從頭插入堰汉。
jdk1.8對再哈希問題提供了全新的算法辽社。我們知道HashMap集合數(shù)組長度必須是2的冪數(shù)(2^n)， 而且每次擴容老數(shù)組的一倍翘鸭，即2^(n+1)爹袁。
- 集合中數(shù)組數(shù)量是2的冪數(shù)2^n即0b00010000..這種形式，進行哈习蹋化失息，就是用一個數(shù)x & (2^n - 1) 返回的就是數(shù)x低位的二進制數(shù)(即低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集合進行數(shù)組擴容時绎秒，得到新數(shù)組長度就是2^(n+1)浦妄，對新數(shù)組進行哈希化见芹，就變成了 數(shù)x & (2^ (n + 1) - 1), 返回的是數(shù)x低n+1位的二進制數(shù)剂娄。
這個時候我們發(fā)現(xiàn)與擴容前相比，哈闲海化的下標值低n位是不變的阅懦，有可能改變的是就是第n+1位(從低往高數(shù))。
- 如果第n+1位是0徘铝，那么新的哈隙ィ化的得到的下標值和原來的是一樣的。
- 如果第n+1位是1惕它，那么新得到的下標值與原來相比怕午，要加上 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ù)組進行哈虾拚粒化，有了更好的方式疚俱，不需要使用數(shù)x & (2^(n+1) - 1)得到新的下標值劝术。變成判斷數(shù)x的第n+1位(從低往高數(shù))是0還是1。
判斷數(shù)x的第n+1位是0還是1呆奕，也有個很簡單的方式养晋。就是用數(shù)x & 2^n ,因為2^n 只有第n+1位是1，其他位置都是0梁钾。那么它與任何數(shù)相&只有兩個結(jié)果绳泉，0表示數(shù)x第n+1是0，1表示數(shù)x第n+1位是1.而2^n就是老數(shù)組的長度姆泻。
4.2 再哈希新算法代碼實現(xiàn)
先遍歷老數(shù)組零酪，用j表示數(shù)組下標冒嫡，獲取下標j對應(yīng)位置的鏈表e，如果鏈表e不為null四苇，那么下標j就是鏈表e中鍵值對對應(yīng)的哈希值孝凌。
根據(jù)鏈表中元素的數(shù)量分為兩種情況：
- 鏈表元素數(shù)量為1
if (e.next == null) newTab[e.hash & (newCap - 1)] = e;
當e.next為null，那么鏈表只有一個元素月腋。發(fā)現(xiàn)這里使用了e.hash & (newCap - 1)計算新的下標值蟀架，然后直接將e賦值到這個位置。這時我們就有兩個疑惑了榆骚。
- 為什么沒有用新的方式計算下標值呢片拍？這里其實是可以用新的計算方式的,例如：
int newIndex = (e.hash & oldCap) == 0 ? j : j + oldCap;
newTab[newIndex] = e;
這個得到的newIndex值與e.hash & (newCap - 1)得到的值是一樣的，而且計算起來更加麻煩妓肢，這里就不用這種方式捌省。
- 為什么直接將e賦值給newTab數(shù)組，難道不怕newTab數(shù)組該位置已經(jīng)有了元素职恳，而導(dǎo)致被覆蓋情況么?
既然源碼這么寫的所禀，那么就不可能出現(xiàn)覆蓋情況方面，這時為什么呢?
我們說過新數(shù)組和老數(shù)組哈戏徘眨化得到的值只有一個位會可能不一樣，也就是說新數(shù)組哈瞎Ы穑化得到的下標值操禀，要么與老數(shù)組哈希化得到的值一樣横腿，要么是老數(shù)組哈贤切迹化得到的值加上老數(shù)組的長度。
也就是說老數(shù)組鏈表中的元素會被分配到這個兩個位置的鏈表中耿焊，而當前位置鏈表長度為1揪惦，它只能分配到一個位置，不會發(fā)生覆蓋情況罗侯。
- 鏈表元素數(shù)量不為1
else {
// loHead表示放入當前j位置鏈表的鏈表頭器腋，loTail表示鏈表尾，
// 因為Node是單向鏈表钩杰，所以要用鏈表尾變量纫塌，將鍵值對插入到鏈表尾
Node<K,V> loHead = null, loTail = null;
// loHead表示放入當前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)遍歷這個鏈表
} 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;
}
}
那么這個鏈表就可能分為兩個鏈表怎披，放到本下標j位置胸嘁，以及j+ oldCap下標位置。
所以我們要創(chuàng)建兩個變量loHead和hiHead表示這兩個鏈表凉逛，但是如果我們要保持鏈表的順序不變缴渊，就還要創(chuàng)建兩個變量loTail和hiTail表示鏈表尾，這樣遍歷鏈表的時候鱼炒，就可以向新鏈表 鏈表尾插入元素衔沼，保證新鏈表的順序和老鏈表一樣。
具體步驟：
- 通過while循環(huán)遍歷鏈表昔瞧。
- 然后用(e.hash & oldCap) == 0 判斷式指蚁，決定鏈表中的元素插入到那個鏈表中。
- 將兩個鏈表放入新數(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)最大容量了酬荞，那么就不能進行數(shù)組擴容搓劫，直接返回老數(shù)組
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 對老數(shù)組長度進行2倍擴容。
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，只有一種情況，那就是使用默認無參構(gòu)造函數(shù)創(chuàng)建的Map集合
// 所以使用默認的初始數(shù)組長度DEFAULT_INITIAL_CAPACITY(16)
newCap = DEFAULT_INITIAL_CAPACITY;
// 這時可以直接計算出它的閾值县匠， 即默認數(shù)組長度 16 * 默認負載因子 0.75f
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
// 因為新的數(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;
// 這個是紅黑樹節(jié)點
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// loHead表示放入當前j位置鏈表的鏈表頭，loTail表示鏈表尾绣的，
// 因為Node是單向鏈表叠赐，所以要用鏈表尾變量，將鍵值對插入到鏈表尾
Node<K,V> loHead = null, loTail = null;
// loHead表示放入當前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)遍歷這個鏈表
} 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;
}
這個方法返回擴容之后的新數(shù)組，主要可能進行那個步驟宏怔，創(chuàng)建符合長度的新數(shù)組奏路，確定新的閾值threshold畴椰，將老數(shù)組中元素移到新數(shù)組中。
這個還分為三種情況：
- 老數(shù)組存在鸽粉，一般是將老數(shù)組進行兩倍擴容斜脂，但是如果老數(shù)組長度已經(jīng)是最大容量MAXIMUM_CAPACITY，不能再擴容了触机，那么就直接返回老數(shù)組帚戳。
- 老數(shù)組不存在，那么閾值threshold就是新數(shù)組的長度儡首，還有一種特殊情況片任，就是threshold也是0。那么它是HashMap空參構(gòu)造函數(shù)創(chuàng)建的蔬胯，特殊處理对供。
- 將老數(shù)組元素移動到新數(shù)組，這個在再哈希過程詳細說了氛濒。
未完待續(xù)
