Java?ConcurrentHashMap的源碼分析詳解
概述
ConcurrentHashMap(CHM)是日常開發(fā)中使用頻率非常高的一種數(shù)據(jù)結構,想對于普通的HashMap,CHM提供了線程安全的讀寫,CHM里面使用了許多比較精妙的優(yōu)化&操作。本文主要對CHM的整體結構、初始化,查找,插入等做分析。
CHM在1.8之前和之后有比較大的變動,1.8之前主要通過Segment 分段鎖 來解決并發(fā)問題,1.8及之后就沒有這些臃腫的數(shù)據(jù)結構了,其數(shù)據(jù)結構與普通的HashMap一樣,都是Node數(shù)組+鏈表+紅黑樹
一顆紅黑樹應滿足如下性質:
1.根節(jié)點是黑色的
- 外部節(jié)點均為黑色(圖中的 leaf 節(jié)點,通常在表述的時候會省略)
- 紅色節(jié)點的孩子節(jié)點必為黑色(通常插入的節(jié)點為紅色)
- 從任一外部節(jié)點到根節(jié)點的沿途,黑節(jié)點的數(shù)目相等
除了上面基本的數(shù)據(jù)結構之外,Node節(jié)點也是一個需要關心的數(shù)據(jù)結構,Node節(jié)點本質上是單向鏈表的節(jié)點,其中包含key
、value
、Hash
、next
屬性
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; volatile V val; volatile Node<K,V> next; }
ForwardingNode節(jié)點
ForwardingNode節(jié)點(簡稱fwd節(jié)點)繼承自Node節(jié)點,主要用于擴容,該節(jié)點里面固定Hash值為MOVED(值為-1),同時持有新表的引用
static final class ForwardingNode<K,V> extends Node<K,V> { final Node<K,V>[] nextTable; ForwardingNode(Node<K,V>[] tab) { super(MOVED, null, null, null); this.nextTable = tab; } Node<K,V> find(int h, Object k) { ... } }
TreeNode
TreeNode節(jié)點也繼承自Node節(jié)點,用于表示紅黑樹上的節(jié)點,主要屬性如下所示
static final class TreeNode<K,V> extends Node<K,V> { TreeNode<K,V> parent; // 父節(jié)點 TreeNode<K,V> left; // 左兒子 TreeNode<K,V> right; // 右兒子 TreeNode<K,V> prev; // 記錄前驅節(jié)點,用于恢復鏈表 boolean red; }
TreeBin
TreeBin節(jié)點內部持有TreeNode節(jié)點的引用,內部實現(xiàn)了讀寫鎖用于控制多線程并發(fā)在紅黑樹上的操作,主要屬性如下所示
static final class TreeBin<K,V> extends Node<K,V> { TreeNode<K,V> root; // 紅黑樹根節(jié)點 volatile TreeNode<K,V> first; // 鏈表根節(jié)點,讀寫分離時會用到 volatile Thread waiter; // 當前線程 volatile int lockState; // 當前紅黑樹的鎖狀態(tài) // values for lockState static final int WRITER = 1; // set while holding write lock static final int WAITER = 2; // set when waiting for write lock static final int READER = 4; // 讀鎖標記 }
SizeCtl
除了數(shù)據(jù)結構需要說明外,SizeCtl也是理解CHM十分重要的一個字段,他是一個整數(shù),不同的值表示不同的狀態(tài)
- 當SizeCtl > 0時,表示下次擴展的閾值,其中閾值計算方式:數(shù)組長度 * 擴展閾值(注意這里是固定的0.75)
- 當SizeCtl = 0時,表示還沒有開始初始化
- 當sizeCtl = -1是,表示此時正在進行初始化
- 當SizeCtl < -1時,表示此時正在進行擴展,其中高16位表示擴容標識戳,低16位表示參與擴容的線程數(shù)+1
初始化
CHM的初始化是惰性初始化的,即當我們使用ConCurrentHashMap<String,string> map = new ConcurrentHashMap(20);
創(chuàng)建一個CHM對象時,并不會真正的創(chuàng)建對象,而是只有在put時才會真正開始創(chuàng)建對象。
public ConcurrentHashMap(int initialCapacity) { // 只是檢查參數(shù)是否合理,并設置好數(shù)組容量和擴容閾值 if (initialCapacity < 0) throw new IllegalArgumentException(); int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY : tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1)); this.sizeCtl = cap; }
初始化流程
private final Node<K,V>[] initTable() { Node<K,V>[] tab; int sc; // 判空,注意這里是while,當線程蘇醒后會記性檢查直到初始化完畢 while ((tab = table) == null || tab.length == 0) { // 如果其他線程正在初始化,則讓出cpu if ((sc = sizeCtl) < 0) Thread.yield(); // lost initialization race; just spin else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { // 當前線程嘗試獲取創(chuàng)建數(shù)組的重任 try { // 這里需要再進行判斷是否為空,防止當前線程創(chuàng)建完畢后又有其他線程進來重復創(chuàng)建 if ((tab = table) == null || tab.length == 0) { int n = (sc > 0) ? sc : DEFAULT_CAPACITY; @SuppressWarnings("unchecked") Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n]; table = tab = nt; // 設置閾值為0.75n sc = n - (n >>> 2); } } finally { sizeCtl = sc; } break; } } return tab; }
查找
get方法進行查找,針對不同情況有不同處理
public V get(Object key) { Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek; // 擾動運算 int h = spread(key.hashCode()); // 判斷表是否為空,表長度是否為0,以及元素對應下標是否為空 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; } else if (eh < 0) // 判斷Node節(jié)點的Hash值是否小于0,如果小于0的話,則會在他的子類上進行查找 //這里情況比較復雜,不同的節(jié)點有不同的處理,如果當前節(jié)點為fwd節(jié)點,則去新表上找,如果為紅黑樹 //節(jié)點,則在紅黑樹上進行查找,后文會展開紅黑樹上的查找流程 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; }
插入
final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException(); int hash = spread(key.hashCode()); int binCount = 0; for (Node<K,V>[] tab = table;;) { // 注意這里是個死循環(huán) Node<K,V> f; int n, i, fh; // 判斷是否初始化 if (tab == null || (n = tab.length) == 0) tab = initTable(); else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 判斷對應節(jié)點是否是空節(jié)點,如果是 //直接通過cas創(chuàng)建節(jié)點 if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null))) break; // no lock when adding to empty bin } else if ((fh = f.hash) == MOVED) // 如果當前節(jié)點是fwd節(jié)點(正在擴容),則幫助擴容 tab = helpTransfer(tab, f); else { V oldVal = null; synchronized (f) { // 這里加鎖 if (tabAt(tab, i) == f) { // 這里需要繼續(xù)判斷是否當前位置的節(jié)點沒有變化,因為其他線程可能 // 改變此節(jié)點 if (fh >= 0) { // fh >= 0表示當前節(jié)點是鏈表節(jié)點,直接next往下找就行 binCount = 1; for (Node<K,V> e = f;; ++binCount) { K ek; if (e.hash == hash && ((ek = e.key) == key || (ek != null && key.equals(ek)))) { oldVal = e.val; if (!onlyIfAbsent) e.val = value; break; } Node<K,V> pred = e; if ((e = e.next) == null) { pred.next = new Node<K,V>(hash, key, value, null); break; } } } else if (f instanceof TreeBin) { // 如果此時節(jié)點是TreeBin節(jié)點,則需要再紅黑樹上進行插入,具體 // 插入流程后文展開 Node<K,V> p; binCount = 2; 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) treeifyBin(tab, i); if (oldVal != null) return oldVal; break; } } } // 計數(shù)器加1,這里使用了計數(shù)器而不是AtomicLong這種 addCount(1L, binCount); return null; }
擴容
CHM的擴容利用了多線程并發(fā)的去擴容
CHM在兩種條件下會發(fā)生擴容:
- 單個鏈表長度大于8,并且數(shù)組長度小于64時,會發(fā)生擴容
- 元素個數(shù)超過閾值會發(fā)生擴容
擴容流程:
- 創(chuàng)建新的Node表,長度為當前數(shù)組長度的兩倍
- 從后往前分配任務區(qū)間,最小長度是16,即每個線程每次擴容最少需要遷移16個桶,具體遷移數(shù)量由cpu核數(shù)決定
- 判斷當前元素是否為空,為空直接cas操作當前節(jié)點為fwd節(jié)點,否則判斷當前元素是否為fwd節(jié)點,如果是,則說明其他線程再次區(qū)間擴容,此時需要重新選定區(qū)間,否則就對當前桶開始進行遷移
- 其他元素在put時如果發(fā)現(xiàn)當前桶位是fwd節(jié)點,會先協(xié)助擴容再put
- 最后一個擴容線程退出擴容時再次檢查一遍舊桶,更新sizeCtl的值,同時引用新桶
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) { int n = tab.length, stride; // 確定任務長度 if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) stride = MIN_TRANSFER_STRIDE; // subdivide range if (nextTab == null) { // 第一個擴容的線程需要創(chuàng)建新數(shù)組 try { @SuppressWarnings("unchecked") Node<K,V>[] nt = (Node<K,V>[])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<K,V> fwd = new ForwardingNode<K,V>(nextTab); boolean advance = true; boolean finishing = false; // 用于最后一次檢查 for (int i = 0, bound = 0;;) { Node<K,V> f; int fh; 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))) { //cas更新transferIndex bound = nextBound; i = nextIndex - 1; advance = false; } } if (i < 0 || i >= n || i + n >= nextn) { // 擴容完畢 int sc; if (finishing) { // 二次檢查后引用新表 nextTable = null; table = nextTab; sizeCtl = (n << 1) - (n >>> 1); return; } if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) { if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) return; finishing = advance = true; i = n; // recheck before commit } } else if ((f = tabAt(tab, i)) == null) // 當前節(jié)點為空,直接賦為fwd advance = casTabAt(tab, i, null, fwd); else if ((fh = f.hash) == MOVED) // 其他線程已經(jīng)遷移好了,此時需要重新分配區(qū)間 advance = true; // already processed else { synchronized (f) { //當前節(jié)點開始遷移,這里需要加鎖,可能會有讀寫操作 if (tabAt(tab, i) == f) { Node<K,V> ln, hn; if (fh >= 0) { //鏈表節(jié)點 這里只需要判斷對應位置是0還是1就可決定遷移到高桶位還是低桶位 int runBit = fh & n; Node<K,V> lastRun = f; 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) { // 紅黑樹節(jié)點,通過判斷對應位是否為0決定放到高 // 桶位還是低桶位 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; } } 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); advance = true; } } } } } }
紅黑樹的讀&寫
紅黑樹上的讀寫操作是基于TreeBin進行的,上文也對其進行了說明。TreeBin其中的lockState
表示當前的讀寫狀態(tài)
讀操作
讀操作和寫操作可可以是并行的,當有現(xiàn)成正在寫或者正在等待寫時,讀線程可以讀,通過代碼我們可以發(fā)現(xiàn),此時并沒有從紅黑樹上去讀,而是通過鏈表去讀了,這里和IO多路復用里面的epoll函數(shù)的底層原理一樣。
final Node<K,V> find(int h, Object k) { if (k != null) { for (Node<K,V> e = first; e != null; ) { int s; K ek; // WAITER : .....010 // WRITER : .....001 // READER : .....100 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, // 表明此時處于無鎖或者讀鎖狀態(tài),直接紅黑樹上查找 s + READER)) { TreeNode<K,V> r, p; try { p = ((r = root) == null ? null : r.findTreeNode(h, k, null)); } finally { Thread w; // 讀操作完畢后檢查是否有寫線程在等待,如果有,需要喚醒等待線程 // READER|WAITER 表示此時是最后一個讀線程 if (U.getAndAddInt(this, LOCKSTATE, -READER) == (READER|WAITER) && (w = waiter) != null) LockSupport.unpark(w); } return p; } } } return null; }
寫操作
紅黑樹上的寫會先查找是否有對應的值,如果有,則更新值即可,如果沒有找到,則插入新的節(jié)點,再插入節(jié)點的過程中,會調用lockRoot
加寫鎖,如果沒有搶到鎖,則會調用contentLock
方法繼續(xù)嘗試或者將自己掛起
final TreeNode<K,V> putTreeVal(int h, K k, V v) { Class<?> kc = null; boolean searched = false; for (TreeNode<K,V> p = root;;) { // 查找是否有值 int dir, ph; K pk; if (p == null) { first = root = new TreeNode<K,V>(h, k, v, null, null); break; } else if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; else if ((pk = p.key) == k || (pk != null && k.equals(pk))) return p; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) { if (!searched) { TreeNode<K,V> q, ch; searched = true; if (((ch = p.left) != null && (q = ch.findTreeNode(h, k, kc)) != null) || ((ch = p.right) != null && (q = ch.findTreeNode(h, k, kc)) != null)) return q; } dir = tieBreakOrder(k, pk); } TreeNode<K,V> xp = p; if ((p = (dir <= 0) ? p.left : p.right) == null) { TreeNode<K,V> x, f = first; first = x = new TreeNode<K,V>(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 { // 鎖住節(jié)點,平衡操作可能會導致樹結構發(fā)生變化 lockRoot(); try { root = balanceInsertion(root, x); } finally { unlockRoot(); } } break; } } assert checkInvariants(root); return null; }
private final void lockRoot() { // 這里嘗試去獲取寫鎖,獲取不到就調用contenedLock方法 if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER)) contendedLock(); // offload to separate method } private final void contendedLock() { boolean waiting = false; for (int s;;) { // ~WAITER 1111111101 // 如果此時處于無鎖,則重新獲取鎖 if (((s = lockState) & ~WAITER) == 0) { if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) { if (waiting) waiter = null; return; } } // 此時不是處于waiter狀態(tài),即其他線程沒有等待,則自己進行等待。如果已經(jīng)有線程在等待了,會一直自旋,也可看出這里是非公平鎖 else if ((s & WAITER) == 0) { if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) { waiting = true; waiter = Thread.currentThread(); } } else if (waiting) // 將當前線程掛起 LockSupport.park(this); } }
小結
在紅黑樹上進行讀寫時,我們可以發(fā)現(xiàn),當有線程在樹上寫時,讀線程是可以讀的,不過不是從紅黑樹上去讀,而不用阻塞,這里可能導致短暫的數(shù)據(jù)不一致的問題,類似于COW;當有線程在樹上讀時,此時寫線程會將自己掛起,當最后一個讀線程查找完畢后會檢查是否有些線程在等待,如果有,則喚醒等待寫的線程
容器計數(shù)
對于一個并發(fā)容器來說,當多線程同時寫入時,此時容器如何計數(shù)成為了一個問題,最簡單的是通過AtomicLong來保證原子性與可見性,但是在多線程情況下絕大多數(shù)線程會cas失敗,然后重試。這無疑是浪費cpu性能的且會有性能瓶頸的。在CHM中引入了,使用分段計數(shù)思想,即通過一個數(shù)組來計數(shù),當多線程并發(fā)計數(shù)時,記在數(shù)組的不同位置上,最后進行統(tǒng)計。
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) { // 累計cells數(shù)組 for (int i = 0; i < as.length; ++i) { if ((a = as[i]) != null) sum += a.value; } } return sum; } // 計數(shù) private final void addCount(long x, int check) { CounterCell[] as; long b, s; // 如果cells數(shù)組不為空或者cas操作baseCount失敗,說明此時出現(xiàn)了競爭,需要再cells數(shù)組上計數(shù) if ((as = counterCells) != null || !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) { CounterCell a; long v; int m; boolean uncontended = true; if (as == null || (m = as.length - 1) < 0 || (a = as[ThreadLocalRandom.getProbe() & m]) == null || !(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { fullAddCount(x, uncontended); return; } if (check <= 1) return; s = sumCount(); } // 判斷是否需要擴容 if (check >= 0) { Node<K,V>[] tab, nt; int n, sc; while (s >= (long)(sc = sizeCtl) && (tab = table) != null && (n = tab.length) < MAXIMUM_CAPACITY) { 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; 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(); } } }
總結
CHM作為線程安全的Map,同時又要兼顧性能,使用了許多巧妙的設計與思想,如位運算,紅黑樹,無鎖并發(fā)等等,里面的思想值得我們去學習和借鑒。本篇文章對其進行簡單的解讀,如有不當之處,還望指出,萬分感謝。
到此這篇關于Java ConcurrentHashMap的源碼分析詳解的文章就介紹到這了,更多相關Java ConcurrentHashMap內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家!
- Java的ConcurrentHashMap原理深入分析
- Java?ConcurrentHashMap實現(xiàn)線程安全的代碼示例
- Java面試常考之ConcurrentHashMap多線程擴容機制詳解
- 淺析Java中ConcurrentHashMap的存儲流程
- Java源碼重讀之ConcurrentHashMap詳解
- Java集合ConcurrentHashMap詳解
- java并發(fā)容器ConcurrentHashMap深入分析
- Java HashTable的原理與實現(xiàn)
- Java中HashMap和Hashtable的區(qū)別小結
- 一文帶你全面了解Java?Hashtable
- Java中Hashtable集合的常用方法詳解
- 詳解Java中的HashTable
- Java容器HashMap與HashTable詳解
- java HashMap和HashTable的區(qū)別詳解
- java面試題——詳解HashMap和Hashtable 的區(qū)別
- Java中HashMap和Hashtable的區(qū)別淺析
- Java中ConcurrentHashMap和Hashtable的區(qū)別
相關文章
mybaties?plus?selectMaps和selectList的區(qū)別說明
這篇文章主要介紹了mybaties?plus?selectMaps和selectList的區(qū)別說明,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-12-12Java語言實現(xiàn)Blowfish加密算法完整代碼分享
這篇文章主要介紹了Java語言實現(xiàn)Blowfish加密算法完整代碼分享,簡單介紹了blowfish加密算法,具有一定借鑒價值,需要的朋友可以參考下。2017-11-11spring cloud feign實現(xiàn)遠程調用服務傳輸文件的方法
這篇文章主要介紹了spring cloud feign實現(xiàn)遠程調用服務傳輸文件的方法,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧2018-09-09