導語
手撕面試官，面試某公司開發的時候被問到了HashMap底層，問到我懷疑人生，不知道是面試官錯了還是我錯了。我相信是我錯了利用下班時間來分析手撕一下HashMap。
通過手撕源碼加上實驗來給自己打臉，這些東西你跟面試官真的懂麼？想要做出創新的東西真的容易麼？就靠着自己對于增删改查就可以馳騁江湖了麼？自己離高手的路還有一段距離。
文章目錄
-
- 實驗
-
- putVal()
- resize()
- treeifyBin()
- treeify()
- moveRootToFront()
- 總結
實驗
不用多說直接上源碼這裡，首先解釋一下傳入的幾個參數。HashMap 傳入的就是KV兩個值，沒有什麼好解釋的，進入方法之後調用的是putVal的方法這裡可以看到。調用了一個hash()的方法。
/**
* Associates the specified value with the specified key in this map.
* If the map previously contained a mapping for the key, the old
* value is replaced.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with <tt>key</tt>, or
* <tt>null</tt> if there was no mapping for <tt>key</tt>.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with <tt>key</tt>.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
到這裡第一個問題來了：這個HashCode是怎麼産生的?
到這裡有面試官會問這個時候我們的hashCode是怎麼産生的。就是通過這個方法，這裡需要通過 (h = key.hashCode()) ^ (h >>> 16) 一個操作，這裡解釋一下這個操作，希望讀者可以擦亮眼睛。看清楚了
hashCode()方法是native方法，而^操作 表示異或，而 >>> 這個操作，我們都知道>> 這個叫做左移
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
什麼是左移，下面這個操作就是左移
原來資料是 1 1 1 1 十進制表示 15
左移操作 0 1 1 1 十進制表示 7
左移兩位 0 0 1 1 十進制表示 3
測試一下
通過上面的分析來測試一下上面這個方法傳回的值是什麼
public class Test {
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
public static void main(String[] args) {
int hash = hash(10);
System.out.println(hash); // 10
}
}
分析一下
10 十進制 二進制表示 1010
首先第一步操作擷取了一個HashCode 假設這個值就是 10
那麼這裡的第一個操作就是 h = key.hashCode() 擷取到 h = 10；
第二個操作 就是 h >>> 16 ，結果為 0 二進制也是 0 最終将兩個值做了異或 異或的意思就是 隻要有1 就是1
是以 最後結果還是 10
到這裡就應該就差不多了，再要往底層問就是要問一下hashCode()方法體内部是什麼操作？有興趣的可以了解一下。
繼續往下就進入了核心方法中，這裡就有好日子過了。
putVal()
/**
* Implements Map.put and related methods
*
* @param hash hash for key 通過hash計算的hash 值
* @param key the key 具體存入的鍵值
* @param value the value to put 放入的value值
* @param onlyIfAbsent if true, don't change existing value 如果為true ，則不去改變現有值 傳入的值是 false
* @param evict if false, the table is in creation mode. 如果為false，則表處于建立模式，傳入的值為 true
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//建立新節點數組，建立節點，初始值
Node<K,V>[] tab; Node<K,V> p; int n, i;
//首先判斷 tab 以及實際存儲的table是否為空，第二步就是看 tab的長度是否為0。
if ((tab = table) == null || (n = tab.length) == 0)
// 重新指派 重置之後會擷取到一個新的數組
n = (tab = resize()).length;
// 如果 tab[i = (n - 1) & hash] 對應的節點為空，這個怎麼了解？
// 首先來分析一下這個時候 n 的值應該是新建立的數組的長度，拿預設值來說這個長度應該是 16
// 這裡 n-1 也就是 15 例如放入這個位置的值為 10 也就是 1010 和 1111 做一個與操作，根據分析可以知道 它應該就是 1010 那麼就知道這裡判斷的是這個數組第10個位置是否有資料，如果沒有資料則進行一個 newNode(hash, key, value, null)操作也就是建立一個新的節點。源碼方法很簡單就是建立一個Node
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//否則就是由Hash沖突了，這裡就需要解決這個沖突，首先想到的就是将該節點上的沖突轉移到連結清單中。
Node<K,V> e; K k;
// 這裡進入hash的判斷，假設一個很極端的情況來進行分析，就是存儲的所有元素都是10
// && 這操作是一個與操作，也就是這兩邊的表達式操作都要為true才可以。那麼首先來看
//p.hash == hash 如果上面這個場景成立，那麼10 和10 的hash應該是一樣的，條件成立
// ((k = p.key) == key || (key != null && key.equals(k)))) 這個表達是很長但是可以根據括号做一個拆分。
//(k = p.key) == key 還是之前的極端情況這裡的key一樣 這個條件為真
// || 表示或也就是說這個符号左右兩邊隻要有一個為true就可以了。
// (key != null && key.equals(k))) 繼續就是判斷這個key的值是否一樣，這裡有一點需要注意就是，如果放入的就是 大量相同資料那麼這個地方條件都成立了，進入的操作應該是e = p; 也就是說如果所有條件都成立了那麼最終的結果應該是這個 p 節點就是 e 節點 直接做了指針交換。也就間接的證明一件事情，如果key相同，那麼存儲到HashMap中的内容無論有多少，隻要key相同就看作一個。這個就是為什麼在HashMap中的Key不能重複的原因。
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 做完上面的判斷之後，就開始做TreeNode的判斷是否是TreeNode，這裡我們知道，這個節點 p 判斷的時候 并不是一個TreeNode，而是一個Node那麼這個條件是不是一直不成立呢？
// 首先 Node 實際上繼承了Entry 而 TreeNode繼承的是LinkedHashMap.Entry<K,V> 也就是HashMap的連結清單實作。
// 第一點 p 節點 在什麼時候會變成 TreeNode。這個就和resize()中的split()方法有關，這裡先不做分析
// 第二點 變化節點類型之後put的方式也發生了變化。就是下面，這個操作。
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 如果整個的條件都不滿足，也就是說既不是樹節點，也不是同一個key，這個時候就需要進入下下面這個邏輯
else {
// 這裡是一個死循環
for (int binCount = 0; ; ++binCount) {
// 判斷如下，首先擷取到p節點的下一個節點判斷是否為空
if ((e = p.next) == null) {
// 如果為空 則建立新的連結清單節點。使用連結清單的尾部插入法
p.next = newNode(hash, key, value, null);
// 判斷一下 計數是否大于等于TREEIFY_THRESHOLD - 1 這裡其實就是轉換紅黑樹的臨界區，當連結清單長度大于8的時候就進行了一個treeifyBin(tab, hash);操作，看看具體傳入的參數，一個是tab ，另個一是hash，這個hash就是傳入的通過 hashCode()計算的哪個值。
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 分析完這個地方的邏輯之後，可以看到，完成轉換之後的操作還是與整個的數組擴容沒有關系，就是解決數組的hash沖突的問題。最終進行傳回
treeifyBin(tab, hash);
break;
}
// 如果e節點的hash值 就是滿足下面這個條件也是解釋了上面分析中的一個key唯一的問題。
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
// 這個時候将e節點指派給p節點。其實就是拿到這個節點做了一個轉換，如果轉換沒成功則就還是原來的東西還給原來的位置。
p = e;
}
}
// 這裡說是判斷鍵的現有映射
// 結束上面判斷的時候最終可以擷取到e的值的隻有上面兩個判斷中的值。一個是往數組中方結果，一個是往數中方結果
// 放入的時候有可能存在值了 e就不會為null
if (e != null) { // existing mapping for key
// 擷取到老值
V oldValue = e.value;
// 如果值為空 或者是不存在
if (!onlyIfAbsent || oldValue == null)
// 就把對應位置的值進行替換
e.value = value;
// 進行一個後置通路 最終的這個後置通路是自擴充的，這個擴充在TreeNode繼承的LinkedHashMap中進行了實作，這個操作就先不多說了
afterNodeAccess(e);
return oldValue;
}
}
// 這字段表示Hash在結構上被修改的次數，是個全局的變量
// 這個結構修改值的是HashMap的修改以及其内部的修改，它的作用是
// 在集合視圖上實作疊代器
++modCount;
// size 記錄的是 HashMap的大小，這裡需要注意的是數組的大小還是裡面的結構的大小
// 在上面的操作中并沒有那個地方來修改這個值，而這個值唯一被增加的地方就是這裡，是以說
// size 記錄的是内部元素的總共進入了多少個，而不是内部的table的大小
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
/**
* The number of times this HashMap has been structurally modified
* Structural modifications are those that change the number of mappings in
* the HashMap or otherwise modify its internal structure (e.g.,
* rehash). This field is used to make iterators on Collection-views of
* the HashMap fail-fast. (See ConcurrentModificationException).
*/
transient int modCount;
上面提到了一個size的概念，有如下的一個問題來，下面這個代碼最後輸出的結果是多少
HashMap<Integer,Object> hashMap = new HashMap<>();
for (int i = 0; i <100 ; i++) {
hashMap.put(i,i);
}
System.out.println(hashMap.size());
// 100
resize()
接上面resize()方法 從上面進入到重新設定大小的操作。
final Node<K,V>[] resize() {
//記錄一下原來的table，這裡不管有沒有值都記錄一下。
Node<K,V>[] oldTab = table;
// 如果舊表為空或者不為空那麼就需要記錄一下器長度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 這裡簡單的解釋一下這個值，capacity * load factor
// 源碼中的英文翻譯過來是 要調整大小的下一個大小值（容量*負載系數）。
// 有人會問這個東西值在什麼地方 具體是通過 static final int tableSizeFor(int cap) 操作算出
int oldThr = threshold;
int newCap, newThr = 0;
// 這裡表示 這個值 表如果有值
if (oldCap > 0) {
// 則 看看是否是 比這個 1<<30 大
if (oldCap >= MAXIMUM_CAPACITY) {
// 如果不是則傳回就是一個原來的表也就是說沒有辦法再操作了，threshold也調成 最大的整數值
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
// 在指定newCap 和newThr的時候就使用預設的初始化大小，
// DEFAULT_INITIAL_CAPACITY = 1<<4
// DEFAULT_LOAD_FACTOR = 0.75
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 在上面的判斷結束之後這裡做了一個newThr 為0 的判斷
// 這裡如何了解 什麼時候這個值會是0
// 經過分析可以看到，這個值在初始化的時候為零，也就是說沒有經過上面的兩個判斷直接進入到了這裡，從代碼邏輯上來看，上面的判斷是對oldCap 和 oldThr的判斷。從這裡可以看出 下面這個IF判斷應該是初始化的邏輯
if (newThr == 0) {
// 上面可以看到如果沒有舊資料，那麼newCap 值應該是預設值16。loadFactor的值應該是 預設值 0.75 進而可以知道 ft的值應該是 12.0f
float ft = (float)newCap * loadFactor;
// 計算出一個新的 newThr
// 我們知道MAXIMUM_CAPACITY 值是 1<<30,ft 經過計算應該是 12.0f，
// 也就是說看看newCap 和 ft的值與 1<<30 的大小。最終的結果應該是 ft ，如果超過對應的大小就是Int類型的最大值。注意這裡的大小全部是對于數組來做的
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 将臨界區 改為新的臨界區，這裡是個人叫法，也就是說如果資料超過這個值就一定會發生 hash沖突。
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) {
// 這裡将老數組中的第j個位置的元素給設定為空
oldTab[j] = null;
if (e.next == null)
// 判斷是否有連結清單存在 如果不存在，則進行e.hash & (newCap - 1) // 給整個元素給定一個新的位置
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 如果 是樹的節點 進行了一個split的操作，整個函數代碼有點多，放到下面分析
((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 {
// 首先 将 e 節點的 下一個節點值擷取到
next = e.next;
// 第二步 将e 節點的 hash值與table的長度 做 與運算，假設 10 和 12 做與運算 1010 和 1100 1000 也就是說 存在兩個1 才是1 否則都是0
// 這個判斷的意思是 如果 e元素的hash值 和 老的 table的長度做與運算為0 那麼什麼時候這操作會為零呢？ 就是這個oldCap為零的時候，那麼什麼時候oldCap為零，或者說這個oldCap為零會帶來什麼樣的後果。
if ((e.hash & oldCap) == 0) {
// 判斷 尾節點是否為空如果不為空則就是它本身是頭節點，如果不是則尾節點的将e節點放入到下一個節點中。
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 如果上面的條件不滿足，一般都是有值的不會為零
else {
// 将原來的資料進行記錄儲存到hiTail中，原則與上面的操作原則是一樣的。
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//周遊完成之後
// 如果loTail 不為空
// 也就是說原來的資料 裡面有資料，并且為其加入了新的資料，并且将所有的資料都放到 數組的第j個節點所在的位置對應的内容中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 如果曆史有資料，則将資料放入到 j+oldCap 這個位置上，為了解決節點hash沖突而存在的一個機制，這裡是放到for循環中是以說這個是解決Hash沖突的一個問題。
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// 最終傳回一個新的數組。而這個數組會根據具體的條件産生 ，繼續傳回到putVal()方法中
return newTab;
}
treeifyBin()
進入到節點到樹的操作
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
// 說明傳入的值是tab 數組 和 hash
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// 判斷tab是否為空 或者是 長度是否小于MIN_TREEIFY_CAPACITY 這個值是 64，這個被稱為是最小樹形化參數 ，為什麼會有這個判斷？連結清單轉換紅黑樹跟tab 的長度沒有關系，為什麼會有這樣一個判斷？帶着這個問題繼續往下分析
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
// 調用了一個擴容操作，其實這個地方就是為了使用其中的一個split方法。因為此時的連結清單還沒有達到那個程度，想象一個極端的場景，通過上面的分析我們知道了，key值不重複，在一定程度上可以避免hash沖突，假設從1到100000來設定key值，會出現什麼結果。假設而已。下面就來分析。在上面的分析中知道 resize()方法中再對 擴容操作的時候其實将數組中存入的都是連結清單的頭節點。如果上面這個情況出現的話就會出現一種情況。GC圖如下
resize();
// 如果上面條件不滿足 也就是說 兩個條件都不滿足。
// 這裡的 n 代表的是長度 做了減一操作 然後與hash做對比。最後看是否在存在。
// 了解一下，如果該位置沒有值 就不處理了以為看到這個條件結束之後沒有其他的處理邏輯
// 第二點，到了這裡一般拿到的位置都是有值的，那麼這個值如何處理
else if ((e = tab[index = (n - 1) & hash]) != null) {
// 當上面的長度條件不滿足的時候也就是說 tab的長度大于 64 之後進入一個樹形化的操作，
// 首先會看到 e 節點 擷取到的hash位置的值。
TreeNode<K,V> hd = null, tl = null;
do {
// 替換為樹節點，可見上面的分析中 p 為啥變成TreeNode是有原因的。下面這個地方就是将元素替換為TreeNode。 思考一個場景，如果這個地方有1千萬的資料，并且hashcode不沖突，那麼就會出現下面這個轉換場景。
TreeNode<K,V> p = replacementTreeNode(e, null);
// 這裡tl是做什麼用的，還記的，在擴充的時候loTail 的作用麼，功能類似就是為了記錄一下本來的值
// 首先會知道第一次進入這個條件的時候這個tl 就是為空
// 将轉換後的節點指派給 hd 繼續就是
if (tl == null)
// 将轉換後的值進行指派
hd = p;
else {
// 原來的值也加入到其中。
p.prev = tl;
// 将 p 節點連接配接到tl的下一個節點。
tl.next = p;
}
// 最終将 p 節點還給原來的節點
// 第一次操作 就會将p的值指派給 tl ，這個時候 看看 e 節點的下一個節點是否為空。
// 根據上面的場景來看，其實這個地方 1千萬的資料如果沒有重複的HashCode也就表示這個條件其實是不成立的，e節點下面沒有next。這個循環隻執行了一次。那麼将這個節點轉換為 TreeNode之後，就會進入到下一次的操作，下一次的操作就繼續往第65 個長度放值。繼續分析
tl = p;
// 上面這個操作成立的條件就是 e 存在下一個節點，也就是将整個連結清單做轉換操作
} while ((e = e.next) != null);
// 做完有序排列後這個地方會被操作，判斷hd 是否是index索引位置的node，并且是否為空。
// 根據上面的條件可以看到 index = (n - 1) & hash] 這個操作 就是同一個，也就會進入到方法中。
if ((tab[index] = hd) != null)
//會看到上面的所有的轉換做成功之後，進行的就是建構的操作将tab上的index位置的設定為hd，整個的tab放入到了 treeify的方法中，需要注意的就是這個條件成立的基礎。tab的長度大于64，假設是65，那麼 一個無HashCode沖突的資料進入之後，得到的 index 值是 就是對應的hashCode，因為我們知道tab的長度一定是比實際存儲的資料要大的。這個時候， replacementTreeNode(e, null);操作是對 e節點進行了一個深拷貝操作，包括所有的節點内容都是原來的，隻不過就是結構發生了變化。也就是是将原來的位置的節點設定成了 TreeNode。從這個角度上看，是将所有大于 64 的部分全部用這個邏輯來進行處理。那麼繼續分析。
hd.treeify(tab);
}
}
測試程式代碼如下。
HashMap<Integer,Object> hashMap = new HashMap<>();
for (int i = 0; i <100000000 ; i++) {
hashMap.put(i,i);
}
System.out.println(hashMap.size());
上面場景的GC圖
停止之後實際實體機記憶體變化使用變化。
通過上面的分析可以知道，根據上面的分析可以知道如果在key不存在hash沖突的時候就不會啟動連結清單，也就沒有具體的連結清單到紅黑樹的轉換過程。進而導緻了這個現象。那麼根據我們對于hash沖突的了解，就是當這個tab中的key出現 n-1&hash 值相同的時候就是hash沖突。那麼就來看看下面這種情況
當我們把下面代碼循環次數從1 到100000000不斷擴大的時候，在7個零的時候都沒有問題，在8個零的時候就有問題了。那麼這個問題到底出現在table還内部的TreeNode或者是連結清單呢。
HashMap<Object,Object> hashMap = new HashMap<>();
for (int i = 0; i <100000000 ; i++) {
hashMap.put("s"+i,i);
}
System.out.println(hashMap.size());
分析問題症結所在其實問題還是出現在這個HashCode上，上面的操作在HashCode上是一個規律性的增長操作并沒有一個合适的操作組合出現key不同的情況，而在判斷的時候我們看到一個判斷
(k = p.key) == key || (key != null && key.equals(k))) 這個判斷 最終的意義我們也了解就是判斷hashcode 以及key的值是否相同。這裡我們測試如下的一個代碼，這段代碼的神奇之處就在于它的這個組合保證了s和d兩個字元串的hashCode 是一樣的，但是字元串本身是不一樣的。這個是根據String類型對于HashCode重寫推算出來的。當然我們可以根據這個思路來實作一個新的内容。
String s ="Ea";
String d ="FB";
HashMap<String,Integer> hashMap= new HashMap<>();
hashMap.put(s,1);
hashMap.put(d,2);
System.out.println(hashMap.size());
根據上面的啟示建構了如下的測試代碼
public class Test {
private static int hash = 0;
public static void main(String[] args) {
HashMap<String,Integer> hashMap= new HashMap<>();
for (int i = 0; i < 100000000 ; i++) {
String s1 = generateShortUUID();
String s2 = generateShortUUID();
int hash1 = hashCode(s1.toCharArray());
int hash2 = hashCode(s2.toCharArray());
if (hash1 == hash2) {
hashMap.put(s1, 1);
}
}
System.out.println(hashMap.size());
}
public static int hashCode(char[] value) {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
public static String[] chars = new String[] { "a", "b", "c", "d", "e", "f",
"g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s",
"t", "u", "v", "w", "x", "y", "z", "0", "1", "2", "3", "4", "5",
"6", "7", "8", "9", "A", "B", "C", "D", "E", "F", "G", "H", "I",
"J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V",
"W", "X", "Y", "Z" };
public static String generateShortUUID() {
StringBuffer shortBuffer = new StringBuffer();
String uuid = UUID.randomUUID().toString().replace("-", "");
for (int i = 0; i < 8; i++) {
String str = uuid.substring(i * 4, i * 4 + 4);
int x = Integer.parseInt(str, 16);
shortBuffer.append(chars[x % 0x3E]);
}
return shortBuffer.toString();
}
在之前線性擴充的過程中7個零的速度是非常快的并且最後列印出來的結果值是10000000，但是使用了上面這種方式的時候，當擴充增加到7個零的時候比之前的耗時要嚴重。
7個零
在8個零的時候也沒有像之前的哪個樣子出現一個整個的老年代被直接占滿的情況。而是一個線性增加的過程。
8個零
treeify()
/**
* Forms tree of the nodes linked from this node.
* @return root of tree
*/
final void treeify(Node<K,V>[] tab) {
// 傳入的是數組，這個地方從上面的内容中其實可以看到傳入的就是原有的tab
// 根據上面的分析思路，這裡傳入的就是一個64 節點的數組，那麼第65 個節點，進入之後，就會進入這個邏輯中。
TreeNode<K,V> root = null;
// 首先來初始化 拿到的樹是不是目前需要操作的樹也就是上面的hd，以及next節點 x 表示hd
// 這裡的this 就是上面的 hd 。我們知道這個hd 其實是沒有next的，也就是說 這裡的循環隻執行了一次
for (TreeNode<K,V> x = this, next; x != null; x = next) {
// 到這裡可以知道其實就是節點連結清單到樹結構的轉換 那麼tab在什麼地方使用呢？
// 就是為了定位在數組中那些節點需要進行操作。
// 由于沒有next 是以說 next 為null；
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
// 根節點為空的話
if (root == null) {
// x 就是根節點，也就是說這裡 這個 65 就是這個65 這個位置樹的根節點。
x.parent = null;
x.red = false;
root = x;
}
// 如果不為空，這裡我們就拿一個極端的例子來分析，還是 65 那麼這裡就不會執行這個步驟
else {
// 否則 就進行操作了
// 首先拿到的key 并且擷取到k的hash值
K k = x.key;
int h = x.hash;
// k了類對象
Class<?> kc = null;
// 進入死循環這裡需要注意循環結束的條件
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
// 這裡的h是x的hash值，ph則是目前節點的hash值，也就是說這個資料的轉換其實是一個hash 值的比較
if ((ph = p.hash) > h)
// 這個操作主要是用來做紅黑樹平衡用的。
dir = -1;
else if (ph < h)
dir = 1;
// 進行 判斷比較
// kc == null Kc為空 && 判斷也就是說這個條件與第二個條件需要全部滿足。
// (kc = comparableClassFor(k)) == null)
// 第三個條件與第一個條件和第二個條件的産生的結果做 || 運算
// (dir = compareComparables(kc, k, pk)) == 0
// 這裡條件滿足之後進行的操作就是 tieBreakOrder(k, pk);
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
// 最終，進入到下面這個邏輯
TreeNode<K,V> xp = p;
// 進行周遊 将 拿到的x全部放入到建構好的樹裡面 條件不成立的時候進行一個平衡操作
if ((p = (dir <= 0) ? p.left : p.right) == null) {
//
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
// 進行一個轉換 這個時候用到了 tab
moveRootToFront(tab, root);
}
moveRootToFront()
移動根到頭
/**
* Ensures that the given root is the first node of its bin.
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
// 傳入的參數是數組和紅黑樹節點，這個地方繼續插入65 ，
// 判斷 條件所有的都成立
if (root != null && tab != null && (n = tab.length) > 0) {
// 條件成立 找到索引位置 這裡使用的是根節點的hash值。n還是數組的長度。
// 這裡的index就應該是 65，
int index = (n - 1) & root.hash;
// 将索引位置的 Node 強轉為 TreeNode
// 将TreeNode的第一個節點轉換為 第 65 位置的節點
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
// 從上面看 65 這個操作進來之後這個操作其實是一樣的。由于65 這個操作進入之後沒有沖突，也沒有轉換，是以說hash是一樣的，root 是對65進行了拷貝，是以說這個結果一定是成立的，那麼這裡判斷是不成立。是以說代碼不會執行，那麼什麼情況會出現這個結果不一緻，進入到這個判斷中呢？首先tab 的index位置的值在什麼情況下會發生變化。就是進入到了上面那個方法的else中。那麼此時的65其實是沒有進行操作的，是以說放入的操作還是繼續用tab
if (root != first) {
Node<K,V> rn;
// 将root 放到了 tab的index位置
tab[index] = root;
//将根 的記錄操作節點 rp 而prev的含義就是 TreeNode 的臨時連接配接存在 TreeNode<K,V> rp = root.prev;
// 這裡到這裡有一個大膽的猜測，就是TreeNode不但有紅黑樹的特點還有連結清單的特點。是這樣麼？
if ((rn = root.next) != null)
// 判斷了root的next 這個時候有點難以了解的就是root為什麼會有next并且不為空的判斷？
// 這裡做的操作就是把 root.next.pre指針指向了 root.pre 所指向的内容
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
//如果 rp不為空 則将rp.next 指向rn
rp.next = rn;
if (first != null)
// 如果 first不為空 将 frist.prev 指向 root
first.prev = root;
// 最終轉換完成之後，進行 root.next = first 的操作 這裡我們知道first是通過根節點的hash值計算出來的連結清單中的位置。其整個作用就是将紅黑樹調整的數組的合适位置上。
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
/**
* Splits nodes in a tree bin into lower and upper tree bins,
* or untreeifies if now too small. Called only from resize;
* see above discussion about split bits and indices.
*
* @param map the map
* @param tab the table for recording bin heads
* @param index the index of the table being split
* @param bit the bit of hash to split on
*/
// 将樹容器中的節點拆分為較低和較高的樹容器，如果現在太小，則取消搜尋。僅從resize調用
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
// 這個方法屬于 TreeNode的方法，首先this就是需要操作的節點，就是上面内容中滿足條件的節點。那麼它具體有什麼樣的作用？這個拆分到底有什麼樣的效果。
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
// 重新連接配接到lo 和 hi 的清單中，保持順序
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
// 周遊 TreeNode ，既然這樣，還是65 放入之後這個節點就隻有一個元素，它所對應的next還是null
for (TreeNode<K,V> e = b, next; e != null; e = next) {
// next 為null
next = (TreeNode<K,V>)e.next;
// e 節點的next也為null；
e.next = null;
// 這裡就 e 的hash 和bit 做了 & 運輸是否為0 那麼 1100 和 1111 做 & 結果是什麼呢？ 1100 ，bit 是傳入的for循環中j 的值。j的範圍是老的容量。那麼當65 進入之後，與65 進行&操作 還是 65，那麼進入到這個循環的條件是第j個位置有資料，并且是TreeNode，上面的内容分析中可以知道這個條件都滿足，也就是說進入了，并且，這個& 操作也不是0 也就是說進入不到下面這個操作中。
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
// 65 的操作進入到這裡
else {
// e節點的prev指針指向了hiTail 這個時候這個條件都是null也就是第一個判斷就成功了。
// 那麼hiHead 就是 e 了也就是65. 到這裡會看到其實如果是順序key的話并不适合與這種場景，如果是順序key的話可以考慮其他資料結構，如果非要是以中KV形式來存儲的話，這個性能其實并不是最高效的。
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
// 最終會發現其實 hiTail也是 e 65 最終到這裡就結束了
hiTail = e;
++hc;
}
}
// 那麼 如果沒有特殊政策進來的話在64 以後對于進入到其中的資料會強制轉換。
// 分别表示,表示低部分容器
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
// 表示高部分容器
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
總結
從源碼的閱讀中，可以看到其實我們都不是真的懂HashMap的真的消耗性能在什麼地方。如果我們真的懂了，應該是合理的組合，讓這個HashMap性能用到極緻。什麼是極緻。就是由一萬個長度的HashMap，table的長度如果是一萬的話，至少我們可以高效利用讓其存儲一百萬的資料。而不是研究第一個元素怎麼把它放入。當然我們要了解第一個元素的放入，而不是糾結第一個元素怎麼放入。這個是第一點。
第二點，我們真的了解table的解決沖突的機制麼？難道真的就是數組加連結清單或者是數組加紅黑樹麼？有沒有更加優化的地方等待我們探索呢？其實這三個點我們都隻是略懂皮毛，來說你精通Java，來寫個JVM出來。寫不出來。保證一個HashMap都寫不出來。怎麼在用到極緻的過程中産生出自己的方法論，到底這個HashMap怎麼使用才能更高效。或者像是LinkHashMap一樣可不可以繼承HashMap實作自己的擴充高效Map。這個研究才有意義。
第三點，面試官自已以為自己了解到夠深刻，其實不然，這個世界上知識很多，其實沒有必要找一個航天工程師來給你打掃衛生。航天工程師其實還有他其他的作用。