1.sizeCtl
- 等于0時(shí),表示數(shù)組還沒有進(jìn)行初始化(即數(shù)組為null)
- 大于0時(shí),如果數(shù)組還沒有進(jìn)行初始化,表示數(shù)組的長度,如果數(shù)組已經(jīng)完成初始化,表示擴(kuò)容的閾值
- 小于0時(shí),如果為-1,表示正在數(shù)組初始化,否則設(shè)該值x = - (1 + n) 那么有n個(gè)線程在協(xié)助擴(kuò)容
2.initTable
- 如果table==null ,再判斷sizeCtl是否為-1,如果是則調(diào)用
Thread.yeild()重新回到就緒態(tài)
- 否則通過cas將sizeCtl設(shè)置為-1,并初始化數(shù)組,將sc設(shè)為擴(kuò)容閾值
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
／／ 如果 sizeCtl < 0 ,說明另外的線程執(zhí)行CAS 成功，正在進(jìn)行初始化盅惜。
if ((sc = sizeCtl) < 0)
// 讓出 CPU 使用權(quán)
Thread.yield(); // lost initialization race; just spin
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<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
3. putVal()
- key == null || value == null 拋出異常
- 數(shù)組沒有進(jìn)行初始化,則進(jìn)行初始化
- 如果對(duì)應(yīng)桶沒有存放元素,使用cas來new一個(gè)Node,并賦新值
- 如果桶中第一個(gè)元素的hash值為-1,表示正在擴(kuò)容,當(dāng)前線程回去協(xié)助擴(kuò)容
- 否則對(duì)桶中的第一個(gè)元素作為synchronized對(duì)象鎖.
判斷如果是鏈表(元素哈希值大于0),則遍歷鏈表,如果遇到f的hash值相等,且使用==判斷相等的元素或equals等,則替換value,并break.否則該元素是新的,則向最后插入.
如果是紅黑樹則調(diào)用紅黑樹的插入方法.
- 判斷是否需要將鏈表轉(zhuǎn)為紅黑樹
- 調(diào)用addCount處理當(dāng)前Node的個(gè)數(shù)和是否需要擴(kuò)容
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;;) {
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) {
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)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
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) {
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;
}
}
}
addCount(1L, binCount);
return null;
}
4. 計(jì)算元素個(gè)數(shù)count
- 每個(gè)線程有一個(gè)隨機(jī)值,類似與hashCode
- 數(shù)組如果為空员串，設(shè)置cellsBusy=0,new一個(gè)長度為2的數(shù)據(jù)芍耘，new里面的Cell對(duì)象
- 如果數(shù)組為空苔可，判斷數(shù)組是否在被創(chuàng)建（cellsBusy=1）召边，這時(shí)另一個(gè)線程來了粪滤，數(shù)組為空官套，且busy,那么使用cas加baseCount,加成功則結(jié)束
- 數(shù)組不為空盛正，判斷哈希值&（len-1）對(duì)應(yīng)的位置有沒有對(duì)象删咱，沒有則創(chuàng)建CounterCell對(duì)象，參數(shù)即為傳入的1豪筝。如果成功cas將忙由0改為1痰滋，那么會(huì)將數(shù)組中的對(duì)應(yīng)位置賦值
- 如果有對(duì)象，則cas加1续崖，如果cas失敗敲街，將會(huì)觸發(fā)擴(kuò)容為2倍，如果數(shù)組長度大于等于cpu核數(shù)严望，如果不能繼續(xù)擴(kuò)容了多艇，換個(gè)位置加。
private final void fullAddCount(long x, boolean wasUncontended) {
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) {
if (cellsBusy == 0) { // Try to attach new Cell
CounterCell r = new CounterCell(x); // Optimistic create
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)
collide = false; // At max size or stale
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
}
}
5. transfer
- 判斷每個(gè)線程負(fù)責(zé)多少個(gè)桶,如果單核cpu,負(fù)責(zé)所有桶.否則計(jì)算原數(shù)組長度len/(8*cpu核數(shù)),如果小于16,則為16,否則為該值
- 一個(gè)線程負(fù)責(zé)這些桶,如果做完了,繼續(xù)做,做之前讓sizectl+1,做完了讓sizectl-1,最后判斷兩個(gè)相等則結(jié)束.
- 一個(gè)線程對(duì)一個(gè)桶遷移時(shí),會(huì)使用桶的第一個(gè)元素加鎖,第一次遍歷會(huì)找到鏈表末尾,對(duì)于hash后還在原來index的連續(xù)的末尾的元素,直接放到新數(shù)組的位置,其余的復(fù)制到兩個(gè)對(duì)應(yīng)位置.
