這篇文章打算詳細理一下HashMap的源碼，可能會比較長，基于JDK1.8
HashMap數(shù)據(jù)結(jié)構(gòu)
HashMap的數(shù)據(jù)結(jié)構(gòu)一句話就是 數(shù)組+鏈表+紅黑樹
首先HashMap是一個數(shù)組顽悼，俗稱Hash桶，每個桶有可能是一個鏈表，也有可能是一棵紅黑樹（當鏈表長度達到8就會轉(zhuǎn)換成紅黑樹）逝嚎，如下圖所示（圖片來自網(wǎng)絡）
table就是一個Hash桶，當一個鍵值對要put炉菲，通過hash算法和高位運算及取模運算來定位該鍵值對的存儲位置堕战。有時兩個key會定位到相同的一個Hash桶，就發(fā)生了Hash碰撞拍霜，當hash算法計算結(jié)果越分散均勻嘱丢，Hash碰撞的概率就越小，Map存儲效率就越高祠饺。
當發(fā)生Hash碰撞越驻，HashMap采用了鏈地址法，就是數(shù)組加鏈表的結(jié)合，每一個Hash桶都是一個鏈表缀旁，如果發(fā)生沖突记劈，則將數(shù)據(jù)接在鏈表下面。Java8增加了紅黑樹來存儲數(shù)據(jù)并巍，在極端情況下目木，大量數(shù)據(jù)非常湊巧的放在同一個Hash桶下，這時對索引就會產(chǎn)生很大的負擔懊渡，所以當鏈表長度達到8時刽射，就會將鏈表轉(zhuǎn)換成紅黑樹，提高查詢性能剃执。
上圖每一個矩形都是一個存放數(shù)據(jù)的節(jié)點Node誓禁，本質(zhì)是鍵值對，有兩種肾档，如果是鏈表摹恰，則是Node類，如果是紅黑樹阁最，則是TreeNode類戒祠，TreeNode繼承了Node類（Node和TreeNode都是HashMap的靜態(tài)內(nèi)部類）。Node類的源碼字段定義如下
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
*/
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;
}
// 省略其他方法...
}
這里的 hash 值是HashMap對key自身的hashCode值進行重新計算的新的Hash值速种，計算方式如下姜盈，key自身的hashCode值的高16位與低16位進行異或操作，即對key進行高位計算（讓高16位也參與計算配阵，為了計算出更加分散的hash值）
/**
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
紅黑樹的TreeNode類字段定義源碼如下：
/**
* Entry for Tree bins. Extends LinkedHashMap.Entry (which in turn
* extends Node) so can be used as extension of either regular or
* linked node.
*/
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
// 省略大量TreeNode的方法
}
parent馏颂、left、right 棋傍，表示紅黑樹當前節(jié)點的父節(jié)點救拉，左孩子節(jié)點，右孩子節(jié)點瘫拣。boolean red亿絮，表示當前節(jié)點是否為紅色。在變成紅黑樹之前麸拄，這個hash桶是一個鏈表派昧，從HashMap.Node可以看出Node節(jié)點只維護了下一個節(jié)點的引用，也就是next 拢切。在變成紅黑樹的時候蒂萎，這里多了個prev，維護當前節(jié)點還是鏈表中的Node節(jié)點時的上一個節(jié)點淮椰，用來恢復成鏈表時使用五慈，所以實際上TreeNode是一個紅黑樹節(jié)點纳寂，也是一個雙向鏈表的節(jié)點。其次 TreeNode 是HashMap的靜態(tài)內(nèi)部類泻拦，包內(nèi)可見毙芜，不可被繼承，并且繼承至 LinkedHashMap.Entry 聪轿。而LinkedHashMap.Entry這個類又是繼承 HashMap.Node 這個內(nèi)部類爷肝。
這里的設計不明白的是，為什么不直接繼承 HashMap.Node ,而是要繼承 LinkedHashMap.Entry
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {
super(hash, key, value, next);
}
}
可以看到 LinkedHashMap.Entry也是繼承HashMap.Node陆错，多了兩個 before 和 after 字段灯抛，這是為了維護 LinkedHashMap 的雙向鏈表的功能。說明 HashMap.TreeNode 就擁有雙向鏈表的能力音瓷，可是TreeNode增加了一個prev屬性來存儲前一個節(jié)點对嚼，加上從Node繼承過來的next屬性，說明即使不繼承LinkedHashMap.Entry也擁有雙向鏈表的能力绳慎，從其他方法也能看出來纵竖，使用的也是 pre 和 next 這兩個屬性，而不是 before 和 after 這兩個屬性杏愤，即從LinkedHashMap.Entry繼承過來的兩個屬性是完全沒有用到的靡砌。所以不明白這樣繼承的意義何在，相當于TreeNode多了兩個用不到的引用珊楼。目前網(wǎng)上還沒有找到合理的解釋通殃，stackoverflow有一個提問就是關(guān)于該問題，不過Answer不太理解
why in Java8 the TreeNode subclass in HashMap extends LinkedHashMap.Entry instead of directly extending HashMap's Node subclass?
HashMap屬性
一個類的屬性成員很重要厕宗，以下就來解釋一波HashMap屬性成員
- HashMap的默認的初始容量是16画舌，也就是數(shù)組的長度，并從注釋可以看出容量大小必須是2的冪次方
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
- HashMap的最大容量已慢，為2的30次冪減1
/**
* The maximum capacity, used if a higher value is implicitly specified
* by either of the constructors with arguments.
* MUST be a power of two <= 1<<30.
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
- 默認的負載因子曲聂，為0.75，當HashMap中的元素個數(shù)達到了這個閾值（容量大小 * 負載因子）佑惠，則會進行擴容
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
- 一個桶存儲的數(shù)據(jù)格式從鏈表轉(zhuǎn)換成紅黑樹的閾值為8朋腋，即在一個桶中鏈表長度達到8，就會轉(zhuǎn)換成紅黑樹
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
- 一個桶存儲的數(shù)據(jù)格式從紅黑樹還原成鏈表的閾值為6膜楷，即在一個桶中乍丈，一棵紅黑樹存儲的數(shù)據(jù)量小于等于6時，這個桶就會從紅黑樹還原成鏈表把将。
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
- 一個桶從鏈表轉(zhuǎn)換成紅黑樹時，容量的最小值為64忆矛，即當一個桶中的鏈表長度達到8了察蹲，可是這時容量（數(shù)組長度）沒有達到64请垛，此時不會轉(zhuǎn)換成樹，而是進行擴容洽议。且這個值不能小于 4 * TREEIFY_THRESHOLD
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
- 實際存儲元素的數(shù)組桶宗收，大小必須為2的冪次倍
/**
* The table, initialized on first use, and resized as
* necessary. When allocated, length is always a power of two.
* (We also tolerate length zero in some operations to allow
* bootstrapping mechanics that are currently not needed.)
*/
transient Node<K,V>[] table;
- 迭代器對象
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet;
- HashMap元素的個數(shù)
/**
* The number of key-value mappings contained in this map.
*/
transient int size;
- HashMap的修改次數(shù)，如對元素的增刪改亚兄，這個值在使用迭代器時會用到混稽，實現(xiàn)快速失敗策略。
/**
* 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;
- 對數(shù)組桶進行擴容時的閾值(=容量*負載因子)审胚，當HashMap中的size(元素個數(shù))達到這個值時匈勋，就會進行擴容
/**
* The next size value at which to resize (capacity * load factor).
*
* @serial
*/
// (The javadoc description is true upon serialization.
// Additionally, if the table array has not been allocated, this
// field holds the initial array capacity, or zero signifying
// DEFAULT_INITIAL_CAPACITY.)
int threshold;
- 負載因子，當元素個數(shù)和容量的比例超過這個比例膳叨，就會進行擴容洽洁，默認為0.75，負載因子越大菲嘴，HashMap的填充程度就越高饿自，也就是能容納更多的元素，但是索引效率就會降低龄坪，空間復雜度也會降低昭雌；負載因子越小，容納更少的元素健田，越容易擴容烛卧，所以會對空間造成浪費，但是索引效率高抄课，而默認值0.75是對空間和時間的一個平衡值唱星，一般不進行修改，直接使用默認值
/**
* The load factor for the hash table.
*
* @serial
*/
final float loadFactor;
HashMap之構(gòu)造方法
共有四種構(gòu)造方法
- 無參跟磨，只做了一件事情间聊，將負載因子賦值為默認的值
/**
* 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
}
- 傳入容量值（即數(shù)組長度），指定默認的負載因子抵拘，調(diào)用另一個構(gòu)造方法
/**
* 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);
}
- 傳入容量值和負載因子哎榴，進行驗證并將負載因子進行賦值，然后將容量大小值暫時賦給threshold（閾值）僵蛛，這里的threshold并不是真正的閾值尚蝌，在第一次resize時，會重新計算threshold的值充尉，注意：第一次put的時候是一定會resize的飘言，因為數(shù)組table在第一次put時才會被初始化
/**
* 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);
}
上面的 this.threshold = tableSizeFor(initialCapacity) 方法是計算出比initialCapacity大，且最小的2的冪次數(shù)驼侠，如傳入的容量值為22姿鸿，這里會自動計算成32谆吴，因為HashMap的容量大小必須為2的冪次數(shù)，源碼如下
/**
* 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;
}
- 傳入一個Map苛预，將該Map中的key, value都put到當前的HashMap中
/**
* Constructs a new <tt>HashMap</tt> with the same mappings as the
* specified <tt>Map</tt>. The <tt>HashMap</tt> is created with
* default load factor (0.75) and an initial capacity sufficient to
* hold the mappings in the specified <tt>Map</tt>.
*
* @param m the map whose mappings are to be placed in this map
* @throws NullPointerException if the specified map is null
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* Implements Map.putAll and Map constructor
*
* @param m the map
* @param evict false when initially constructing this map, else
* true (relayed to method afterNodeInsertion).
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
threshold = tableSizeFor(t);
}
else if (s > threshold)
resize();
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);
}
}
}
根據(jù)傳入Map的size句狼，計算當前HashMap的容量，遍歷Map將Key一個個put到當前HashMap中热某。
HashMap的put操作
put 方法實際調(diào)用的是putVal 方法腻菇，跟隨源碼一步步解釋：
/**
* 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);
}
/**
* Implements Map.put and related methods
*
* @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) {
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;
}
- 參數(shù)解釋：
- hash： 對key的hashCode值重新計算的hash值
- key： key值
- value： value值
- onlyIfAbsent： 如果是true，則HashMap中已經(jīng)存在這個key昔馋，并且這個key對應的value不為空時筹吐，就不會進行put的覆蓋操作。
- evict： 用于LinkedHashMap中的尾部操作绒极，這里沒有實際意義骏令。
- 如果table（Hash桶數(shù)組）為空，進行擴容垄提，實際上當我們構(gòu)造一個HashMap對象時榔袋，table是沒有初始化的，真正初始化擴容是在第一次put的時候
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
- 當要插入的key所對應Hash桶為空铡俐，則直接新建一個Node放在這個桶里面凰兑。(n - 1) & hash這個操作實際上是hash算法的第三步，取模操作审丘，判斷應該存放在哪一個桶下面
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
- 當要插入的key與計算出的對應的Hash桶的第一個節(jié)點相等吏够，則直接進行賦值，p在這里指向?qū)狧ash桶的第一個節(jié)點的引用滩报，e變量是最終要插入的節(jié)點引用
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
- 如果對應的Hash桶的第一個節(jié)點為TreeNode（紅黑樹節(jié)點類）锅知，表示這個Hash桶是一棵紅黑樹，則以紅黑樹的方法進行添加節(jié)點脓钾，紅黑樹的操作這里不展開
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
- 對鏈表進行遍歷售睹，如果下一個節(jié)點為空，表示到鏈表結(jié)尾了可训，則直接新建一個節(jié)點接到鏈表最后面昌妹，然后去判斷鏈表長度是否達到閾值（8），達到則轉(zhuǎn)換成紅黑樹握截，操作就算完成了飞崖。否則不為空則判斷是否跟當前要插入的節(jié)點相同，如果相同表示這個節(jié)點已經(jīng)存在了谨胞，直接停止循環(huán)固歪，后面會對這個節(jié)點進行覆蓋操作
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;
}
}
- 針對已經(jīng)存在key的情況做處理，e如果有值胯努，則表示找到了一個跟要插入的key相同的節(jié)點昼牛，如果原本節(jié)點的值為空术瓮，或者onlyIfAbsent為false則進行覆蓋操作，并返回原本的值贰健。
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
- 增加HashMap修改次數(shù)，判斷總節(jié)點個數(shù)是否達到閾值（threshold）恬汁，達到進行擴容操作
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
afterNodeInsertion(evict); 和 afterNodeAccess(e); 是空函數(shù)伶椿，它存在主要是為了LinkedHashMap的一些后續(xù)處理工作。
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
流程圖如下：
HashMap之remove
先看下HashMap的remove方法
/**
* Removes the mapping for the specified key from this map if present.
*
* @param key key whose mapping is to be removed from the map
* @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 remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
removeNode 方法根據(jù) key 匹配氓侧，如果匹配成功脊另，則刪除，返回刪除的value值约巷。否則返回null偎痛。而實際上，如果返回null也可以表示為匹配成功独郎，只不過匹配的是 key 為 null value也為null 的Node節(jié)點（HashMap允許key和value為null的踩麦，key為null的hash值是0，所以是放在第一個Hash桶中）氓癌。
其實刪除的過程也包含了查找的過程谓谦，先找出來，然后刪除贪婉，如下是removeNode方法：
/**
* Implements Map.remove and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to match if matchValue, else ignored
* @param matchValue if true only remove if value is equal
* @param movable if false do not move other nodes while removing
* @return the node, or null if none
*/
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))))
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);
}
}
// 找出節(jié)點后執(zhí)行刪除操作
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode) // 以紅黑樹的方式刪除節(jié)點
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
參數(shù)解析：
- hash ：key的hash值
- key ：節(jié)點的key
- value : 節(jié)點的value值
- matchValue : 為true時反粥，需被刪除的節(jié)點的Value值與給定的value一致，才刪除
- movable : 刪除節(jié)點之后是否移動（在刪除紅黑樹節(jié)點時使用）
- 先做判空處理：保證數(shù)組桶不為空疲迂，也元素個數(shù)大于0才顿，且待刪除的節(jié)點所在的hash桶也不為空（(n - 1) & hash 取模計算數(shù)組桶下標）
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
- 判斷首節(jié)點是否是待刪除節(jié)點，node節(jié)點就是需要刪除的節(jié)點引用
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
- 如果是紅黑樹節(jié)點尤蒿，調(diào)用紅黑樹的方式找出這個節(jié)點
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
- 如果是普通節(jié)點郑气，則遍歷鏈表找出這個節(jié)點
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);
}
- 找出節(jié)點后執(zhí)行刪除操作
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); // 以紅黑樹的方式刪除節(jié)點
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount; // 增加修改次數(shù)
--size; // 減少元素個數(shù)
afterNodeRemoval(node); // 提供給LinkedHashMap的后續(xù)操作
return node;
}
總的流程就是 根據(jù)key找出節(jié)點 -> 然后刪除節(jié)點。找出節(jié)點時先常規(guī)性的判空操作优质，順便根據(jù)hash值定位出Hash桶竣贪。先判斷首節(jié)點的key是否匹配，匹配則直接刪除巩螃，然后再遍歷Hash桶中的其他節(jié)點演怎。如果這個Hash桶中的節(jié)點是TreeNode，則以紅黑樹的方式去查找節(jié)點避乏，這個方式實際是調(diào)用了find方法爷耀。如果是普通的Node節(jié)點（單向鏈表），則遍歷鏈表匹配節(jié)點拍皮。找出節(jié)點之后歹叮，就刪除了它跑杭，如果是紅黑樹則使用紅黑樹的方式刪除節(jié)點。afterNodeRemoval方法是空的方法咆耿，在HashMap中沒有意義德谅，在LinkedHashMap中有具體的實現(xiàn)。
HashMap之擴容resize
HashMap的擴容resize方法是HashMap非常重要的一個方法萨螺，當Key的數(shù)量達到閾值的時候窄做，為了保持查詢效率，HashMap會進行擴容慰技，將原本的Hash桶數(shù)量變?yōu)樵镜膬杀锻终担⒃镜腒ey重新計算放在新的Hash桶中。我們先看一下源碼吻商，在一步步解析掏颊。
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
* @return the table
*/
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
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];
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;
}
- 首先看一下這三個條件處理。
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
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
- 第一個if表示有容量艾帐，該map已經(jīng)存在key了乌叶，已經(jīng)不是第一次擴容了。容量和閾值都變?yōu)樵瓉淼膬杀堆诟颍绻^最大值枉昏，就取最大值。
- 接下來兩個條件都表示是第一次擴容揍鸟，第二個 else if 條件表示在調(diào)用構(gòu)造方法創(chuàng)建實例時兄裂，傳了參數(shù)。在構(gòu)造方法篇阳藻，我們講到晰奖，如果傳了參數(shù)，則會把傳進來的initialCapacity（容量）值暫時存放在threshold（閾值）變量中腥泥，實際上值表示的是容量匾南，所以threshold是有值的。這里的操作就是直接把threshold值賦給newCap（新的容量）
- 第三個條件則表示第一次擴容蛔外，且創(chuàng)建HashMap時是沒有傳參數(shù)的蛆楞，在構(gòu)造方法篇中講到，無參的構(gòu)造方法只做了一件事情夹厌，將負載因子賦值為默認的值豹爹，所以threshold（閾值）是沒有值的，所以這里就將容量和閾值都設置成默認的值
- 重新計算threshold（閾值）
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
- 由于數(shù)組是不可變的矛纹，擴容時就需要新建一個新的數(shù)組臂聋，大小為新的容量newCap。接下來的操作就是遍歷將舊數(shù)組里面的數(shù)據(jù)移到新的數(shù)組中
有數(shù)據(jù)的Hash桶總共三種情況
- 第一種：如果Hash桶中只有一個key，則直接賦值到新的Hash桶中
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
其中的 e.hash & (newCap - 1) 為取模操作孩等，重新計算的數(shù)組下標艾君，進行存放
- 第二種：如果Hash桶中是一課紅黑樹，則使用紅黑樹的操作方法
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
split方法如下：
/**
* 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
*/
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
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);
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的數(shù)據(jù)結(jié)構(gòu)中有講到TreeNode的數(shù)據(jù)結(jié)構(gòu)冰垄，我們知道TreeNode是一個紅黑樹的節(jié)點，也是一個雙向鏈表的節(jié)點权她，所以這里就算按順序遍歷這個雙向鏈表播演，將這個鏈表拆分成兩個鏈表，一個低鏈表伴奥，一個高鏈表，起始點就是調(diào)用這個方法的TreeNode節(jié)點翼闽，也就是方法中的this拾徙，從resize方法知道，這個節(jié)點就是這個Hash桶的首節(jié)點感局，也就是紅黑樹中的根節(jié)點尼啡。
接下來判斷低鏈表是否有值，并且判斷低鏈表是否少于UNTREEIFY_THRESHOLD值（紅黑樹轉(zhuǎn)鏈表的閾值询微，值為6）崖瞭，是的話就執(zhí)行紅黑樹轉(zhuǎn)成普通鏈表的方法 tab[index] = loHead.untreeify(map) ，否則的話撑毛，就是不需要將紅黑樹轉(zhuǎn)成普通鏈表书聚，直接將首節(jié)點賦予這個Hash桶科展，然后這時候判斷高鏈表是否有值稿存，如果有值，說明原來的雙向鏈表被拆分了半抱，那么這個時候低鏈表的紅黑樹性質(zhì)被破壞了胯杭，就需要重新進行構(gòu)建紅黑樹的操作 loHead.treeify(tab) 驯杜。同理高鏈表也進行同樣的操作。
上面講的可能有點亂做个，實際上就是如果一個Hash桶原本是一棵紅黑樹（也是雙向鏈表）鸽心，那么在擴容的時候可能會把這個棵樹的節(jié)點分為兩部分，一部分留在原來的Hash桶中居暖，一部分移到往后移動 oldCap 的位置顽频。然后再判斷兩部分的節(jié)點個數(shù)，如果少于6個膝但，就執(zhí)行 untreeify 方法冲九，最后對兩部分的節(jié)點進行重新構(gòu)建紅黑樹的操作 treeify （下面單獨講）方法。
untreeify 方法如下：
/**
* Returns a list of non-TreeNodes replacing those linked from
* this node.
*/
final Node<K,V> untreeify(HashMap<K,V> map) {
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {
Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
這個方法是紅黑樹轉(zhuǎn)普通鏈表的方法，邏輯就是遍歷這個Hash桶的節(jié)點莺奸，將TreeNode全部轉(zhuǎn)為Node即可丑孩，最后返回首節(jié)點。（雖然這個Hash桶是一棵紅黑樹灭贷，但也是雙向鏈表温学，所以操作的時候直接按雙向鏈表的性質(zhì)操作即可）。
replacementNode方法如下：
// For conversion from TreeNodes to plain nodes
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {
return new Node<>(p.hash, p.key, p.value, next);
}
- 第三種：如果Hash桶中存放的是多個key的鏈表形式甚疟，則使用以下方式仗岖。
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;
}
}
這里重點講解鏈表形式下的數(shù)據(jù)轉(zhuǎn)移：
將原本的鏈表拆分成兩條鏈表 e.hash & oldCap 這個結(jié)果為 0 的節(jié)點放在低的鏈表中，為 1 的放在高的鏈表中览妖，在新的數(shù)組中轧拄，低鏈表依然放在原本的位置，高鏈表放在 往后移 oldCap 個位置的地方讽膏。
最重要的一個操作為 ( e.hash & oldCap )檩电， 因為cap（數(shù)組長度）是2的冪次數(shù)，所以cap的二進制只有一位最高位是1府树，例如16（10000）俐末，這一步的操作就是查看節(jié)點的hash值與oldCap為1的那一位相同的位置是1還是0，如果是0則移到新數(shù)組中相同的下標位置奄侠，如果為1則往后移動此次增加的數(shù)組長度的位置卓箫，，垄潮，這個過程也就是 rehash 的過程
舉個栗子：
- 舊數(shù)組長度為16
- 有兩個key的計算出來的hash分別為5和21烹卒，所以他們兩個都存放在數(shù)組下標為5的Hash桶中，形成一個鏈表
- 現(xiàn)在要進行擴容魂挂，新數(shù)組長度為32甫题，然后遍歷這個鏈表，進行 (e.hash & oldCap) 操作涂召，5（00101）坠非，舊數(shù)組長度16（10000），16的二進制為1的位數(shù)是右數(shù)第五位果正，而5的二進制右數(shù)第五位是0炎码，所以5移動到新的數(shù)組中下標為5的Hash桶中。
- 另一個是21（10101）秋泳，和16（10000）進行 & 的結(jié)果是1潦闲，也就是21的二進制右數(shù)第五位是1，所以21在移動到新的數(shù)組中是放在下標為（5+16）的Hash桶中
不好理解的話就理解迫皱，(e.hash & oldCap) 的結(jié)果如果是0歉闰，則下標位置不變辖众，如果是1則下標位置增加oldCap個位置。
這里的代碼設計和敬，是基于數(shù)組長度cap一定是2的冪次數(shù)才成立凹炸，這也是HashMap將數(shù)組長度（容量）設計成2的冪次數(shù)的原因之一
這里的解析是看了源碼和網(wǎng)上的博客之后自己的總結(jié)，不對的地方歡迎探討昼弟。
HashMap的鏈表轉(zhuǎn)紅黑樹 treeify
在HashMap的putVal方法中啤它，有這么一段：
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); // 鏈表轉(zhuǎn)紅黑樹
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
遍歷Hash桶中的元素當鏈表長度大于等于 TREEIFY_THRESHOLD 時，就會進行鏈表轉(zhuǎn)紅黑樹的動作舱痘，至于判斷條件為什么是 binCount >= TREEIFY_THRESHOLD - 1变骡，是因為 binCount沒包含前兩個元素，后面有注釋 -1 for 1st（-1 表示 第一個）芭逝。
再來看下 treeifyBin(tab, hash) 方法：
/**
* Replaces all linked nodes in bin at index for given hash unless
* table is too small, in which case resizes instead.
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null; // 定義首塌碌、尾節(jié)點
do {
TreeNode<K,V> p = replacementTreeNode(e, null); // 將節(jié)點轉(zhuǎn)換成樹節(jié)點
if (tl == null) // 說明還沒有根節(jié)點
hd = p;
else {
p.prev = tl; // 維護雙向鏈表
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
首先判斷數(shù)組長度是否達到了 MIN_TREEIFY_CAPACITY（64），如果沒有的話旬盯，就進行擴容誊爹，而不是結(jié)構(gòu)轉(zhuǎn)換。即當數(shù)組長度沒有達到64的話瓢捉，沒必要進行結(jié)構(gòu)轉(zhuǎn)換，而是進行擴容办成，將元素拆分到不同的Hash桶中
將hash值取模泡态，得到數(shù)組下標，然后遍歷這個Hash桶中的鏈表迂卢，將每個節(jié)點都轉(zhuǎn)換成樹節(jié)點（TreeNode）某弦，如下是 replacementTreeNode 方法
// For treeifyBin
TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
return new TreeNode<>(p.hash, p.key, p.value, next);
}
到目前為止，也只是把Node節(jié)點轉(zhuǎn)換成TreeNode節(jié)點而克，并把單向鏈表變成雙向鏈表靶壮，
hd.treeify(tab) 方法才是將鏈表轉(zhuǎn)成紅黑樹的方法：
/**
* Forms tree of the nodes linked from this node.
* @return root of tree
*/
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 {
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) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
moveRootToFront(tab, root);
}
這是個紅黑樹的構(gòu)建過程，按照查找二叉樹的性質(zhì)员萍，進行插入腾降，然后再進行插入后的平衡操作。具體不詳細講碎绎，請搜索紅黑樹螃壤，雖然有點差異，但總體思路一致筋帖。
我們這里看幾點奸晴，一個是對 dir 的判斷
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);
dir 是 x（待插入節(jié)點）和 p（當前節(jié)點）的比較結(jié)果，如果是 -1 表示 x 比較小日麸，放在 p 的左側(cè)寄啼。否則 x 比較大，放在 p 的右側(cè)。不可能為0（即相等）墩划。
首先根據(jù) key 的 hash 值的大小來判斷涕刚，但是 hash 值有可能會相等（即使是 equals 不相等的情況），如果相等走诞，就要根據(jù)其他方式進行比較副女，如果 key 實現(xiàn)了comparable接口，并且當前樹節(jié)點和鏈表節(jié)點是相同Class的實例蚣旱，那么通過comparable的方式再比較兩者碑幅。如果還是相等，最后再通過tieBreakOrder比較一次塞绿。先看下 kc = comparableClassFor(k) 方法：
/**
* Returns x's Class if it is of the form "class C implements
* Comparable<C>", else null.
*/
static Class<?> comparableClassFor(Object x) {
if (x instanceof Comparable) {
Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks
return c;
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
if (((t = ts[i]) instanceof ParameterizedType) &&
((p = (ParameterizedType)t).getRawType() ==
Comparable.class) &&
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
return c;
}
}
}
return null;
}
comparableClassFor 方法就是判斷傳進來的對象是否實現(xiàn)了 Comparable 接口沟涨，如果實現(xiàn)了，就返回這個對象的 Class 類對象异吻，否則返回null裹赴。
再看 dir = compareComparables(kc, k, pk) 方法：
/**
* Returns k.compareTo(x) if x matches kc (k's screened comparable
* class), else 0.
*/
@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable)k).compareTo(x));
}
調(diào)用這個方法就說明了這個 key 是實現(xiàn)了 Comparable 接口的，然后調(diào)用 compareTo 獲得比較結(jié)果诀浪。
如果比較結(jié)果是0棋返，說明又是相等，那么這時候就使用終極絕招雷猪，調(diào)用 dir = tieBreakOrder(k, pk) 方法睛竣。
/**
* Tie-breaking utility for ordering insertions when equal
* hashCodes and non-comparable. We don't require a total
* order, just a consistent insertion rule to maintain
* equivalence across rebalancings. Tie-breaking further than
* necessary simplifies testing a bit.
*/
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
當 key 的 hash 值無法比較時，并且沒有實現(xiàn) Comparable 接口求摇，這是就調(diào)用 System.identityHashCode(a) 方法 比較大小射沟，且返回值不可能為0。
System.identityHashCode 方法是根據(jù)內(nèi)存地址計算出來的一個數(shù)值与境，默認情況下跟Object的hashCode方法的結(jié)果一致验夯，但是hashCode方法是可以重寫的，而這個方法不會被重寫摔刁，計算出來的結(jié)果一定是跟內(nèi)存地址相關(guān)的挥转。所以用這個計算出來的結(jié)果進行比較，幾乎是不可能會出現(xiàn)相等的情況共屈。
計算出 dir 之后扁位，用查找二叉樹的方式插入，插入之后需要進行平衡操作:
root = balanceInsertion(root, x);
平衡操作不詳細講趁俊，請查閱紅黑樹
把所有的鏈表節(jié)點都遍歷完之后域仇，最終構(gòu)造出來的樹可能經(jīng)歷多次平衡操作，根節(jié)點目前到底是鏈表的哪一個節(jié)點是不確定的寺擂，所以我們需要把紅黑樹的根節(jié)點作為Hash桶的第一個節(jié)點暇务。
moveRootToFront(tab, root);
/**
* 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;
if (root != null && tab != null && (n = tab.length) > 0) {
int index = (n - 1) & root.hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
if (root != first) {
Node<K,V> rn;
tab[index] = root;
TreeNode<K,V> rp = root.prev;
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
assert checkInvariants(root);
}
}
TreeNode既是一個紅黑樹結(jié)構(gòu)泼掠，也是一個雙鏈表結(jié)構(gòu)，這個方法里做的事情垦细，就是保證樹的根節(jié)點一定也要成為鏈表的首節(jié)點择镇。
我們看到在代碼的最后一段：
assert checkInvariants(root);
/**
* Recursive invariant check
*/
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
tb = t.prev, tn = (TreeNode<K,V>)t.next;
if (tb != null && tb.next != t)
return false;
if (tn != null && tn.prev != t)
return false;
if (tp != null && t != tp.left && t != tp.right)
return false;
if (tl != null && (tl.parent != t || tl.hash > t.hash))
return false;
if (tr != null && (tr.parent != t || tr.hash < t.hash))
return false;
if (t.red && tl != null && tl.red && tr != null && tr.red)
return false;
if (tl != null && !checkInvariants(tl))
return false;
if (tr != null && !checkInvariants(tr))
return false;
return true;
}
這一步是防御性編程，用遞歸的方式校驗每一個TreeNode節(jié)點是否滿足紅黑樹和雙向鏈表的特性括改。如果這個方法校驗不通過：可能是因為用戶編程失誤腻豌，破壞了結(jié)構(gòu)（例如：并發(fā)場景下）；也可能是TreeNode的實現(xiàn)有問題（這個是理論上的以防萬一）
至此嘱能，鏈表轉(zhuǎn)紅黑樹的整個過程就已經(jīng)結(jié)束了吝梅。我們可以看出，鏈表轉(zhuǎn)紅黑樹的條件還是比較苛刻的惹骂，Hash 桶數(shù)組長度不能少于64個苏携，否則節(jié)點達到閾值會先考慮擴容，擴容的時候就會重新拆分節(jié)點到新的 Hash 桶中对粪，而且右冻，只有在 hashCode 的實現(xiàn)很糟糕，極端的情況下著拭，才會導致一個Hash桶有超過8個節(jié)點纱扭。
JDK1.8 雖然引入了紅黑樹，但實際情況中還是會很少用到的儡遮，但是紅黑樹是一個非常經(jīng)典優(yōu)秀的數(shù)據(jù)結(jié)構(gòu)跪但，所以學習一下還是非常有必要的
HashMap的hash算法
HashMap是用Hash表來存儲數(shù)據(jù)的，存放數(shù)據(jù)之前第一步要做的就是定位Hash桶峦萎，一個好的hash算法可以減少Hash碰撞，使數(shù)據(jù)更加分散均勻地存儲在Hash桶中忆首，Map的存儲效率就會越高爱榔。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
在調(diào)用真正的putVal方法之前，調(diào)用了hash(key)方法對key進行hash計算糙及。
HashMap的hash算法分為三步详幽，1、獲取key自身的hashCode值浸锨；2唇聘、高位運算；3柱搜、取模運算迟郎。
前兩步在hash方法中，而第三步在putVal中才會計算
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
i = (n - 1) & hash
- key.hashCode()：獲取key自身的hashCode值
- (h = key.hashCode()) ^ (h >>> 16)：將獲取的hashCode值進行高位運算聪蘸，讓高16位也參與運算宪肖，計算出更加分散的hash值表制，具體是將hashCode值向右移16位，再與自身進行異或控乾。
- 計算出來的新的hash值對容量（也就是Hash桶數(shù)組長度）取模么介，最終定位某一個Hash桶，第三步在putVal方法中蜕衡。因為n一定為2的冪次數(shù)壤短，所以 (n - 1) & hash 實際上就是hash對n的取模，而這樣子的操作比 hash%n 快很多慨仿，這也是為什么HashMap要將數(shù)組長度設為2的冪次數(shù)的原因之一久脯。
計算流程如下：
HashMap為何將容量設計為2的冪次數(shù)？
我們知道HashMap的容量大小镶骗，也就是Hash桶的數(shù)量一定要是2的冪次數(shù)桶现，這是一種非常規(guī)的設計。為了能減少沖突的概率鼎姊，一般會選擇素數(shù)骡和，像Hashtable初始化桶的數(shù)量就是11
那這么設計的目的是什么呢？ 主要是為了在取模和擴容時做優(yōu)化
在HashMap構(gòu)造方法中相寇，如果傳入的參數(shù)不為2的冪次數(shù)慰于，HashMap會將其轉(zhuǎn)換為向上取最小的2的冪次數(shù)，如傳入的大小為20唤衫，則HashMap會轉(zhuǎn)換為32婆赠，最終創(chuàng)建了一個Hash桶長度為32的實例。利用了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;
}
上面的位運算可以理解為佳励，將cap的尾部幾位全部置1休里，最后在加1，就可以計算出比cap大的最小冪次數(shù)了赃承。
上面講到妙黍，設計為2的冪次數(shù)主要為了在取模和擴容時做優(yōu)化：
- 在取模時，對于新計算出來的hash值瞧剖，對Hash桶長度n取模拭嫁，可以 hash & (n - 1) ,這種操作比 hash % n 速度快很多，而這種方式的優(yōu)化只有在 n 為2的冪次數(shù)的時候才有效抓于。上面的HashMap的hash算法有講到
- 在擴容時做粤，由于Hash桶是2的冪次數(shù)，在擴容之后捉撮，Hash桶的長度變?yōu)樵瓉淼膬杀杜缕罚敲此械膋ey要么在原來的位置，要么在增加2的冪次數(shù)的位置巾遭，只要將原本的hash值往前看一位堵泽，如果是0修己，就在原位置，如果是1迎罗，就是往后增加2的冪次數(shù)的位置睬愤。上面的擴容resize中有講到
還有其他的，有空再梳理
以上只是簡單梳理了源碼的流程纹安，更多的細節(jié)以及設計的思路還等待探索...
參考：
https://www.cnblogs.com/kangkaii/p/8473793.html
https://www.zhihu.com/question/20733617
等等...
