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