Java中的CurrentHashMap源碼詳解
更新時間：2023年12月31日 09:00:30 作者：_Romeo
這篇文章主要介紹了Java中的CurrentHashMap源碼詳解,HashMap是數(shù)組+鏈表構(gòu)成的,JDK1.8之后,加入了紅黑樹,HashMap默認(rèn)數(shù)組初始化大小為16,如果瞎設(shè)置數(shù)字,它會自動調(diào)整成2的倍數(shù),需要的朋友可以參考下
紅黑樹定律
（1）每個節(jié)點或者是黑色，或者是紅色。
（2）根節(jié)點是黑色。
（3）每個葉子節(jié)點（NIL）是黑色。 [注意：這里葉子節(jié)點，是指為空(NIL或NULL)的葉子節(jié)點！]
（4）如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的。
（5）從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點。
HashMap的總結(jié)：
- HashMap是數(shù)組+鏈表構(gòu)成的，JDK1.8之后，加入了紅黑樹.
- HashMap默認(rèn)數(shù)組初始化大小為16，如果瞎設(shè)置數(shù)字，它會自動調(diào)整成2的倍數(shù).
- HashMap鏈表在長度為8之后，會自動轉(zhuǎn)換成紅黑樹,數(shù)組擴(kuò)容之后，會打散紅黑樹，重新設(shè)置.
- HashMap擴(kuò)容變化因子是0.75，也就是數(shù)組的3/4被占用之后，開始擴(kuò)容。
在第一次調(diào)用PUT方法之前，HashMap是沒有數(shù)組也沒有鏈表的，在每次put元素之后，開始檢查(生成)數(shù)組和鏈表.
CurrentHashMap代碼(帶注釋)
分析new CurrentHashMap時它在做什么(三個參數(shù)的暫時不討論，大家可以自己去看)
//帶參數(shù)構(gòu)造器 ，不帶參的啥都沒干。
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1)); //這個公式可以轉(zhuǎn)換為sizeCtl = 【 (1.5 * initialCapacity + 1)，然 后向上取最近的 2 的 n 次方】 這樣可以理解
this.sizeCtl = cap; //這個sizeCtl是什么不要著急.
}分析put代碼的過程
public V put(K key, V value) { return putVal(key, value, false); } //put方法里直接去調(diào)用了 putVal()
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException(); //沒有反正異常了
int hash = spread(key.hashCode()); //還是算hashCode
int binCount = 0; //局部變量 ,肯定有說法
for (Node<K,V>[] tab = table;;) { //注意 這里是個循環(huán) 因為后面是CAS操作，會需要大量的重試
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0) //如果沒數(shù)組，創(chuàng)建
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //找到hash值對應(yīng)的數(shù)組下標(biāo)，這里會得到第一個節(jié)點，也就是我們的元素頭
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null))) //如果沒放成功，繼續(xù)向下走，因為這肯定是出現(xiàn)了并發(fā)操作，所以去判斷沒放成功的理由.如果放成功了，那就打斷循環(huán)，結(jié)束了.
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED) //出現(xiàn)了，這個標(biāo)記MOVED,可以去猜，這個東西肯定是擴(kuò)容時要去做的事情
tab = helpTransfer(tab, f); //幫助數(shù)據(jù)遷移
else { //這里就是數(shù)組已經(jīng)有元素了，這時候就該掛鏈表或者掛樹了
V oldVal = null;
synchronized (f) { //獲取頭節(jié)點的監(jiān)視器鎖
if (tabAt(tab, i) == f) {
if (fh >= 0) { //頭節(jié)點的hash值,大于0表示這下面有點東西
binCount = 1; //這個玩意是記錄鏈表的長度的。 ---還是為了轉(zhuǎn)樹
for (Node<K,V> e = f;; ++binCount) { //for循環(huán)，表示遍歷鏈表
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) { //這段代碼不解釋了,覆蓋重復(fù)的key
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) { //到最后了沒重復(fù)的key，就向后面掛
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) { //如果是個樹
Node<K,V> p;
binCount = 2;
//插節(jié)點
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD) //判斷鏈表的長度，然后轉(zhuǎn)樹.
//這里要注意一個地方?。。。?！ --不是說像HashMap那樣轉(zhuǎn)樹就沒事了，這里涉及到一個核心思路，CurrentHashMap做了優(yōu)化，這里如果數(shù)組長度小于64，它會先擴(kuò)容，擴(kuò)容代表什么含義？-- 原來的鏈表會被1分為2 分別散落在不同的節(jié)點上，這還是個數(shù)學(xué)公式，大家自己去證明,擴(kuò)容代碼，后面去說.
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}put的主流程結(jié)束了，當(dāng)然會遺留問題！
初始化方法沒看的，這個初始化和HashMap一樣嗎？
數(shù)組小于64會先擴(kuò)容，從哪里體現(xiàn)的？
擴(kuò)容的時候它是怎么去做的?
helpTransfer(tab, f) 這個方法為何會叫一個help方法？
初始化方法 initTable
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) { //是個空的，循環(huán)吧
if ((sc = sizeCtl) < 0) //注意這個變量sizeCtl 它是小于0的時候 說明了被占用了
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { //這里通過CAS操作去設(shè)置，告訴你，我拿到了鎖了。
try {
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY; //默認(rèn)初始容量16
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];//初始化數(shù)組，長度為16或者初始化提供的長度
table = tab = nt; //賦值給全局變量table，它是可見的
sc = n - (n >>> 2); //這個SC就是之前我們討論的擴(kuò)容閾值-->這個閾值還是 0.75*n
}
} finally {
sizeCtl = sc; //又去改了這個變量sizeCtl了，真的坑.
}
break;
}
}
return tab;
}轉(zhuǎn)紅黑樹方法 ：treeifyBin
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) {
//MIN_TREEIFY_CAPACITY為64
// 雖然進(jìn)入到轉(zhuǎn)樹方法，如果數(shù)組長度小于64，那么先擴(kuò)容
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1); //擴(kuò)容方法后面再說
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) { //確定 頭節(jié)點沒問題開始加鎖，轉(zhuǎn)樹
synchronized (b) {
if (tabAt(tab, index) == b) {
TreeNode<K,V> hd = null, tl = null;
for (Node<K,V> e = b; e != null; e = e.next) { //遍歷鏈表，沒什么說的.生成一棵紅黑樹
TreeNode<K,V> p =
new TreeNode<K,V>(e.hash, e.key, e.val,
null, null);
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
setTabAt(tab, index, new TreeBin<K,V>(hd)); //把數(shù)據(jù)放到紅黑樹中
}
}
}
}
}擴(kuò)容方法: tryPresize (注意，核心重點)
如果說CurrentHashMap的源碼比較巧妙，就在擴(kuò)容和遷移操作.
private final void tryPresize(int size) {
//c:size的1.5倍，在加1，再向上取最近的2的N次方
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
int sc;
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table; int n;
//這個if分支和之前初始化數(shù)組是一樣的，不看了。
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if (table == tab) {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = nt;
sc = n - (n >>> 2); //0.75*n
}
} finally {
sizeCtl = sc; //注意這個sizeCtl 它只有在cas操作后會變成-1，告訴我們有個線程在操作它。
}
}
}
else if (c <= sc || n >= MAXIMUM_CAPACITY) //如果數(shù)組已經(jīng)到達(dá)最大長度了，就直接結(jié)束
break;
else if (tab == table) {
int rs = resizeStamp(n); //這個rs我不能確定干什么，但是影響不大。
if (sc < 0) { //剛開始擴(kuò)容，我們的sc在上面已經(jīng)被賦值了，于是這段代碼不會執(zhí)行.
Node<K,V>[] nt;
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2)) //第一次擴(kuò)容會執(zhí)行這里的邏輯
transfer(tab, null);
}
}
}數(shù)據(jù)遷移：transfer (難點)
//該方法通過全局的transferIndex來控制每個線程的遷移任務(wù)
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
//n為舊tab的長度，stride為步長(就是每個線程遷移的節(jié)點數(shù))
int n = tab.length, stride;
//單核步長為1，多核為（n>>>3）/ NCPU,最小值為16
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
// 新的 table 尚未初始化
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];// 擴(kuò)容 2 倍
nextTab = nt;// 更新
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE; //擴(kuò)容失敗， sizeCtl 使用 int 最大值。
return;
}
//nextTable為全局屬性
nextTable = nextTab;
transferIndex = n;// 更新轉(zhuǎn)移下標(biāo)，就是 老的 tab 的 length
}
int nextn = nextTab.length;// 新 tab 的 length
// 創(chuàng)建一個 fwd 節(jié)點，用于占位。當(dāng)別的線程發(fā)現(xiàn)這個槽位中是 fwd 類型的節(jié)點，則跳過這個節(jié)點
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
// 首次推進(jìn)為 true，如果等于 true，說明需要再次推進(jìn)一個下標(biāo)（i--），反之，如果是 false，那么就不能推進(jìn)下標(biāo)，需要將當(dāng)前的下標(biāo)處理完畢才能繼續(xù)推進(jìn)
boolean advance = true;
// 完成狀態(tài)，如果是 true，就結(jié)束此方法。
boolean finishing = false; // to ensure sweep before committing nextTab
// 死循環(huán),i 表示下標(biāo)，bound 表示當(dāng)前線程可以處理的當(dāng)前桶區(qū)間最小下標(biāo)
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
// 如果當(dāng)前線程可以向后推進(jìn)；這個循環(huán)就是控制 i 遞減。同時，每個線程都會進(jìn)入這里取得自己需要轉(zhuǎn)移的桶的區(qū)間
while (advance) {
int nextIndex, nextBound;
// 對 i 減一，判斷是否大于等于 bound （正常情況下，如果大于 bound 不成立，說明該線程上次領(lǐng)取的任務(wù)已經(jīng)完成了。那么，需要在下面繼續(xù)領(lǐng)取任務(wù)）
// 如果對 i 減一大于等于 bound（還需要繼續(xù)做任務(wù)），或者完成了，修改推進(jìn)狀態(tài)為 false，不能推進(jìn)了。任務(wù)成功后修改推進(jìn)狀態(tài)為 true。
// 通常，第一次進(jìn)入循環(huán)，i-- 這個判斷會無法通過，從而走下面的 nextIndex 賦值操作（獲取最新的轉(zhuǎn)移下標(biāo)）。其余情況都是：如果可以推進(jìn)，將 i 減一，然后修改成不可推進(jìn)。如果 i 對應(yīng)的桶處理成功了，改成可以推進(jìn)。
if (--i >= bound || finishing)
advance = false;// 這里設(shè)置 false，是為了防止在沒有成功處理一個桶的情況下卻進(jìn)行了推進(jìn) 這里的目的是：1. 當(dāng)一個線程進(jìn)入時，會選取最新的轉(zhuǎn)移下標(biāo)。2. 當(dāng)一個線程處理完自己的區(qū)間時，如果還有剩余區(qū)間的沒有別的線程處理。再次獲取區(qū)間。
else if ((nextIndex = transferIndex) <= 0) {
// 如果小于等于0，說明沒有區(qū)間了 ，i 改成 -1，推進(jìn)狀態(tài)變成 false，不再推進(jìn)，表示，擴(kuò)容結(jié)束了，當(dāng)前線程可以退出了
// 這個 -1 會在下面的 if 塊里判斷，從而進(jìn)入完成狀態(tài)判斷
i = -1;
advance = false;// 這里設(shè)置 false，是為了防止在沒有成功處理一個桶的情況下卻進(jìn)行了推進(jìn)
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;// 這個值就是當(dāng)前線程可以處理的最小當(dāng)前區(qū)間最小下標(biāo)
i = nextIndex - 1;// 初次對i 賦值，這個就是當(dāng)前線程可以處理的當(dāng)前區(qū)間的最大下標(biāo)
advance = false;// 這里設(shè)置 false，是為了防止在沒有成功處理一個桶的情況下卻進(jìn)行了推進(jìn)，這樣對導(dǎo)致漏掉某個桶。下面的 if (tabAt(tab, i) == f) 判斷會出現(xiàn)這樣的情況。
}
}
// 如果 i 小于0 （不在 tab 下標(biāo)內(nèi)，按照上面的判斷，領(lǐng)取最后一段區(qū)間的線程擴(kuò)容結(jié)束）
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {// 如果完成了擴(kuò)容
nextTable = null;// 刪除成員變量
table = nextTab;// 更新 table
sizeCtl = (n << 1) - (n >>> 1);// 更新閾值
return;
}
// 嘗試將 sc -1. 表示這個線程結(jié)束幫助擴(kuò)容了，將 sc 的低 16 位減一。
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
// 如果 sc - 2 不等于標(biāo)識符左移 16 位。如果他們相等了，說明沒有線程在幫助他們擴(kuò)容了。也就是說，擴(kuò)容結(jié)束了。
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;// 不相等，說明沒結(jié)束，當(dāng)前線程結(jié)束方法。
finishing = advance = true;// 如果相等，擴(kuò)容結(jié)束了，更新 finising 變量
i = n; // recheck before commit// 再次循環(huán)檢查一下整張表
}
}
// 獲取老 tab i 下標(biāo)位置的變量，如果是 null，就使用 fwd 占位。
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);// 如果成功寫入 fwd 占位，再次推進(jìn)一個下標(biāo)
else if ((fh = f.hash) == MOVED)// 如果不是 null 且 hash 值是 MOVED。
advance = true; // already processed// 說明別的線程已經(jīng)處理過了，再次推進(jìn)一個下標(biāo)
else {// 到這里，說明這個位置有實際值了，且不是占位符。對這個節(jié)點上鎖。為什么上鎖，防止 putVal 的時候向鏈表插入數(shù)據(jù)
synchronized (f) {
// 判斷 i 下標(biāo)處的桶節(jié)點是否和 f 相同
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;// low, height 高位桶，低位桶
if (fh >= 0) {
// 對老長度進(jìn)行與運(yùn)算（第一個操作數(shù)的的第n位于第二個操作數(shù)的第n位如果都是1，那么結(jié)果的第n為也為1，否則0）
// 由于 Map 的長度都是 2 的次方（000001000 這類的數(shù)字），那么取于 length 只有 2 種結(jié)果，一種是 0，一種是1
// 如果是結(jié)果是0 ，Doug Lea 將其放在低位，反之放在高位，目的是將鏈表重新 hash，放到對應(yīng)的位置上，讓新的取于算法能夠擊中他。
int runBit = fh & n;
Node<K,V> lastRun = f; // 尾節(jié)點，且和頭節(jié)點的 hash 值取于不相等
// 遍歷這個桶 接下來是常規(guī)的設(shè)置操作，我們先略過
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;
}
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);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
else if (f instanceof TreeBin) {
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;
}
}
// 如果樹的節(jié)點數(shù)小于等于 6，那么轉(zhuǎn)成鏈表，反之，創(chuàng)建一個新的樹
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);
// 舊的設(shè)置成占位符
setTabAt(tab, i, fwd);
// 繼續(xù)向后推進(jìn)
advance = true;
}
}
}
}
}
}到此這篇關(guān)于Java中的CurrentHashMap源碼詳解的文章就介紹到這了,更多相關(guān)CurrentHashMap源碼內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了關(guān)于文件合并與修改md5值的問題,使用本博客的方法，不僅僅可以修改md5值，還可以達(dá)到隱藏文件的目的,需要的朋友可以參考下2023-04-04
這篇文章主要介紹了mybatis動態(tài)sql之新增與更新方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-07-07
mybatis插入數(shù)據(jù)后如何返回新增數(shù)據(jù)的id值
當(dāng)往mysql數(shù)據(jù)庫插入一條數(shù)據(jù)時,有時候需要知道剛插入的信息,下面這篇文章主要給大家介紹了關(guān)于mybatis插入數(shù)據(jù)后如何返回新增數(shù)據(jù)id值的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-06-06
這篇文章主要介紹了java 基本算法之歸并排序?qū)嵗a的相關(guān)資料,需要的朋友可以參考下2017-05-05
這篇文章主要介紹了MyBatis-Plus之邏輯刪除的實現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-11-11
這篇文章主要介紹了Spring中的事件發(fā)布機(jī)制原理解析,當(dāng)我們關(guān)心spring容器什么時候刷新，或者想在spring容器刷新的時候做一些事情,監(jiān)聽關(guān)心的事件，主要就是在ApplicationListener中寫對應(yīng)的事件,需要的朋友可以參考下2023-11-11
本文主要介紹了springboot接入mq的方法示例,主要實現(xiàn)配置以及實現(xiàn)一個簡單的發(fā)送、接收消息的例子,具有一定的參考價值,感興趣的可以了解一下2023-09-09
解決在IDEA中創(chuàng)建多級package的問題
這篇文章主要介紹了解決在IDEA中創(chuàng)建多級package的問題，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-02-02
SpringBoot獲取http數(shù)據(jù)、打印HTTP參數(shù)的4種方式
Java的話本地打斷點可以調(diào)試獲取rest入?yún)?但是在生產(chǎn)環(huán)境可能我們獲取入?yún)ⅲ℉ttp?header/parameter）可能就沒有那么的輕松了,所以本文給大家介紹了SpringBoot獲取http數(shù)據(jù)、打印HTTP參數(shù)的4種方式,需要的朋友可以參考下2024-03-03
SpringBoot使用Spring-Data-Jpa實現(xiàn)CRUD操作
這篇文章主要為大家詳細(xì)介紹了SpringBoot使用Spring-Data-Jpa實現(xiàn)CRUD操作，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-08-08