本文首寫于有道雲筆記，并在小組分享會分享，先整理釋出，希望和大家交流探讨。雲筆記位址
概述： 1、設計首要目的：維護并發可讀性（get、疊代相關）；次要目的：使空間消耗比HashMap相同或更好，且支援多線程高效率的初始插入（empty table）。 2、HashTable 線程安全，但采用synchronized，多線程下效率低下。線程1put時，線程2無法put或get。
實作原理： 鎖分離： 在HashMap的基礎上，将資料分段存儲， ConcurrentHashMap由多個Segment組成，每個Segment都有把鎖。Segment下包含很多Node，也就是我們的鍵值對了。
如果還停留在鎖分離、Segment，那已經out了。 Segment雖保留，但已經簡化屬性，僅僅是為了相容舊版本。
- CAS算法；unsafe.compareAndSwapInt(this, valueOffset, expect, update); CAS(Compare And Swap)，意思是如果valueOffset位置包含的值與expect值相同，則更新valueOffset位置的值為update，并傳回true，否則不更新，傳回false。
- 與Java8的HashMap有相通之處，底層依然由“數組”+連結清單+紅黑樹；
- 底層結構存放的是TreeBin對象，而不是TreeNode對象；
- CAS作為知名無鎖算法，那ConcurrentHashMap就沒用鎖了麼？當然不是，hash值相同的連結清單的頭結點還是會synchronized上鎖。
private static final int MAXIMUM_CAPACITY = 1 << 30; // 2的30次方=1073741824
private static final intDEFAULT_CAPACITY = 16;
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // MAX_VALUE=2^31-1=2147483647
private static finalint DEFAULT_CONCURRENCY_LEVEL = 16;
private static final float LOAD_FACTOR = 0.75f;
static final int TREEIFY_THRESHOLD = 8; // 連結清單轉樹閥值，大于8時
static final int UNTREEIFY_THRESHOLD = 6; //樹轉連結清單閥值，小于等于6（tranfer時，lc、hc=0兩個計數器分别++記錄原bin、新binTreeNode數量，<=UNTREEIFY_THRESHOLD 則untreeify(lo)）。【僅在擴容tranfer時才可能樹轉連結清單】
static final int MIN_TREEIFY_CAPACITY = 64;
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; // 2^15-1，help resize的最大線程數
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS; // 32-16=16，sizeCtl中記錄size大小的偏移量
static final int MOVED = -1; // hash for forwarding nodes（forwarding nodes的hash值）、标示位
static final int TREEBIN = -2; // hash for roots of trees（樹根節點的hash值）
static final int RESERVED = -3; // hash for transient reservations（ReservationNode的hash值）
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
static final int NCPU = Runtime.getRuntime().availableProcessors(); // 可用處理器數量
private transient volatile int sizeCtl;
sizeCtl是控制辨別符，不同的值表示不同的意義。
- 負數代表正在進行初始化或擴容操作
- -1代表正在初始化
- -N 表示有N-1個線程正在進行擴容操作
- 正數或0代表hash表還沒有被初始化，這個數值表示初始化或下一次進行擴容的大小，類似于擴容門檻值。它的值始終是目前ConcurrentHashMap容量的0.75倍，這與loadfactor是對應的。實際容量>=sizeCtl，則擴容。
部分構造函數：
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
thrownew 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);
this.sizeCtl = cap;
}
concurrencyLevel： concurrencyLevel，能夠同時更新ConccurentHashMap且不産生鎖競争的最大線程數，在Java8之前實際上就是ConcurrentHashMap中的分段鎖個數，即Segment[]的數組長度 。 正确地估計很重要，當低估，資料結構将根據額外的競争，進而導緻線程試圖寫入目前鎖定的段時阻塞； 相反，如果高估了并發級别，你遇到過大的膨脹，由于段的不必要的數量; 這種膨脹可能會導緻性能下降，由于高數緩存未命中。 在Java8裡，僅僅是為了相容舊版本而保留。唯一的作用就是保證構造map時初始容量不小于concurrencyLevel。 源碼122行： Also, for compatibility with previous versions of this class, constructors may optionally specify an expected {@code concurrencyLevel} as an additional hint for internal sizing. 源碼482行： Mainly: We leave untouched but unused constructor arguments refering to concurrencyLevel .…… …… 1、重要屬性： 1.1 Node：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val; // Java8增加volatile，保證可見性
volatile Node<K,V> next;
Node(inthash, K key, V val, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return val; }
// HashMap調用Objects.hashCode()，最終也是調用Object.hashCode()；效果一樣
public final int hashCode() { returnkey.hashCode() ^ val.hashCode(); }
public final String toString(){ returnkey + "=" + val; }
public final V setValue(V value) { // 不允許修改value值，HashMap允許
throw new UnsupportedOperationException();
}
// HashMap使用if (o == this)，且嵌套if；concurrent使用&&
public final boolean equals(Object o) {
Object k, v, u; Map.Entry<?,?> e;
return ((oinstanceof Map.Entry) &&
(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
(v = e.getValue()) != null &&
(k == key || k.equals(key)) &&
(v == (u = val) || v.equals(u)));
}
/**
* Virtualized support for map.get(); overridden in subclasses.
*/
Node<K,V> find(inth, Object k) { // 增加find方法輔助get方法
Node<K,V> e = this;
if (k != null) {
do {
K ek;
if (e.hash == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
returne;
} while ((e = e.next) != null);
}
returnnull;
}
}
1.2 TreeNode
// Nodes for use in TreeBins，連結清單>8，才可能轉為TreeNode.
// HashMap的TreeNode繼承至LinkedHashMap.Entry；而這裡繼承至自己實作的Node，将帶有next指針，便于treebin通路。
static final class TreeNode<K,V> extends Node<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(inthash, K key, V val, Node<K,V> next,
TreeNode<K,V> parent) {
super(hash, key, val, next);
this.parent = parent;
}
Node<K,V> find(inth, Object k) {
return findTreeNode(h, k, null);
}
/**
* Returns the TreeNode (or null if not found) for the given key
* starting at given root.
*/ // 查找hash為h，key為k的節點
final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
if (k != null) { // 比HMap增加判空
TreeNode<K,V> p = this;
do {
intph, dir; K pk; TreeNode<K,V> q;
TreeNode<K,V> pl = p.left, pr = p.right;
if ((ph = p.hash) > h)
p = pl;
elseif (ph < h)
p = pr;
elseif ((pk = p.key) == k || (pk != null && k.equals(pk)))
returnp;
elseif (pl == null)
p = pr;
elseif (pr == null)
p = pl;
elseif ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
elseif ((q = pr.findTreeNode(h, k, kc)) != null)
returnq;
else
p = pl;
} while (p != null);
}
return null;
}
}
// 和HashMap相比，這裡的TreeNode相當簡潔；ConcurrentHashMap連結清單轉樹時，并不會直接轉，正如注釋（Nodes for use in TreeBins）所說，隻是把這些節點包裝成TreeNode放到TreeBin中，再由TreeBin來轉化紅黑樹。
1.3 TreeBin
// TreeBin用于封裝維護TreeNode，包含putTreeVal、lookRoot、UNlookRoot、remove、balanceInsetion、balanceDeletion等方法，這裡隻分析其構造函數。
// 當連結清單轉樹時，用于封裝TreeNode，也就是說，ConcurrentHashMap的紅黑樹存放的時TreeBin，而不是treeNode。
TreeBin(TreeNode<K,V> b) {
super(TREEBIN, null, null, null);//hash值為常量TREEBIN=-2,表示roots of trees
this.first = b;
TreeNode<K,V> r = null;
for (TreeNode<K,V> x = b, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (r == null) {
x.parent = null;
x.red = false;
r = x;
}
else {
K k = x.key;
inth = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = r;;) {
intdir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
elseif (ph < h)
dir = 1;
elseif ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
r = balanceInsertion(r, x);
break;
}
}
}
}
this.root = r;
assert checkInvariants(root);
}
1.4 treeifyBin
/**
* Replaces all linked nodes in bin at given index unless table is
* too small, in which case resizes instead.連結清單轉樹
*/
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; intn, sc;
if (tab != null) {
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1); // 容量<64，則table兩倍擴容，不轉樹了
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
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));
}
}
}
}
}
1.5 ForwardingNode
// A node inserted at head of bins during transfer operations.連接配接兩個table
// 并不是我們傳統的包含key-value的節點，隻是一個标志節點，并且指向nextTable，提供find方法而已。生命周期：僅存活于擴容操作且bin不為null時，一定會出現在每個bin的首位。
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); // 此節點hash=-1，key、value、next均為null
this.nextTable = tab;
}
Node<K,V> find(int h, Object k) {
// 查nextTable節點，outer避免深度遞歸
outer: for (Node<K,V>[] tab = nextTable;;) {
Node<K,V> e; intn;
if (k == null || tab == null || (n = tab.length) == 0 ||
(e = tabAt(tab, (n - 1) & h)) == null)
returnnull;
for (;;) { // CAS算法多和死循環搭配！直到查到或null
int eh; K ek;
if ((eh = e.hash) == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
returne;
if (eh < 0) {
if (e instanceof ForwardingNode) {
tab = ((ForwardingNode<K,V>)e).nextTable;
continue outer;
}
else
return e.find(h, k);
}
if ((e = e.next) == null)
return null;
}
}
}
}
1.6 3個原子操作（調用頻率很高）
@SuppressWarnings("unchecked") // ASHIFT等均為private static final
static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) { // 擷取索引i處Node
return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}
// 利用CAS算法設定i位置上的Node節點（将c和table[i]比較，相同則插入v）。
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
// 設定節點位置的值，僅在上鎖區被調用
static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {
U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);
}
1.7 Unsafe
//在源碼的6277行到最後，有着ConcurrentHashMap中極為重要的幾個屬性（SIZECTL），unsafe靜态塊控制其修改行為。Java8中，大量運用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 = 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);
intscale = U.arrayIndexScale(ak);
if ((scale & (scale - 1)) != 0)
thrownew Error("data type scale not a power of two");
ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
} catch (Exception e) {
thrownew Error(e);
}
}
1.8 擴容相關 tryPresize 在putAll以及treeifyBin中調用
private final void tryPresize(int size) {
// 給定的容量若>=MAXIMUM_CAPACITY的一半，直接擴容到允許的最大值，否則調用函數擴容
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(tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c; // 擴容閥值取較大者
// 期間沒有其他線程對表操作，則CAS将SIZECTL狀态置為-1，表示正在進行初始化
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); //無符号右移2位，此即0.75*n
}
} finally {
sizeCtl = sc; // 更新擴容閥值
}
}
}// 若欲擴容值不大于原閥值，或現有容量>=最值，什麼都不用做了
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
else if (tab == table) { // table不為空，且在此期間其他線程未修改table
int rs = resizeStamp(n);
if (sc < 0) {
Node<K,V>[] nt;//RESIZE_STAMP_SHIFT=16,MAX_RESIZERS=2^15-1
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);
}
}
}
private static final int tableSizeFor(int c){//和HashMap一樣,傳回>=n的最小2的自然數幂
int n = c - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
/**
* 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));
}// numberOfLeadingZeros傳回n對應32位二進制數左側0的個數，如9（1001）傳回28
// RESIZE_STAMP_BITS=16,(左側0的個數)|(2^15)
ConcurrentHashMap無鎖多線程擴容，減少擴容時的時間消耗。 transfer擴容操作 ：單線程建構兩倍容量的nextTable；允許多線程複制原table元素到nextTable。
- 為每個核心均分任務，并保證其不小于16；
- 若nextTab為null，則初始化其為原table的2倍；
- 死循環周遊，直到finishing。
- 節點為空，則插入ForwardingNode；
- 連結清單節點（fh>=0），分别插入nextTable的i和i+n的位置；
- TreeBin節點（fh<0），判斷是否需要untreefi，分别插入nextTable的i和i+n的位置；
- finishing時，nextTab賦給table，更新sizeCtl為新容量的0.75倍 ，完成擴容。
以上說的都是單線程，多線程又是如何實作的呢？ 周遊到ForwardingNode節點((fh = f.hash) == MOVED)，說明此節點被處理過了，直接跳過。這是控制并發擴容的核心 。 由于給節點上了鎖，隻允許目前線程完成此節點的操作，處理完畢後，将對應值設為ForwardingNode（fwd），其他線程看到forward，直接向後周遊。如此便完成了多線程的複制工作，也解決了線程安全問題。
private transient volatile Node<K,V>[] nextTable; //僅僅在擴容使用，并且此時非空
// 将table每一個bin（桶位）的Node移動或複制到nextTable
// 隻在addCount(long x, int check)、helpTransfer、tryPresize中調用
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// 每核處理的量小于16，則強制指派16
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
if (nextTab == null) { // initiating
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;
//連節點指針,标志位，fwd的hash值為-1，fwd.nextTable=nextTab。
ForwardingNode<K,V> fwd= new ForwardingNode<K,V>(nextTab);
boolean advance= true;//并發擴容的關鍵屬性,等于true,說明此節點已經處理過
boolean finishing = false; // to ensure sweep before committing nextTab
for (int i = 0, bound = 0;;) { // 死循環
Node<K,V> f; int fh;
while (advance) { // 控制--i，周遊原hash表中的節點
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}//TRANSFERINDEX 即用CAS計算得到的transferIndex
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
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); //擴容閥值設為原來的1.5倍，即現在的0.75倍
return; // 僅有的2個跳出死循環出口之一
}//CAS更新擴容門檻值,sc-1表明新加入一個線程參與擴容
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;// 僅有的2個跳出死循環出口之一
finishing = advance = true;
i = n; // recheck before commit
}
}
else if ((f = tabAt(tab, i)) == null) //該節點為空，則插入ForwardingNode
advance = casTabAt(tab, i, null, fwd);
//周遊到ForwardingNode節點，說明此節點被處理過了，直接跳過。這是控制并發擴容的核心
else if ((fh = f.hash) == MOVED) // MOVED=-1，hash for fwd
advance = true; // already processed
else {
synchronized (f) { //上鎖
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn; //ln原位置節點，hn新位置節點
if (fh >= 0) { // 連結清單
int runBit = fh & n; // f.hash & n
Node<K,V> lastRun = f; // lastRun和p兩個連結清單，逆序？？
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n; // f.next.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) // 和HashMap确定擴容後的節點位置一樣
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn); //新位置節點
}//類似HashMap，為何i+n？參見HashMap的筆記
setTabAt(nextTab, i, ln);//在nextTable[i]插入原節點
setTabAt(nextTab, i + n, hn);//在nextTable[i+n]插入新節點
//在nextTable[i]插入forwardNode節點，表示已經處理過該節點
setTabAt(tab, i, fwd);
//設定advance為true 傳回到上面的while循環中 就可以執行--i操作
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;
//lc、hc=0兩計數器分别++記錄原、新bin中TreeNode數量
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;
}
}//擴容後樹節點個數若<=6，将樹轉連結清單
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;
}
}
}
}
}
}
// 協助擴容方法。多線程下，目前線程檢測到其他線程正進行擴容操作，則協助其一起擴容；（隻有這種情況會被調用）從某種程度上說，其“優先級”很高，隻要檢測到擴容，就會放下其他工作，先擴容。
// 調用之前，nextTable一定已存在。
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; intsc;
if (tab != null && (finstanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
intrs = 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;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);//調用擴容方法，直接進入複制階段
break;
}
}
return nextTab;
}
return table;
}
2、 put相關：
理一下put的流程： ① 判空：null直接抛空指針異常； ② hash：計算h=key.hashcode；調用spread計算hash= ( h ^( h >>> 16 ))& HASH_BITS； ③ 周遊table
- 若table為空，則初始化，僅設定相關參數；
- @@@計算目前key存放位置，即table的下标i=(n - 1) & hash；
- 若待存放位置為null，casTabAt無鎖插入；
- 若是forwarding nodes（檢測到正在擴容），則helpTransfer（幫助其擴容）；
- else（待插入位置非空且不是forward節點，即碰撞了），将頭節點上鎖（保證了線程安全）：區分連結清單節點和樹節點，分别插入（遇到hash值與key值都與新節點一緻的情況，隻需要更新value值即可。否則依次向後周遊，直到連結清單尾插入這個結點）；
- 若連結清單長度>8，則treeifyBin轉樹（Note：若length<64,直接tryPresize,兩倍table.length;不轉樹）。
④ addCount(1L, binCount)。 Note： 1、put操作共計兩次hash操作，再利用“與&”操作計算Node的存放位置。 2、ConcurrentHashMap不允許key或value為null。 3、 addCount(longx,intcheck)方法： ①利用CAS快速更新baseCount的值； ②check>=0.則檢驗是否需要擴容； if sizeCtl<0（正在進行初始化或擴容操作）【nexttable null等情況break；如果有線程正在擴容，則協助擴容】； else if 僅目前線程在擴容，調用協助擴容函數，注其參數nextTable為null。
public V put(K key, V value) {
return putVal(key, value, false);
}
final V <span style="background-color: rgb(255, 255, 51);">putVal</span>(K key, V value, boolean onlyIfAbsent) {
// 不允許key、value為空
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode()); //傳回(h^(h>>>16))&HASH_BITS
int binCount = 0;
for (Node<K,V>[] tab = table;;) { // 死循環，直到插入成功
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable(); // table為空，初始化table
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {// 索引處無值
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) // MOVED=-1;//hash for forwarding nodes
tab = helpTransfer(tab, f); //檢測到正在擴容，則幫助其擴容
else {
V oldVal = null;
synchronized (f) { // 節點上鎖（hash值相同的連結清單的頭節點）
if (tabAt(tab, i) == f) {
if (fh >= 0) { // 連結清單節點
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;// hash和key相同，則修改value
if (e.hash == hash &&
((ek = e.key) == key ||(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent) //僅putIfAbsent()方法中onlyIfAbsent為true
e.val = value; //putIfAbsent()包含key則傳回get，否則put并傳回
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) { // 樹節點
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)//實則是>8,執行else,說明該桶位本就有Node
treeifyBin(tab, i);//若length<64,直接tryPresize,兩倍table.length;不轉樹
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
// Initializes table, using the size recorded in sizeCtl.
private final Node<K,V>[] <span style="background-color: rgb(255, 255, 51);">initTable</span>() { // 僅僅設定參數，并未實質初始化
Node<K,V>[] tab; intsc;
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0) // 其他線程正在初始化，此線程挂起
Thread.yield(); // lost initialization race; just spin
//CAS方法把sizectl置為-1，表示本線程正在進行初始化
elseif (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
intn = (sc > 0) ? sc : DEFAULT_CAPACITY;//DEFAULT_CAPACITY=16
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2); // 擴容閥值，0.75*n
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
3、 get、contains相關
public V <span style="background-color: rgb(255, 255, 51);">get</span>(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; intn, eh; K ek;
inth = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {//tabAt(i),擷取索引i處Node
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
returne.val;
}
elseif (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))))
returne.val;
}
}
return null;
}
public boolean containsKey(Object key) {return get(key) != null;}
public boolean containsValue(Object value) {}
理一下get的流程： ①spread計算hash值； ②table不為空； ③tabAt(i)處桶位不為空； ④check first，是則傳回目前Node的value；否則分别根據樹、連結清單查詢。
4、 Size相關： 由于ConcurrentHashMap在統計size時 可能正被 多個線程操作，而我們又不可能讓他停下來讓我們計算，是以隻能計量一個估計值。
計數輔助：
| // Table of counter cells. When non-null, size is a power of 2 private transient volatile CounterCell[] counterCells; |
| @sun.misc.Contended static final class CounterCell { volatile long value; CounterCell(long x) { value = x; } } |
| final long sumCount(){ CounterCell as[] = counterCells; long sum = baseCount; if(as != null){ for(int i = 0; i < as.length; i++){ CounterCell a; if((a = as[i]) != null) sum += a.value; } } return sum; } |
| private final void fullAddCount(long x, boolean wasUncontended) {} |
| public int size() { // 舊版本方法，和推薦的mappingCount傳回的值基本無差別 longn = sumCount(); return ((n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n); } |
| // 傳回Mappings中的元素個數，官方建議用來替代size。此方法傳回的是一個估計值；如果sumCount時有線程插入或删除，實際數量是和mappingCount不同的。since 1.8 public long mappingCount() { longn = sumCount(); return (n < 0L) ? 0L : n; // ignore transient negative values } |
| private transient volatile long baseCount ; //ConcurrentHashMap中元素個數,基于CAS無鎖更新,但傳回的不一定是目前Map的真實元素個數。 |
5、remove、clear相關：
public void clear() { // 移除所有元素
long delta = 0L; // negative number of deletions
inti = 0;
Node<K,V>[] tab = table;
while (tab != null && i < tab.length) {
intfh;
Node<K,V> f = tabAt(tab, i);
if (f == null) // 為空，直接跳過
++i;
else if ((fh = f.hash) == MOVED) { //檢測到其他線程正對其擴容
//則協助其擴容，然後重置計數器，重新挨個删除元素，避免删除了元素，其他線程又新增元素。
tab = helpTransfer(tab, f);
i = 0; // restart
}
else{
synchronized (f) { // 上鎖
if (tabAt(tab, i) == f) { // 其他線程沒有在此期間操作f
Node<K,V> p = (fh >= 0 ? f :
(finstanceof TreeBin) ?
((TreeBin<K,V>)f).first : null);
while (p != null) { // 首先删除鍊、樹的末尾元素，避免産生大量垃圾
--delta;
p = p.next;
}
setTabAt(tab, i++, null); // 利用CAS無鎖置null
}
}
}
}
if (delta != 0L)
addCount(delta, -1); // 無實際意義，參數check<=1，直接return。
}
public V remove(Object key) { // key為null，将在計算hashCode時報空指針異常
return replaceNode(key, null, null);
}
public boolean remove(Object key, Object value) {
if (key == null)
thrownew NullPointerException();
returnvalue != null && replaceNode(key, null, value) != null;
}
// remove核心方法，注意，這裡的cv才是key-value中的value！
final V replaceNode(Object key, V value, Object cv) {
inthash = spread(key.hashCode());
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; intn, i, fh;
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
break; // 該桶位第一個元素為空，直接跳過
elseif ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f); // 先協助擴容再說
else {
V oldVal = null;
booleanvalidated = false;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
validated = true;
//pred沒看出來有什麼用，全是别人指派給他，他卻不影響其他參數
for (Node<K,V> e = f, pred = null;;) {
K ek;
if (e.hash == hash &&((ek = e.key) == key ||
(ek != null && key.equals(ek)))){//hash且可以相等
V ev = e.val;
// value為null或value和查到的值相等
if (cv == null || cv == ev ||
(ev != null && cv.equals(ev))) {
oldVal = ev;
if (value != null) // replace中調用
e.val = value;
elseif (pred != null)
pred.next = e.next;
else
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
if ((e = e.next) == null)
break;
}
}
elseif (finstanceof TreeBin) { // 以樹的方式find、remove
validated = true;
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> r, p;
if ((r = t.root) != null &&
(p = r.findTreeNode(hash, key, null)) != null) {
V pv = p.val;
if (cv == null || cv == pv ||
(pv != null && cv.equals(pv))) {
oldVal = pv;
if (value != null)
p.val = value;
elseif (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
if (validated) {
if (oldVal != null) {
if (value == null)
addCount(-1L, -1);
returnoldVal;
}
break;
}
}
}
return null;
}
public boolean replace(K key, V oldValue, V newValue) {}
6、其他函數：
public boolean isEmpty() {
return sumCount() <= 0L; // ignore transient negative values
}
參考資料: http://ifeve.com/concurrenthashmap/ http://ifeve.com/java-concurrent-hashmap-2/ 、、、、、、、、、 http://ashkrit.blogspot.com/2014/12/what-is-new-in-java8-concurrenthashmap.html http://blog.csdn.net/u010723709/article/details/48007881 http://yucchi.jp/blog/?p=2048 http://blog.csdn.net/q291611265/article/details/47985145 、、、、、、、、、、 SynchronizedMap：http://blog.sina.com.cn/s/blog_5157093c0100hm3y.html http://blog.csdn.net/yangfanend/article/details/7165742 http://blog.csdn.net/xuefeng0707/article/details/40797085
ArrayList源碼分析（jdk1.8）：http://blog.csdn.net/u010887744/article/details/49496093
HashMap源碼分析（jdk1.8）：http://write.blog.csdn.net/postedit/50346257
ConcurrentHashMap源碼分析--Java8：http://blog.csdn.net/u010887744/article/details/50637030
ThreadLocal源碼分析（JDK8） ：http://blog.csdn.net/u010887744/article/details/54730556
每篇文章都包含 有道雲筆記位址，可直接儲存。
線上查閱JDK源碼：
JDK8：https://github.com/zxiaofan/JDK1.8-Src
JDK7：https://github.com/zxiaofan/JDK_Src_1.7
史上最全Java集合關系圖：http://blog.csdn.net/u010887744/article/details/50575735
歡迎個人轉載，但須在文章頁面明顯位置給出原文連接配接；
未經作者同意必須保留此段聲明、不得随意修改原文、不得用于商業用途，否則保留追究法律責任的權利。
【 CSDN 】：csdn.zxiaofan.com
【GitHub】：github.zxiaofan.com
如有任何問題，歡迎留言。祝君好運！
Life is all about choices！
将來的你一定會感激現在拼命的自己！
![Java小案例——随機數猜測随機數猜測[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)