這次只講解部分源碼婴渡，不會全部講完。并且代碼來自API 26 Platfrom凯亮。前段時間又重新簡單看了一次HashMap的源碼边臼，想簡單記錄一下碰到的問題和在源碼中能參考到的代碼寫法。
我先提出我的幾個問題假消，如果有大佬路過的話麻煩請幫忙解答一下：
為什么獲取hash的時候要與自身的右移動16位做異或運算
為什么根據(jù)key生成下標(biāo)的做法是 (n - 1) & hash
為什么擴(kuò)展數(shù)組的時候拆分鏈表的條件是e.hash & oldCap
接下來進(jìn)入正題
1.HashMap節(jié)點結(jié)構(gòu)體
可以先看看節(jié)點的數(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;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
用一個靜態(tài)內(nèi)部類來定義節(jié)點硼瓣，節(jié)點里面有4個屬性
（1）hash：這個節(jié)點的hashcode
（2）key/value：鍵值對
（3）next：指向下一個節(jié)點的指針
hashmap內(nèi)部的操作基本都是對節(jié)點進(jìn)行操作。
2.重要參數(shù)
hashmap中有幾個重要的參數(shù)置谦，在源碼中也有明顯的注釋
這樣的注釋可以讓開發(fā)者更快的找到相應(yīng)的功能模塊，如果一個類里面代碼量多的話我也會這么寫注釋亿傅。
transient Node<K,V>[] table;
transient Set<Map.Entry<K,V>> entrySet;
transient int size;
transient int modCount;
int threshold;
final float loadFactor;
（1）table就是節(jié)點的數(shù)組媒峡，java中hashmap基本的形態(tài)就是一個鏈表數(shù)組（這是我的理解，不知道這樣說對不對葵擎，反正就是數(shù)組和鏈表的結(jié)合）谅阿，table就是這個數(shù)組。
entrySet本章先不解釋
（2）size是長度酬滤，不是數(shù)組的長度签餐，而是hashmap中包含的鍵值對的長度。
（3）modCount是操作次數(shù)盯串，這個本章也不會細(xì)講氯檐。
（4）threshold是數(shù)組的擴(kuò)展容量（我的理解），往下看就知道有什么用了体捏。
（5）loadFactor加載因子冠摄，往下看就知道有什么用了。
3.構(gòu)造方法
構(gòu)造方法是一個類的入口几缭，所以我們先從構(gòu)造方法看河泳。
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);
}
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
這里有3個構(gòu)造方法，兩個參數(shù)分別是initialCapacity表示數(shù)組容量年栓，loadFactor表示加載因子拆挥，簡單了解下就行，按照最常見的用法某抓，我們一般都是調(diào)用無參的構(gòu)造方法
加載因子默認(rèn)為DEFAULT_LOAD_FACTOR纸兔，也就是0.75（看下面的源碼就知道loadFactor有什么用了）
4.put方法
我們一般調(diào)用無參構(gòu)造函數(shù)實例化對象之后惰瓜，就會調(diào)用put方法，也就是只設(shè)置了loadFactor的值之后就調(diào)put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
第一個參數(shù)為key的hashcode食拜，我們可以看看hashcode怎么生成的
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
看到有調(diào)用object的hashCode()方法鸵熟。
public int hashCode() {
return identityHashCode(this);
}
// Android-changed: add a local helper for identityHashCode.
// Package-private to be used by j.l.System. We do the implementation here
// to avoid Object.hashCode doing a clinit check on j.l.System, and also
// to avoid leaking shadow$_monitor_ outside of this class.
/* package-private */ static int identityHashCode(Object obj) {
int lockWord = obj.shadow$_monitor_;
final int lockWordStateMask = 0xC0000000; // Top 2 bits.
final int lockWordStateHash = 0x80000000; // Top 2 bits are value 2 (kStateHash).
final int lockWordHashMask = 0x0FFFFFFF; // Low 28 bits.
if ((lockWord & lockWordStateMask) == lockWordStateHash) {
return lockWord & lockWordHashMask;
}
return identityHashCodeNative(obj);
}
@FastNative
private static native int identityHashCodeNative(Object obj);
簡單可以看出，這里是調(diào)用原生的方法生成的负甸，那么我這里并沒有追去看原生怎么生成的流强，我只是去網(wǎng)上收看到有人說生成的hashcode是內(nèi)存地址，32位呻待，如果不是這樣的話希望能有大佬在評論指正
那么這里獲取hash值就是用內(nèi)存地址異或內(nèi)存地址右移16位打月，至于為什么這樣做，我也不知道蚕捉，這說明即便光看源碼奏篙，也并非什么都能看懂，我查了下迫淹，聽被人說大概的意思是這樣做能減少碰撞的次數(shù)秘通，這個我也沒認(rèn)證過。
回頭繼續(xù)看putVal方法
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;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
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;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
為了方便看敛熬，我把沒有走的代碼先屏蔽掉肺稀，第一次put的時候，注意应民，是第一次調(diào)用hashmap.put的時候
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;
.........
}
我們上面調(diào)用構(gòu)造方法的時候话原，并沒有對table進(jìn)行初始化，所以它是空诲锹，所以肯定進(jìn)入這個判斷繁仁，有調(diào)一個resize()的方法，這個resize()方法很重要归园，主要做兩個操作黄虱，初始化table數(shù)組和擴(kuò)展table數(shù)組，第一次調(diào)肯定是初始化庸诱，我同樣先屏蔽部分代碼
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
......
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
......
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
......
}
return newTab;
}
要注意這里定義了幾個參數(shù)悬钳，
（1）oldTab：變化之前的節(jié)點數(shù)組
（2）oldCap：變化前的數(shù)組的長度
（3）oldThr ：舊的threshold，也就是默認(rèn)0
（4）newCap：記錄改變后的數(shù)組長度
（5）newThr ：記錄改變后的threshold
數(shù)組默認(rèn)沒初始化偶翅，所以oldCap是0默勾，oldThr 默認(rèn)也是0，所以
newCap = DEFAULT_INITIAL_CAPACITY; //(1<< 4 = 16)
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // (0.75 * 16 = 12)
可以看出聚谁，第一次調(diào)用put的時候會先判斷數(shù)組有沒有初始化枫匾，如果沒有洲炊，默認(rèn)設(shè)置長度為16（1向左移動4位）绸吸，threshold是數(shù)組長度的0.75倍（threshold是什么，下面會有說）
然后賦值給全局變量
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
好了习霹，這里調(diào)用resize()方法就是為了初始化數(shù)組長度，還能從這個源碼中看出一種做法炫隶，就是你設(shè)計某個模塊的時候可以不用設(shè)計初始化方法淋叶，可以在調(diào)用的時候再去判斷之前有沒有初始化，沒有就先進(jìn)行初始化伪阶，這樣的做法就會顯得比較靈活煞檩。
繼續(xù)看putVal方法
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;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
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;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
看到有4個參數(shù)，tab是形參栅贴，就是節(jié)點數(shù)組斟湃，p就是記錄某個節(jié)點，n是記錄數(shù)組的長度檐薯，i是記錄某個下標(biāo)凝赛。
剛才因為第一次Table為空，所以走進(jìn)這個判斷
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
調(diào)用上面resize()方法初始化數(shù)組之后坛缕，tab得到一個長度為16的數(shù)組墓猎，n等于16。
說實話赚楚，我很不喜歡賦值操作和邏輯操作寫在一起陶衅，感覺這樣寫不好看
之后往下看，做判斷
if ((p = tab[i = (n - 1) & hash]) == null)
看到&操作直晨，肯定是位運算，n-1就是1111膨俐，用1111去和hash勇皇，一個32位的二進(jìn)制做與運算，得出的結(jié)果就是下標(biāo)焚刺。簡單來說就是用某個方法生成一個0—15之前的一個小標(biāo)敛摘，比如生成5，那結(jié)果就是tab[5]的值是不是空
所以第二個問題來了乳愉，生成下標(biāo)為什么要用長度-1和hash做與運算
由于我們這個第一次肯定是空的數(shù)組兄淫，所以為空
tab[i] = newNode(hash, key, value, null);
為空的話就新建一個節(jié)點賦值給這個數(shù)組的下標(biāo)。然后賦值邏輯就走完了蔓姚，看看后續(xù)的邏輯
++modCount; // 操作數(shù)+1
if (++size > threshold)
resize();
afterNodeInsertion(evict); // 提供給子類重寫來給子類在該步驟下做特定操作
中間的操作捕虽，鍵值對的長度加1，如果鍵值對的長度超過threshold坡脐，則對數(shù)組進(jìn)行擴(kuò)展
到這里應(yīng)該就能看出threshold的左右泄私，相當(dāng)于是一個閥值，如果鍵值對的數(shù)量超過這個閥值，我們就擴(kuò)展數(shù)組晌端，這是java里面HashMap擴(kuò)展長度的一個思想捅暴。
那么第一次put我們講完了，其實還挺簡單的咧纠，假如我們put第二個參數(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 ((tab = table) == null || (n = tab.length) == 0)
....... // 初始化的情況上面講過了
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
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;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
根據(jù)這個Key的hash，用i = (n - 1) & hash算出下標(biāo)漆羔，如果這個下標(biāo)下的值不存在梧奢，那就創(chuàng)建這個節(jié)點和放到這個下標(biāo)中，比如tab[6]钧椰，我們和上面一樣粹断，創(chuàng)建節(jié)點放入數(shù)組就結(jié)束，很簡單嫡霞。但是假如算出是5瓶埋，tab[5]在第一次put的時候已經(jīng)賦值了，那我們這里就要走else
if ((p = tab[i = (n - 1) & hash]) == null)
......
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
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;
}
}
有兩個參數(shù)诊沪，e表示記錄節(jié)點养筒，k表示Key。這命名端姚，我得吐槽一下晕粪，咋不整個aaa呢
判斷
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
如果當(dāng)前的hash值和之前存的節(jié)點的hash值相同并且key也相同，那就e = p;然后
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
把這個節(jié)點的value換成傳進(jìn)來的value渐裸，沒錯巫湘，這步就做了替換操作。
如果hash不等或者key不等昏鹃，然后判斷p instanceof TreeNode尚氛，這個節(jié)點是否是紅黑樹的數(shù)據(jù)結(jié)構(gòu)。本章不討論紅黑樹的情況洞渤，你只要知道在某個節(jié)點鏈表長度到一點值的時候阅嘶，這條鏈表會轉(zhuǎn)成紅黑樹就行。
假如當(dāng)前節(jié)點的數(shù)據(jù)結(jié)構(gòu)不是紅黑樹载迄，
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
死循環(huán)讯柔，e指向p的下一個節(jié)點（怕你亂多啰嗦一句，p就是數(shù)組中某個下標(biāo)的那個節(jié)點护昧，也就是鏈表的頭節(jié)點）魂迄。如果e等于空（說明e處于鏈表最后一個節(jié)點的next的情況），新建一個節(jié)點加入鏈表
p.next = newNode(hash, key, value, null);
然后判斷是否需要把鏈表轉(zhuǎn)成紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
這里就印證我上面說的惋耙，當(dāng)這條鏈表長度大于等于7的時候极祸，鏈表會轉(zhuǎn)成紅黑樹慈格，因為我說了這篇不討論紅黑樹，所以我假設(shè)長度沒到7
如果沒到尾遥金，e!=null浴捆，判斷e的hash和key與傳進(jìn)來的相不相同，相同的話覆蓋（這里的break跳出死循環(huán)能走下面的賦值操作）
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
那假如key也不相等稿械，就把指針移到下一位
p = e;
然后循環(huán)操作选泻。
總結(jié)：put方法中，先判斷節(jié)點數(shù)組初始化沒有美莫，沒初始化的話會先初始化页眯，然后判斷數(shù)組某個下標(biāo)是否為空，為空的話直接創(chuàng)建一個節(jié)點給這個下標(biāo)厢呵，不為空的話窝撵，循環(huán)這個數(shù)組下標(biāo)下的節(jié)點的鏈表，判斷是否鏈表中的某個節(jié)點key相同襟铭，相同的話覆蓋碌奉，不相同的話創(chuàng)建一個節(jié)點添加到鏈表的最后，如果長度到達(dá)7寒砖，將鏈表轉(zhuǎn)成紅黑樹赐劣。put操作完成之后，最后判斷size的長度有沒有超過閥值哩都，如果超過閥值魁兼，則擴(kuò)展數(shù)組。
5.數(shù)組擴(kuò)展resize方法
上邊有講初始化的情況漠嵌，這里就直接講擴(kuò)展的情況
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
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) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
......
}
if (newThr == 0) {
......
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = 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;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
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;
}
}
}
}
}
return newTab;
}
oldCap在第一次擴(kuò)展的情況下是16咐汞，大于0
newCap = oldCap << 1
新的數(shù)組長度就是舊的長度向左移動一位，就是32儒鹿。每次擴(kuò)展都是左移一位化撕，所以擴(kuò)展肯定是2的倍數(shù)
newThr = oldThr << 1;
這玩意就沒這么好算，12左移一位挺身，要把12換成2進(jìn)制比16換成二進(jìn)制麻煩，有個更好的方法是拿newCap * 0.75 = 24锌仅，你去算也是相等的章钾。那么新的閥值就是24。然后進(jìn)入循環(huán)
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;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
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;
}
}
}
}
for循環(huán)是循環(huán)數(shù)組热芹，如果當(dāng)前下標(biāo)沒有next贱傀，那么這個新數(shù)組的這個下標(biāo)的值就等于舊數(shù)組當(dāng)前下標(biāo)的值。如果這個下標(biāo)的節(jié)點是紅黑樹（就是之前鏈表長度達(dá)到7）伊脓，那就對紅黑樹做操作（這里不講紅黑樹府寒，大概了解就行）魁衙。如果都不是（說明當(dāng)前數(shù)組下標(biāo)的節(jié)點是個長度小于7 的鏈表）
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;
}
這個操作是，對鏈表進(jìn)行遍歷株搔，按照e.hash & oldCap這個條件把一條鏈表拆分成high和low兩條鏈表剖淀，把low鏈表放到新數(shù)組的當(dāng)前下標(biāo)，high鏈表放到新數(shù)組當(dāng)前下標(biāo)+舊長度的下標(biāo)纤房。
舉個例子纵隔，舊的長度16，tab[5]的長度為6炮姨，它分成長度為2的low和長度為4的high捌刮，新數(shù)組tab[5] = low(長度2)，tab[21]=high(長度4)
那么我的第三個問題來了舒岸，一分二的意圖其實很容易理解绅作，但是為什么要根據(jù)這個條件來分？
6. 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;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
根據(jù)這個key可以用(n - 1) & hash來拿到下標(biāo)蛾派，put的時候也是這個條件俄认，拿到下標(biāo)之后判斷當(dāng)前這個下標(biāo)的節(jié)點是否為這個key，是的話直接返回它的value碍脏，不是的話判斷是不是紅黑樹梭依，不是的話遍歷鏈表來找相同的key，遍歷完還沒有的話就返回空典尾。
7.總結(jié)
（1）主要講了put役拴、get和resize這3個方法
（2）hashmap中有兩個神奇的操作，第一是擴(kuò)展數(shù)組钾埂，第二是把鏈表轉(zhuǎn)成紅黑樹
（3）提出幾個問題河闰，如果有大佬知道，請幫忙解答
為什么獲取hash的時候要與自身的右移動16位做異或運算
為什么根據(jù)key生成下標(biāo)的做法是 (n - 1) & hash
為什么擴(kuò)展數(shù)組的時候拆分鏈表的條件是e.hash & oldCap
