一些基礎(chǔ)基礎(chǔ)概念
一些默認(rèn)參數(shù)
初始容量 16
默認(rèn)擴(kuò)展加載因子 0.75 坤学，即表中元素超過0.75就進(jìn)行擴(kuò)容
sizeCtl :
當(dāng)為負(fù)數(shù)時黍氮，-1 表示正在初始化抹腿，-N 表示 N - 1 個線程正在進(jìn)行擴(kuò)容；
當(dāng)為 0 時松却，表示 table 還沒有初始化暴浦；
當(dāng)為其他正數(shù)時溅话，表示初始化或者下一次進(jìn)行擴(kuò)容的大小
當(dāng)轉(zhuǎn)化為紅黑樹的時候，會使用TreeBin包裝 歌焦，此時 TreeBin的 hash 默認(rèn)是-2
為什么鏈表過深使用紅黑樹
- 因?yàn)榧t黑樹解決了二叉樹平衡的問題飞几，在性能和速度之后有了平衡，不像二叉平衡樹那么絕對平衡独撇，也不像二叉查找樹可能會比變成一個鏈表屑墨。
轉(zhuǎn)換為紅黑樹的閾值為什么是8
- 紅黑樹的插入，搜索纷铣，刪除 時間復(fù)雜度為 O(log(n)) 卵史，而且TreeNode的大小是普通的節(jié)點(diǎn)的兩倍，所以不能直接使用用紅黑樹搜立。
- HashMap的作者在注釋中解釋以躯，在隨機(jī)Hash的情況下，節(jié)點(diǎn)的元素分布復(fù)合泊松分布啄踊，根據(jù)作者的計(jì)算忧设，節(jié)點(diǎn)超過8的概率一般非常小，所以根據(jù)概率統(tǒng)計(jì)選擇了8
- 是
退化為列表為什么是6
- 如果設(shè)置為8社痛，那么數(shù)據(jù)結(jié)果可能就會在鏈表和紅黑樹直接反復(fù)轉(zhuǎn)換见转，為了增加一個緩沖的余地，所以設(shè)置為6為退化條件
插入
image.png
擴(kuò)容
擴(kuò)容條件：
- 某條鏈表長度達(dá)到8蒜哀，但數(shù)組長度卻小于64時。
- 元素個數(shù)達(dá)到擴(kuò)容閾值吏砂。
- 調(diào)用 putAll 方法撵儿，但目前容量不足以存放所有元素時。
image.png
下面的不是我注釋的狐血，是別人注釋的
/**
* 數(shù)據(jù)轉(zhuǎn)移和擴(kuò)容.
* 每個調(diào)用tranfer的線程會對當(dāng)前舊table中[transferIndex-stride, transferIndex-1]位置的結(jié)點(diǎn)進(jìn)行遷移
*
* @param tab 舊table數(shù)組
* @param nextTab 新table數(shù)組
*/
private final void transfer(Node<K, V>[] tab, Node<K, V>[] nextTab) {
int n = tab.length, stride;
// stride可理解成“步長”淀歇，即數(shù)據(jù)遷移時，每個線程要負(fù)責(zé)舊table中的多少個桶
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE){
stride = MIN_TRANSFER_STRIDE;
}
if (nextTab == null) { // 首次擴(kuò)容
try {
// 創(chuàng)建新table數(shù)組
Node<K, V>[] nt = (Node<K, V>[]) new Node<?, ?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // 處理內(nèi)存溢出（OOME）的情況
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n; // [transferIndex-stride, transferIndex-1]表示當(dāng)前線程要進(jìn)行數(shù)據(jù)遷移的桶區(qū)間
}
int nextn = nextTab.length;
// ForwardingNode結(jié)點(diǎn)匈织，當(dāng)舊table的某個桶中的所有結(jié)點(diǎn)都遷移完后浪默，用該結(jié)點(diǎn)占據(jù)這個桶
ForwardingNode<K, V> fwd = new ForwardingNode<K, V>(nextTab);
// 標(biāo)識一個桶的遷移工作是否完成，advance == true 表示可以進(jìn)行下一個位置的遷移
boolean advance = true;
// 最后一個數(shù)據(jù)遷移的線程將該值置為true缀匕，并進(jìn)行本輪擴(kuò)容的收尾工作
boolean finishing = false;
// i標(biāo)識桶索引, bound標(biāo)識邊界
for (int i = 0, bound = 0; ; ) {
Node<K, V> f;
int fh;
// 每一次自旋前的預(yù)處理纳决，主要是定位本輪處理的桶區(qū)間
// 正常情況下，預(yù)處理完成后：i == transferIndex-1乡小，bound == transferIndex-stride
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
} else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) { // CASE1：當(dāng)前是處理最后一個tranfer任務(wù)的線程或出現(xiàn)擴(kuò)容沖突
int sc;
if (finishing) { // 所有桶遷移均已完成
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
// 擴(kuò)容線程數(shù)減1,表示當(dāng)前線程已完成自己的transfer任務(wù)
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
// 判斷當(dāng)前線程是否是本輪擴(kuò)容中的最后一個線程阔加，如果不是，則直接退出
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
/**
* 最后一個數(shù)據(jù)遷移線程要重新檢查一次舊table中的所有桶满钟，看是否都被正確遷移到新table了：
* ①正常情況下胜榔，重新檢查時胳喷，舊table的所有桶都應(yīng)該是ForwardingNode;
* ②特殊情況下，比如擴(kuò)容沖突(多個線程申請到了同一個transfer任務(wù))夭织，此時當(dāng)前線程領(lǐng)取的任務(wù)會作廢吭露，那么最后檢查時，
* 還要處理因?yàn)樽鲝U而沒有被遷移的桶尊惰，把它們正確遷移到新table中
*/
i = n; // recheck before commit
}
} else if ((f = tabAt(tab, i)) == null) // CASE2：舊桶本身為null奴饮，不用遷移，直接嘗試放一個ForwardingNode
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED) // CASE3：該舊桶已經(jīng)遷移完成择浊，直接跳過
advance = true;
else { // CASE4：該舊桶未遷移完成戴卜，進(jìn)行數(shù)據(jù)遷移
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K, V> ln, hn;
if (fh >= 0) { // CASE4.1：桶的hash>0，說明是鏈表遷移
/**
* 下面的過程會將舊桶中的鏈表分成兩部分：ln鏈和hn鏈
* 按照節(jié)點(diǎn)hash的高低位進(jìn)行劃分
* ln鏈會插入到新table的槽i中琢岩，hn鏈會插入到新table的槽i+n中
*/
int runBit = fh & n; // 由于n是2的冪次投剥，所以runBit要么是0，要么高位是1
Node<K, V> lastRun = f; // lastRun指向最后一個相鄰runBit不同的結(jié)點(diǎn)
for (Node<K, V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
} else {
hn = lastRun;
ln = null;
}
// 以lastRun所指向的結(jié)點(diǎn)為分界担孔，將鏈表拆成2個子鏈表ln江锨、hn
for (Node<K, V> p = f; p != lastRun; p = p.next) {
int ph = p.hash;
K pk = p.key;
V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K, V>(ph, pk, pv, ln);
else
hn = new Node<K, V>(ph, pk, pv, hn);
}
setTabAt(nextTab, i, ln); // ln鏈表存入新桶的索引i位置
setTabAt(nextTab, i + n, hn); // hn鏈表存入新桶的索引i+n位置
setTabAt(tab, i, fwd); // 設(shè)置ForwardingNode占位
advance = true; // 表示當(dāng)前舊桶的結(jié)點(diǎn)已遷移完畢
}
else if (f instanceof TreeBin) { // CASE4.2：紅黑樹遷移
/**
* 下面的過程會先以鏈表方式遍歷，復(fù)制所有結(jié)點(diǎn)糕篇，然后根據(jù)高低位組裝成兩個鏈表啄育；
* 然后看下是否需要進(jìn)行紅黑樹轉(zhuǎn)換，最后放到新table對應(yīng)的桶中
*/
TreeBin<K, V> t = (TreeBin<K, V>) f;
TreeNode<K, V> lo = null, loTail = null;
TreeNode<K, V> hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node<K, V> e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode<K, V> p = new TreeNode<K, V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
} else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
// 判斷是否需要進(jìn)行 紅黑樹 <-> 鏈表 的轉(zhuǎn)換
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K, V>(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K, V>(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd); // 設(shè)置ForwardingNode占位
advance = true; // 表示當(dāng)前舊桶的結(jié)點(diǎn)已遷移完畢
}
}
}
}
}
}
