前言
注意：我們今天所有的一切都是基于 JDK 8晶密，JDK 8 的實現(xiàn)和 JDK 7 有重大區(qū)別剂陡。
前面我們分析了 hashCode 和 hash 算法的原理邑时，其實都是為我們解析 HashMap 做鋪墊左医，因為 HashMap 確實比較復(fù)雜（如果你每一行代碼都看的話授帕，每個位移都糾結(jié)的話）同木，雖然總的來說，HashMap 不過是 Node 數(shù)組加 鏈表和紅黑樹跛十。但是里面的細(xì)節(jié)確是無比的優(yōu)雅和有趣彤路。樓主為什么選擇 put 方法來講呢？因為從樓主看來芥映，HashMap 的精髓就在 put 方法中洲尊。
HashMap 的解析從樓主來看，主要可以分為幾個部分：
- hash 算法（這個我們之前說過了奈偏，今天就不再贅述了）
- 初始化數(shù)組坞嘀。
- 通過 hash 計算下標(biāo)并檢查 hash 是否沖突，也就是對應(yīng)的下標(biāo)是否已存在元素惊来。
- 通過判斷是否含有元素丽涩，決定是否創(chuàng)建還是追加鏈表或樹。
- 判斷已有元素的類型裁蚁，決定是追加樹還是追加鏈表矢渊。
- 判斷是否超過閥值，如果超過枉证，則重新散列數(shù)組矮男。
- Java 8 重新散列時是如何優(yōu)化的。
開始吧Ｊ已琛Ｕ奔！
1. 初始化數(shù)組
首先我們來一個測試?yán)樱?/p>
public static void main(String[] args) {
HashMap<String, Integer> hashMap = new HashMap<>(2);
hashMap.put("one", 1);
Integer one = hashMap.get("one");
System.out.println(one);
}
}
一個簡單的不能再簡單的使用 HashMap 的例子舞萄，其中包含了對于 HashMap 來說關(guān)鍵的 3 個步驟眨补，初始化，put 元素倒脓，get 元素撑螺。
由于我們預(yù)計會放入一個元素，出于性能考慮崎弃，我們將容量設(shè)置為 2甘晤，既保證了性能，也節(jié)約了空間（置于為什么饲做，我們在之前的文章中講過）线婚。
那么我們就看看 new 操作的時候做了些什么事情：
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
* @param initialCapacity the initial capacity.
* @throws IllegalArgumentException if the initial capacity is negative.
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//=================================================================================
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity
* @param loadFactor the load factor
* @throws IllegalArgumentException if the initial capacity is negative
* or the load factor is nonpositive
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
上面是 HashMap 的兩個構(gòu)造方法，其中盆均，我們設(shè)置了初始容量為 2塞弊， 而默認(rèn)的加載因子我們之前說過：0.75，當(dāng)然也可以自己設(shè)置，但 0.75 是最均衡的設(shè)置游沿，沒有特殊要求不要修改該值饰抒，加載因子過小，理論上能減少 hash 沖突诀黍，加載因子過大可以節(jié)約空間袋坑，減少 HashMap 中最耗性能的操作：reHash。
從代碼中我可以看到眯勾，如果我們設(shè)置的初始化容量小于0枣宫，將會拋出異常，如果加載因子小于0也會拋出異常吃环。同時也颤，如果初始容量大于最大容量，則重新設(shè)置為最大容量模叙。
我們開最后兩行代碼歇拆，首先，對負(fù)載因子進(jìn)行賦值范咨，這個沒什么可說的故觅。
牛逼的是下面一行代碼：this.threshold = tableSizeFor(initialCapacity); 可以看的出來這個動作是計算閥值，上面是閥值呢渠啊？閥值就是输吏，如果容器中的元素大于閥值了，就需要進(jìn)行擴容替蛉，那么這里的這行代碼贯溅，就是根據(jù)初始容量進(jìn)行閥值的計算。
我們進(jìn)入到該方法查看：
/**
* Returns a power of two size for the given target capacity.
*/
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;
}
一通或運算和無符號右移運算躲查，那么這個運算的的最后結(jié)果是什么呢它浅？這里其實就是如果用戶輸入的值不是2的冪次方（我們通過之前的分析，應(yīng)該直到初始容量如果不是2的冪次方會有多么不好的結(jié)果）镣煮。通過位移運算和或運算姐霍，最后得到一定是2的冪次方，并且是那個離那個數(shù)最近的數(shù)字典唇，我們仔細(xì)看看該方法：
| : 或運算镊折，第一個操作數(shù)的的第n位于第二個操作數(shù)的第n位 只要有一個是1，那么結(jié)果的第n為也為1介衔，否則為0
首先恨胚，將容量減1，我們后面就知道了炎咖。然后將該數(shù)字無符號右移1赃泡，2寒波，4，8升熊，16影所，總共移了32位，剛好是一個int類型的長度僚碎。在移動的過程中，還對該數(shù)字進(jìn)行或運算阴幌，為了方便查看勺阐，樓主寫一下2進(jìn)制的運算過程，假如我輸入的是10矛双，明顯不是2的冪次方渊抽。我們看看會怎么樣：
10 = 1010；
n = 9;
1001 == 9议忽；
1001 >>> 1 = 0100;
1001 或 0100 = 1101懒闷；
1101 >>> 2 = 0011;
110 或 0011 = 1111；
1111 >>> 4 = 0000;
1111 或 0000 = 1111栈幸；
1111 >>> 8 = 0000;
1111 或 0000 = 1111愤估；
1111 >>> 16 = 0000；
1111 或 0000 = 1111速址；
最后玩焰，1111 也就是 15 ，15 + 1 = 16芍锚，剛好就是距離10 最近的并且沒有變小的2的冪次方數(shù)昔园。可以說這個算法非常的牛逼并炮。樓主五體投地默刚。
但是如果是 16 呢，并且沒有不減一逃魄，我們看看什么結(jié)果：
16 = 10000荤西；
10000 >>> 1 = 01000;
10000 或 01000 = 11000；
11000 >>> 2 = 00110;
11000 或 00110 = 11110嗅钻；
11110 >>> 4 = 00001;
11110 或 00001 = 11111皂冰；
11111 >>> 8 = 00000;
11111 或 00000 = 11111；
11111 >>> 16 = 00000养篓；
11111 或 00000 = 11111秃流；
最后的數(shù)字就是31 ，31+ 1 = 32柳弄，同樣也是上升到了更大的2次冪的數(shù)字舶胀。但是這不是我想要的結(jié)果概说，所以，JDK 的作者在之前先減去了1. 防止出現(xiàn)這樣的問題嚣伐。
我們仔細(xì)觀察其算法的過程糖赔，可以說，任何一個int 數(shù)字轩端，都能找到離他最近的 2 的冪次方數(shù)字（并且比他大）放典。
好了。到這里就完成了初始化基茵，不過請注意奋构，這里設(shè)置的閥值并不是最終的閥值，最終的閥值我們會在后面詳細(xì)說明拱层。這里我們更加關(guān)注這個算法弥臼。真的牛逼啊。
2. 通過 hash 計算下標(biāo)并檢查 hash 是否沖突根灯，也就是對應(yīng)的下標(biāo)是否已存在元素径缅。
初始化好了 HashMap，我們接著就調(diào)用了 put 方法烙肺，該方法如下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
其中調(diào)用 hash 方法纳猪，該方法我們之前已經(jīng)深入討論過，今天就不贅述了茬高，如果有同學(xué)沒有看過兆旬，也不要緊，看完這篇 再去看 或者 看完那篇 再來 看這篇都可以怎栽。有點繞丽猬。好，然后調(diào)用了 puVal 方法熏瞄，我們看看該方法：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 當(dāng)前對象的數(shù)組是null 或者數(shù)組長度時0時脚祟，則需要初始化數(shù)組
if ((tab = table) == null || (n = tab.length) == 0)
// 得到數(shù)組的長度 16
n = (tab = resize()).length;
// 如果通過hash值計算出的下標(biāo)的地方?jīng)]有元素，則根據(jù)給定的key 和 value 創(chuàng)建一個元素
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else { // 如果hash沖突了
Node<K,V> e; K k;
// 如果給定的hash和沖突下標(biāo)中的 hash 值相等并且 （已有的key和給定的key相等（地址相同强饮，或者equals相同））由桌，說明該key和已有的key相同
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
// 那么就將已存在的值賦給上面定義的e變量
e = p;
// 如果以存在的值是個樹類型的，則將給定的鍵值對和該值關(guān)聯(lián)邮丰。
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 如果key不相同行您，只是hash沖突，并且不是樹剪廉，則是鏈表
else {
// 循環(huán)娃循，直到鏈表中的某個節(jié)點為null，或者某個節(jié)點hash值和給定的hash值一致且key也相同斗蒋，則停止循環(huán)捌斧。
for (int binCount = 0; ; ++binCount) {
// 如果next屬性是空
if ((e = p.next) == null) {
// 那么創(chuàng)建新的節(jié)點賦值給已有的next 屬性
p.next = newNode(hash, key, value, null);
// 如果樹的閥值大于等于7笛质，也就是，鏈表長度達(dá)到了8（從0開始）捞蚂。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 如果鏈表長度達(dá)到了8妇押，且數(shù)組長度小于64，那么就重新散列姓迅，如果大于64敲霍，則創(chuàng)建紅黑樹
treeifyBin(tab, hash);
// 結(jié)束循環(huán)
break;
}
// 如果hash值和next的hash值相同且（key也相同）
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
// 結(jié)束循環(huán)
break;
// 如果給定的hash值不同或者key不同。
// 將next 值賦給 p丁存，為下次循環(huán)做鋪墊
p = e;
}
}
// 通過上面的邏輯色冀，如果e不是null，表示：該元素存在了(也就是他們呢key相等)
if (e != null) { // existing mapping for key
// 取出該元素的值
V oldValue = e.value;
// 如果 onlyIfAbsent 是 true柱嫌，就不要改變已有的值，這里我們是false屯换。
// 如果是false编丘，或者 value 是null
if (!onlyIfAbsent || oldValue == null)
// 將新的值替換老的值
e.value = value;
// HashMap 中什么都不做
afterNodeAccess(e);
// 返回之前的舊值
return oldValue;
}
}
// 如果e== null，需要增加 modeCount 變量彤悔，為迭代器服務(wù)嘉抓。
++modCount;
// 如果數(shù)組長度大于了閥值
if (++size > threshold)
// 重新散列
resize();
// HashMap 中什么都不做
afterNodeInsertion(evict);
// 返回null
return null;
}
該方法可以說是 HashMap 的核心方法，樓主已經(jīng)在該方法中寫滿了注釋晕窑。樓主說一下該方法的步驟：
- 判斷數(shù)組是否為空抑片，如果是空，則創(chuàng)建默認(rèn)長度位 16 的數(shù)組杨赤。
- 通過與運算計算對應(yīng) hash 值的下標(biāo)敞斋，如果對應(yīng)下標(biāo)的位置沒有元素，則直接創(chuàng)建一個疾牲。
- 如果有元素植捎，說明 hash 沖突了，則再次進(jìn)行 3 種判斷阳柔。
- 判斷兩個沖突的key是否相等焰枢，equals 方法的價值在這里體現(xiàn)了。如果相等舌剂，則將已經(jīng)存在的值賦給變量e济锄。最后更新e的value步清，也就是替換操作侄刽。
- 如果key不相等，則判斷是否是紅黑樹類型旷痕，如果是紅黑樹谴忧，則交給紅黑樹追加此元素很泊。
- 如果key既不相等角虫，也不是紅黑樹，則是鏈表委造，那么就遍歷鏈表中的每一個key和給定的key是否相等戳鹅。如果，鏈表的長度大于等于8了昏兆，則將鏈表改為紅黑樹枫虏，這是Java8 的一個新的優(yōu)化。
- 最后爬虱，如果這三個判斷返回的 e 不為null隶债，則說明key重復(fù)，則更新key對應(yīng)的value的值跑筝。
- 對維護(hù)著迭代器的modCount 變量加一死讹。
- 最后判斷，如果當(dāng)前數(shù)組的長度已經(jīng)大于閥值了曲梗。則重新hash赞警。
3. 通過判斷是否含有元素，決定是否創(chuàng)建還是追加鏈表或樹虏两。
首先判斷是否含有元素愧旦，通過什么判斷呢？
tab[i = (n - 1) & hash]定罢；
這個算式根據(jù) hash 值獲取對應(yīng)的下標(biāo)笤虫，具體是什么原理，我們在上一篇文章已經(jīng)說了原因祖凫。這里也不在贅述了琼蚯。如果 hash 值沒有沖突，則創(chuàng)建一個 Node 對象惠况，參數(shù)是hash值凌停，key，value售滤，還有為null 的next 屬性罚拟。下面是構(gòu)造函數(shù)。
// 構(gòu)造函數(shù)
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
如果沒有沖突完箩，后面緊接著就走 ++modCount赐俗，然后，判斷容量是否大于閥值（默認(rèn)是12）弊知。如果大于阻逮，則調(diào)用 resize 方法，重新散列秩彤。resize 方法我們后面詳細(xì)分析叔扼。
4. 判斷已有元素的類型事哭，決定是追加樹還是追加鏈表。
如果 hash 沖突了怎么辦瓜富？我們剛剛說會有3種判斷：
- 判斷兩個沖突的key是否相等鳍咱，equals 方法的價值在這里體現(xiàn)了。如果相等与柑，則將已經(jīng)存在的值賦給變量e谤辜。最后更新e的value，也就是替換操作价捧。
- 如果key不相等丑念，則判斷是否是紅黑樹類型，如果是紅黑樹结蟋，則交給紅黑樹追加此元素脯倚。
- 如果key既不相等，也不是紅黑樹嵌屎，則是鏈表挠将，那么就遍歷鏈表中的每一個key和給定的key是否相等。如果编整，鏈表的長度大于等于8了，則將鏈表改為紅黑樹乳丰，這是Java8 的一個新的優(yōu)化掌测。
注意：在鏈表的循環(huán)中，有一個方法 treeifyBin产园，這個方法在鏈表長度大于等于8 的時候會調(diào)用汞斧，那么該方法的內(nèi)容是什么呢？
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 如果數(shù)組是null 或者數(shù)組的長度小于 64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// 重新散列
resize();
// 如果給定的hash沖突了什燕，則創(chuàng)建紅黑樹結(jié)構(gòu)
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
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);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
該方法雖然主要功能是替換鏈表結(jié)構(gòu)為紅黑樹粘勒，但是在替換前，會先判斷屎即，如果數(shù)組是 null 或者數(shù)組的長度小于 64庙睡，則重新散列，因為重新散列會拆分鏈表技俐，使得鏈表的長度變短乘陪。提高性能。如果長度大于64了雕擂。就只能將鏈表變?yōu)榧t黑樹了啡邑。
5. 判斷是否超過閥值，如果超過井赌，則重新散列數(shù)組谤逼。
最后贵扰，判斷是否閥值，如果超過則進(jìn)行散列流部；
// 如果 e == null戚绕，需要增加 modeCount 變量，為迭代器服務(wù)贵涵。
++modCount;
// 如果數(shù)組長度大于了閥值
if (++size > threshold)
// 重新散列
resize();
// HashMap 中什么都不做
afterNodeInsertion(evict);
// 返回null
return null;
我們知道列肢，閥值默認(rèn)是16，那么 resize 方法就是重新散列的核心方法宾茂，我們看看該方法實現(xiàn)：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 如果老的容量大于0
if (oldCap > 0) {
// 如果容量大于容器最大值
if (oldCap >= MAXIMUM_CAPACITY) {
// 閥值設(shè)為int最大值
threshold = Integer.MAX_VALUE;
// 返回老的數(shù)組瓷马，不再擴充
return oldTab;
}// 如果老的容量*2 小于最大容量并且老的容量大于等于默認(rèn)容量
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
// 新的閥值也再老的閥值基礎(chǔ)上*2
newThr = oldThr << 1; // double threshold
}// 如果老的閥值大于0
else if (oldThr > 0) // initial capacity was placed in threshold
// 新容量等于老閥值
newCap = oldThr;
else { // 如果容量是0，閥值也是0跨晴，認(rèn)為這是一個新的數(shù)組欧聘，使用默認(rèn)的容量16和默認(rèn)的閥值12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果新的閥值是0，重新計算閥值
if (newThr == 0) {
// 使用新的容量 * 負(fù)載因子（0.75）
float ft = (float)newCap * loadFactor;
// 如果新的容量小于最大容量 且 閥值小于最大 則新閥值等于剛剛計算的閥值端盆，否則新閥值為 int 最大值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 將新閥值賦值給當(dāng)前對象的閥值怀骤。
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 創(chuàng)建一個Node 數(shù)組，容量是新數(shù)組的容量（新容量要么是老的容量焕妙，要么是老容量*2蒋伦，要么是16）
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// 將新數(shù)組賦值給當(dāng)前對象的數(shù)組屬性
table = newTab;
// 如果老的數(shù)組不是null
if (oldTab != null) {
// 循環(huán)老數(shù)組
for (int j = 0; j < oldCap; ++j) {
// 定義一個節(jié)點
Node<K,V> e;
// 如果老數(shù)組對應(yīng)下標(biāo)的值不為空
if ((e = oldTab[j]) != null) {
// 設(shè)置為空
oldTab[j] = null;
// 如果老數(shù)組沒有鏈表
if (e.next == null)
// 將該值散列到新數(shù)組中
newTab[e.hash & (newCap - 1)] = e;
// 如果該節(jié)點是樹
else if (e instanceof TreeNode)
// 調(diào)用紅黑樹 的split 方法，傳入當(dāng)前對象焚鹊，新數(shù)組痕届，當(dāng)前下標(biāo)，老數(shù)組的容量末患，目的是將樹的數(shù)據(jù)重新散列到數(shù)組中
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 如果既不是樹研叫，next 節(jié)點也不為空，則是鏈表璧针，注意嚷炉，這里將優(yōu)化鏈表重新散列（java 8 的改進(jìn)）
// Java8 之前，這里曾是并發(fā)操作會出現(xiàn)環(huán)狀鏈表的情況探橱，但是Java8 優(yōu)化了算法申屹。此bug不再出現(xiàn)，但并發(fā)時仍然不建議HashMap
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 這里的判斷需要引出一些東西：oldCap 假如是16隧膏，那么二進(jìn)制為 10000独柑，擴容變成 100000，也就是32.
// 當(dāng)舊的hash值 與運算 10000私植，結(jié)果是0的話忌栅，那么hash值的右起第五位肯定也是0，那么該于元素的下標(biāo)位置也就不變。
if ((e.hash & oldCap) == 0) {
// 第一次進(jìn)來時給鏈頭賦值
if (loTail == null)
loHead = e;
else
// 給鏈尾賦值
loTail.next = e;
// 重置該變量
loTail = e;
}
// 如果不是0索绪，那么就是1湖员，也就是說，如果原始容量是16瑞驱，那么該元素新的下標(biāo)就是：原下標(biāo) + 16（10000b）
else {
// 同上
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 理想情況下娘摔，可將原有的鏈表拆成2組，提高查詢性能唤反。
if (loTail != null) {
// 銷毀實例凳寺，等待GC回收
loTail.next = null;
// 置入bucket中
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
該方法可以說還是比較復(fù)雜的。初始的時候也是調(diào)用的這個方法彤侍，當(dāng)鏈表數(shù)超過8的時候同時數(shù)組長度小于64的時候也是調(diào)用的這個方法肠缨。該方法步驟如下：
- 判斷容量是否大于0，如果大于0盏阶，并且容量已將大于最大值晒奕，則設(shè)置閥值為 int 最大值，并返回名斟，如果老的容量乘以 2 小于最大容量脑慧，且老的容量大于等于16，則更新閥值砰盐。也就是乘以2.
- 如果老的閥值大于0闷袒，則新的容量等于老的閥值。注意：這里很重要岩梳。還記的我們之前使用new 操作符的時候囊骤，會設(shè)置閥值為 2 的冪次方，那么這里就用上了那個計算出來的數(shù)字蒋腮，也就是說，就算我們設(shè)置的不是2的冪次方藕各，HashMap 也會自動將你的容量設(shè)置為2的冪次方池摧。
- 如果老的閥值和容量都不大于0，則認(rèn)為是一個新的數(shù)組激况，默認(rèn)初始容量為16作彤，閥值為 16 * 0.75f，也就是 12乌逐。
- 如果竭讳，新的閥值還是0，那么就使用我們剛剛設(shè)置的容量（HashMap 幫我們算的）浙踢，通過乘以 0.75绢慢，得到一個閥值，然后判斷算出的閥值是否合法：如果容量小于最大容量并且閥值小于最大容量洛波，那么則使用該閥值胰舆，否則使用 int 最大值骚露。
- 將剛剛的閥值設(shè)置打當(dāng)前Map實例的閥值屬性中。
- 將剛剛的數(shù)組設(shè)置到當(dāng)前Map實例的數(shù)組屬性中缚窿。
- 如果老的數(shù)組不是null棘幸，則將老數(shù)組中的值重新散列到新數(shù)組中。如果是null倦零，直接返回新數(shù)組误续。
那么，將老鼠組重新散列的過程到底是怎么樣的呢扫茅？
6. Java 8 重新散列時是如何優(yōu)化的蹋嵌。
重新散列的代碼：
// 如果老的數(shù)組不是null
if (oldTab != null) {
// 循環(huán)老數(shù)組
for (int j = 0; j < oldCap; ++j) {
// 定義一個節(jié)點
Node<K,V> e;
// 如果老數(shù)組對應(yīng)下標(biāo)的值不為空
if ((e = oldTab[j]) != null) {
// 設(shè)置為空
oldTab[j] = null;
// 如果老數(shù)組沒有鏈表
if (e.next == null)
// 將該值散列到新數(shù)組中
newTab[e.hash & (newCap - 1)] = e;
// 如果該節(jié)點是樹
else if (e instanceof TreeNode)
// 調(diào)用紅黑樹 的split 方法，傳入當(dāng)前對象诞帐，新數(shù)組欣尼，當(dāng)前下標(biāo)，老數(shù)組的容量停蕉，目的是將樹的數(shù)據(jù)重新散列到數(shù)組中
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // 如果既不是樹愕鼓，next 節(jié)點也不為空，則是鏈表慧起，注意菇晃，這里將優(yōu)化鏈表重新散列（java 8 的改進(jìn)）
// Java8 之前，這里曾是并發(fā)操作會出現(xiàn)環(huán)狀鏈表的情況蚓挤，但是Java8 優(yōu)化了算法磺送。此bug不再出現(xiàn)，但并發(fā)時仍然不建議HashMap
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 這里的判斷需要引出一些東西：oldCap 假如是16灿意，那么二進(jìn)制為 10000估灿，擴容變成 100000，也就是32.
// 當(dāng)舊的hash值 與運算 10000缤剧，結(jié)果是0的話馅袁，那么hash值的右起第五位肯定也是0，那么該于元素的下標(biāo)位置也就不變荒辕。
if ((e.hash & oldCap) == 0) {
// 第一次進(jìn)來時給鏈頭賦值
if (loTail == null)
loHead = e;
else
// 給鏈尾賦值
loTail.next = e;
// 重置該變量
loTail = e;
}
// 如果不是0汗销，那么就是1，也就是說抵窒，如果原始容量是16弛针，那么該元素新的下標(biāo)就是：原下標(biāo) + 16（10000b）
else {
// 同上
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 理想情況下，可將原有的鏈表拆成2組李皇，提高查詢性能削茁。
if (loTail != null) {
// 銷毀實例，等待GC回收
loTail.next = null;
// 置入bucket中
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
這里樓主重新貼了上面的代碼，因為這段代碼比較重要付材。還是說一下該部分代碼的步驟朦拖。
- 首先循環(huán)老數(shù)組。下標(biāo)從0開始厌衔，如果對應(yīng)下標(biāo)的值不是null璧帝，則判斷該值有沒有next 節(jié)點，也就是判斷是否是鏈表富寿。
- 如果不是鏈表睬隶，則根據(jù)新的數(shù)組長度重新hash該元素。
- 如果該節(jié)點是樹页徐，則調(diào)用紅黑樹的 split 方法苏潜，傳入當(dāng)前對象和新數(shù)組還有下標(biāo)，該方法會重新計算紅黑樹中的每個hash值变勇，如果重新計算后恤左，樹中元素的hash值不同，則重新散列到不同的下標(biāo)中搀绣。達(dá)到拆分紅黑樹的目的飞袋，提高性能。具體如何拆分下面再說链患。
- 之后的判斷就是鏈表巧鸭，在Java8中，該部分代碼不是簡單的將舊鏈表中的數(shù)據(jù)拷貝到新數(shù)組中的鏈表就完了麻捻，而是會對舊的鏈表進(jìn)行重新 hash纲仍，如果 hash 得到的值和之前不同，則會從舊的鏈表中拆出贸毕，放到另一個下標(biāo)中去郑叠，提高性能，剛剛的紅黑樹也是這么做的明棍。
這里的重新hash 不是使用的 [e.hash & (newCap - 1)] 方法乡革，而是使用更加效率的方法，直接 hash 老的數(shù)組容量击蹲，就沒有了減一的操作署拟，可見 JDK 的作者為了性能可以說是無所不用其極了婉宰。
其實我們的注釋已經(jīng)寫了歌豺，但是樓主還是再解釋一遍吧：
仔細(xì)閱讀下面這段話：
oldCap 假如是16，那么二進(jìn)制為 10000心包，擴容變成 100000类咧，也就是32.當(dāng)舊的hash值 與運算 10000，結(jié)果是0的話，那么hash值的右起第五位肯定也是0痕惋，那么該于元素的下標(biāo)位置也就不變区宇。但如果不是0是1的話，說明該hash值變化了值戳，那么就需要對這個元素重新散列放置议谷。那么應(yīng)該放哪里呢？如果是16堕虹，那么最左邊是1的話卧晓，說明hash值變大了16，那么只需要在原有的基礎(chǔ)上加上16便好了赴捞。
這段代碼還有一個需要注意的地方：在JDK 7 中逼裆，這里的的代碼是不同的，在并發(fā)情況下會鏈表會變成環(huán)狀赦政，形成死鎖胜宇。而JDK 8 已經(jīng)修復(fù)了該問題，但是仍然不建議使用 HashMap 并發(fā)編程恢着。
總結(jié)
截至到這里桐愉，我們的 HashMap 的 put 方法已經(jīng)剖析完了，此次可以說收獲不腥黄馈：
我們知道了仅财，無論我們?nèi)绾卧O(shè)置初始容量，HashMap 都會將我們改成2的冪次方碗淌，也就是說盏求，HashMap 的容量百分之百是 2的冪次方，因為HashMap 太依賴他了亿眠。但是碎罚，請注意：如果我們預(yù)計插入7條數(shù)據(jù)，那么我們寫入7纳像，HashMap 會設(shè)置為 8荆烈，雖然是2的冪次方，但是竟趾，請注意憔购，當(dāng)我們放入第7條數(shù)據(jù)的時候，就會引起擴容岔帽，造成性能損失玫鸟，所以，知曉了原理犀勒，我們以后在設(shè)置容量的時候還是自己算一下屎飘，比如放7條數(shù)據(jù)妥曲，我們還是都是設(shè)置成16，這樣就不會擴容了钦购。
HashMap 的默認(rèn)加載因子是 0.75檐盟，雖然可以修改，但是出于安全考慮押桃，除非你經(jīng)過大量測試葵萎，請不要修改此值，HashMap 使用此值基本是平衡了性能和空間的取舍唱凯。
HashMap 擴容的時機是陌宿，容器中的元素數(shù)量 > 負(fù)載因此 * 容量，如果負(fù)載因子是0.75波丰，容量是16壳坪，那么當(dāng)容器中數(shù)量達(dá)到13 的時候就會擴容。還有掰烟，如果某個鏈表長度達(dá)到了8爽蝴，并且容量小于64，則也會用擴容代替紅黑樹纫骑。
HashMap 在 JDK 7 中并發(fā)擴容的時候是非常危險的蝎亚，非常容易導(dǎo)致鏈表成環(huán)狀。但 JDK 8 中已經(jīng)修改了此bug先馆。但還是不建議使用发框。強烈推薦并發(fā)容器 ConcurrentHashMap。
HashMap 擴容的時候煤墙，不管是鏈表還是紅黑樹梅惯，都會對這些數(shù)據(jù)進(jìn)行重新的散列計算，然后縮短他們的長度仿野，優(yōu)化性能铣减。在進(jìn)行散列計算的時候，會進(jìn)一步優(yōu)化性能脚作，減少減一的操作葫哗，直接使用& 運算∏蛱危可謂神來之筆劣针。
總之，HashMap 中的優(yōu)秀的設(shè)計思想值得我們?nèi)W(xué)習(xí)亿扁，最讓樓主震驚的就是那個將任意一個數(shù)變成了2的冪次方的數(shù)捺典，并且該數(shù)字很合理，說實話魏烫，如果讓樓主寫辣苏，樓主是寫不出來的。
所以哄褒，請努力吧稀蟋，現(xiàn)在做不到，不代表以后做不到呐赡，通過學(xué)習(xí)優(yōu)秀的源碼退客，一定能夠提高我們的編碼能力。
加油加油Ａ脆帧Ｃ瓤瘛！；巢础Ｃ２亍！
對了霹琼，今天是 2017年的最后一天务傲，明天就是2018 年了，借這篇文章祝大家新年快樂枣申。每個人都能實現(xiàn)自己的新年愿望售葡。
