前面已經說明了HashMap以及紅黑樹的一些基本知識,對JDK8的HashMap也有了一定的了解,本篇就開始看看并發包下的ConcurrentHashMap,說實話,還是比較復雜的,筆者在這里也不會過多深入,源碼層次上了解一些主要流程即可,清楚多線程環境下整個Map的運作過程就算是很大進步了,更細的底層部分需要時間和精力來研究,暫不深入
前言jdk版本:1.8
JDK7中,ConcurrentHashMap把內部細分成了若干個小的HashMap,稱之為段(Segment),默認被分為16個段。多線程寫操作對每個段進行加鎖,段與段之間互不影響。而JDK8則拋棄了這種結構,類似HashMap,多線程下為了保證線程安全,通過CAS和synchronized進行并發控制,降低鎖顆粒度,性能上也就提高許多
同時由于降低鎖粒度,同時需要兼顧讀操作的正確性,增加了許多內部類來幫助完成并發控制,保證讀操作的正確執行,同時支持了并發擴容操作,算是相當復雜了,由于過于復雜,對ConcurrentHashMap的說明將分為兩章說明,本章就對ConcurrentHashMap的常量,變量,內部類和構造方法進行說明,下一章將重點分析其中的重要方法
這里先提前說明下,有個整體印象:
ConcurrentHashMap結構上類似HashMap,即數組+鏈表+紅黑樹
鎖顆粒度降低,復雜度提升
多線程并發擴容
多線程下保證讀操作正確性
計數方式處理:分段處理
函數式編程(不是本文重點,自行查閱)
類定義public class ConcurrentHashMapextends AbstractMap implements ConcurrentMap , Serializable
繼承AbstractMap,實現了ConcurrentMap接口,ConcurrentMap也可以看看源碼,加入了并發操作方法,是一個實現了并發訪問的集合接口
常量有些常量和變量可能不是很好理解,在后邊到方法時會盡量詳細說明
/** * 最大容量 */ private static final int MAXIMUM_CAPACITY = 1 << 30; /** * 默認初始化容量,同HashMap,必須為2的倍數 */ private static final int DEFAULT_CAPACITY = 16; /** * 可能達到的最大的數組大小值(非2的次冪),2的31次方-8 */ static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * 默認并發級別,新版本無用,為了兼容舊版本,使用的地方在序列化方法writeObject中 */ private static final int DEFAULT_CONCURRENCY_LEVEL = 16; /** * 負載因子,只是為了兼容性 * 構造方法里指定的負載因子只會影響初始化的table容量 * 一般也不使用浮點數計算 * ConcurrentHashMap不會使用這個常量,而使用類似 n -(n >>> 2) 的方式來進行調整大小 */ private static final float LOAD_FACTOR = 0.75f; /** * 樹化閾值 * 同HashMap */ static final int TREEIFY_THRESHOLD = 8; /** * 調整大小時樹轉化為鏈表的閾值 */ static final int UNTREEIFY_THRESHOLD = 6; /** * 可以轉化為紅黑樹的最小數組容量,即調整為紅黑樹時數組長度最小值必須為MIN_TREEIFY_CAPACITY * 如果bin包含太多節點,則會調整表的大小 * 該值應至少為4 * TREEIFY_THRESHOLD,避免擴容和樹化閾值之間的沖突。 */ static final int MIN_TREEIFY_CAPACITY = 64; /** * * 擴容的每個線程每次最少要遷移16個hash桶 * 每個線程都可參與遷移任務,每個線程至少要連續遷移MIN_TRANSFER_STRIDE個hash桶 * 幫助擴容提高了效率,當然復雜性也提高了很多,要處理的事情更多 */ private static final int MIN_TRANSFER_STRIDE = 16; /** * 與移位量和最大線程數相關 * 先了解就好,后邊涉及到方法會進行說明 */ private static int RESIZE_STAMP_BITS = 16; /** * 幫助擴容的最大線程數 */ private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1; /** * 移位量 */ private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS; /** * Node hash值編碼,規定了各自的含義 */ // forwarding nodes節點hash值 // 臨時節點,擴容時出現,不存儲實際數據 // 如果舊數組的一個hash桶中全部的節點都遷移到新數組中,舊數組就在這個hash桶中放置一個ForwardingNode // 讀操作遇見該節點時,轉到新的table數組上執行,寫操作遇見時,則幫助擴容 static final int MOVED = -1; // hash for forwarding nodes // TREEBIN節點 // TreeBin是ConcurrentHashMap中用于代理操作TreeNode的特殊節點 // 保存實際的紅黑樹根節點,在紅黑樹插入節點時會對讀操作造成影響,該對象維護了一個讀寫鎖來保證多線程的正確性 static final int TREEBIN = -2; // hash for roots of trees // ReservationNode節點hash值 // 保留節點,JDK8的新特性會用到,這里不過多說明 static final int RESERVED = -3; // hash for transient reservations // 負數轉正數,定位hash桶時用到了,負數Hash值有特殊含義,具體看后邊 static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash // CPU數量,限制邊界,計算一個線程需要做多少遷移量 static final int NCPU = Runtime.getRuntime().availableProcessors(); // 序列化兼容性 private static final ObjectStreamField[] serialPersistentFields = { new ObjectStreamField("segments", Segment[].class), new ObjectStreamField("segmentMask", Integer.TYPE), new ObjectStreamField("segmentShift", Integer.TYPE) };變量
/** * The array of bins. Lazily initialized upon first insertion. * Size is always a power of two. Accessed directly by iterators. * * volatile保證可見性 * Node類和HashMap中的類似,val和next屬性通過volatile保證可見性 */ transient volatile Node[] table; /** * The next table to use; non-null only while resizing. * * 擴容時使用的數組,只在擴容時非空,擴容時會創建 */ private transient volatile Node [] nextTable; /** * Table initialization and resizing control. When negative, the * table is being initialized or resized: -1 for initialization, * else -(1 + the number of active resizing threads). Otherwise, * when table is null, holds the initial table size to use upon * creation, or 0 for default. After initialization, holds the * next element count value upon which to resize the table. * * sizeCtl = -1,表示有線程在進行初始化操作 * sizeCtl < 0且不為-1表示有多個線程正在進行擴容操作,jdk源碼解釋部分感覺有點問題 * 每次第一個線程參與擴容時,會將sizeCtl設置為一個與當前table長度相關的數值,避免出現問題,講解方法時進行說明 * sizeCtl > 0,表示第一次初始化操作中使用的容量,或者初始化/擴容完成后的閾值 * sizeCtl = 0,默認值,此時在真正的初始化操作中使用默認容量 */ private transient volatile int sizeCtl; /** * 多線程幫助擴容相關 * 下一個transfer任務的起始下標index + 1 的值 * transfer時下標index從length - 1到0遞減 * 擴容index從后往前和迭代從前往后為了避免沖突 */ private transient volatile int transferIndex; /** * Base counter value, used mainly when there is no contention, * but also as a fallback during table initialization * races. Updated via CAS. * * 計數器基礎值,記錄元素個數,通過CAS操作進行更新 */ private transient volatile long baseCount; /** * Spinlock (locked via CAS) used when resizing and/or creating CounterCells. * * CAS自旋鎖標志位,counterCells擴容或初始化時使用 */ private transient volatile int cellsBusy; /** * Table of counter cells. When non-null, size is a power of 2. * * 高并發下計數數組,counterCells數組非空時大小是2的n次冪 */ private transient volatile CounterCell[] counterCells; // views private transient KeySetView keySet; private transient ValuesView values; private transient EntrySetView entrySet;
同時需要注意靜態代碼塊中已經獲取了一些變量在對象中的內存偏移量,這個是為了方便我們在CAS中的使用,如果不明白CAS,請自行查閱資料學習,源碼如下:
// Unsafe mechanics private static final sun.misc.Unsafe U; private static final long SIZECTL; private static final long TRANSFERINDEX; private static final long BASECOUNT; private static final long CELLSBUSY; private static final long CELLVALUE; private static final long ABASE; private static final int ASHIFT; static { try { U = sun.misc.Unsafe.getUnsafe(); Class> k = ConcurrentHashMap.class; // 獲取sizeCtl在對象中的內存偏移量,下同 SIZECTL = U.objectFieldOffset (k.getDeclaredField("sizeCtl")); TRANSFERINDEX = U.objectFieldOffset (k.getDeclaredField("transferIndex")); BASECOUNT = U.objectFieldOffset (k.getDeclaredField("baseCount")); CELLSBUSY = U.objectFieldOffset (k.getDeclaredField("cellsBusy")); Class> ck = CounterCell.class; CELLVALUE = U.objectFieldOffset (ck.getDeclaredField("value")); Class> ak = Node[].class; ABASE = U.arrayBaseOffset(ak); int scale = U.arrayIndexScale(ak); if ((scale & (scale - 1)) != 0) throw new Error("data type scale not a power of two"); ASHIFT = 31 - Integer.numberOfLeadingZeros(scale); } catch (Exception e) { throw new Error(e); } }內部類
ConcurrentHashMap中增加了許多內部類來幫助完成并發下的操作
Node普通Entry,與HashMap.Node類似,不同主要在于val和next屬性設置為了volatile,同時不支持setValue方法,直接拋錯,增加了find方法
TreeNode繼承自Node節點,與HashMap.TreeNode類似,之前文章專門介紹過這個內部類,可以去看看,同時需要說明的是,在ConcurrentHashMap中并不是直接操作TreeNode節點,而是通過TreeBin來代理操作的
TreeBin代理操作TreeNode節點,保存紅黑樹的根節點,Hash值固定為-2,構造方法里傳入對應的節點創建一棵紅黑樹。故在數組中保存的hash桶為紅黑樹結構時,在數組上的節點類型為TreeBin,該節點類自帶讀寫鎖
static final class TreeBinTraverserextends Node { // 保存樹的根節點 TreeNode root; // 鏈表頭節點 volatile TreeNode first; // 最近一次waiter狀態的線程 volatile Thread waiter; // 鎖狀態 volatile int lockState; // values for lockState // 寫鎖,二進制001 static final int WRITER = 1; // set while holding write lock // 等待獲取寫鎖的狀態,二進制010 static final int WAITER = 2; // set when waiting for write lock // 讀鎖狀態,二進制100 static final int READER = 4; // increment value for setting read lock /** * 紅黑樹結構重構時需要獲取寫鎖 */ private final void lockRoot() { // CAS嘗試獲取寫鎖 if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER)) // 當線程獲取到寫鎖時,才會返回 contendedLock(); // offload to separate method } /** * 釋放寫鎖 */ private final void unlockRoot() { lockState = 0; } /** * 寫線程不斷嘗試獲取寫鎖,出現的幾種情況的處理,這里不會有寫線程和寫線程競爭的情況出現 * 在寫線程進入這個方法時,這個紅黑樹對應的桶已經被外部鎖住,不會讓寫線程進入,故不需要考慮寫寫競爭的情況 * 故當前線程為寫線程,則判斷讀線程即可 */ private final void contendedLock() { boolean waiting = false; for (int s;;) { // 取反與操作,其他線程未持有讀鎖 if (((s = lockState) & ~WAITER) == 0) { // CAS嘗試修改狀態為寫鎖狀態 if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) { // 當前線程曾經處于waiting狀態,將其清除 if (waiting) waiter = null; return; } } // 有讀線程 else if ((s & WAITER) == 0) { // 當前線程置為wait狀態,waiter記錄線程 if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) { waiting = true; waiter = Thread.currentThread(); } } // 當前線程處于waiting狀態 else if (waiting) // 阻塞線程 LockSupport.park(this); } } /** * 從根節點開始進行遍歷,查找到對應匹配的節點 * 同時需要注意多線程環境下如果有寫鎖則通過鏈表結構(不是用紅黑樹結構查詢)進行查詢 */ final Node find(int h, Object k) { if (k != null) { // 從first開始 for (Node e = first; e != null; ) { int s; K ek; // 1.有寫線程操作,通過鏈表查詢不進行阻塞 // 2.WAITER狀態 if (((s = lockState) & (WAITER|WRITER)) != 0) { if (e.hash == h && ((ek = e.key) == k || (ek != null && k.equals(ek)))) return e; e = e.next; } // 讀線程累加 else if (U.compareAndSwapInt(this, LOCKSTATE, s, s + READER)) { TreeNode r, p; try { p = ((r = root) == null ? null : r.findTreeNode(h, k, null)); } finally { Thread w; // 當線程為最后一個讀線程并且有寫鎖被阻塞,此時應該通知阻塞的寫線程重新嘗試獲得寫鎖 // getAndAddInt更新之后返回舊值 if (U.getAndAddInt(this, LOCKSTATE, -READER) == (READER|WAITER) && (w = waiter) != null) // 喚醒阻塞的線程 LockSupport.unpark(w); } return p; } } } return null; } /** * 大部分與HashMap.TreeNode中的putTreeVal操作類似 * 這里只說下不同的部分 * 多線程環境下主要是在平衡時加鎖操作,防止讀線程操作時樹結構在變化 */ final TreeNode putTreeVal(int h, K k, V v) { ...... TreeNode xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { TreeNode x, f = first; first = x = new TreeNode (h, k, v, f, xp); if (f != null) f.prev = x; if (dir <= 0) xp.left = x; else xp.right = x; // 新添加節點父節點為黑色,添加節點置為紅色即可保證平衡 if (!xp.red) x.red = true; else { //在進行插入平衡操作時會對讀線程造成影響,需要加鎖,讓讀線程以鏈表方式進行查詢操作 lockRoot(); try { root = balanceInsertion(root, x); } finally { unlockRoot(); } } break; } } assert checkInvariants(root); return null; } /** * 刪除時修改鏈表關系和刪除平衡操作時需要添加鎖,防止讀線程讀取錯誤 * 代碼操作參考HashMap.TreeNode,這里不再詳細說明了 */ final boolean removeTreeNode(TreeNode p) { ...... lockRoot(); try { TreeNode replacement; TreeNode pl = p.left; TreeNode pr = p.right; if (pl != null && pr != null) { TreeNode s = pr, sl; while ((sl = s.left) != null) // find successor s = sl; boolean c = s.red; s.red = p.red; p.red = c; // swap colors TreeNode sr = s.right; TreeNode pp = p.parent; if (s == pr) { // p was s"s direct parent p.parent = s; s.right = p; } else { TreeNode sp = s.parent; if ((p.parent = sp) != null) { if (s == sp.left) sp.left = p; else sp.right = p; } if ((s.right = pr) != null) pr.parent = s; } p.left = null; if ((p.right = sr) != null) sr.parent = p; if ((s.left = pl) != null) pl.parent = s; if ((s.parent = pp) == null) r = s; else if (p == pp.left) pp.left = s; else pp.right = s; if (sr != null) replacement = sr; else replacement = p; } else if (pl != null) replacement = pl; else if (pr != null) replacement = pr; else replacement = p; if (replacement != p) { TreeNode pp = replacement.parent = p.parent; if (pp == null) r = replacement; else if (p == pp.left) pp.left = replacement; else pp.right = replacement; p.left = p.right = p.parent = null; } root = (p.red) ? r : balanceDeletion(r, replacement); if (p == replacement) { // detach pointers TreeNode pp; if ((pp = p.parent) != null) { if (p == pp.left) pp.left = null; else if (p == pp.right) pp.right = null; p.parent = null; } } } finally { unlockRoot(); } assert checkInvariants(root); return false; }
首先需要明白的是在并發下遍歷讀操作和擴容操作同時進行時,讀操作有可能不會正確的進行,而為了解決這個問題,引入了Traverser這個內部類來完成并發操作下的讀操作。在涉及到讀取所有hash桶時,比如containsValue操作,不能使用HashMap的方式進行,一個一個hash桶遍歷進行讀取,此時擴容時,ConcurrentHashMap會在轉移完一個hash桶后將一個ForwardingNode節點填入,如果還是非并發遍歷,導致這個hash桶將不會被遍歷到,正確的處理方式也就是遇到ForwardingNode節點時將當前數組信息和索引保存,然后在ForwardingNode節點的nextTable數組(也就是擴容后的數組)上進行遍歷。這里還使用了棧結構TableStack,是為了處理多個ForwardingNode節點遍歷的情況,同時需要注意的是,參考HashMap,在nextTable上需要遍歷舊的hash桶和新的對應的擴容hash桶(index+size)
static class Traverser{ // 當前table Node [] tab; // current table; updated if resized // 下一個entry Node next; // the next entry to use // 保存/恢復ForwardingNodes TableStack stack, spare; // to save/restore on ForwardingNodes // 下一個遍歷的hash桶index int index; // index of bin to use next // 開始index int baseIndex; // current index of initial table // 結尾index int baseLimit; // index bound for initial table // 數組長度 final int baseSize; // initial table size Traverser(Node [] tab, int size, int index, int limit) { this.tab = tab; this.baseSize = size; this.baseIndex = this.index = index; this.baseLimit = limit; this.next = null; } /** * 遍歷到下一個有數據的節點并返回,無則返回null */ final Node advance() { Node e; // next值不為空,則直接獲取其下一個節點 if ((e = next) != null) e = e.next; for (;;) { Node [] t; int i, n; // must use locals in checks // e非空則直接返回當前值e并將next賦值為e便于下次再次調用該方法使用 if (e != null) return next = e; // 判斷邊界同時做了一些賦值操作 // 數組 t = tab // 數組長度 n = t.length // 數組index i = index // 不滿足直接返回null if (baseIndex >= baseLimit || (t = tab) == null || (n = t.length) <= (i = index) || i < 0) return next = null; // e賦值為t的第i處hash桶節點值,判斷是否為特殊節點 if ((e = tabAt(t, i)) != null && e.hash < 0) { // ForwardingNode節點說明正在擴容,此時遍歷讀需要轉移到擴容數組上進行 if (e instanceof ForwardingNode) { // tab指向擴容數組 tab = ((ForwardingNode )e).nextTable; // e置空,繼續循環 e = null; // 保存此時的未擴容前的數組狀態,相當于入棧操作 pushState(t, i, n); continue; } // TreeBin節點,e置為first節點 else if (e instanceof TreeBin) e = ((TreeBin )e).first; else // 保留節點 e = null; } if (stack != null) // 出棧操作,恢復tab到未擴容之前的數組繼續遍歷 recoverState(n); else if ((index = i + baseSize) >= n) // 更新為下一個hash桶索引 index = ++baseIndex; // visit upper slots if present } } /** * 入棧操作,保存當前數組的狀態 */ private void pushState(Node [] t, int i, int n) { TableStack s = spare; // reuse if possible if (s != null) spare = s.next; else s = new TableStack (); s.tab = t; s.length = n; s.index = i; s.next = stack; stack = s; } /** * 出棧操作,恢復擴容之前的數組狀態 */ private void recoverState(int n) { TableStack s; int len; while ((s = stack) != null && (index += (len = s.length)) >= n) { n = len; index = s.index; tab = s.tab; s.tab = null; TableStack next = s.next; s.next = spare; // save for reuse stack = next; spare = s; } if (s == null && (index += baseSize) >= n) index = ++baseIndex; } }
遍歷過程可參考下圖(圖中數據非真實數據):
ForwardingNodeForwardingNode節點在擴容時被使用,hash值固定為-1,當進行擴容操作時,轉移hash桶時會在原數組位置上放置一個ForwardingNode節點,表示當前位置hash桶已轉移到新擴容數組上,當讀線程讀到ForwardingNode節點時則需要到新擴容數組對應的位置進行讀操作,如果是寫線程,則需要幫助進行擴容操作
/** * A node inserted at head of bins during transfer operations. */ static final class ForwardingNodeReservationNodeextends Node { final Node [] nextTable; ForwardingNode(Node [] tab) { // MOVED hash值固定為-1 super(MOVED, null, null, null); this.nextTable = tab; } // 提供find方法查找,這里通過nextTable進行遍歷 Node find(int h, Object k) { // loop to avoid arbitrarily deep recursion on forwarding nodes outer: for (Node [] tab = nextTable;;) { Node e; int n; // 前置判斷 if (k == null || tab == null || (n = tab.length) == 0 || (e = tabAt(tab, (n - 1) & h)) == null) return null; for (;;) { int eh; K ek; // 判斷是hash桶第一個節點,返回這個節點 if ((eh = e.hash) == h && ((ek = e.key) == k || (ek != null && k.equals(ek)))) return e; if (eh < 0) { // 遞歸 if (e instanceof ForwardingNode) { tab = ((ForwardingNode )e).nextTable; continue outer; } else // 特殊節點調用其自身方法 return e.find(h, k); } // 找到最后返回空 if ((e = e.next) == null) return null; } } } }
保留節點,源碼僅compute,computeIfAbsent中使用,通過ReservationNode對hash桶進行加鎖處理,寫操作時正常情況下需要對第一個節點進行加鎖處理,put操作使用CAS不需要加鎖,而在compute,computeIfAbsent方法中比較復雜,需加鎖處理,在hash桶節點為空時,添加一個ReservationNode節點,同時對其加鎖處理
static final class ReservationNode構造方法extends Node { ReservationNode() { super(RESERVED, null, null, null); } Node find(int h, Object k) { return null; } }
在有參構造函數中,傳入初始容量參數,調用tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1)),這里和HashMap就不一樣了,可自行查閱源碼,ConcurrentHashMap先擴大了1.5倍再調用tableSizeFor方法,可以回想下tableSizeFor方法的含義,和HashMap是相同的處理方式,同時構造方法也不是table進行初始化的地方,和HashMap類似,都是在插入K-V值時進行數組的初始化,構造方法僅僅是來設置屬性值的,重要的在于sizeCtl,此時是用來記錄數組初始化使用容量的,在initTable方法中使用
public ConcurrentHashMap() { } public ConcurrentHashMap(int initialCapacity) { if (initialCapacity < 0) throw new IllegalArgumentException(); int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1)); // 設置sizeCtl,此時表示數組初始化使用容量,因為在初始化時將會使用這個變量 this.sizeCtl = cap; } public ConcurrentHashMap(Map extends K, ? extends V> m) { // sizeCtl設置為默認容量,此時表示數組初始化使用容量 this.sizeCtl = DEFAULT_CAPACITY; putAll(m); } public ConcurrentHashMap(int initialCapacity, float loadFactor) { this(initialCapacity, loadFactor, 1); } // concurrencyLevel 并發級別 兼容舊版本 public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) { if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0) throw new IllegalArgumentException(); if (initialCapacity < concurrencyLevel) // Use at least as many bins initialCapacity = concurrencyLevel; // as estimated threads long size = (long)(1.0 + (long)initialCapacity / loadFactor); int cap = (size >= (long)MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : tableSizeFor((int)size); // 同樣進行設置sizeCtl,此時表示數組初始化使用容量 this.sizeCtl = cap; }initTable
構造方法并沒有創建Node數組,最終執行是在put方法中的initTable方法,這個方法中也能看出sizeCtl在不同值下代表了不同的含義
private final Node總結[] initTable() { Node [] tab; int sc; while ((tab = table) == null || tab.length == 0) { // 在初始化時不能并發執行,在已經有線程進入初始化狀態時,非初始化線程需讓步操作,等待完成 if ((sc = sizeCtl) < 0) Thread.yield(); // lost initialization race; just spin // CAS將sizeCtl置為-1 else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { try { // 檢查是否已經初始化,否則進入初始化過程 if ((tab = table) == null || tab.length == 0) { int n = (sc > 0) ? sc : DEFAULT_CAPACITY; @SuppressWarnings("unchecked") Node [] nt = (Node [])new Node,?>[n]; table = tab = nt; // sc = 3n/4,相當于0.75n sc = n - (n >>> 2); } } finally { // sizeCtl代表了閾值,類似threshold sizeCtl = sc; } break; } } return tab; }
本文從整體上對ConcurrentHashMap進行了介紹,其中常量和變量以及其中重要的內部類都進行了相關的解釋說明,當然,限于篇幅以及復雜度暫未涉及方法的源碼部分,下一篇將結合本文的相關知識重點說明其中涉及的方法,在看本文時請完全理解HashMap的源碼,將會事半功倍,畢竟結構上和HashMap非常相似
ConcurrentHashMap從HashMap的基礎上進行演變,適應多線程并發情況下的操作,理解下列幾點:
初始化數組,單線程創建
擴容時,多線程可幫助擴容(下一章將詳細說明)
hash桶頭節點有4種類型,ForwardingNode節點表明當前hash桶正在擴容移動中,TreeBin節點表明為紅黑樹結構,ReservationNode節點暫不多說,還有就是正常鏈表節點
遍歷操作通過一個特殊的內部類Traverser實現
CAS操作大大增加了并發執行的效率
水平有限,如有錯誤,請及時指出,謝謝!
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/77874.html
摘要:上一篇文章已經就進行了部分說明,介紹了其中涉及的常量和變量的含義,有些部分需要結合方法源碼來理解,今天這篇文章就繼續講解并發前言本文主要介紹中的一些重要方法,結合上篇文章中的講解部分進行更進一步的介紹回顧下上篇文章,我們應該已經知道的整體結 上一篇文章已經就ConcurrentHashMap進行了部分說明,介紹了其中涉及的常量和變量的含義,有些部分需要結合方法源碼來理解,今天這篇文章就...
摘要:用這種范例表示紅黑樹是可能的,但是這會改變一些性質并使算法復雜。插入會出現種情況為根節點,即紅黑樹的根節點。 說到HashMap,就一定要說到紅黑樹,紅黑樹作為一種自平衡二叉查找樹,是一種用途較廣的數據結構,在jdk1.8中使用紅黑樹提升HashMap的性能,今天就來說一說紅黑樹。 前言 限于篇幅,本文只對紅黑樹的基礎進行說明,暫不涉及源碼部分,大部分摘抄自維基百科,這里也貼出對應鏈接...
摘要:前面已經講解集合中的并且也對其中使用的紅黑樹結構做了對應的說明,這次就來看下簡單一些的另一個集合類,也是日常經常使用到的,整體來說,算是比較好理解的集合了,一起來看下前言版本類定義繼承了,實現了,提供對數組隊列的增刪改查操作實現接口,提供隨 前面已經講解集合中的HashMap并且也對其中使用的紅黑樹結構做了對應的說明,這次就來看下簡單一些的另一個集合類,也是日常經常使用到的ArrayL...
摘要:如果沖突了,同步頭節點,進行鏈表操作,如果鏈表長度達到,分成紅黑樹。每次加入一個線程都會將的低位加一。擴容最大的幫助線程是,這是低位的最大值限制的。線程處理完之后,如果沒有可選區間,且任務沒有完成,就會將整個表檢查一遍,防止遺漏。 前言 每一次總結都意味著重新開始,同時也是為了更好的開始。ConcurrentHashMap 一直是我心中的痛。雖然不敢說完全讀懂了,但也看了幾個重要的方法...
閱讀 1535·2023-04-26 02:08
閱讀 3128·2021-10-14 09:42
閱讀 7177·2021-09-22 15:34
閱讀 3236·2019-08-30 13:16
閱讀 2718·2019-08-26 13:49
閱讀 1342·2019-08-26 11:59
閱讀 1251·2019-08-26 10:31
閱讀 2170·2019-08-23 17:19