首先放上參考的博客
https://blog.csdn.net/v123411739/article/details/78996181
jdk1.8之前 的hashMap 是基于數(shù)組加鏈表的形式的担败，jdk1.8 oracleJdk優(yōu)化了jdk的源碼 采用數(shù)組加鏈表 或者數(shù)組加紅黑樹(shù)的形式 在鏈表上掛的數(shù)據(jù)超過(guò)一定長(zhǎng)度后就會(huì)轉(zhuǎn)為紅黑樹(shù) 坪哄。
我先搬上面博客的一點(diǎn)內(nèi)容：
幾個(gè)點(diǎn)：
先了解以下幾個(gè)點(diǎn)有序，有利于更好的理解HashMap的源碼和閱讀本文。
頭節(jié)點(diǎn)指的是table表上索引位置的節(jié)點(diǎn)比伏，也就是鏈表的頭節(jié)點(diǎn)。
根結(jié)點(diǎn)（root節(jié)點(diǎn)）指的是紅黑樹(shù)最上面的那個(gè)節(jié)點(diǎn)，也就是沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)。
紅黑樹(shù)的根結(jié)點(diǎn)不一定是索引位置的頭結(jié)點(diǎn)灼伤。
轉(zhuǎn)為紅黑樹(shù)節(jié)點(diǎn)后，鏈表的結(jié)構(gòu)還存在哟沫，通過(guò)next屬性維持，紅黑樹(shù)節(jié)點(diǎn)在進(jìn)行操作時(shí)都會(huì)維護(hù)鏈表的結(jié)構(gòu)锌介，并不是轉(zhuǎn)為紅黑樹(shù)節(jié)點(diǎn)嗜诀，鏈表結(jié)構(gòu)就不存在了。
在紅黑樹(shù)上孔祸，葉子節(jié)點(diǎn)也可能有next節(jié)點(diǎn)隆敢，因?yàn)榧t黑樹(shù)的結(jié)構(gòu)跟鏈表的結(jié)構(gòu)是互不影響的，不會(huì)因?yàn)槭侨~子節(jié)點(diǎn)就說(shuō)該節(jié)點(diǎn)已經(jīng)沒(méi)有next節(jié)點(diǎn)崔慧。
源碼中一些變量定義：如果定義了一個(gè)節(jié)點(diǎn)p拂蝎，則pl為p的左節(jié)點(diǎn)，pr為p的右節(jié)點(diǎn)惶室，pp為p的父節(jié)點(diǎn)温自，ph為p的hash值，pk為p的key值皇钞，kc為key的類等等悼泌。源碼中很喜歡在if/for等語(yǔ)句中進(jìn)行賦值并判斷，請(qǐng)注意夹界。
鏈表中移除一個(gè)節(jié)點(diǎn)只需如下圖操作馆里，其他操作同理宰僧。
紅黑樹(shù)在維護(hù)鏈表結(jié)構(gòu)時(shí)晋南，移除一個(gè)節(jié)點(diǎn)只需如下圖操作（紅黑樹(shù)中增加了一個(gè)prev屬性）撵儿，其他操作同理第练。注：此處只是紅黑樹(shù)維護(hù)鏈表結(jié)構(gòu)的操作喘蟆，紅黑樹(shù)還需要單獨(dú)進(jìn)行紅黑樹(shù)的移除或者其他操作戚丸。
源碼中進(jìn)行紅黑樹(shù)的查找時(shí)痴奏，會(huì)反復(fù)用到以下兩條規(guī)則：1）如果目標(biāo)節(jié)點(diǎn)的hash值小于p節(jié)點(diǎn)的hash值冰蘑，則向p節(jié)點(diǎn)的左邊遍歷目锭；否則向p節(jié)點(diǎn)的右邊遍歷卵贱。2）如果目標(biāo)節(jié)點(diǎn)的key值小于p節(jié)點(diǎn)的key值滥沫，則向p節(jié)點(diǎn)的左邊遍歷；否則向p節(jié)點(diǎn)的右邊遍歷键俱。這兩條規(guī)則是利用了紅黑樹(shù)的特性（左節(jié)點(diǎn)<根結(jié)點(diǎn)<右節(jié)點(diǎn)）兰绣。
源碼中進(jìn)行紅黑樹(shù)的查找時(shí)，會(huì)用dir（direction）來(lái)表示向左還是向右查找编振，dir存儲(chǔ)的值是目標(biāo)節(jié)點(diǎn)的hash/key與p節(jié)點(diǎn)的hash/key的比較結(jié)果缀辩。
HashMap的基本數(shù)據(jù)結(jié)構(gòu)
/**
* The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默認(rèn)容量16
/**
* 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; // 最大容量
/**
* The load factor used when none specified in constructor.
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默認(rèn)負(fù)載因子0.75
/**
* 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; // 鏈表節(jié)點(diǎn)轉(zhuǎn)換紅黑樹(shù)節(jié)點(diǎn)的閾值, 9個(gè)節(jié)點(diǎn)轉(zhuǎn)
/**
* 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; // 紅黑樹(shù)節(jié)點(diǎn)轉(zhuǎn)換鏈表節(jié)點(diǎn)的閾值, 6個(gè)節(jié)點(diǎn)轉(zhuǎn)
/**
* 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; // 轉(zhuǎn)紅黑樹(shù)時(shí), table的最小長(zhǎng)度
/* ---------------- Fields -------------- */
/**
* 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; // node數(shù)組 也就是上面的 數(shù)組加鏈表的數(shù)組
/**
* Holds cached entrySet(). Note that AbstractMap fields are used
* for keySet() and values().
*/
transient Set<Map.Entry<K,V>> entrySet; // 內(nèi)部key的set集合
/**
* The number of key-value mappings contained in this map.
*/
transient int size; //map大小
/**
* 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í)
/**
* The next size value at which to resize (capacity * load factor).
* 要調(diào)整大小的下一個(gè)大小值（容量*加載因子）。
* @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;
/**
* The load factor for the hash table.
* 負(fù)載因子
* @serial
*/
final float loadFactor;
/* ---------------- Public operations -------------- */
/**
* 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> { // 基本hash節(jié)點(diǎn), 繼承自Entry
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;
}
}
/**
* 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> {// 紅黑樹(shù)節(jié)點(diǎn)
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);
}
}
定位哈希桶數(shù)組索引位置
不管增加踪央、刪除臀玄、查找鍵值對(duì)，定位到哈希桶數(shù)組的位置都是很關(guān)鍵的第一步畅蹂。前面說(shuō)過(guò)HashMap的數(shù)據(jù)結(jié)構(gòu)是“數(shù)組+鏈表+紅黑樹(shù)”的結(jié)合健无，所以我們當(dāng)然希望這個(gè)HashMap里面的元素位置盡量分布均勻些，盡量使得每個(gè)位置上的元素?cái)?shù)量只有一個(gè)液斜，那么當(dāng)我們用hash算法求得這個(gè)位置的時(shí)候累贤，馬上就可以知道對(duì)應(yīng)位置的元素就是我們要的，不用遍歷鏈表/紅黑樹(shù)少漆，大大優(yōu)化了查詢的效率臼膏。HashMap定位數(shù)組索引位置，直接決定了hash方法的離散性能示损。下面是定位哈希桶數(shù)組的源碼：
// 代碼1
static final int hash(Object key) { // 計(jì)算key的hash值
int h;
// 1.先拿到key的hashCode值; 2.將hashCode的高16位參與運(yùn)算
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 代碼2
int n = tab.length;
// 將(tab.length - 1) 與 hash值進(jìn)行&運(yùn)算
int index = (n - 1) & hash;
整個(gè)過(guò)程本質(zhì)上就是三步：
拿到key的hashCode值
將hashCode的高位參與運(yùn)算渗磅，重新計(jì)算hash值
將計(jì)算出來(lái)的hash值與(table.length - 1)進(jìn)行&運(yùn)算
代碼1 是hashMap的 核心方法，代碼2 和代碼3是 get 和 put 時(shí)定位 當(dāng)前node 的 位置 也就是上面 定義的 Node[] table 的索引值检访。
這位老哥寫的太好 我都不知道能補(bǔ)充啥始鱼。
方法解讀：
對(duì)于任意給定的對(duì)象，只要它的hashCode()返回值相同脆贵，那么計(jì)算得到的hash值總是相同的风响。我們首先想到的就是把hash值對(duì)table長(zhǎng)度取模運(yùn)算，這樣一來(lái)丹禀，元素的分布相對(duì)來(lái)說(shuō)是比較均勻的状勤。
但是模運(yùn)算消耗還是比較大的，我們知道計(jì)算機(jī)比較快的運(yùn)算為位運(yùn)算双泪，因此JDK團(tuán)隊(duì)對(duì)取模運(yùn)算進(jìn)行了優(yōu)化持搜，使用上面代碼2的位與運(yùn)算來(lái)代替模運(yùn)算。這個(gè)方法非常巧妙焙矛，它通過(guò) “(table.length -1) & h” 來(lái)得到該對(duì)象的索引位置葫盼，這個(gè)優(yōu)化是基于以下公式：x mod 2^n = x & (2^n - 1)。我們知道HashMap底層數(shù)組的長(zhǎng)度總是2的n次方村斟，并且取模運(yùn)算為“h mod table.length”贫导，對(duì)應(yīng)上面的公式抛猫，可以得到該運(yùn)算等同于“h & (table.length - 1)”。這是HashMap在速度上的優(yōu)化孩灯，因?yàn)?amp;比%具有更高的效率闺金。
在JDK1.8的實(shí)現(xiàn)中，還優(yōu)化了高位運(yùn)算的算法峰档，將hashCode的高16位與hashCode進(jìn)行異或運(yùn)算败匹，主要是為了在table的length較小的時(shí)候，讓高位也參與運(yùn)算讥巡，并且不會(huì)有太大的開(kāi)銷掀亩。
下圖是一個(gè)簡(jiǎn)單的例子，table長(zhǎng)度為16：
膜拜之情油然而生欢顷！
下面就來(lái)看下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;
// table不為空 && table長(zhǎng)度大于0 && table索引位置(根據(jù)hash值計(jì)算出)不為空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) { // 這里的 tab[(n - 1) & hash] 就是取到 當(dāng)前key在 Node數(shù)組中所在索引的位置
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first; // first的key等于傳入的key則返回first對(duì)象
if ((e = first.next) != null) { // 向下遍歷
if (first instanceof TreeNode) // 判斷是否為TreeNode
// 如果是紅黑樹(shù)節(jié)點(diǎn)槽棍，則調(diào)用紅黑樹(shù)的查找目標(biāo)節(jié)點(diǎn)方法getTreeNode
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 走到這代表節(jié)點(diǎn)為鏈表節(jié)點(diǎn)
do { // 向下遍歷鏈表, 直至找到節(jié)點(diǎn)的key和傳入的key相等時(shí),返回該節(jié)點(diǎn)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null; // 找不到符合的返回空
}
1.先對(duì)table進(jìn)行校驗(yàn)，校驗(yàn)是否為空抬驴，length是否大于0
2.使用table.length - 1和hash值進(jìn)行位與運(yùn)算炼七，得出在table上的索引位置，將該索引位置的節(jié)點(diǎn)賦值給first節(jié)點(diǎn)怎爵，校驗(yàn)該索引位置是否為空
3.檢查first節(jié)點(diǎn)的hash值和key是否和入?yún)⒌囊粯犹厥绻粯觿tfirst即為目標(biāo)節(jié)點(diǎn)盅蝗，直接返回first節(jié)點(diǎn)
4.如果first的next節(jié)點(diǎn)不為空則繼續(xù)遍歷
5.如果first節(jié)點(diǎn)為TreeNode鳖链，則調(diào)用getTreeNode方法（見(jiàn)下文代碼塊1）查找目標(biāo)節(jié)點(diǎn)
6.如果first節(jié)點(diǎn)不為TreeNode，則調(diào)用普通的遍歷鏈表方法查找目標(biāo)節(jié)點(diǎn)
7.如果查找不到目標(biāo)節(jié)點(diǎn)則返回空
第一次看的時(shí)候一臉懵逼墩莫，但是等過(guò)了幾個(gè)月 看過(guò)了很多開(kāi)源框架后芙委，現(xiàn)在再來(lái)看 覺(jué)得也就那樣，所有還是要多看多學(xué)習(xí)狂秦，才能有進(jìn)步灌侣。
這里對(duì)于查鏈表來(lái)說(shuō) 很簡(jiǎn)單，不需要解釋裂问，但是對(duì)于該索引上的Node 是一顆紅黑樹(shù)的情況 來(lái)說(shuō) 就比較復(fù)雜了侧啼。
final TreeNode<K,V> getTreeNode(int h, Object k) {
// 使用根結(jié)點(diǎn)調(diào)用find方法
return ((parent != null) ? root() : this).find(h, k, null);
}
final TreeNode<K,V> root() {
for (TreeNode<K,V> r = this, p;;) {
// 如果一個(gè)節(jié)點(diǎn)的父為空那么他就是 根節(jié)點(diǎn) 上面的for是一個(gè)類似死循環(huán)的東西，只有當(dāng)r為null時(shí)退出 而r又被每次循環(huán)賦值為r.parent
if ((p = r.parent) == null)
return r;
r = p;
}
}
然后就是 find方法了
/**
* 從調(diào)用此方法的結(jié)點(diǎn)開(kāi)始查找, 通過(guò)hash值和key找到對(duì)應(yīng)的節(jié)點(diǎn)
* 此處是紅黑樹(shù)的遍歷, 紅黑樹(shù)是特殊的自平衡二叉查找樹(shù)
* 平衡二叉查找樹(shù)的特點(diǎn)：左節(jié)點(diǎn)<根節(jié)點(diǎn)<右節(jié)點(diǎn)
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this; // this為調(diào)用此方法的節(jié)點(diǎn)
do {
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
if ((ph = p.hash) > h) // 傳入的hash值小于p節(jié)點(diǎn)的hash值, 則往p節(jié)點(diǎn)的左邊遍歷
p = pl; // p賦值為p節(jié)點(diǎn)的左節(jié)點(diǎn)
else if (ph < h) // 傳入的hash值大于p節(jié)點(diǎn)的hash值, 則往p節(jié)點(diǎn)的右邊遍歷
p = pr; // p賦值為p節(jié)點(diǎn)的右節(jié)點(diǎn)
// 傳入的hash值和key值等于p節(jié)點(diǎn)的hash值和key值,則p節(jié)點(diǎn)為目標(biāo)節(jié)點(diǎn),返回p節(jié)點(diǎn)
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if (pl == null) // p節(jié)點(diǎn)的左節(jié)點(diǎn)為空則將向右遍歷
p = pr;
else if (pr == null) // p節(jié)點(diǎn)的右節(jié)點(diǎn)為空則向左遍歷
p = pl;
else if ((kc != null ||
// 如果傳入的key(k)所屬的類實(shí)現(xiàn)了Comparable接口,則將傳入的key跟p節(jié)點(diǎn)的key比較
(kc = comparableClassFor(k)) != null) && // 此行不為空代表k實(shí)現(xiàn)了Comparable
(dir = compareComparables(kc, k, pk)) != 0)//k<pk則dir<0, k>pk則dir>0
p = (dir < 0) ? pl : pr; // k < pk則向左遍歷(p賦值為p的左節(jié)點(diǎn)), 否則向右遍歷
// 代碼走到此處, 代表key所屬類沒(méi)有實(shí)現(xiàn)Comparable, 直接指定向p的右邊遍歷
else if ((q = pr.find(h, k, kc)) != null)
return q;
else// 代碼走到此處代表上一個(gè)向右遍歷（pr.find(h, k, kc)）為空, 因此直接向左遍歷
p = pl;
} while (p != null);
return null;
}
接下來(lái)看 put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// table是否為空或者length等于0, 如果是則調(diào)用resize方法進(jìn)行初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 通過(guò)hash值計(jì)算索引位置, 如果table表該索引位置節(jié)點(diǎn)為空則新增一個(gè)
if ((p = tab[i = (n - 1) & hash]) == null)// 將索引位置的頭節(jié)點(diǎn)賦值給p
tab[i] = newNode(hash, key, value, null);
else { // table表該索引位置不為空
Node<K,V> e; K k;
if (p.hash == hash && // 判斷p節(jié)點(diǎn)的hash值和key值是否跟傳入的hash值和key值相等
((k = p.key) == key || (key != null && key.equals(k))))
e = p; // 如果相等, 則p節(jié)點(diǎn)即為要查找的目標(biāo)節(jié)點(diǎn)堪簿，賦值給e
// 判斷p節(jié)點(diǎn)是否為TreeNode, 如果是則調(diào)用紅黑樹(shù)的putTreeVal方法查找目標(biāo)節(jié)點(diǎn)
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { // 走到這代表p節(jié)點(diǎn)為普通鏈表節(jié)點(diǎn)
for (int binCount = 0; ; ++binCount) { // 遍歷此鏈表, binCount用于統(tǒng)計(jì)節(jié)點(diǎn)數(shù)
if ((e = p.next) == null) { // p.next為空代表不存在目標(biāo)節(jié)點(diǎn)則新增一個(gè)節(jié)點(diǎn)插入鏈表尾部
p.next = newNode(hash, key, value, null);
// 計(jì)算節(jié)點(diǎn)是否超過(guò)8個(gè), 減一是因?yàn)檠h(huán)是從p節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)開(kāi)始的
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);// 如果超過(guò)8個(gè)痊乾，調(diào)用treeifyBin方法將該鏈表轉(zhuǎn)換為紅黑樹(shù)
break;
}
if (e.hash == hash && // e節(jié)點(diǎn)的hash值和key值都與傳入的相等, 則e即為目標(biāo)節(jié)點(diǎn),跳出循環(huán)
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e; // 將p指向下一個(gè)節(jié)點(diǎn)
}
}
// e不為空則代表根據(jù)傳入的hash值和key值查找到了節(jié)點(diǎn),將該節(jié)點(diǎn)的value覆蓋,返回oldValue
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e); // 用于LinkedHashMap
return oldValue;
}
}
++modCount;
if (++size > threshold) // 插入節(jié)點(diǎn)后超過(guò)閾值則進(jìn)行擴(kuò)容
resize();
afterNodeInsertion(evict); // 用于LinkedHashMap
return null;
}
首先來(lái)看resize方法動(dòng)態(tài)擴(kuò)容
final Node<K,V>[] resize() {
// 新建一個(gè) oldTab 指向 table
Node<K,V>[] oldTab = table;
// 獲取舊的 數(shù)組大小和擴(kuò)容閾值
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
// 新建新的 數(shù)組大小和閾值
int newCap, newThr = 0;
// 如果舊的 cap大于0
if (oldCap > 0) {
// 舊的大小已經(jīng)超過(guò) hashMap的最大長(zhǎng)度
if (oldCap >= MAXIMUM_CAPACITY) {
// 閾值視為int最大值
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 如果原來(lái)的oldCap * 2 小于最大值，且原來(lái)的 大小大于等于 16 那么新的 閾值 等于舊閾值 * 2
// 這里如果 oldCap * 2 大于最大值那么 新閾值就不被賦值
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 如果 oldCap == 0 也就是沒(méi)有初始化
// newCap = 原先的閾值
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// oldCap 和 oldThr 都為 0 那么就設(shè)置新的cap 為 default = 16 newThr = 16 * 0.75
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果newThr == 0 也就是 上面 oldCap * 2 超過(guò) 最大長(zhǎng)度限制
if (newThr == 0) {
//定義一個(gè)float
float ft = (float)newCap * loadFactor;
// 如果新的cap或者新的閾值都小于 int最大長(zhǎng)度 那么就能轉(zhuǎn)為int 否則 直接設(shè)置為最大值
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 設(shè)置類的新閾值
threshold = newThr;
// 接下來(lái)就是生成新的table 并且把數(shù)據(jù) 重新塞到新table中
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 如果是第一次初始化 這里的oldTab是null 直接返回新table即可
if (oldTab != null) {
// 進(jìn)到這里說(shuō)明就table 有信息就循環(huán)信息 循環(huán)的是數(shù)組的頭結(jié)點(diǎn)
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 這里e就是頭結(jié)點(diǎn) 并且頭結(jié)點(diǎn)不為null
if ((e = oldTab[j]) != null) {
// 原來(lái)的數(shù)據(jù)沒(méi)有用了 置為null等待gc回收
oldTab[j] = null;
// 如果e沒(méi)有next 說(shuō)明該索引位置只有一個(gè)節(jié)點(diǎn) 直接 算hash桶 塞到新的table的頭結(jié)點(diǎn)
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果節(jié)點(diǎn)是紅黑樹(shù)
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 到這里也就是鏈表不止一個(gè)值 處理該節(jié)點(diǎn)下的鏈表數(shù)據(jù)
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;
/**
* e.hash & oldCap 判斷用來(lái)計(jì)算hash值的高位是否為1椭更。
* 這個(gè)1決定著節(jié)點(diǎn)在新的數(shù)組中的位置哪审，這是因?yàn)閿?shù)組擴(kuò)容即 oldCap << 1 右移了一位
* 舉個(gè)栗子，假設(shè)原數(shù)組容量為 4 （只要是2的冪就行）虑瀑，即： 100
* hash值為 5,(101) 的節(jié)點(diǎn)在原數(shù)組的下標(biāo)為：
* 5 & (4-1)
* = 101
* & 011
* = 001;
* 在 數(shù)組容量為4的情況下 索引位置為 1
* 數(shù)組擴(kuò)容后湿滓，容量為8 (1000), 節(jié)點(diǎn)在新數(shù)組下標(biāo)為 ：
* 5&(8-1)
* = 101
* & 111
* = 101;
* 在 數(shù)組容量為8的情況下 索引位置為 5滴须。
* 我們?cè)賮?lái)看一個(gè)例子:
* hash值為 1,(101) 的節(jié)點(diǎn)在原數(shù)組的下標(biāo)為：
* 1 & (4-1)
* = 001
* & 011
* = 001;
* 在 數(shù)組容量為4的情況下 索引位置為 1
* 數(shù)組擴(kuò)容后，容量為8 (1000), 節(jié)點(diǎn)在新數(shù)組下標(biāo)為 ：
* 1&(8-1)
* = 001
* & 111
* = 001;
* 在 數(shù)組容量為8的情況下 索引位置為 1叽奥。
* 所以在擴(kuò)容后 原鏈表的值 由于高位不同 就要分成兩組 扔水，這時(shí)我們直接拿 2的冪 的容量大小 和 hash &
* 就能得到它在擴(kuò)容2倍后是在原索引位置還是在 原索引位置+ 擴(kuò)容數(shù)位置
* 新的下標(biāo)正好等于 舊的下標(biāo) 001 加上 舊容量 4(100) ,即 101.
* 上面是hash & oldCapacity = 1 的情況
* 當(dāng) hash & oldCapacity = 0 時(shí)自然容易算出新的下標(biāo)和舊的下標(biāo)相等。
*/
// 由以上結(jié)論可知 e.hash & oldCap為1時(shí) 他就要位移到 原索引位置 + 擴(kuò)容數(shù)的位置
// 為 0 時(shí)還在原位
if ((e.hash & oldCap) == 0) {
// 這里操作的是lo 也就是還在原索引位置的Node
// 如果 loTail為null 說(shuō)明 位置為空 也就是第一次進(jìn)來(lái)時(shí)
// 這時(shí) loHead = e = loTail
// 第二次進(jìn)來(lái)時(shí) 走else loHead.next = loTail.next = e
// 然后 loTail = e
// 第三次進(jìn)來(lái)時(shí) 走else loHead.next.next = loTail.next = e
if (loTail == null)
loHead = e;
// 否則 當(dāng)前指向位置的next為e
else
loTail.next = e;
// 當(dāng)前指針下移一位
loTail = e;
}
// 這里同理 只是 操作的是 hi相關(guān)
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
// 沒(méi)有next 以后 newTab[j] = head
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 高位 為1 的 到 新擴(kuò)容的地方去
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
此方法初看前面比較簡(jiǎn)單 但是到后面 賦值 給新 table的時(shí)候就會(huì)非常繞 主要就是 控制新生產(chǎn)的table 維持新的鏈表結(jié)構(gòu)
重點(diǎn)理解 2的冪次長(zhǎng)度 的 hash & oldCap 和 hash & (oldCap -1 ) 的關(guān)系而线、靈活應(yīng)用了 擴(kuò)容兩倍后 高位為1的hash值會(huì)跑到新的鏈表里 也就是[j+oldCap]的索引處铭污。
看完了resize()方法，我們來(lái)看 鏈表轉(zhuǎn)樹(shù)的方法 treeifyBin
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;
// 這里其實(shí)只是構(gòu)建了TreeNode 的節(jié)點(diǎn) 以及 構(gòu)建了一個(gè)雙向的鏈表 還沒(méi)有轉(zhuǎn)換成樹(shù)
do {
// 這里其實(shí)就是簡(jiǎn)單的 new 了一個(gè) TreeNode
TreeNode<K,V> p = replacementTreeNode(e, null);
// 第一次tl是null 就給 hd掛上 p
if (tl == null)
hd = p;
// 不是第一次 循環(huán)
else {
// p的上一個(gè)是pl
p.prev = tl;
// tl的下一個(gè)是p
tl.next = p;
}
// 然后tl = p 游標(biāo)下移 準(zhǔn)備下一次循環(huán)
tl = p;
} while ((e = e.next) != null);
// 如果有值 真正的轉(zhuǎn)為 紅黑樹(shù)才開(kāi)始
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
這里其實(shí)就是給原先的Node節(jié)點(diǎn)綁上 prev屬性和 next屬性膀篮，原先node屬性只有next屬性,這個(gè)方法的邏輯很簡(jiǎn)單嘹狞。最主要的還是看下面的treeify方法
這個(gè)才是真正轉(zhuǎn)樹(shù)的地方
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
// 這里的 this 就是hd
for (TreeNode<K,V> x = this, next; x != null; x = next) {
// 開(kāi)始遍歷 鏈表
next = (TreeNode<K,V>)x.next;
// 清除 left 和 right （這里可能是因?yàn)?tree退化會(huì)鏈表時(shí)沒(méi)有清除left 和 right）
x.left = x.right = null;
// 如果沒(méi)有根節(jié)點(diǎn) 就 設(shè)置當(dāng)前為 根節(jié)點(diǎn)
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
// 從 root 開(kāi)始 找該節(jié)點(diǎn) 應(yīng)該在樹(shù)的 位置
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
// 如果這次循環(huán)的 hash大于 x的hash dir - 1 說(shuō)明要向左找子
if ((ph = p.hash) > h)
dir = -1;
//反之到右邊找
else if (ph < h)
dir = 1;
// hash 值相等 比較key 值
else if ((kc == null && // 如果k沒(méi)有實(shí)現(xiàn)Comparable接口 或者 x節(jié)點(diǎn)的key和p節(jié)點(diǎn)的key相等
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
// 使用定義的一套規(guī)則來(lái)比較x節(jié)點(diǎn)和p節(jié)點(diǎn)的大小，用來(lái)決定向左還是向右查找
dir = tieBreakOrder(k, pk);
//知道了dir 繼續(xù)向下
// 保留當(dāng)前位置
TreeNode<K,V> xp = p;
// 當(dāng)前p 根據(jù)dir 的規(guī)則 變成了 p的左 或者 右 并且這是左或者右為null 時(shí) 說(shuō)明找到了 x的正確位置
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// x的父節(jié)點(diǎn)就是 xp （這里p已經(jīng)變成了 p的左或右 因?yàn)?p.parent 可能為 null 這里給x.parent 賦值）
x.parent = xp;
// 根據(jù)dir 給 xp 幫左子樹(shù)還是右字?jǐn)?shù)
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// 重新構(gòu)建平衡樹(shù) 也就是把x 放到紅黑樹(shù)的正確位置
// 進(jìn)行紅黑樹(shù)的插入平衡(通過(guò)左旋誓竿、右旋和改變節(jié)點(diǎn)顏色來(lái)保證當(dāng)前樹(shù)符合紅黑樹(shù)的要求)
root = balanceInsertion(root, x);
break;
}
}
}
}
// 如果root節(jié)點(diǎn)不在table索引位置的頭結(jié)點(diǎn), 則將其調(diào)整為頭結(jié)點(diǎn)
moveRootToFront(tab, root);
}
上面的步驟中給每一個(gè)TreeNode找到自己合適的位置磅网，也就是balanceInsertion()方法之前的代碼，定位當(dāng)前TreeNode 屬于左子樹(shù)還是右子樹(shù)筷屡。而balanceInsertion才是真正保證樹(shù)是紅黑樹(shù)涧偷。
接下來(lái)balanceInsertion方法
然后是moveRootToFront方法，將root節(jié)點(diǎn)移至頭結(jié)點(diǎn)
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
// hash 桶
int index = (n - 1) & root.hash;
//得到樹(shù)的第一個(gè)節(jié)點(diǎn) 后面 tab[index] 會(huì)被賦值 這里做保留
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
// 如果 root 不等于 first
if (root != first) {
Node<K,V> rn;
// 索引值頭結(jié)點(diǎn)設(shè)置為root
tab[index] = root;
// 維護(hù) 鏈表結(jié)構(gòu)
// 拿到上一個(gè)節(jié)點(diǎn)
TreeNode<K,V> rp = root.prev;
// 這里相當(dāng)于是 rn ->rp rp -> rn 把 root給解放出來(lái) 并且掛在first前面
// 由于原來(lái)first 前就是null 所有不影響毙死，把root移除也不影響原先的鏈表結(jié)構(gòu)
// rn的上一個(gè)是rp
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
// rp的下一個(gè)是rn
if (rp != null)
rp.next = rn;
// first的上一個(gè)是 root
if (first != null)
first.prev = root;
// root的下一個(gè)是 first
root.next = first;
// root的前一個(gè)是null
root.prev = null;
//到這就重新把first加入鏈表
}
assert checkInvariants(root);
}
}
這個(gè)過(guò)程也是很簡(jiǎn)單 就是如果原先頭結(jié)點(diǎn)不是root 就把 原來(lái)的first 轉(zhuǎn)為 root的下一個(gè) 然后把root 放到 頭結(jié)點(diǎn)燎潮。
接下來(lái)我們來(lái)看 putAll方法
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
if (table == null) { // pre-size
// 重新計(jì)算需要的數(shù)組長(zhǎng)度
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
// 如果 大于了閾值 重新計(jì)算 閾值
if (t > threshold)
threshold = tableSizeFor(t);
}
// 如果長(zhǎng)度大于閾值 直接 擴(kuò)容
else if (s > threshold)
resize();
// 其實(shí) 就是putVal
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);
}
}
}
主要的方法就是 putMapEntries 其實(shí)他最終調(diào)用的其實(shí)就是 putVal方法。然后就是一些計(jì)算容量 擴(kuò)容的東西了扼倘。
接下來(lái)我們來(lái)看containsKey方法
// 直接getNode
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
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 &&
// hash桶 拿到頭結(jié)點(diǎn)
(first = tab[(n - 1) & hash]) != null) {
// 如果頭結(jié)點(diǎn)就是 目標(biāo)節(jié)點(diǎn) 直接返回 這里其實(shí)利用了 無(wú)論是Node還是TreeNode 第一個(gè)節(jié)點(diǎn) 都是可以直接判斷的
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果頭結(jié)點(diǎn)不是目標(biāo) 就next
if ((e = first.next) != null) {
// 樹(shù)
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
// 鏈表
do {
// 循環(huán) 直到找到了為止
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
// 這里其實(shí)調(diào)用的TreeNode的getTreeNode的 這個(gè)方法之前已經(jīng)說(shuō)過(guò)了
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
接著講remove方法
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 &&
// 又是hash桶 hash桶真是無(wú)處不在啊
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
//其實(shí)這里就是getNode 的邏輯 找到需要?jiǎng)h除的node
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);
}
}
// 如果找到了node
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
// 如果是tree
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
// 如果是頭結(jié)點(diǎn) 將頭結(jié)點(diǎn)置為 下一個(gè)節(jié)點(diǎn)
else if (node == p)
tab[index] = node.next;
// 不是頭結(jié)點(diǎn) 就 把p的next 指向node的next 這里其實(shí)p就是node的下一個(gè)節(jié)點(diǎn) 因?yàn)樯厦嫜h(huán)找node 的同時(shí) p的指向一直在變
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);
return node;
}
}
return null;
}
就像上面說(shuō)的确封，有從鏈表轉(zhuǎn)為樹(shù)，就有從樹(shù)退化為鏈表removeTreeNode方法是一個(gè)極其復(fù)雜的過(guò)程 我還沒(méi)看明白再菊，這里想說(shuō)一點(diǎn) 之前我猜測(cè)要將left 和 right 置為null的原因就是因?yàn)橥嘶癁閠ree的時(shí)候 我們的 left 和 right 并未被清空爪喘。
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;
}
看上去不是很難理解，接下來(lái)看一下clear 和 containsValue方法
public void clear() {
Node<K,V>[] tab;
// 操作次數(shù)+1
modCount++;
if ((tab = table) != null && size > 0) {
size = 0;
// 循環(huán) 給tab置null 并沒(méi)有直接 tab = new tab[];
for (int i = 0; i < tab.length; ++i)
tab[i] = null;
}
}
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
// 兩重循環(huán) 外層 遍歷tab數(shù)組 內(nèi)層遍歷兩邊 這里并沒(méi)有用到紅黑樹(shù)的特性
// 所以如果 鏈表很長(zhǎng) 會(huì)有性能的損耗纠拔，說(shuō)實(shí)話我之前并不知道hashMap還有這個(gè)方法
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
到這里我們基本的方法就看的差不多了剩下的紅黑樹(shù)的構(gòu)建與維護(hù)以及1.8新增的幾個(gè)函數(shù)式方法 我還沒(méi)看明白秉剑，后續(xù)補(bǔ)充吧。
