本文件出處https://shenyifengtk.github.io/2020/05/10/HashMap源碼解析
轉(zhuǎn)載請說明出處
以后面試官問你HashMap原理平道，不能再答數(shù)組+鏈表的結(jié)構(gòu)了臊泌，
JDK1.8添加了紅黑樹結(jié)構(gòu)篷店，知識要與時俱進(jìn)啊。受限于文章篇幅瘪弓，我會從HashMap 初始化劫映，put、get方面解析底層原理府蛇。
內(nèi)部設(shè)定
常量設(shè)定
/**
* HashMap 默認(rèn)初始化長度
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* HashMap 允許容器數(shù)組最大長度
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 負(fù)載因子集索，容器數(shù)量/容器最大長度 大于等于，數(shù)組進(jìn)行擴容
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 鏈表的長度超過閾值汇跨，在添加元素的時候鏈表轉(zhuǎn)化成紅黑樹
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 在擴容的時候务荆，紅黑樹數(shù)量小于閾值轉(zhuǎn)換成鏈表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 最小table 容器數(shù)量支持鏈表樹化
*/
static final int MIN_TREEIFY_CAPACITY = 64;
內(nèi)部元素結(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;
}
}
Node對象只擁有三個屬性，key穷遂，value函匕，next，結(jié)構(gòu)非常簡單蚪黑，操作也簡單盅惜。
內(nèi)部屬性變量
/**
* 內(nèi)部數(shù)組，上面所說table 指的就是這個
*/
transient Node<K,V>[] table;
/**
* entrySet() 返回容器
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* 鍵值對的數(shù)量忌穿，也是HashMap size
*/
transient int size;
/**
* HashMap 結(jié)構(gòu)修改次數(shù)
*/
transient int modCount;
/**
* 擴容table 閾值
*/
int threshold;
/**
* 擴容因子
*/
final float loadFactor;
解析代碼
構(gòu)造函數(shù)
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);
}
/**
* Constructs an empty <tt>HashMap</tt> with the specified initial
* capacity and the default load factor (0.75).
*
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* Constructs an empty <tt>HashMap</tt> with the default initial capacity
* (16) and the default load factor (0.75).
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
這段代碼很簡單抒寂，主要是判斷兩個輸入?yún)?shù)是否合法，將容器長度重新計算擴容閾值掠剑。
看下tableSizeFor怎么計算閾值
/**
* 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;
}
這個方法其實通過輸入數(shù)屈芜，返回一個最接近大于等于他的2次方數(shù)。
通過將cap 高位1不斷右移，返回cap最近2次方的數(shù)井佑。如果有同學(xué)看不懂這個算法属铁，可以參考這位老哥寫的https://blog.csdn.net/fan2012huan/article/details/51097331，解析得非常易懂躬翁。
上面的構(gòu)造函數(shù)焦蘑，并沒有初始化Node 數(shù)組，我進(jìn)入put方法看下怎么樣初始化的姆另！
添加元素
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//p 如果存在就是鏈頭
Node<K,V>[] tab; Node<K,V> p; int n, i;
//數(shù)組未初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//根據(jù)hash 值 計算數(shù)組下標(biāo)位置喇肋，這個位置下沒有元素
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null); //插入元素
else {//hash 值沖突
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) //key 相等
e = p;
else if (p instanceof TreeNode) //紅黑樹
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) { //遍歷鏈表，插入數(shù)據(jù)
if ((e = p.next) == null) { //下一個元素為空迹辐，說明已經(jīng)遍歷到最后一個元素 蝶防，插入 終止循環(huán)
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // 到達(dá)轉(zhuǎn)化成樹鏈的閾值
treeifyBin(tab, hash); //將鏈表轉(zhuǎn)換成樹
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) //出現(xiàn)key 相等
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); //空方法 ，LinkedHashMap 實現(xiàn)
return oldValue;
}
}
++modCount;
if (++size > threshold) //超出閾值
resize();
afterNodeInsertion(evict);
return null;
}
整體流程： 先判斷數(shù)組為空明吩，沒有則使用resize()方法初始化數(shù)組间学，使用hash 值& 數(shù)組長度計算下標(biāo)，下標(biāo)值為空印荔，直接插入低葫。處理hash沖突情況，先判斷鏈頭key是否相等仍律，判斷數(shù)組Node是否樹鏈嘿悬，則使用putTreeVal方法插入樹鏈中，否則遍歷鏈表在結(jié)尾插入水泉。最后判斷數(shù)組元素是否超過閾值善涨，使用reszie()擴容。這個流程基本和我們平常寫業(yè)務(wù)代碼差不多草则。
計算hash方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
假設(shè)沒有這個hash算法钢拧，對象hashCode直接&數(shù)組長度(n-1),當(dāng)n比較小的時候，hash雖然是32位整數(shù)炕横，但是只要低位是有效的源内，hash沖突概率比較大，會導(dǎo)致鏈表比較長份殿。使用hash方法將高16位影響到低16位膜钓，將低16位的二進(jìn)制打散了，減少了hash沖突概率卿嘲。
resize擴容颂斜，初始化數(shù)組方法
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) { //大于最大數(shù)組長度，不會進(jìn)行擴容操作
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) // 使用構(gòu)造函數(shù)cap初始化數(shù)組長度
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 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]; //創(chuàng)建新數(shù)組
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null; //刪除數(shù)組元素
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 { //將鏈條分成兩個鏈條焚鲜，一個是原數(shù)組下標(biāo)掌唾，另一個則下標(biāo) x 2移動下標(biāo)
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); //將兩種鏈條的鏈頭元素插入到數(shù)組中
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
整體流程還是比較簡單的放前，先確定數(shù)組長度忿磅，threshold屬性，創(chuàng)建新數(shù)組移動copy元素凭语，刪除原數(shù)組元素葱她。這個方法基本就是初始化table數(shù)組，擴容數(shù)組似扔，處理鏈條或樹鏈的內(nèi)部細(xì)節(jié)吨些。
if ((e.hash & oldCap) == 0) { 這個寫法，看了好久才明白什么意思啊炒辉。我們都知道數(shù)組長度永遠(yuǎn)都是2的次方豪墅，二進(jìn)制表現(xiàn)就是最高位是1 其他都是0， 比如默認(rèn)長度16 黔寇，二進(jìn)制就是10000偶器。 計算數(shù)組長度算法e.hash & (oldCap- 1)， 長度-1 二機制的數(shù)11111,先數(shù)組擴容長度 * 2缝裤，計算下標(biāo)結(jié)果下標(biāo)前面不變屏轰，最高位是0還是1，是0保存下標(biāo)不變憋飞，是1表示下標(biāo)需要x 2.霎苗。覺得講得不清楚，可以看下圖
image
下面了解拆分樹鏈的
split
/**
* @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
*/
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// 按hash 計算結(jié)果區(qū)分兩個樹鏈榛做，統(tǒng)計樹鏈的長度
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
tab[index] = loHead.untreeify(map); //拆分樹鏈轉(zhuǎn)化成鏈條結(jié)構(gòu)
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);
}
}
}
首先要知道TreeNode間接繼承Node唁盏，擁有單向鏈條的屬性。理解上面流程就很簡單了瘤睹，先遍歷樹鏈升敲，按照hash & 數(shù)組長度方式，分成移動下標(biāo)和不移動兩個類型樹鏈轰传。再判斷鏈條數(shù)量是否大于UNTREEIFY_THRESHOLD(6) ,滿足使用untreeify方法拆分成鏈條驴党。如果樹鏈頭不為空，則說明紅黑樹結(jié)構(gòu)依然存在获茬，使用treeify方法將鏈表轉(zhuǎn)換成樹鏈港庄。
要理解鏈表怎么轉(zhuǎn)化成樹鏈，必須深入treeify方法
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//從this 鏈頭開始遍歷
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) { //root 根元素
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) { //如果子節(jié)點黑紅都是null恕曲，直接插入指向鹏氧，否則向下遞歸
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x); //調(diào)整節(jié)點位置，著色佩谣，左旋或者右旋
break;
}
}
}
}
moveRootToFront(tab, root); //判斷root是否根節(jié)點把还，如果不是插入根節(jié)點位置
}
看到這里，大家是不是跟我一樣，覺得代碼寫得還是比較簡單的吊履，沒什么難度啊安皱。下面代碼就不是這樣了，沒有一點黑紅樹基礎(chǔ)的同學(xué)艇炎，麻煩先補下課先酌伊，不然你很難理解代碼什么意思。
紅黑樹的性質(zhì)
- 節(jié)點是紅色或黑色缀踪。
- 根節(jié)點是黑色居砖。
- 所有葉子都是黑色（葉子是NIL節(jié)點）
- 每個紅色節(jié)點的兩個孩子節(jié)點必須是黑色. (從葉子到根的所有路徑上不能有兩個連續(xù)的紅色節(jié)點)
- 從任意節(jié)點到其葉子節(jié)點的所有路徑都包含相同數(shù)目的黑色節(jié)點。
紅黑樹.png
在紅黑樹插入或刪除情況驴娃，上面的特征可能會被打破奏候。所以要使用
balanceInsertion方法平衡樹鏈結(jié)構(gòu)。我們在分析代碼的時候唇敞，一定要把上面5個性質(zhì)帶上有助于理解鼻由。
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
x.red = true; //默認(rèn)x 就是紅色
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//x 的父節(jié)點xp為空，則說明x 就是根節(jié)點 , 根據(jù)1屬性厚棵，節(jié)點變成黑色就可以了
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
//父節(jié)點黑色蕉世，插入紅色，以上條件都滿足婆硬，終止循環(huán)
else if (!xp.red || (xpp = xp.parent) == null)
return root;
if (xp == (xppl = xpp.left)) {
//見圖1-1 狠轻，不滿足性質(zhì)4、性質(zhì)5彬犯，改變著色向楼，向上遞歸
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {
//見圖1-2 不滿足 性質(zhì)4，xp左移
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// 圖1-3情況 不滿足性質(zhì)4谐区，xpp 右移 調(diào)整著色
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);
}
}
}
}
}
}
上面的代碼配合這三個圖片宋列，看出1-3 處理完后昭抒，剛好是圖1-1 處理條件，向上遞歸炼杖，直到終止循環(huán)灭返。這個就是插入后，調(diào)整紅黑樹平衡整體流程坤邪。這些代碼熙含，我當(dāng)時看了一整天也明白什么意思，后面結(jié)合紅黑樹知識艇纺，自己畫圖對應(yīng)代碼流程怎静，理解起來就很簡單了邮弹。
圖1-1
圖1-2
圖1-3
有了這些理解在去看
putTreeVal方法就很簡單了
/**
* Tree version of putVal.
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
TreeNode<K,V> root = (parent != null) ? root() : this;
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
// 獲取key 類型，判斷是是compare接口 比較大小
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
dir = tieBreakOrder(k, pk); //使用類名蚓聘，原生hash比較大小
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
遍歷樹鏈肠鲫，比較hash 大小，找到子節(jié)點插入位置或粮，使用balanceInsertion方法平衡紅黑樹。
獲取value 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 && //空數(shù)組不指望了
(first = tab[(n - 1) & hash]) != null) { //計算數(shù)組下標(biāo)位置
if (first.hash == hash && // 獲取到value
((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;
}
看下紅黑樹查找
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h) //大于往左邊
p = pl;
else if (ph < h) //小于往右邊
p = pr;
else if ((pk = p.key) == k || (k != null && k.equals(pk))) //找到了
return p;
else if (pl == null) //遍歷到最底下一個節(jié)點為止氯材，這個p節(jié)點肯定沒有字節(jié)點
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}
刪除節(jié)點
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) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) //根據(jù)key 找到value
node = p;
else if ((e = p.next) != null) {
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);
}
}
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); //在紅黑樹中刪除，這個有點復(fù)雜
else if (node == p) //如果p剛好是鏈頭硝岗，指引刪除
tab[index] = node.next;
else //p 剛好表示前一位氢哮，node 要被刪除，p指向node 下一個節(jié)點型檀，即可刪除冗尤。
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
數(shù)組和鏈表刪除還是比較簡單的，下標(biāo)指引變更即可胀溺。紅黑樹元素刪除就相當(dāng)復(fù)雜了裂七，比插入數(shù)據(jù)要麻煩等多了
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
if (tab == null || (n = tab.length) == 0)
return;
int index = (n - 1) & hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
if (pred == null) //前置節(jié)點為空，將鏈頭指向succ仓坞，即子節(jié)點
tab[index] = first = succ;
else //將前置節(jié)點指向next背零，相當(dāng)于刪除this
pred.next = succ;
if (succ != null) //刪除
succ.prev = pred;
if (first == null)
return;
if (root.parent != null)
root = root.root();
if (root == null //根據(jù)紅黑樹特性，最短路徑不能小于最長路徑1/2无埃，樹鏈長度不足 2 +4 = 6徙瓶，拆分
|| (movable
&& (root.right == null
|| (rl = root.left) == null
|| rl.left == null))) {
tab[index] = first.untreeify(map); // too small
return;
}
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
if (pl != null && pr != null) {
TreeNode<K,V> s = pr, sl;
while ((sl = s.left) != null) // 找到右孩子的左子樹找最小值
s = sl;
boolean c = s.red; s.red = p.red; p.red = c; // 交換顏色
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
if (s == pr) { // s 是 p直系右子節(jié)點 ，交換位置
p.parent = s;
s.right = p;
}
else {
TreeNode<K,V> sp = s.parent;
if ((p.parent = sp) != null) { //p 移動到s 位置
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if ((s.right = pr) != null) //s 移動到位置
pr.parent = s;
}
p.left = null;
if ((p.right = sr) != null) //p 右節(jié)點 和s 關(guān)聯(lián)
sr.parent = p;
if ((s.left = pl) != null) //s 和p子左邊節(jié)點pl關(guān)聯(lián)起來
pl.parent = s;
if ((s.parent = pp) == null) // s 父節(jié)點 指向 p 父節(jié)點 s 已經(jīng)完全替換p
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
if (sr != null)
replacement = sr;
else
replacement = p;
}
else if (pl != null) //只有左節(jié)點情況
replacement = pl;
else if (pr != null) //只有右節(jié)點情況
replacement = pr;
else
replacement = p;
if (replacement != p) {
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
(root = replacement).red = false;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
p.left = p.right = p.parent = null;
}
//調(diào)整元素在紅黑樹中著色嫉称，保持平衡
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
if (replacement == p) { // 刪除元素p
TreeNode<K,V> pp = p.parent;
p.parent = null;
if (pp != null) {
if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
if (movable)
moveRootToFront(tab, r);
}
簡單說一下侦镇，這個方法代碼是思路，首先處理最簡單的鏈表刪除元素织阅，將鏈表中對象的引用改成旁邊的元素壳繁。
紅黑樹刪除元素則比較復(fù)雜點，考慮的情況比較多荔棉。比如刪除節(jié)點在底下氮趋，沒有子節(jié)點，還要考慮元素的著手江耀，如果是紅色則可以直接刪除剩胁，黑色需要著色。如果擁有一個左節(jié)點祥国、右節(jié)點或者兩個都要昵观，情況就更加復(fù)雜了晾腔。這個方法大部分代碼都是在處理左右節(jié)點不為空的情況，將刪除節(jié)點位置和右節(jié)點下最左邊的子節(jié)點交換位置啊犬，并且交換著色灼擂。為什么要這么做呢？主要是因為這個節(jié)點的hash值和刪除節(jié)點值最為接近觉至，紅黑樹的特性小于在左邊剔应，大于在右邊，大于刪除值的最小值语御，就整個紅黑樹最接近刪除的值峻贮。在調(diào)整紅黑樹著色，任務(wù)就算完成了应闯。
心得
整體來說HashMap的代碼并不是很復(fù)雜纤控，底層業(yè)務(wù)代碼，其實就跟我們平常寫的crud代碼碉纺。但是我在看代碼的時候船万，有一些地方好難看懂啊，主要是涉及到紅黑樹的知識點骨田。很多程序員（包括我）平常都會抱怨數(shù)據(jù)結(jié)構(gòu)沒什么用耿导，在工作中用不上，其實我們掌握不夠熟練态贤，在工作上不知道使用碎节。
