JDK 8ソースコードの分析-concurrenthashmap
372613 ワード
ConccurrenthashMapの主なコアデザインは、*データ構造：1.7に対して単一要素segmentを採用しており、チェーン+レッドツリーストレージ構造*同時安全面を採用しています。読み取りはCAS楽観ロックを採用し、読み取りはSynchronized悲観ロックを採用しています。
二つの関数からソースを見ます。
関数を追加:putVal
要素を取得:get
詳細な実装:
二つの関数からソースを見ます。
関数を追加:putVal
/**
* @param key
* @param value
* @param onlyIfAbsent: key ，false- ，
* ： ， ；absent：
* @return
*/
private V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) {
throw new NullPointerException();
}
int hash = spread(key.hashCode()); // hash
/** ;
* ：
* ：0
* ， 2
* ：>0，
*/
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();
} else if ((f = tabAt(tab, i = (n - 1) & hash)) != null) { tabAt CAS i
// ，
V oldVal = null;
// ，
// n 2 ， (n-1)&hash hash n
if (casTabAt(tab, i, null, new Node<K, V>(hash, key, value, null))) {
// CAS ， ， ； ，
break;
}
if ((fh = f.hash) == MOVED) {
// hash MOVED，
tab = helpTransfer(tab, f);
} else {
synchronized (f) {
if ((tabAt(tab, i) == f)) {
// hash fh 0（ ， ）
//
if (fh >= 0) {
binCount = 1; // 1
for (Node<K, V> e = f; ; ++binCount) {
K ek;
if ((e.hash == hash) && ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
// hash key
oldVal = e.val;
if (!onlyIfAbsent) {
e.val = value;
}
break;
}
//
Node<K, V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<>(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) {
treeifyBin(tab, i);
}
if (oldVal != null) {
return oldVal;
}
break;
}
}
}
// ， 1（ ）
addCount(1L, binCount);
return null;
}
要素を取得:get
//
//Volatile unsafe CAS
public V get(Object key) {
Node<K, V>[] tab;
Node<K, V> e, p;
int n, eh;
K ek;
// hash
int h = spread(key.hashCode());
// table null， hash
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 1.
if ((eh = e.hash) == h) {
// ，
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//hash ， ForwardingNode find nextTable
//eh=-1， ForwardingNode， ， ForwardingNode find nextTable 。
//eh=-2， TreeBin， TreeBin find ， ， find 。
//eh>=0， ， 。
else if (eh < 0) {
// 2.
// 3.
// e ：ForwardingNode TreeBin find
return (p = e.find(h, key)) != null ? p.val : null;
}
// 4.
// eh>0,
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
詳細な実装:
package concurrent;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.Map;
import java.util.concurrent.locks.LockSupport;
/**
* @description:
* @author: zoutai
* @create: 2019/4/14
**/
public class ConcurrentHashMapDemo<K, V> {
private static final long serialVersionUID = 7249069246763182397L;
//
private static final int MAXIMUM_CAPACITY = 1 << 30;
private static final int DEFAULT_CAPACITY = 16;
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
private static final float LOAD_FACTOR = 0.75f;
//
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
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;
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
//
static final int MOVED = -1; // hash for forwarding nodes
// TreeBin
static final int TREEBIN = -2; // hash for roots of trees
static final int RESERVED = -3; // hash for transient reservations
// 0，
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
static final int NCPU = Runtime.getRuntime().availableProcessors(); // CPU
static class Node<K, V> implements Map.Entry<K, V> {
final int hash;
final K key;
// volatile
volatile V val;
volatile Node<K, V> next;
Node(int hash, K key, V val, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
@Override
public K getKey() {
return key;
}
@Override
public V getValue() {
return val;
}
// setValue Node value
// get e.val ，
// CAS
@Override
public V setValue(V value) {
throw new UnsupportedOperationException();
}
@Override
public final int hashCode() {
return key.hashCode() ^ val.hashCode();
}
@Override
public final String toString() {
return key + "=" + val;
}
@Override
public final boolean equals(Object o) {
Object k, v, u;
Map.Entry<?, ?> e;
return ((o instanceof Map.Entry) &&
(k = (e = (Map.Entry<?, ?>) o).getKey()) != null &&
(v = e.getValue()) != null &&
(k == key || k.equals(key)) &&
(v == (u = val) || v.equals(u)));
}
// ， ；
// treeNode， ； ， ，
Node<K, V> find(int h, Object k) {
Node<K, V> e = this;
if (k != null) {
do {
K ek;
if (e.hash == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
} while ((e = e.next) != null);
}
return null;
}
}
// transient- ： ，
// Node 2
transient volatile Node<K, V>[] table;
//
private transient volatile Node<K, V>[] nextTable;
// ， ？
private transient volatile long baseCount;
/**
* hash /
* 1. 0，
* 2. ， ，0.75n；
* 3.-1
* 4.-(1+ )：
*/
private transient volatile int sizeCtl;
// ，
private transient volatile int transferIndex;
private transient volatile int cellsBusy;
//
private transient volatile CounterCell[] counterCells;
public ConcurrentHashMapDemo() {
}
public ConcurrentHashMapDemo(int initialCapacity) {
if (initialCapacity < 0) {
throw new IllegalArgumentException();
}
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}
public ConcurrentHashMapDemo(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
}
public ConcurrentHashMapDemo(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0) {
throw new IllegalArgumentException();
}
if (initialCapacity < concurrencyLevel) {
initialCapacity = concurrencyLevel;
}
long size = (long) (1.0 + (long) initialCapacity / loadFactor);
int cap = (size >= (long) MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int) size);
this.sizeCtl = cap;
}
private int tableSizeFor(int c) {
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;
}
/**
*
*
* @return
*/
public V put(K key, V value) {
return putVal(key, value, false);
}
/**
* @param key
* @param value
* @param onlyIfAbsent: key ，false- ，
* ： ， ；absent：
* @return
*/
private V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) {
throw new NullPointerException();
}
int hash = spread(key.hashCode());
/** ;
* ：
* ：0
* ， 2
* ：>0，
*/
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();
} else if ((f = tabAt(tab, i = (n - 1) & hash)) != null) {
// ，
V oldVal = null;
// ，
// n 2 ， (n-1)&hash hash n
if (casTabAt(tab, i, null, new Node<K, V>(hash, key, value, null))) {
// CAS ， ， ； ，
break;
}
if ((fh = f.hash) == MOVED) {
// hash MOVED，
tab = helpTransfer(tab, f);
} else {
synchronized (f) {
if ((tabAt(tab, i) == f)) {
// hash fh 0（ ， ）
//
if (fh >= 0) {
binCount = 1; // 1
for (Node<K, V> e = f; ; ++binCount) {
K ek;
if ((e.hash == hash) && ((ek = e.key) == key || (ek != null && key.equals(ek)))) {
// hash key
oldVal = e.val;
if (!onlyIfAbsent) {
e.val = value;
}
break;
}
//
Node<K, V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<>(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) {
treeifyBin(tab, i);
}
if (oldVal != null) {
return oldVal;
}
break;
}
}
}
// ， 1（ ）
addCount(1L, binCount);
return null;
}
//
//Volatile unsafe CAS
public V get(Object key) {
Node<K, V>[] tab;
Node<K, V> e, p;
int n, eh;
K ek;
// hash
int h = spread(key.hashCode());
// table null， hash
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 1.
if ((eh = e.hash) == h) {
// ，
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//hash ， ForwardingNode find nextTable
//eh=-1， ForwardingNode， ， ForwardingNode find nextTable 。
//eh=-2， TreeBin， TreeBin find ， ， find 。
//eh>=0， ， 。
else if (eh < 0) {
// 2.
// 3.
// e ：ForwardingNode TreeBin find
return (p = e.find(h, key)) != null ? p.val : null;
}
// 4.
// eh>0,
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
public V remove(Object key) {
return replaceNode(key, null, null);
}
/**
* value: value==null ， 。 value
* cv: ， null value； key-value ，
*
* value
* cv key ， key-value
*/
private V replaceNode(Object key, V value, Object cv) {
int hash = spread(key.hashCode());
for (Node<K, V>[] tab = table; ; ) {
Node<K, V> f;
int i, n, fh;
if ((tab == null) || (n = tab.length) == 0
|| (f = (tabAt(tab, i = (n - 1) & hash))) == null) {
// null， key
break;
} else if ((fh = f.hash) == MOVED) {
// ，
helpTransfer(tab, f);
} else {
// ，
V oldVal = null;
// replace ： ；
// ， ， ， -1
boolean validated = false;
synchronized (f) {
//
if (tabAt(tab, i) == f) {
// >=0
if (fh >= 0) {
//
validated = true;
for (Node<K, V> e = f, pred = null; ; ) {
K ek;
// hash
// (ek=e.key)==key ： ， 100， ；
// (ek!=null && ek.equals(key)) ， new String("hello")；
// key ， ==
if (e.hash == hash && ((ek = e.key) == key || (ek != null && ek.equals(key)))) {
V ev = e.val; //
if (cv == null || ((ev == cv || (ev != null && ev.equals(cv))))) {
// null
oldVal = ev;
//
if (value != null) {
e.val = value;
} else if (pred != null) {
// value null，
// next
pred.next = e.next;
} else {
//pred == null， ， 。 e，
setTabAt(tab, i, e.next);
}
}
// ，
pred = e;
// ， ， ， replace
if ((e = e.next) == null) {
break;
}
}
}
}
//
else if (f instanceof TreeBin) {
validated = true;
TreeBin<K, V> t = (TreeBin<K, V>) f;
TreeNode<K, V> r, p;
// findTreeNode key
if ((r = t.root) != null && (p = r.findTreeNode(hash, key, null)) != null) {
V pv = p.val;
if (cv == null || ((cv == pv || (pv != null && pv.equals(cv))))) {
oldVal = pv;
if (value != null) {
p.val = value; // null ，
} else if (t.removeTreeNode(p)) {
// removeTreeNode ， true ，
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
}
// 1.
if(validated){
// 2.
if(oldVal!=null) {
// 3. ， -1；
if (value == null) {
addCount(-1L, -1);
}
return oldVal;
}
// , null
break;
}
}
}
return null;
}
//
private final void addCount(long x, int check) {
CounterCell[] as;
long b, s;
// CAS baseCount+1
// counterCells null baseCount +1
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))) {
/** ：
* U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x)
* 1 ； 2 ； 3 ； 4
* ；
*/
/**
* as null length 0
* null，ThreadLocalRandom.getProbe()
* CAS
* fullAddCount count
*/
fullAddCount(x, uncontended); //
return;
}
if (check <= 1) {
// ==1，
return;
}
//
s = sumCount();
}
if (check >= 0) {
Node<K, V>[] tab, nt;
int n, sc;
// ， -0.75n
while (s >= (long) (sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
//
int rs = resizeStamp(n);
if (sc < 0) {
// sc<0
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0) {
// ，
// nextTable==null ，
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)) {
//
// sizeCtl 16 rs
// sizeCtl 16 1， (1+nThreads)
// sizeCtl -(1+nThreads)
//
transfer(tab, null);
}
//
s = sumCount();
}
}
}
/**
* Helps transfer if a resize is in progress.
*
* @param tab
* @param f
* @return
*/
private Node<K, V>[] helpTransfer(Node<K, V>[] tab, Node<K, V> f) {
Node<K, V>[] nextTab;
int sc;
if (tab == null && (f instanceof ForwardingNode)
&& (nextTab = ((ForwardingNode<K, V>) f).nextTable) != null) {
// length ， ？
int rs = resizeStamp(tab.length);
while (nextTab == nextTable && tab == table && (sc = sizeCtl) < 0) {
// nextTab tab
// sizeCtl < 0 （ ）
if ((sc >>> RESIZE_STAMP_BITS) != rs || (sc == rs + 1)
|| sc == rs + MAXIMUM_CAPACITY || transferIndex <= 0) {
// sizeCtl 16 rs （ sc 16 ， ）
// sizeCtl == rs + 1 （ ， ）（ sc ==rs 16 + 2， ， sc 。 ，sc rs + 1）
// sizeCtl == rs + 65535 （ ， 65535）
// （ ）
// ， table
break;
}
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
// , sizeCtl + 1, （ ）
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return tab;
}
private final void tryPresize(int size) {
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;
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);
}
} finally {
sizeCtl = sc;
}
}
} else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
else if (tab == table) {
int rs = resizeStamp(n);
if (sc < 0) {
Node<K, V>[] 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);
}
}
}
private 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) {
// hash （MIN_TRANSFER_STRIDE ， ）
stride = MIN_TRANSFER_STRIDE;
}
try {
if (nextTab == null) {
//
Node<K, V>[] nt = (Node<K, V>[]) new Node<?, ?>[n << 1];
nextTab = nt;
}
} catch (Throwable e) {
sizeCtl = Integer.MAX_VALUE;
transferIndex = n;
//
}
int nextn = nextTab.length;
ForwardingNode<K, V> fwd = new ForwardingNode<K, V>(nextTab);
boolean advance = true; //
boolean finishing = false; // to ensure sweep before committing nextTab
for (int i = 0, bound = 0; ; ) {
Node<K, V> f;
int fh;
// hash ,
while (advance) {
//
int nextIndex, nextBound;
// i。
if (--i >= bound || finishing) {
advance = false;
} else if ((nextIndex = transferIndex) < 0) {
// transferIndex<=0， ， ，
i = -1;
advance = false;
} else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
// bound ， transferIndex，， hash
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
// transfe
// ， ，
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
// ， -
nextTable = null;
table = nextTab;
// sizeof 2n*0.75,
sizeCtl = (n << 1) - (n >>> 1);
return;
}
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
/**
， transfer ， sizeCtl = (resizeStamp(n) << RESIZE_STAMP_SHIFT) + 2)
， transfer ， sizeCtl = sizeCtl+1
transfer ， ， sizeCtl = sizeCtl-1
：
sc == (resizeStamp(n) << RESIZE_STAMP_SHIFT) + 2)， (sc - 2) == resizeStamp(n) << RESIZE_STAMP_SHIFT
*/
//
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) {
return;
}
//
finishing = advance = true;
// check
// ， ， i ， if (finishing) {
// ，
i = n; // recheck before commit
}
} else if ((f = tabAt(tab, i)) == null) {
// null，
advance = casTabAt(tab, i, null, fwd);
} else if ((fh = f.hash) == MOVED) {
//
advance = true; // already processed
} else {
// node
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K, V> ln, hn;
//
if (fh >= 0) {
// fh 0-n n-2n ， hash
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;
}
// node ， 2 node
// n ， 0-n ； n ， n-2n
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) {
// ，
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;
}
}
}
}
}
}
//
@sun.misc.Contended
static final class CounterCell {
volatile long value;
CounterCell(long x) {
value = x;
}
}
//
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;
}
/**
* 16
* 16 ， 16
*
* @param n
* @return
*/
static final int resizeStamp(int n) {
return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}
private Node<K, V>[] initTable() {
Node<K, V>[] tab;
int sc;
while ((tab = table) == null || tab.length == 0) {
/**
* ，
*/
if ((sc = sizeCtl) < 0) {
Thread.yield();
} else if (U.compareAndSwapInt(this, SIZECTL, sizeCtl, -1)) {
/**
* ： sizeCtl，
*/
try {
if (tab == null || tab.length == 0) {
// ； 0， ， ， 16
int n = sc > 0 ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K, V>[] nt = (Node<K, V>[]) new Node<?, ?>[n];
table = tab = nt;
// sc 0.75
// n - (n >>> 2) = n - n/4 = 0.75n
//
// threshold loadFactor
sc = sc - (sc >>> 2);
}
} finally {
//
sizeCtl = sc;
}
break;
}
}
return tab;
}
// ， ， ，
// Key hashCode 16 0（ ）。
private int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS; // hash
}
// tab
@SuppressWarnings("unchecked")
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);
}
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) {
// volatile
U.putObjectVolatile(tab, ((long) i << ASHIFT) + ABASE, v);
}
/**
* ： table 。
* nextTable ， 。 key value next null，
* hash -1. find nextTable ， 。
*/
static final class ForwardingNode<K, V> extends Node<K, V> {
final Node<K, V>[] nextTable;
ForwardingNode(Node<K, V>[] tab) {
// hash -1
super(MOVED, null, null, null);
this.nextTable = tab;
}
}
// CAS baseCount ， ， fullAddCount ，
// counterCells， CounterCell， 。
private final void fullAddCount(long x, boolean wasUncontended) {
// wasUncontended: CAS CounterCell -false
int h;
//
if ((h = ThreadLocalRandom.getProbe()) == 0) {
ThreadLocalRandom.localInit(); // force initialization
h = ThreadLocalRandom.getProbe();
wasUncontended = true;
}
boolean collide = false; // True if last slot nonempty
for (; ; ) {
CounterCell[] as;
CounterCell a;
int n;
long v;
//
if ((as = counterCells) != null && (n = as.length) > 0) {
//
if ((a = as[(n - 1) & h]) == null) {
// cellsBusy ； 0，
if (cellsBusy == 0) { // Try to attach new Cell
CounterCell r = new CounterCell(x); // Optimistic create
// 1
if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean created = false;
try { // Recheck under lock
CounterCell[] rs;
int m, j;
if ((rs = counterCells) != null &&
(m = rs.length) > 0 &&
rs[j = (m - 1) & h] == null) {
//
rs[j] = r;
created = true;
}
} finally {
// ，
cellsBusy = 0;
}
if (created) {
// ，
break;
} //
continue; // Slot is now non-empty
}
}
collide = false;
} else if (!wasUncontended) {
// CAS already known to fail
// ， ， ，
wasUncontended = true; // Continue after rehash
}
else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x)) {
// ，
break;
}
else if (counterCells != as || n >= NCPU)
// counterCells ： ，
// cpu ？
collide = false;
else if (!collide)
collide = true;
else if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
//
try {
if (counterCells == as) {// Expand table unless stale
CounterCell[] rs = new CounterCell[n << 1];
for (int i = 0; i < n; ++i)
rs[i] = as[i];
counterCells = rs;
}
} finally {
cellsBusy = 0;
}
collide = false;
continue; // Retry with expanded table
}
h = ThreadLocalRandom.advanceProbe(h);
} else if (cellsBusy == 0 && counterCells == as &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean init = false;
try { // Initialize table
if (counterCells == as) {
CounterCell[] rs = new CounterCell[2];
rs[h & 1] = new CounterCell(x);
counterCells = rs;
init = true;
}
} finally {
cellsBusy = 0;
}
if (init) {
break;
}
} else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
break; // Fall back on using base
}
}
private final void treeifyBin(Node<K, V>[] tab, int index) {
Node<K, V> b;
int n, sc;
if (tab != null) {
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
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));
}
}
}
}
}
static <K, V> Node<K, V> untreeify(Node<K, V> b) {
Node<K, V> hd = null, tl = null;
for (Node<K, V> q = b; q != null; q = q.next) {
Node<K, V> p = new Node<K, V>(q.hash, q.key, q.val, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
// ： >8， TreeNode
// HashMap ， ，
// TreeNode TreeBin ， 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(int hash, K key, V val, Node<K, V> next,
TreeNode<K, V> parent) {
super(hash, key, val, next);
this.parent = parent;
}
Node<K, V> find(int h, Object k) {
return findTreeNode(h, k, null);
}
/**
* Returns the TreeNode (or null if not found) for the given key
* starting at given root.
*/
final TreeNode<K, V> findTreeNode(int h, Object k, Class<?> kc) {
if (k != null) {
TreeNode<K, V> p = this;
do {
int ph, dir;
K pk;
TreeNode<K, V> q;
TreeNode<K, V> pl = p.left, pr = p.right;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.findTreeNode(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
}
return null;
}
}
// TreeNode
static final class TreeBin<K, V> extends Node<K, V> {
TreeNode<K, V> root;
volatile TreeNode<K, V> first;
volatile Thread waiter;
volatile int lockState;
// 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; // increment value for setting read lock
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
/**
* Creates bin with initial set of nodes headed by b.
*/
TreeBin(TreeNode<K, V> b) {
super(TREEBIN, null, null, null);
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;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K, V> p = r; ; ) {
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((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);
}
/**
* Acquires write lock for tree restructuring.
*/
private final void lockRoot() {
if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
contendedLock(); // offload to separate method
}
/**
* Releases write lock for tree restructuring.
*/
private final void unlockRoot() {
lockState = 0;
}
/**
* Possibly blocks awaiting root lock.
*/
private final void contendedLock() {
boolean waiting = false;
for (int s; ; ) {
if (((s = lockState) & ~WAITER) == 0) {
if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
if (waiting)
waiter = null;
return;
}
} else if ((s & WAITER) == 0) {
if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
waiting = true;
waiter = Thread.currentThread();
}
} else if (waiting)
LockSupport.park(this);
}
}
/**
* Returns matching node or null if none. Tries to search
* using tree comparisons from root, but continues linear
* search when lock not available.
*/
final Node<K, V> find(int h, Object k) {
if (k != null) {
for (Node<K, V> e = first; e != null; ) {
int s;
K ek;
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<K, V> r, p;
try {
p = ((r = root) == null ? null :
r.findTreeNode(h, k, null));
} finally {
Thread w;
if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
(READER | WAITER) && (w = waiter) != null)
LockSupport.unpark(w);
}
return p;
}
}
}
return null;
}
/**
* Finds or adds a node.
*
* @return null if added
*/
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 {
lockRoot();
try {
root = balanceInsertion(root, x);
} finally {
unlockRoot();
}
}
break;
}
}
assert checkInvariants(root);
return null;
}
/**
* Removes the given node, that must be present before this
* call. This is messier than typical red-black deletion code
* because we cannot swap the contents of an interior node
* with a leaf successor that is pinned by "next" pointers
* that are accessible independently of lock. So instead we
* swap the tree linkages.
*
* @return true if now too small, so should be untreeified
*/
final boolean removeTreeNode(TreeNode<K, V> p) {
TreeNode<K, V> next = (TreeNode<K, V>) p.next;
TreeNode<K, V> pred = p.prev; // unlink traversal pointers
TreeNode<K, V> r, rl;
if (pred == null)
first = next;
else
pred.next = next;
if (next != null)
next.prev = pred;
if (first == null) {
root = null;
return true;
}
if ((r = root) == null || r.right == null || // too small
(rl = r.left) == null || rl.left == null)
return true;
lockRoot();
try {
TreeNode<K, V> replacement;
TreeNode<K, V> pl = p.left;
TreeNode<K, V> pr = p.right;
if (pl != null && pr != null) {
TreeNode<K, V> 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<K, V> sr = s.right;
TreeNode<K, V> pp = p.parent;
if (s == pr) { // p was s's direct parent
p.parent = s;
s.right = p;
} else {
TreeNode<K, V> 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<K, V> 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<K, V> 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;
}
/* ------------------------------------------------------------ */
// Red-black tree methods, all adapted from CLR
static <K, V> TreeNode<K, V> rotateLeft(TreeNode<K, V> root,
TreeNode<K, V> p) {
TreeNode<K, V> r, pp, rl;
if (p != null && (r = p.right) != null) {
if ((rl = p.right = r.left) != null)
rl.parent = p;
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;
else if (pp.left == p)
pp.left = r;
else
pp.right = r;
r.left = p;
p.parent = r;
}
return root;
}
static <K, V> TreeNode<K, V> rotateRight(TreeNode<K, V> root,
TreeNode<K, V> p) {
TreeNode<K, V> l, pp, lr;
if (p != null && (l = p.left) != null) {
if ((lr = p.left = l.right) != null) {
lr.parent = p;
}
if ((pp = l.parent = p.parent) == null) {
(root = l).red = false;
} else if (pp.right == p) {
pp.right = l;
} else {
pp.left = l;
}
l.right = p;
p.parent = l;
}
return root;
}
static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root,
TreeNode<K, V> x) {
x.red = true;
for (TreeNode<K, V> xp, xpp, xppl, xppr; ; ) {
if ((xp = x.parent) == null) {
x.red = false;
return x;
} else if (!xp.red || (xpp = xp.parent) == null)
return root;
if (xp == (xppl = xpp.left)) {
if ((xppr = xpp.right) != null && xppr.red) {
xppr.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
} else {
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
} else {
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
} else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
static <K, V> TreeNode<K, V> balanceDeletion(TreeNode<K, V> root,
TreeNode<K, V> x) {
for (TreeNode<K, V> xp, xpl, xpr; ; ) {
if (x == null || x == root)
return root;
else if ((xp = x.parent) == null) {
x.red = false;
return x;
} else if (x.red) {
x.red = false;
return root;
} else if ((xpl = xp.left) == x) {
if ((xpr = xp.right) != null && xpr.red) {
xpr.red = false;
xp.red = true;
root = rotateLeft(root, xp);
xpr = (xp = x.parent) == null ? null : xp.right;
}
if (xpr == null)
x = xp;
else {
TreeNode<K, V> sl = xpr.left, sr = xpr.right;
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
xpr.red = true;
x = xp;
} else {
if (sr == null || !sr.red) {
if (sl != null)
sl.red = false;
xpr.red = true;
root = rotateRight(root, xpr);
xpr = (xp = x.parent) == null ?
null : xp.right;
}
if (xpr != null) {
xpr.red = (xp == null) ? false : xp.red;
if ((sr = xpr.right) != null)
sr.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateLeft(root, xp);
}
x = root;
}
}
} else { // symmetric
if (xpl != null && xpl.red) {
xpl.red = false;
xp.red = true;
root = rotateRight(root, xp);
xpl = (xp = x.parent) == null ? null : xp.left;
}
if (xpl == null)
x = xp;
else {
TreeNode<K, V> sl = xpl.left, sr = xpl.right;
if ((sl == null || !sl.red) &&
(sr == null || !sr.red)) {
xpl.red = true;
x = xp;
} else {
if (sl == null || !sl.red) {
if (sr != null)
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);
xpl = (xp = x.parent) == null ?
null : xp.left;
}
if (xpl != null) {
xpl.red = (xp == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}
x = root;
}
}
}
}
}
/**
* Recursive invariant check
*/
static <K, V> boolean checkInvariants(TreeNode<K, V> t) {
TreeNode<K, V> tp = t.parent, tl = t.left, tr = t.right,
tb = t.prev, tn = (TreeNode<K, V>) t.next;
if (tb != null && tb.next != t) {
return false;
}
if (tn != null && tn.prev != t) {
return false;
}
if (tp != null && t != tp.left && t != tp.right) {
return false;
}
if (tl != null && (tl.parent != t || tl.hash > t.hash)) {
return false;
}
if (tr != null && (tr.parent != t || tr.hash < t.hash)) {
return false;
}
if (t.red && tl != null && tl.red && tr != null && tr.red) {
return false;
}
if (tl != null && !checkInvariants(tl)) {
return false;
}
return tr == null || checkInvariants(tr);
}
private static final sun.misc.Unsafe U;
private static final long LOCKSTATE;
static {
try {
U = sun.misc.Unsafe.getUnsafe();
Class<?> k = TreeBin.class;
LOCKSTATE = U.objectFieldOffset
(k.getDeclaredField("lockState"));
} catch (Exception e) {
throw new Error(e);
}
}
}
static Class<?> comparableClassFor(Object x) {
if (x instanceof Comparable) {
Class<?> c;
Type[] ts, as;
Type t;
ParameterizedType p;
if ((c = x.getClass()) == String.class) // bypass checks
{
return c;
}
if ((ts = c.getGenericInterfaces()) != null) {
for (int i = 0; i < ts.length; ++i) {
if (((t = ts[i]) instanceof ParameterizedType) &&
((p = (ParameterizedType) t).getRawType() ==
Comparable.class) &&
(as = p.getActualTypeArguments()) != null &&
as.length == 1 && as[0] == c) // type arg is c
{
return c;
}
}
}
}
return null;
}
@SuppressWarnings({"rawtypes", "unchecked"}) // for cast to Comparable
static int compareComparables(Class<?> kc, Object k, Object x) {
return (x == null || x.getClass() != kc ? 0 :
((Comparable) k).compareTo(x));
}
// Unsafe mechanics
// U.compareAndSwapXXX : ，
/**
* ，
* ， ， 。
* ， 。
* ，SVN 。
*/
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 = ConcurrentHashMapDemo.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);
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);
}
}
}