HashMap源碼分析
HashMap的底層實作是面試中問到最多的，其原理也更加複雜，涉及的知識也越多，在項目中的使用也最多。是以清晰分析出其底層源碼對于深刻了解其實作有重要的意義，jdk1.8之後其設計與實作也有所改變。
在Java集合類中最常用的除了ArrayList外，就是HashMap了。Java最基本的資料結構有數組和連結清單。數組的特點是空間連續（大小固定）、尋址迅速，但是插入和删除時需要移動元素，是以查詢快，增加删除慢。連結清單恰好相反，可動态增加或減少空間以适應新增和删除元素，但查找時隻能順着一個個節點查找，是以增加删除快，查找慢。有沒有一種結構綜合了數組和連結清單的優點呢？當然有，那就是哈希表（雖說是綜合優點，但實際上查找肯定沒有數組快，插入删除沒有連結清單快，一種折中的方式吧）。
- 主要知識點：
- 哈希表綜合了數組和連結清單的特點。一般采用拉鍊法實作哈希表；
- 概括的說，HashMap 是一個關聯數組、哈希表，它是線程不安全的，允許key為null,value為null。周遊時無序；
- 其底層資料結構是數組稱之為哈希桶，每個桶裡面放的是連結清單，連結清單中的每個節點，就是哈希表中的每個元素；
- 在JDK8中，當連結清單長度達到8，會轉化成紅黑樹，以提升它的查詢、插入效率；
- 因其底層哈希桶的資料結構是數組，是以也會涉及到擴容的問題。當HashMap的容量達到threshold域值時，就會觸發擴容。擴容前後，哈希桶的長度一定會是2的次方。這樣在根據key的hash值尋找對應的哈希桶時，可以用位運算替代取餘操作，更加高效。
- 而key的hash值，并不僅僅隻是key對象的hashCode()方法的傳回值，還會經過擾動函數的擾動，以使hash值更加均衡。
- 擾動函數就是為了解決hash碰撞的。它會綜合hash值高位和低位的特征，并存放在低位，是以在與運算時，相當于高低位一起參與了運算，以減少hash碰撞的機率。（在JDK8之前，擾動函數會擾動四次，JDK8簡化了這個操作）
- 擴容操作時，會new一個新的Node數組作為哈希桶，然後将原哈希表中的所有資料(Node節點)移動到新的哈希桶中，相當于對原哈希表中所有的資料重新做了一個put操作。是以性能消耗很大，可想而知，在哈希表的容量越大時，性能消耗越明顯。
-
擴容時，如果發生過哈希碰撞，節點數小于8個。則要根據連結清單上每個節點的哈希值，依次放入新哈希桶對應下标位置。
因為擴容是容量翻倍，是以原連結清單上的每個節點，現在可能存放在原來的下标，即low位， 或者擴容後的下标，即high位。 high位= low位+原哈希桶容量。
- 拉鍊法的實作：
一、類聲明
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable HashMap繼承自AbstractMap，實作了Map接口，Map接口定義了所有Map子類必須實作的方法。AbstractMap也實作了Map接口，并且提供了兩個實作Entry的内部類：SimpleEntry和SimpleImmutableEntry。
二、成員變量
//預設的初始容量，必須是2的幂。
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
//最大容量（必須是2的幂且小于2的30次方，傳入容量過大将被這個值替換）
static final int MAXIMUM_CAPACITY = 1 << 30;
//預設裝載因子，預設值為0.75，如果實際元素所占容量占配置設定容量的75%時就要擴容了。如果填充比很大，說明利用的空間很多，但是查找的效率很低，因為連結清單的長度很大（當然最新版本使用了紅黑樹後會改進很多），HashMap本來是以空間換時間，是以填充比沒必要太大。但是填充比太小又會導緻空間浪費。如果關注記憶體，填充比可以稍大，如果主要關注查找性能，填充比可以稍小。
static final float _LOAD_FACTOR = 0.75f;
//一個桶的樹化門檻值
//當桶中元素個數超過這個值時，需要使用紅黑樹節點替換連結清單節點
//這個值必須為 8，要不然頻繁轉換效率也不高
static final int TREEIFY_THRESHOLD = 8;
//一個樹的連結清單還原門檻值
//當擴容時，桶中元素個數小于這個值，就會把樹形的桶元素 還原（切分）為連結清單結構
//這個值應該比上面那個小，至少為 6，避免頻繁轉換
static final int UNTREEIFY_THRESHOLD = 6;
//哈希表的最小樹形化容量
//當哈希表中的容量大于這個值時，表中的桶才能進行樹形化
//否則桶内元素太多時會擴容，而不是樹形化
//為了避免進行擴容、樹形化選擇的沖突，這個值不能小于 4 * TREEIFY_THRESHOLD
static final int MIN_TREEIFY_CAPACITY = 64;
//存儲資料的Entry數組，長度是2的幂。
transient Entry[] table;
//
transient Set<Map.Entry<K,V>> entrySet;
//map中儲存的鍵值對的數量
transient int size;
//需要調整大小的極限值（容量*裝載因子）
int threshold;
//裝載因子
final float loadFactor;
//map結構被改變的次數
transient volatile int modCount; 内部類，連結清單節點Node：
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;
}
} 三、構造方法
/**
*使用預設的容量及裝載因子構造一個空的HashMap
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
/**
* 根據給定的初始容量和裝載因子建立一個空的HashMap
* 初始容量小于0或裝載因子小于等于0将報異常
*/
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
*/
public HashMap(int initialCapacity) {
//調用上面的構造方法，容量為指定的容量，裝載因子是預設值
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//通過傳入的map建立一個HashMap，容量為預設容量（16）和(map.zise()/DEFAULT_LOAD_FACTORY)+1的較大者，裝載因子為預設值
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
} HashMap提供了四種構造方法：
（1）使用預設的容量及裝載因子構造一個空的HashMap；
（2）根據給定的初始容量和裝載因子建立一個空的HashMap；
（3）根據指定容量建立一個空的HashMap；
（4）通過傳入的map建立一個HashMap。
第三種構造方法會調用第二種構造方法，而第四種構造方法将會調用putMapEntries方法将元素添加到HashMap中去。
putMapEntries方法是一個final方法，不可以被修改，該方法實作了将另一個Map的所有元素加入表中，參數evict初始化時為false，其他情況為true
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) {
//根據m的元素數量和目前表的加載因子，計算出門檻值
float ft = ((float)s / loadFactor) + 1.0F;
//修正門檻值的邊界 不能超過MAXIMUM_CAPACITY
int t = ((ft < (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);
//如果新的門檻值大于目前門檻值
if (t > threshold)
//傳回一個>=新的門檻值的 滿足2的n次方的門檻值
threshold = tableSizeFor(t);
}
//如果目前元素表不是空的，但是 m的元素數量大于門檻值，說明一定要擴容。
else if (s > threshold)
resize();
//周遊 m 依次将元素加入目前表中。
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
} 其中，涉及到兩個操作，一個是計算新的門檻值，另一個是擴容方法：
1）如果新的門檻值大于目前門檻值，需要傳回一個>=新的門檻值的 滿足2的n次方的門檻值，這涉及到了tableSizeFor：
static final int tableSizeFor(int cap) {
//經過下面的 或 和位移 運算， n最終各位都是1。
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
//判斷n是否越界，傳回 2的n次方作為 table（哈希桶）的門檻值
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
} 2）如果目前元素表不是空的，但是 m的元素數量大于門檻值，說明一定要擴容。這涉及到了擴容方法resize，這是個人認為HashMap中最複雜的方法：
final Node<K,V>[] resize() {
//oldTab 為目前表的哈希桶
Node<K,V>[] oldTab = table;
//目前哈希桶的容量 length
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//目前的門檻值
int oldThr = threshold;
//初始化新的容量和門檻值為0
int newCap, newThr = 0;
//如果目前容量大于0
if (oldCap > 0) {
//如果目前容量已經到達上限
if (oldCap >= MAXIMUM_CAPACITY) {
//則設定門檻值是2的31次方-1
threshold = Integer.MAX_VALUE;
//同時傳回目前的哈希桶，不再擴容
return oldTab;
}//否則新的容量為舊的容量的兩倍。
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果舊的容量大于等于預設初始容量16
//那麼新的門檻值也等于舊的門檻值的兩倍
newThr = oldThr << 1; // double threshold
}
//如果目前表是空的，但是有門檻值。代表是初始化時指定了容量、門檻值的情況
else if (oldThr > 0)
newCap = oldThr;//那麼新表的容量就等于舊的門檻值
else {
//如果目前表是空的，而且也沒有門檻值。代表是初始化時沒有任何容量/門檻值參數的情況
newCap = DEFAULT_INITIAL_CAPACITY;//此時新表的容量為預設的容量 16
//新的門檻值為預設容量16 * 預設加載因子0.75f = 12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
//如果新的門檻值是0，對應的是 目前表是空的，但是有門檻值的情況
float ft = (float)newCap * loadFactor;//根據新表容量 和 加載因子 求出新的門檻值
//進行越界修複
newThr = (newCap < MAXIMUM_CAPACITY && ft <(float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
}
//更新門檻值
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) {
//取出目前的節點 e
Node<K,V> e;
//如果目前桶中有元素,則将連結清單指派給e
if ((e = oldTab[j]) != null) {
//将原哈希桶置空以便GC
oldTab[j] = null;
//如果目前連結清單中就一個元素，（沒有發生哈希碰撞）
if (e.next == null)
//直接将這個元素放置在新的哈希桶裡。
//注意這裡取下标 是用 哈希值 與 桶的長度-1 。 由于桶的長度是2的n次方，這麼做其實是等于 一個模運算。但是效率更高
newTab[e.hash & (newCap - 1)] = e;
//如果發生過哈希碰撞 ,而且是節點數超過8個，轉化成了紅黑樹
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//如果發生過哈希碰撞，節點數小于8個。則要根據連結清單上每個節點的哈希值，依次放入新哈希桶對應下标位置。
else {
//因為擴容是容量翻倍，是以原連結清單上的每個節點，現在可能存放在原來的下标，即low位，或者擴容後的下标，即high位。high位=low位+原哈希桶容量
//低位連結清單的頭結點、尾節點
Node<K,V> loHead = null, loTail = null;
//高位連結清單的頭節點、尾節點
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;//臨時節點 存放e的下一個節點
do {
next = e.next;
//利用位運算代替正常運算：利用哈希值與舊的容量，可以得到哈希值去模後，是大于等于oldCap還是小于oldCap，等于0代表小于oldCap，應該存放在低位，否則存放在高位
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);
//将低位連結清單存放在原index處
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//将高位連結清單存放在新index處
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
} resize的操作主要涉及以下幾步操作： - 如果到達最大容量，那麼傳回目前的桶，并不再進行擴容操作，否則的話擴容為原來的兩倍，傳回擴容後的桶；
- 根據擴容後的桶，修改其他的成員變量的屬性值；
- 根據新的容量建立新的擴建後的桶，并更新桶的引用；
- 如果原來的桶裡面有元素就需要進行元素的轉移；
- 在進行元素轉移的時候需要考慮到元素碰撞和轉紅黑樹操作；
- 在擴容的過程中，按次從原來的桶中取對外連結表頭節點，并對該連結清單上的所有元素重新計算hash值進行配置設定；
- 在發生碰撞的時候，将新加入的元素添加到末尾；
- 在元素複制的時候需要同時對低位和高位進行操作。
四、成員方法
- put方法：
//向哈希表中添加元素
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
} 向使用者開放的put方法調用的是putVal方法：
putVal方法需要判斷是否出現哈希沖突問題：
其中如果哈希值相等，key也相等，則是覆寫value操作；如果不是覆寫操作，則插入一個普通連結清單節點；
周遊到尾部，追加新節點到尾部；
在元素添加的過程中需要随時檢查是否需要進行轉換成紅黑樹的操作；
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
//tab存放目前的哈希桶，p用作臨時連結清單節點
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果目前哈希表是空的，代表是初始化
if ((tab = table) == null || (n = tab.length) == 0)
//那麼直接去擴容哈希表，并且将擴容後的哈希桶長度指派給n
n = (tab = resize()).length;
//如果目前index的節點是空的，表示沒有發生哈希碰撞。直接建構一個新節點Node，挂載在index處即可。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {//否則 發生了哈希沖突。
Node<K,V> e; K k;
//如果哈希值相等，key也相等，則是覆寫value操作
if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))
e = p;//将目前節點引用指派給e
else if (p instance of 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);
//如果追加節點後，連結清單數量>=8，則轉化為紅黑樹
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;
}
}
//如果e不是null，說明有需要覆寫的節點，
if (e != null) { // existing mapping for key
//則覆寫節點值，并傳回原oldValue
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//這是一個空實作的函數，用作LinkedHashMap重寫使用。
afterNodeAccess(e);
return oldValue;
}
}
//如果執行到了這裡，說明插入了一個新的節點，是以會修改modCount，以及傳回null。
++modCount;
//更新size，并判斷是否需要擴容。
if (++size > threshold)
resize();
//這是一個空實作的函數，用作LinkedHashMap重寫使用。
afterNodeInsertion(evict);
return null;
} 當存入的key是null的時候将調用putVal方法，看key不為null的情況。先調用了hash(int h)方法擷取了一個hash值。
“擾動函數”，這個方法的主要作用是防止品質較差的哈希函數帶來過多的沖突（碰撞）問題。Java中int值占4個位元組，即32位。根據這32位值進行移位、異或運算得到一個值。
那HashMap中最核心的部分就是哈希函數，又稱散列函數。也就是說，哈希函數是通過把key的hash值映射到數組中的一個位置來進行通路。
hashCode右移16位，正好是32bit的一半。與自己本身做異或操作（相同為0，不同為1）。就是為了混合哈希值的高位和低位，增加低位的随機性。并且混合後的值也變相保持了高位的特征。
HashMap之是以不能保持元素的順序有以下幾點原因：
- 插入元素的時候對元素進行哈希處理，不同元素配置設定到table的不同位置；
- 容量拓展的時候又進行了hash處理；第三，複制原表内容的時候連結清單被倒置。
- 複制原表内容的時候連結清單被倒置。
//隻做一次16位右位移異或混合：
static int hash(Object key) {
int h;
return (key == null) ? 0 : (h=key.hashCode())^(h>>>16);
} 其中，key.hashCode（）是Key自帶的hashCode()方法，傳回一個int類型的散列值。我們大家知道，32位帶符号的int表值範圍從-2147483648到2147483648。這樣隻要hash函數松散的話，一般是很難發生碰撞的，因為HashMap的初始容量隻有16。但是這樣的散列值我們是不能直接拿來用的。用之前需要對數組的長度取模運算。得到餘數才是索引值。
indexFor傳回hash值和table數組長度減1的與運算結果。為什麼使用的是length-1？因為這樣可以保證結果的最大值是length-1，不會産生數組越界問題。
static int indexFor(int h, int length) {
return h & (length-1);
} - get方法
public V get(Object key) {
Node<K,V> e;
//傳入擾動後的哈希值 和 key 找到目标節點Node
return (e = getNode(hash(key), key)) == null ? null : e.value;
} HashMap向使用者分開放的get方法是調用的getNode方法來實作的，
//傳入擾動後的哈希值 和 key 找到目标節點Node
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//查找過程，找到傳回節點，否則傳回null
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && ((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;
} 查找的判斷條件是：e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))，在比較hash值的同時需要比較key的值是否相同。
- 其他方法
1）contains
HashMap沒有提供判斷元素是否存在的方法，隻提供了判斷Key是否存在及Value是否存在的方法，分别是containsKey(Object key)、containsValue(Object value)。
containsKey(Object key)方法很簡單，隻是判斷getNode (key)的結果是否為null，是則傳回false，否傳回true。 public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
//周遊哈希桶上的每一個連結清單
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
//如果找到value一緻的傳回true
if ((v = e.value) == value || (value != null && value.equals(v)))
return true;
}
}
}
return false;
}
判斷一個value是否存在比判斷key是否存在還要簡單，就是周遊所有元素判斷是否有相等的值。這裡分為兩種情況處理，value為null何不為null的情況，但内容差不多，隻是判斷相等的方式不同。這個判斷是否存在必須周遊所有元素，是一個雙重循環的過程，是以是比較耗時的操作。
2）remove方法
HashMap中“删除”相關的操作，有remove(Object key)和clear()兩個方法。
其中向使用者開放的remove方法調用的是removeNode方法，，removeNode (key)的傳回結果應該是被移除的元素，如果不存在這個元素則傳回為null。remove方法根據removeEntryKey傳回的結果e是否為null傳回null或e.value。 public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value, boolean matchValue, boolean movable) {
// p 是待删除節點的前置節點
Node<K,V>[] tab; Node<K,V> p; int n, index;
//如果哈希表不為空，則根據hash值算出的index下 有節點的話。
if ((tab = table) != null && (n = tab.length) > 0&&(p = tab[index = (n - 1) & hash]) != null) {
//node是待删除節點
Node<K,V> node = null, e; K k; V v;
//如果連結清單頭的就是需要删除的節點
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
node = p;//将待删除節點引用賦給node
else if ((e = p.next) != null) {//否則循環周遊 找到待删除節點，指派給node
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash && ((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//如果有待删除節點node， 且 matchValue為false，或者值也相等
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)//如果node == p，說明是連結清單頭是待删除節點
tab[index] = node.next;
else//否則待删除節點在表中間
p.next = node.next;
++modCount;//修改modCount
--size;//修改size
afterNodeRemoval(node);//LinkedHashMap回調函數
return node;
}
}
return null;
} clear()方法删除HashMap中所有的元素，這裡就不用一個個删除節點了，而是直接将table數組内容都置空，這樣所有的連結清單都已經無法通路，Java的垃圾回收機制會去處理這些連結清單。table數組置空後修改size為0。
public void clear() {
Node<K,V>[] tab;
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
} 五、樹形化和紅黑樹的操作
可以看到無論是put，get還是remove方法中都有if (node instanceof TreeNode)方法來判斷目前節點是否是一個樹形化的節點，如果是的話就需要調用相應的紅黑樹的相關操作。
- 紅黑樹的成員變量的定義：
TreeNode<K,V> parent; // 父節點
TreeNode<K,V> left; //左節點
TreeNode<K,V> right; //右節點
TreeNode<K,V> prev; // 在連結清單中的前一個節點
boolean red; //染紅或者染黑标記 - 桶的樹形化
桶的樹形化 treeifyBin()，如果一個桶中的元素個數超過 TREEIFY_THRESHOLD(預設是 8 )，就使用紅黑樹來替換連結清單，進而提高速度。這個替換的方法叫 treeifyBin() 即樹形化。
//将桶内所有的 連結清單節點 替換成 紅黑樹節點
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//如果目前哈希表為空，或者哈希表中元素的個數小于進行樹形化的門檻值(預設為 64)，就去建立/擴容
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
//如果哈希表中的元素個數超過了樹形化門檻值，進行樹形化，e是哈希表中指定位置桶裡的連結清單節點，從第一個開始
else if ((e = tab[index = (n - 1) & hash]) != null) {
//建立一個樹形節點，内容和目前連結清單節點e一緻
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);
}
} 這段代碼很簡單，隻是對桶裡面的每個元素調用了replacementTreeNode方法将目前的節點變為一個樹形節點來進行樹形化：
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
} 在所有的節點都替換成樹形節點後需要讓桶的第一個元素指向建立的紅黑樹頭結點，以後這個桶裡的元素就是紅黑樹而不是連結清單了，之前的操作并沒有設定紅黑樹的顔色值，現在得到的隻能算是個二叉樹。在最後調用樹形節點 hd.treeify(tab) 方法進行塑造紅黑樹，這是HashMap中個人認為第二個比較難的方法：
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) { //第一次進入循環，确定頭結點，為黑色
x.parent = null;
x.red = false;
root = x;
}
else { //後面進入循環走的邏輯，x 指向樹中的某個節點
K k = x.key;
int h = x.hash;
Class<?> kc = null;
//又一個循環，從根節點開始，周遊所有節點跟目前節點 x 比較，調整位置，有點像冒泡排序
for (TreeNode<K,V> p = root;;) {
int dir, ph; //這個 dir
K pk = p.key;
if ((ph = p.hash) > h) //當比較節點的哈希值比 x 大時，dir 為 -1
dir = -1;
else if (ph < h) //哈希值比 x 小時 dir 為 1
dir = 1;
else if ((kc == null && (kc = comparableClassFor(k)) == null) ||(dir = compareComparables(kc, k, pk)) == 0)
// 如果比較節點的哈希值x
dir = tieBreakOrder(k, pk);
//把目前節點變成 x 的父親
//如果目前比較節點的哈希值比 x 大，x 就是左孩子，否則 x 是右孩子
TreeNode<K,V> xp = p;
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;
}
}
}
}
moveRootToFront(tab, root);
} 可以看到，将二叉樹變為紅黑樹時，需要保證有序。這裡有個雙重循環，拿樹中的所有節點和目前節點的哈希值進行對比(如果哈希值相等，就對比鍵，這裡不用完全有序），然後根據比較結果确定在樹種的位置。
紅黑樹的基本要求：
紅黑樹是一種近似平衡的二叉查找樹，它能夠確定任何一個節點的左右子樹的高度差不會超過二者中較低那個的一倍。它不是嚴格控制左、右子樹高度或節點數之差小于等于1，但紅黑樹高度依然是平均log(n)，且最壞情況高度不會超過2log(n)。紅黑樹是滿足如下條件的二叉查找樹（binary search tree）：
- 每個節點要麼是紅色，要麼是黑色。
- 根節點必須是黑色
- 紅色節點不能連續（也即是，紅色節點的孩子和父親都不能是紅色）。
- 對于每個節點，從該點至
null
上面的方法treeify涉及到的修正紅黑樹的方法balanceInsertion方法需要對樹中節點進行重新的染色，這個函數也是紅黑樹樹插入資料時需要調用的函數，其中涉及到的是左旋和右旋操作，這也是紅黑樹中兩個主要的操作：
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root, TreeNode<K,V> x) {
//插入的節點必須是紅色的，除非是根節點
x.red = true;
//周遊到x節點為黑色,整個過程是一個上濾的過程
xp=x.parent;xpp=xp.parent;xppl=xpp.left;xppr=xpp.right;
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//如果xp是黑色就直接完成，最簡單的情況
else if (!xp.red || (xpp = xp.parent) == null)
return root;
//如果x的父節點是xp父節點的左節點
if (xp == (xppl = xpp.left)) {
//x的父親節點的兄弟是紅色的（需要顔色翻轉）case1
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false; //x父親節點的兄弟節點置成黑色
xp.red = false; //父親和其兄弟節點一樣是黑色
xpp.red = true; //祖父節點置成紅色
x = xpp; //然後上濾（就是不斷的重複上面的操作）
}
else {
//如果x是xp的右節點整個要進行兩次旋轉,先左旋轉再右旋轉
// case2
if (x == xp.right) {
root = rotateLeft(root, x = xp);//左旋
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//case3
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);//右旋
}
}
}
}
//以左節點鏡像對稱
else {
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
} 左旋操作和右旋操作，拿出其中的代碼：
//左旋轉
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root, TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
if (p != null && (r = p.right) != null) {
if ((rl = p.right = r.left) != null)
rl.parent = p;
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;
else if (pp.left == p)
pp.left = r;
else
pp.right = r;
r.left = p;
p.parent = r;
}
return root;
}
//右旋轉
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root, TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
if (p != null && (l = p.left) != null) {
if ((lr = p.left = l.right) != null)
lr.parent = p;
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
else if (pp.right == p)
pp.right = l;
else
pp.left = l;
l.right = p;
p.parent = l;
}
return root;
} 代碼看上去比較繞，借用部落格https://www.cnblogs.com/CarpenterLee/p/5503882.html中的圖來解釋：
左旋
左旋的過程是将
x
的右子樹繞
x
逆時針旋轉，使得
x
的右子樹成為
x
的父親，同時修改相關節點的引用。旋轉之後，二叉查找樹的屬性仍然滿足。
右旋
右旋的過程是将
x
的左子樹繞
x
順時針旋轉，使得
x
的左子樹成為
x
的父親，同時修改相關節點的引用。旋轉之後，二叉查找樹的屬性仍然滿足。
針對HashMap的樹形結構的插入，删除，查找操作也與資料結構中紅黑樹的操作是類似的，了解紅黑樹的操作也就了解了HashMap的樹形結構的操作，balanceInsertion和左旋右旋的操作是上述HashMap的樹形結構操作的關鍵。