摘要:上一篇文章已經(jīng)就進(jìn)行了部分說(shuō)明,介紹了其中涉及的常量和變量的含義,有些部分需要結(jié)合方法源碼來(lái)理解,今天這篇文章就繼續(xù)講解并發(fā)前言本文主要介紹中的一些重要方法,結(jié)合上篇文章中的講解部分進(jìn)行更進(jìn)一步的介紹回顧下上篇文章,我們應(yīng)該已經(jīng)知道的整體結(jié)
上一篇文章已經(jīng)就ConcurrentHashMap進(jìn)行了部分說(shuō)明,介紹了其中涉及的常量和變量的含義,有些部分需要結(jié)合方法源碼來(lái)理解,今天這篇文章就繼續(xù)講解并發(fā)ConcurrentHashMap
前言本文主要介紹ConcurrentHashMap中的一些重要方法,結(jié)合上篇文章中的講解部分進(jìn)行更進(jìn)一步的介紹
回顧下上篇文章,我們應(yīng)該已經(jīng)知道ConcurrentHashMap的整體結(jié)構(gòu)和HashMap基本一致,不同的是處理多線程并發(fā)下保證操作的正確性,ConcurrentHashMap通過(guò)CAS和synchronized進(jìn)行并發(fā)控制,當(dāng)然,這種情況下各種處理都會(huì)變的更為復(fù)雜,下面我們就通過(guò)方法來(lái)深入理解ConcurrentHashMap的操作
重要方法在一些方法中展示了各個(gè)變量以及常量的使用,能讓我們更好的理解其中的操作
tabAt/casTabAt/setTabAt下列方法用于讀寫table數(shù)組,使用Unsafe提供的更新獲取volatile變量,CAS更新數(shù)組元素等操作
// 讀取table[i] @SuppressWarnings("unchecked") static finalsizeNode tabAt(Node [] tab, int i) { return (Node )U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE); } // CAS更新table[i] static final boolean casTabAt(Node [] tab, int i, Node c, Node v) { return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v); } // 插入table[i] static final void setTabAt(Node [] tab, int i, Node v) { U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v); }
size方法返回了一個(gè)不精確的值,在多線程環(huán)境下,返回一個(gè)不精確的值,通過(guò)sumCount迭代counterCells統(tǒng)計(jì)sum值。
public int size() { long n = sumCount(); return ((n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n); } final long sumCount() { CounterCell[] as = counterCells; CounterCell a; long sum = baseCount; if (as != null) { for (int i = 0; i < as.length; ++i) { if ((a = as[i]) != null) sum += a.value; } } return sum; }
這里很多人可能會(huì)問(wèn),為什么需要疊加counterCells數(shù)組的值呢?
其實(shí)這和ConcurrentHashMap特點(diǎn)有關(guān),多線程環(huán)境下,同時(shí)插入值,執(zhí)行CAS操作,執(zhí)行成功的更新了baseCount,而執(zhí)行失敗的則將值放入到了counterCells數(shù)組中,可以查閱CounterCell內(nèi)部類源碼,只有一個(gè)long類型變量,每次進(jìn)行插入或者刪除時(shí)調(diào)用addCount通過(guò)CAS操作更新baseCount,失敗時(shí)執(zhí)行fullAddCount方法,初始化counterCells數(shù)組,并將1(相當(dāng)于插入或刪除一個(gè)元素)插入到CounterCell類中,這樣盡可能保證了Map長(zhǎng)度的正確性,這里理解流程即可,不深入,addCount部分有具體操作可查看
@sun.misc.Contended static final class CounterCell { volatile long value; CounterCell(long x) { value = x; } }get
參考HashMap,類似操作流程,需要注意的也就是在eh < 0處,如果是特殊節(jié)點(diǎn),比如TreeBin或者ForwardingNode節(jié)點(diǎn),則調(diào)用其具體類實(shí)現(xiàn)的find方法完成遍歷查詢,內(nèi)部類解釋可以參考我的上一篇文章
計(jì)算hash值
判斷table是否為空,不為空,找到對(duì)應(yīng)hash桶根節(jié)點(diǎn)判斷
非根節(jié)點(diǎn)繼續(xù)遍歷樹(shù)或者鏈表,存在對(duì)應(yīng)值則返回對(duì)應(yīng)值,否則返回null
public V get(Object key) { NodecontainsValue[] tab; Node e, p; int n, eh; K ek; // 計(jì)算key的hash值 int h = spread(key.hashCode()); // table非空并且對(duì)應(yīng)的hash桶根節(jié)點(diǎn)不為空 if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) { // 查找節(jié)點(diǎn)為根節(jié)點(diǎn) if ((eh = e.hash) == h) { if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val; } // 樹(shù)節(jié)點(diǎn)或者擴(kuò)容中(FN節(jié)點(diǎn)) else if (eh < 0) return (p = e.find(h, key)) != null ? p.val : null; // 鏈表遍歷查找 while ((e = e.next) != null) { if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek)))) return e.val; } } return null; } // 參考HashMap的hash方法,不同之處在于和HASH_BITS進(jìn)行了一次與操作,最高位變?yōu)榱?,即為正數(shù),因?yàn)榍耙黄恼乱惨呀?jīng)說(shuō)過(guò)負(fù)數(shù)hash值有特殊意義 static final int spread(int h) { return (h ^ (h >>> 16)) & HASH_BITS; }
這里通過(guò)靜態(tài)內(nèi)部類實(shí)現(xiàn)Traverser來(lái)遍歷數(shù)組,具體的內(nèi)部實(shí)現(xiàn)查看上篇文章里中的內(nèi)部類說(shuō)明,advance相當(dāng)于查找到下一個(gè)非空節(jié)點(diǎn)
public boolean containsValue(Object value) { if (value == null) throw new NullPointerException(); Node[] t; if ((t = table) != null) { Traverser it = new Traverser (t, t.length, 0, t.length); for (Node p; (p = it.advance()) != null; ) { V v; if ((v = p.val) == value || (v != null && value.equals(v))) return true; } } return false; }
遍歷時(shí)遇見(jiàn)特殊節(jié)點(diǎn)的處理上一篇文章中已經(jīng)畫圖說(shuō)明,如下:
putValputVal整體同HashMap的putVal操作,操作流程上基本類似,只是在多線程操作下需要正確的處理插入值操作,同時(shí)如果發(fā)現(xiàn)有線程在進(jìn)行擴(kuò)容操作時(shí),需幫助擴(kuò)容,然后再進(jìn)行插入值的流程操作
final V putVal(K key, V value, boolean onlyIfAbsent) { // 空值判斷 if (key == null || value == null) throw new NullPointerException(); // hash值計(jì)算,保證了hash值為正數(shù) int hash = spread(key.hashCode()); // 當(dāng)前bin中元素的個(gè)數(shù),判斷是否樹(shù)化處理 int binCount = 0; // 無(wú)限循環(huán)直到被正確處理 for (NoderesizeStamp[] tab = table;;) { Node f; int n, i, fh; // 空表進(jìn)行初始化操作 if (tab == null || (n = tab.length) == 0) tab = initTable(); // 計(jì)算出的hash桶位置鏈表頭節(jié)點(diǎn)無(wú)值則通過(guò)CAS插入值 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { if (casTabAt(tab, i, null, new Node (hash, key, value, null))) break; // no lock when adding to empty bin } // 如果hash桶鏈表頭節(jié)點(diǎn)為MOVED狀態(tài),即說(shuō)明有線程在進(jìn)行擴(kuò)容操作,則通過(guò)helpTransfer幫助擴(kuò)容操作 else if ((fh = f.hash) == MOVED) tab = helpTransfer(tab, f); else { V oldVal = null; // hash桶鏈表頭節(jié)點(diǎn)加鎖,在多線程環(huán)境下其他線程不能同時(shí)操作當(dāng)前相同的頭節(jié)點(diǎn)代碼塊 synchronized (f) { if (tabAt(tab, i) == f) { // 正常鏈表插入操作 if (fh >= 0) { binCount = 1; for (Node e = f;; ++binCount) { K ek; // key和hash值相同則進(jìn)行替換 if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node pred = e; // 沒(méi)匹配到則直接插入到鏈表尾部 if ((e = e.next) == null) { pred.next = new Node (hash, key, value, null); break; } } } // 紅黑樹(shù)插入操作 else if (f instanceof TreeBin) { Node p; binCount = 2; if ((p = ((TreeBin )f).putTreeVal(hash, key, value)) != null) { oldVal = p.val; if (!onlyIfAbsent) p.val = value; } } } } if (binCount != 0) { // 達(dá)到樹(shù)化閾值,則可能進(jìn)行樹(shù)化操作 if (binCount >= TREEIFY_THRESHOLD) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } // size+1操作 addCount(1L, binCount); return null; }
前一篇文章在對(duì)sizeCtl說(shuō)明時(shí)在多個(gè)線程幫忙擴(kuò)容時(shí)其值小于0時(shí)做過(guò)一些說(shuō)明,在源碼中涉及到了下面這個(gè)方法,先理解清楚這個(gè)方法比較重要
這里的參數(shù)每次傳入的都是當(dāng)前數(shù)組的長(zhǎng)度,也就是說(shuō)每次這里生成的數(shù)都與當(dāng)時(shí)擴(kuò)容時(shí)的數(shù)組長(zhǎng)度有關(guān),Integer.numberOfLeadingZeros(n),返回二進(jìn)制表示,前面有多少個(gè)連續(xù)的0,RESIZE_STAMP_BITS固定為16,沒(méi)發(fā)現(xiàn)有提供方法來(lái)修改這個(gè)變量,位或運(yùn)算得到一個(gè)值,這個(gè)值表示了與擴(kuò)容時(shí)數(shù)組的長(zhǎng)度相關(guān),這里需記得是左移了(RESIZE_STAMP_BITS - 1),因?yàn)楹筮叴a中我們需要反向操作右移來(lái)重新獲取
這里通過(guò)這個(gè)方法與數(shù)組長(zhǎng)度關(guān)聯(lián),同時(shí)sizeCtl也會(huì)與之關(guān)聯(lián),同時(shí)也記錄當(dāng)前擴(kuò)容中的線程數(shù),故sizeCtl在擴(kuò)容中同時(shí)兼顧了兩種作用,一是判斷是否是在同一個(gè)批次的擴(kuò)容中(都是從16擴(kuò)容到32),同時(shí)判斷當(dāng)前擴(kuò)容中參與的線程數(shù)來(lái)確定是否結(jié)束和初始化操作
/** * Returns the stamp bits for resizing a table of size n. * Must be negative when shifted left by RESIZE_STAMP_SHIFT. */ static final int resizeStamp(int n) { return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1)); }addCount
整體來(lái)看主要進(jìn)行了兩部分內(nèi)容,一是更新baseCount,二是檢查是否進(jìn)行擴(kuò)容操作。其實(shí)這個(gè)方法里還是相當(dāng)復(fù)雜的,涉及到了線程私有的偽隨機(jī)數(shù)生成器ThreadLocalRandom,并發(fā)效率更高的LongAdder,不過(guò)初學(xué)者可以不用研究那么深入,這里不詳細(xì)說(shuō)明,大概了解就好
private final void addCount(long x, int check) { CounterCell[] as; long b, s; // 通過(guò)CAS更新baseCount if ((as = counterCells) != null || !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { // 更新baseCount失敗 CounterCell a; long v; int m; boolean uncontended = true; // 相當(dāng)于每個(gè)線程的probe就是它在CounterCell數(shù)組中的hash code,用來(lái)定位counterCells數(shù)組 if (as == null || (m = as.length - 1) < 0 || (a = as[ThreadLocalRandom.getProbe() & m]) == null || !(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { // 更新cellvalue失敗則執(zhí)行fullAddCount,具體不看了,比較復(fù)雜,不停嘗試更新計(jì)數(shù) // 源碼注釋上也寫了類似LongAdder fullAddCount(x, uncontended); return; } // 執(zhí)行到此說(shuō)明更新計(jì)數(shù)器成功,判斷是否退出,為什么是1其實(shí)還是有點(diǎn)困惑 if (check <= 1) return; s = sumCount(); } // check大于0代表著對(duì)應(yīng)hash桶下的節(jié)點(diǎn)數(shù),檢查是否擴(kuò)容 // 滿足條件幫助擴(kuò)容,不滿足退出 if (check >= 0) { Node[] tab, nt; int n, sc; // 注意,這里條件中3個(gè)變量賦值同時(shí)while判斷 // sc = sizeCtl,tab = table,n = tab.length // 在并發(fā)操作中可能會(huì)出現(xiàn)變量錯(cuò)誤的情況造成擴(kuò)容處理出錯(cuò),通過(guò)resizeStamp保證擴(kuò)容時(shí)版本一致 while (s >= (long)(sc = sizeCtl) && (tab = table) != null && (n = tab.length) < MAXIMUM_CAPACITY) { // resizeStamp根據(jù)n返回一個(gè)擴(kuò)容版本戳,保證唯一性,上邊一個(gè)方法我已經(jīng)說(shuō)明了 int rs = resizeStamp(n); // 說(shuō)明有別的線程在擴(kuò)容 if (sc < 0) { // 判斷是否幫助擴(kuò)容,滿足條件,不幫助擴(kuò)容,這里會(huì)分析下,看下面的分析部分 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0) break; // 幫助擴(kuò)容,線程數(shù)+1 if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) transfer(tab, nt); } // 無(wú)線程幫助擴(kuò)容,當(dāng)前線程嘗試成為第一個(gè)擴(kuò)容的線程 else if (U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)) transfer(tab, null); s = sumCount(); } } }
在上面這段代碼中,不幫助擴(kuò)容的條件中有些地方讓人困惑
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || (nt = nextTable) == null || transferIndex <= 0) break;
(sc >>> RESIZE_STAMP_SHIFT) != rs
首先需要明白上邊整個(gè)擴(kuò)容中的第一個(gè)線程會(huì)通過(guò)U.compareAndSwapInt(this, SIZECTL, sc, (rs << RESIZE_STAMP_SHIFT) + 2)設(shè)置sizeCtl,之后擴(kuò)容線程增加則通過(guò)U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)更新
sc右移RESIZE_STAMP_SHIFT(由于RESIZE_STAMP_BITS不提供修改方法,RESIZE_STAMP_SHIFT也只能取到16),第一個(gè)條件為什么是這個(gè)?需要結(jié)合擴(kuò)容代碼來(lái)看,首個(gè)線程搶到擴(kuò)容任務(wù)時(shí)需先創(chuàng)建nextTable,設(shè)置transferIndex,在執(zhí)行之前需要將sizeCtl更新,即U.compareAndSwapInt(this, SIZECTL, sc,(rs << RESIZE_STAMP_SHIFT) + 2),代碼存在于addCount和tryPresize方法中,sizeCtl在每次擴(kuò)容時(shí)會(huì)更新成(rs << RESIZE_STAMP_SHIFT) + 2。判斷條件里sc無(wú)符號(hào)右移,如果是相同的一次擴(kuò)容過(guò)程,則與rs相等是肯定的,rs是由resizeStamp根據(jù)長(zhǎng)度n計(jì)算得來(lái),其實(shí)最終這里比較的也就是table的長(zhǎng)度,防止多次擴(kuò)容下錯(cuò)誤的幫助了擴(kuò)容
另外在已經(jīng)有線程擴(kuò)容的情況下增加擴(kuò)容線程會(huì)會(huì)更新sizeCtl,U.compareAndSwapInt(this, SIZECTL, sc, sc + 1) 看出在首次更新的基礎(chǔ)上加1即可,擴(kuò)容線程完成自己的任務(wù)同理減1,結(jié)合上邊對(duì)resizeStamp的說(shuō)明應(yīng)該算很清楚了
以上部分也證實(shí)了上篇文章中sizeCtl注釋是不正確的
sc == rs + 1 || sc == rs + MAX_RESIZERS
這個(gè)條件是有問(wèn)題的,sc小于0,rs大于0,兩個(gè)條件一直為false,沒(méi)有true的可能,從這個(gè)條件上看,應(yīng)該是判斷擴(kuò)容完畢和擴(kuò)容線程數(shù)達(dá)到最大時(shí)不能幫助擴(kuò)容。
我們想一下,第一次線程擴(kuò)容時(shí)已經(jīng)將sc更新成(rs << RESIZE_STAMP_SHIFT) + 2,這里判斷的話需要改為sc == ( rs << RESIZE_STAMP_SHIFT ) +1 才對(duì),不能將sc右移,右移將會(huì)導(dǎo)致低16位記錄的線程數(shù)數(shù)據(jù)丟失,最大線程數(shù)判斷同理,應(yīng)改為sc == ( rs << RESIZE_STAMP_SHIFT ) + MAX_RESIZERS
我在Oracle官網(wǎng)bug庫(kù)里看到已經(jīng)提到了這個(gè)問(wèn)題:https://bugs.java.com/bugdata...
(nt = nextTable) == null
此時(shí)狀態(tài)可能表明擴(kuò)容已經(jīng)結(jié)束或者第一個(gè)線程在擴(kuò)容中,不能幫助擴(kuò)容
transferIndex <= 0
transfer任務(wù)已經(jīng)被分配完畢,不能分配任務(wù)給當(dāng)前線程,不能幫助擴(kuò)容,幫助擴(kuò)容部分下面會(huì)說(shuō)到
helpTransfer如果正在進(jìn)行擴(kuò)容操作,則幫助擴(kuò)容
/** * Helps transfer if a resize is in progress. */ final NodetryPresize[] helpTransfer(Node [] tab, Node f) { Node [] nextTab; int sc; // 判斷是否為ForwardingNode并且nextTable是否已經(jīng)被創(chuàng)建 if (tab != null && (f instanceof ForwardingNode) && (nextTab = ((ForwardingNode )f).nextTable) != null) { // 根據(jù)長(zhǎng)度獲取擴(kuò)容戳 int rs = resizeStamp(tab.length); // 再次驗(yàn)證是否正在擴(kuò)容 while (nextTab == nextTable && table == tab && (sc = sizeCtl) < 0) { // 幾個(gè)條件上邊已經(jīng)解釋過(guò)了,滿足不幫助擴(kuò)容 if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 || sc == rs + MAX_RESIZERS || transferIndex <= 0) break; // sizeCtl加1,表示當(dāng)前線程加入擴(kuò)容,多了一個(gè)線程幫忙 if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) { transfer(tab, nextTab); break; } } return nextTab; } return table; }
預(yù)先擴(kuò)容,putAll和treeifyBin中使用到,不滿足table容量時(shí),進(jìn)行一次擴(kuò)容操作
/** * Tries to presize table to accommodate the given number of elements. * * @param size number of elements (doesn"t need to be perfectly accurate) */ private final void tryPresize(int size) { // 判斷長(zhǎng)度是否超過(guò)最大值,超過(guò)則賦值為最大值,正常則通過(guò)tableSizeFor計(jì)算擴(kuò)容后的長(zhǎng)度 int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(size + (size >>> 1) + 1); int sc; // 未初始化或擴(kuò)容完成才能執(zhí)行本次擴(kuò)容操作 while ((sc = sizeCtl) >= 0) { Nodetransfer[] tab = table; int n; // table未初始化 if (tab == null || (n = tab.length) == 0) { n = (sc > c) ? sc : c; // 置為-1表示數(shù)組初始化,前一篇文章已經(jīng)說(shuō)明 if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try { if (table == tab) { @SuppressWarnings("unchecked") Node [] nt = (Node [])new Node,?>[n]; table = nt; sc = n - (n >>> 2); } } finally { // 此時(shí)相當(dāng)于閾值 sizeCtl = sc; } } } // 已經(jīng)初始化,擴(kuò)容長(zhǎng)度小于閾值或者大于最大值,不進(jìn)行擴(kuò)容操作 else if (c <= sc || n >= MAXIMUM_CAPACITY) break; // 再次驗(yàn)證table未改變 else if (tab == table) { int rs = resizeStamp(n); // 同上邊代碼部分,判斷是否幫助擴(kuò)容 if (sc < 0) { Node [] 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)) transfer(tab, null); } } }
table遷移操作,通過(guò)transferIndex來(lái)完成任務(wù)的分配,之前文章變量中也提及了MIN_TRANSFER_STRIDE(最小步長(zhǎng)),對(duì)每個(gè)擴(kuò)容線程申請(qǐng)遷移的hash桶數(shù)量做了限制,每次需要擴(kuò)容線程執(zhí)行完畢已經(jīng)領(lǐng)取完的hash桶遷移任務(wù)才可以繼續(xù)領(lǐng)取任務(wù)幫助遷移,最后一個(gè)遷移線程在遷移完畢后會(huì)進(jìn)行檢查
private final void transfer(Node[] tab, Node [] nextTab) { int n = tab.length, stride; // 設(shè)置步長(zhǎng),即每個(gè)遷移任務(wù)遷移多少個(gè)hash桶,默認(rèn)最小遷移步長(zhǎng)16 // 即每個(gè)擴(kuò)容線程最小遷移16個(gè)hash桶 if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) stride = MIN_TRANSFER_STRIDE; // subdivide range // nextTab未初始化,則進(jìn)行初始化操作,這里不需要CAS,調(diào)用的地方已經(jīng)做了控制,保證只有一個(gè)線程能執(zhí)行 if (nextTab == null) { // initiating try { @SuppressWarnings("unchecked") // 新數(shù)組長(zhǎng)度擴(kuò)容為原有數(shù)組的2倍 Node [] nt = (Node [])new Node,?>[n << 1]; nextTab = nt; } catch (Throwable ex) { // try to cope with OOME // 內(nèi)存溢出時(shí)不能繼續(xù)擴(kuò)容 sizeCtl = Integer.MAX_VALUE; return; } nextTable = nextTab; transferIndex = n; } int nextn = nextTab.length; // 設(shè)置ForwardingNode節(jié)點(diǎn) ForwardingNode fwd = new ForwardingNode (nextTab); // 線程可以繼續(xù)分配遷移任務(wù)的標(biāo)識(shí) boolean advance = true; // 設(shè)置結(jié)束標(biāo)識(shí) boolean finishing = false; // to ensure sweep before committing nextTab // i表示數(shù)組下標(biāo),bound表示遷移任務(wù)的最小下標(biāo) for (int i = 0, bound = 0;;) { Node f; int fh; // advance為false則表明當(dāng)前線程分配的遷移任務(wù)未完成或已經(jīng)擴(kuò)容完畢 while (advance) { int nextIndex, nextBound; // --i 大于等于 bound 則表明本次分配的遷移任務(wù)還未完成,將advance置為false // 表明不能繼續(xù)分配遷移任務(wù) if (--i >= bound || finishing) advance = false; // 設(shè)置nextIndex // 如果小于等于0則表示遷移hash桶已被分配完畢,不用繼續(xù),將advance置為false else if ((nextIndex = transferIndex) <= 0) { i = -1; advance = false; } // 設(shè)置遷移任務(wù)區(qū)間bound到i else if (U.compareAndSwapInt (this, TRANSFERINDEX, nextIndex, nextBound = (nextIndex > stride ? nextIndex - stride : 0))) { bound = nextBound; i = nextIndex - 1; advance = false; } } // 上邊計(jì)算了區(qū)間和任務(wù)狀態(tài) // i < 0 上邊代碼已經(jīng)說(shuō)明,transfer任務(wù)已經(jīng)執(zhí)行完畢,退出 // i >= n 這里n表示的是傳入的tab數(shù)組長(zhǎng)度,而i有可能因?yàn)閠ransferIndex改變而改變 // 比如連續(xù)擴(kuò)容從16擴(kuò)容到32,然后又從32擴(kuò)容到64,此時(shí)這個(gè)條件是可能成立的,這里的i有可能在32到64之間,大于n的32 // 不在一個(gè)擴(kuò)容維度內(nèi),需退出。最后一個(gè)條件沒(méi)看明白是什么情況出現(xiàn)這種狀態(tài) if (i < 0 || i >= n || i + n >= nextn) { int sc; if (finishing) { // 擴(kuò)容遷移完畢設(shè)置table和sizeCtl nextTable = null; table = nextTab; sizeCtl = (n << 1) - (n >>> 1); return; } // 線程數(shù)減1,表明當(dāng)前線程退出 if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) { // 判斷當(dāng)前線程是否為最后一個(gè)擴(kuò)容線程,不是,則退出,條件可以看上邊的說(shuō)明,已經(jīng)講解過(guò) if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) return; // 確定當(dāng)前線程為最后一個(gè)擴(kuò)容線程,則需要進(jìn)行檢查工作 // 檢查所有的舊數(shù)組hash桶是否被正確的遷移 finishing = advance = true; i = n; // recheck before commit } } // i處的hash桶為null則直接放置ForwardingNode節(jié)點(diǎn) else if ((f = tabAt(tab, i)) == null) advance = casTabAt(tab, i, null, fwd); // i處的hash桶為ForwardingNode節(jié)點(diǎn) else if ((fh = f.hash) == MOVED) // 最后的線程執(zhí)行檢查 advance = true; // already processed else { synchronized (f) { // 再次驗(yàn)證hash桶頭節(jié)點(diǎn)為f if (tabAt(tab, i) == f) { // 進(jìn)行遷移任務(wù),類似HashMap,分高位和低位,不明白的可以看我HashMap的文章 Node ln, hn; if (fh >= 0) { // 正常鏈表操作 // runBit表明首節(jié)點(diǎn)的位置,0則表示在低位,非0表示在高位 int runBit = fh & n; Node lastRun = f; // 找到尾部最后一個(gè)高低位不同的節(jié)點(diǎn),之后的節(jié)點(diǎn)不需要進(jìn)行操作,直接進(jìn)行復(fù)用 for (Node p = f.next; p != null; p = p.next) { int b = p.hash & n; if (b != runBit) { runBit = b; lastRun = p; } } // 低位lastRun在下面循環(huán)時(shí)使用 if (runBit == 0) { ln = lastRun; hn = null; } // 高位lastRun在下面循環(huán)時(shí)使用 else { hn = lastRun; ln = null; } // 確定lastRun為了提高效率,復(fù)用原有鏈表 for (Node 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 (ph, pk, pv, ln); // 高位鏈表 else hn = new Node (ph, pk, pv, hn); } // 新數(shù)組上設(shè)置低位鏈表 setTabAt(nextTab, i, ln); // 新數(shù)組上設(shè)置高位鏈表 setTabAt(nextTab, i + n, hn); // 舊數(shù)組i處設(shè)置為ForwardingNode節(jié)點(diǎn) setTabAt(tab, i, fwd); advance = true; } // 紅黑樹(shù)通過(guò)TreeBin操作 else if (f instanceof TreeBin) { TreeBin t = (TreeBin )f; // 同樣劃分為高低位進(jìn)行處理,通過(guò)鏈表來(lái)操作 TreeNode lo = null, loTail = null; TreeNode hi = null, hiTail = null; int lc = 0, hc = 0; for (Node e = t.first; e != null; e = e.next) { int h = e.hash; TreeNode p = new TreeNode (h, e.key, e.val, null, null); // 判斷是低位還是高位然后修改鏈表關(guān)系 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; } } // 同鏈表類似,判斷下是否需轉(zhuǎn)成鏈表,通過(guò)TreeBin將高低位鏈表構(gòu)建成紅黑樹(shù) ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) : (hc != 0) ? new TreeBin (lo) : t; hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) : (lc != 0) ? new TreeBin (hi) : t; setTabAt(nextTab, i, ln); setTabAt(nextTab, i + n, hn); setTabAt(tab, i, fwd); advance = true; } } } } } }
遷移任務(wù)是從數(shù)組尾部向頭部進(jìn)行,這樣做的目的應(yīng)該是與迭代正向操作相反來(lái)減少?zèng)_突,當(dāng)?shù)鷷r(shí)是已經(jīng)遷移好的hash桶,遷移時(shí)是已經(jīng)迭代完畢的hash桶
clear清空操作,比較簡(jiǎn)單
public void clear() { // 刪除節(jié)點(diǎn)數(shù)記錄最后需要更新 long delta = 0L; // negative number of deletions // 數(shù)組下標(biāo) int i = 0; Node總結(jié)[] tab = table; while (tab != null && i < tab.length) { int fh; Node f = tabAt(tab, i); // hash桶首節(jié)點(diǎn)為null表明不需要執(zhí)行 if (f == null) ++i; // 擴(kuò)容中幫助擴(kuò)容然后重新開(kāi)始循環(huán)清空操作 else if ((fh = f.hash) == MOVED) { tab = helpTransfer(tab, f); i = 0; // restart } // 正常鏈表或TreeBin節(jié)點(diǎn) else { synchronized (f) { if (tabAt(tab, i) == f) { Node p = (fh >= 0 ? f : (f instanceof TreeBin) ? ((TreeBin )f).first : null); // 獲取hash桶的節(jié)點(diǎn)數(shù) while (p != null) { --delta; p = p.next; } // 將hash桶置null setTabAt(tab, i++, null); } } } } // 更新數(shù)組長(zhǎng)度 if (delta != 0L) addCount(delta, -1); }
本文緊接上一篇文章講解了ConcurrentHashMap的重要的方法,對(duì)于一些變量和常量結(jié)合方法進(jìn)行了更多的解釋說(shuō)明,本身而言還是比較復(fù)雜,其中部分筆者也不能完全理解,不過(guò)整體的流程有了一個(gè)更清晰的認(rèn)知,重點(diǎn)需要理解的在下面幾點(diǎn):
涉及到Map長(zhǎng)度的計(jì)算:通過(guò)counterCells完成以及通過(guò)addCount進(jìn)行長(zhǎng)度的更新
擴(kuò)容操作:sizeCtl的設(shè)置以及更新和各種情況下對(duì)應(yīng)的含義
遷移操作:遷移步長(zhǎng),線程檢查
節(jié)點(diǎn)類型:幾種節(jié)點(diǎn)類型的不同處理方式
當(dāng)然,有些條件可能比較復(fù)雜,難以理解,只能盡力多看多想,希望對(duì)各位有所幫助
以上內(nèi)容如有問(wèn)題歡迎指出,筆者驗(yàn)證后將及時(shí)修正,謝謝
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://systransis.cn/yun/75191.html
前面已經(jīng)說(shuō)明了HashMap以及紅黑樹(shù)的一些基本知識(shí),對(duì)JDK8的HashMap也有了一定的了解,本篇就開(kāi)始看看并發(fā)包下的ConcurrentHashMap,說(shuō)實(shí)話,還是比較復(fù)雜的,筆者在這里也不會(huì)過(guò)多深入,源碼層次上了解一些主要流程即可,清楚多線程環(huán)境下整個(gè)Map的運(yùn)作過(guò)程就算是很大進(jìn)步了,更細(xì)的底層部分需要時(shí)間和精力來(lái)研究,暫不深入 前言 jdk版本:1.8 JDK7中,ConcurrentH...
摘要:強(qiáng)調(diào)一下,紅黑樹(shù)中的葉子節(jié)點(diǎn)指的都是節(jié)點(diǎn)。故刪除之后紅黑樹(shù)平衡不用調(diào)整。將達(dá)到紅黑樹(shù)平衡。到此關(guān)于紅黑樹(shù)的基礎(chǔ)已經(jīng)介紹完畢,下一章我將就源碼中的進(jìn)行講解說(shuō)明,看一看紅黑樹(shù)是如何在源碼中實(shí)現(xiàn)的。 說(shuō)到HashMap,就一定要說(shuō)到紅黑樹(shù),紅黑樹(shù)作為一種自平衡二叉查找樹(shù),是一種用途較廣的數(shù)據(jù)結(jié)構(gòu),在jdk1.8中使用紅黑樹(shù)提升HashMap的性能,今天就來(lái)說(shuō)一說(shuō)紅黑樹(shù),上一講已經(jīng)給出插入平衡...
摘要:前面已經(jīng)講解集合中的并且也對(duì)其中使用的紅黑樹(shù)結(jié)構(gòu)做了對(duì)應(yīng)的說(shuō)明,這次就來(lái)看下簡(jiǎn)單一些的另一個(gè)集合類,也是日常經(jīng)常使用到的,整體來(lái)說(shuō),算是比較好理解的集合了,一起來(lái)看下前言版本類定義繼承了,實(shí)現(xiàn)了,提供對(duì)數(shù)組隊(duì)列的增刪改查操作實(shí)現(xiàn)接口,提供隨 前面已經(jīng)講解集合中的HashMap并且也對(duì)其中使用的紅黑樹(shù)結(jié)構(gòu)做了對(duì)應(yīng)的說(shuō)明,這次就來(lái)看下簡(jiǎn)單一些的另一個(gè)集合類,也是日常經(jīng)常使用到的ArrayL...
摘要:如果沖突了,同步頭節(jié)點(diǎn),進(jìn)行鏈表操作,如果鏈表長(zhǎng)度達(dá)到,分成紅黑樹(shù)。每次加入一個(gè)線程都會(huì)將的低位加一。擴(kuò)容最大的幫助線程是,這是低位的最大值限制的。線程處理完之后,如果沒(méi)有可選區(qū)間,且任務(wù)沒(méi)有完成,就會(huì)將整個(gè)表檢查一遍,防止遺漏。 前言 每一次總結(jié)都意味著重新開(kāi)始,同時(shí)也是為了更好的開(kāi)始。ConcurrentHashMap 一直是我心中的痛。雖然不敢說(shuō)完全讀懂了,但也看了幾個(gè)重要的方法...
閱讀 2825·2021-11-18 10:02
閱讀 3689·2021-11-15 17:59
閱讀 2315·2021-09-06 15:00
閱讀 3353·2019-08-29 16:58
閱讀 1067·2019-08-26 10:34
閱讀 1587·2019-08-26 10:15
閱讀 1295·2019-08-26 10:11
閱讀 2728·2019-08-23 18:33