一些常量：
-
- 一些特殊的hash值
//特殊的node hash值 在后續(xù)使用中判斷是否在擴(kuò)容浩考、是否為樹(shù)節(jié)點(diǎn)等 static final int MOVED = -1; // hash for forwarding nodes static final int TREEBIN = -2; // hash for roots of trees static final int RESERVED = -3; // hash for transient reservations
-
- sizeCtl(很有用)
/** * 初始化時(shí)值為-1 * 擴(kuò)容時(shí)sizeCtl的低位為擴(kuò)容線程數(shù) * 如果table未初始化岂嗓，表示table需要初始化的大小。 * 如果table初始化完成狞谱，表示table的容量，默認(rèn)是table大小的0.75倍 * 后續(xù)判斷需要用到這個(gè) */ private transient volatile int sizeCtl; -
- 鏈表和樹(shù)轉(zhuǎn)換條件
//桶的數(shù)量大于64時(shí)轉(zhuǎn)紅黑樹(shù) static final int MIN_TREEIFY_CAPACITY = 64; //鏈表和樹(shù)轉(zhuǎn)換的閾值 static final int TREEIFY_THRESHOLD = 8;
一些方法：
? HASH_BITS = 0x7fffffff
? 先用高16位異或然后和HASH_BITS進(jìn)行&計(jì)算 禁漓，減少碰撞
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
? 結(jié)果為最小的可容納值（2的冪次）跟衅，如輸入18結(jié)果為32
private static final 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;
}
? 相對(duì)擴(kuò)容來(lái)說(shuō)，get播歼、putVal比較簡(jiǎn)單- -
? 先說(shuō)一下伶跷，當(dāng)表的長(zhǎng)度為2的冪次時(shí)，(h % n) 和 (h & (n - 1))效果相同秘狞，以此來(lái)確定槽的位置叭莫。
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
//用key的hash重新散列，用來(lái)獲取槽的位置
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
//獲取槽的位置
(e = tabAt(tab, (n - 1) & h)) != null) {
// e 為對(duì)應(yīng)槽的初始Node
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//擴(kuò)容中
else if (eh < 0)
//在槽中遍歷查找烁试，正在擴(kuò)容所以節(jié)點(diǎn)為ForwardingNode,ForwardingNode中的find實(shí)際上是在擴(kuò)容后的新表中進(jìn)行查找
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;
}
? put實(shí)際上調(diào)用putVal
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
//再次計(jì)算
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)
//當(dāng)前table為空則執(zhí)行初始化
tab = initTable();
//每次循環(huán)都重新計(jì)算槽的位置（防止中途擴(kuò)容導(dǎo)致槽位置變動(dòng)）
//f為對(duì)應(yīng)槽位置的節(jié)點(diǎn)雇初，i為對(duì)應(yīng)槽位置，如果對(duì)應(yīng)槽的位置是空的就直接cas添加
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
}
//MOVED = -1减响，F(xiàn)orwardingNode繼承Node,只在擴(kuò)容中使用,它的key,value,next全是null,hash=-1
else if ((fh = f.hash) == MOVED)
//幫助擴(kuò)容
tab = helpTransfer(tab, f);
else {
V oldVal = null;
//同步鎖
synchronized (f) {
//對(duì)應(yīng)槽的初始節(jié)點(diǎn)為f則繼續(xù)靖诗，否則頭節(jié)點(diǎn)發(fā)生改變郭怪，重新循環(huán)
if (tabAt(tab, i) == f) {
//是一個(gè)鏈表，不是樹(shù)
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
//存在相同的key,替換value
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;
//不存在相同的key刊橘，在最后添加節(jié)點(diǎn)
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
//為樹(shù)的根節(jié)點(diǎn)鄙才，用樹(shù)的方式添加(紅黑樹(shù)的根節(jié)點(diǎn)hash值為-2)
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;
}
}
}
}
//判斷要不要轉(zhuǎn)成樹(shù)
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//元素?cái)?shù)量+1，看看要不要擴(kuò)容
addCount(1L, binCount);
return null;
}
? 簡(jiǎn)單的結(jié)束促绵，transfer開(kāi)始攒庵，orz 看了好久還是只有大概TAT
? 之前說(shuō)的ForwardingNode，這個(gè)只有擴(kuò)容時(shí)會(huì)用到
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) {
// loop to avoid arbitrarily deep recursion on forwarding nodes
outer: for (Node<K,V>[] tab = nextTable;;) {
Node<K,V> 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;
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<K,V>)e).nextTable;
continue outer;
}
else
return e.find(h, k);
}
if ((e = e.next) == null)
return null;
}
}
}
}
? transfer
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
//NCPU=cpu核心線程數(shù) MIN_TRANSFER_STRIDE=16
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
//如果nextTab為null败晴，先進(jìn)行一次初始化
//外圍保證第一個(gè)線程調(diào)用此方法時(shí)浓冒，參數(shù) nextTab 為 null
//之后參與協(xié)助的線程調(diào)用時(shí)，nextTab不會(huì)為null
if (nextTab == null) { // initiating
try {
//構(gòu)造一個(gè)nextTable對(duì)象尖坤，容量為原來(lái)的兩倍
@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是過(guò)渡的table表裆蒸，別的地方基本用不到
nextTable = nextTab;
transferIndex = n;
}
int nextn = nextTab.length;
//構(gòu)造一個(gè)節(jié)點(diǎn)，用于標(biāo)記(之前代碼中有碰到過(guò))
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
//這個(gè)值為true說(shuō)明節(jié)點(diǎn)已經(jīng)處理
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
//這邊圈定范圍
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
//一次遍歷原h(huán)ash表的節(jié)點(diǎn)
//簡(jiǎn)單理解：i 指向了 transferIndex糖驴，bound 指向了 transferIndex-stride
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
//將 transferIndex 值賦給 nextIndex
//這里 transferIndex 一旦小于等于 0僚祷，說(shuō)明原數(shù)組的所有位置都有相應(yīng)的線程去處理
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
//看括號(hào)中的代碼，nextBound 是這次遷移任務(wù)的邊界贮缕，注意辙谜，是從后往前
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
//如果所有的節(jié)點(diǎn)都已經(jīng)完成復(fù)制工作 就把nextTable賦值給table 清空臨時(shí)對(duì)象nextTable
if (finishing) {
nextTable = null;
table = nextTab;
//擴(kuò)容閾值設(shè)置為原來(lái)容量的1.5倍 依然相當(dāng)于現(xiàn)在容量的0.75倍
sizeCtl = (n << 1) - (n >>> 1);
return;
}
//sizeCtl 在遷移前會(huì)設(shè)置為 (rs << RESIZE_STAMP_SHIFT) + 2
//然后，每有一個(gè)線程參與遷移就會(huì)將 sizeCtl 加 1感昼，
//這里使用 CAS 操作對(duì) sizeCtl 進(jìn)行減 1装哆，代表做完了屬于自己的任務(wù)
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
//任務(wù)結(jié)束，方法退出
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
//到這里定嗓，說(shuō)明 (sc - 2) == resizeStamp(n) << RESIZE_STAMP_SHIFT蜕琴，
//也就是說(shuō)，所有的遷移任務(wù)都做完了宵溅，也就會(huì)進(jìn)入到上面的 if(finishing){} 分支了
finishing = advance = true;
i = n; // recheck before commit
}
}
//如果遍歷到的節(jié)點(diǎn)為空 則放入ForwardingNode指針
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
//存在ForwardingNode,已經(jīng)處理了,跳過(guò)
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
//鎖
synchronized (f) {
//和putVal一樣,檢查節(jié)點(diǎn)
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
if (fh >= 0) {
//下面這一塊和 Java7 中的 ConcurrentHashMap 遷移是差不多的凌简，
//需要將鏈表一分為二，
//找到原鏈表中的 lastRun恃逻，然后 lastRun 及其之后的節(jié)點(diǎn)是一起進(jìn)行遷移的
//lastRun 之前的節(jié)點(diǎn)需要進(jìn)行克隆雏搂，然后分到兩個(gè)鏈表中
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);
}
// 其中的一個(gè)鏈表放在新數(shù)組的位置 i
setTabAt(nextTab, i, ln);
// 另一個(gè)鏈表放在新數(shù)組的位置 i+n
setTabAt(nextTab, i + n, hn);
// 將原數(shù)組該位置處設(shè)置為 fwd，代表該位置已經(jīng)處理完畢寇损，
// 其他線程一旦看到該位置的 hash 值為 MOVED凸郑，就不會(huì)進(jìn)行遷移了
setTabAt(tab, i, fwd);
advance = true;
}
else if (f instanceof TreeBin) {
// 紅黑樹(shù)的遷移
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;
}
}
// 如果一分為二后，節(jié)點(diǎn)數(shù)少于 8矛市，那么將紅黑樹(shù)轉(zhuǎn)換回鏈表
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;
// 將 ln 放置在新數(shù)組的位置 i
setTabAt(nextTab, i, ln);
// 將 hn 放置在新數(shù)組的位置 i+n
setTabAt(nextTab, i + n, hn);
// 將原數(shù)組該位置處設(shè)置為 fwd芙沥，代表該位置已經(jīng)處理完畢，
// 其他線程一旦看到該位置的 hash 值為 MOVED，就不會(huì)進(jìn)行遷移了
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
? tryPresize
? 首先只有兩個(gè)地方調(diào)用了這個(gè)方法
putAll(Map<? extends K, ? extends V> m) 中 tryPresize(m.size())而昨；
-
treeifyBin(Node<K,V>[] tab, int index) 中
if ((n = tab.length) < MIN_TREEIFY_CAPACITY) //這邊已經(jīng)擴(kuò)了一倍 tryPresize(n << 1);
private final void tryPresize(int size) {
//這邊再次翻倍救氯，就是擴(kuò)到了4倍，emmmm不是很理解這個(gè)
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;
//這邊源碼錯(cuò)了詳見(jiàn)
//https://bugs.java.com/bugdatabase/view_bug.do?bug_id=JDK-8214427
//修正為 (sc >>> RESIZE_STAMP_SHIFT) == rs + 1 || (sc >>> RESIZE_STAMP_SHIFT) == rs + MAX_RESIZERS
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);
}
}
}
