putVal()方法
/**
* Implementation for put and putIfAbsent
*/
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
// 通过对hash值的计算达到减少hash冲突的目的
int hash = spread(key.hashCode());
// 用于统计链表上节点的数量
int binCount = 0;
// 通过自旋初始化、put值等操作
for (Node<K, V>[] tab = table; ; ) {
Node<K, V> f;
int n, i, fh;
if (tab == null || (n = tab.length) == 0)
// 当Node数组未初始化时，初始化Node数组
tab = initTable();
// 此处通过n-1获取节点f，那么当扩容时由于n发生改变，有些节点可能取不到了，所以在扩容的过程中会涉及到数据迁移
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 如果从table中取到的node为空，则可以用了存储
// 通过CAS操作把新创建的节点赋值给这个空节点
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)
// 协助扩容（协助当前正在扩容的线程进行node迁移）
tab = helpTransfer(tab, f);
else { //key已经存在
V oldVal = null;
// f是通过key获取到的node，对node加锁
synchronized (f) {
// 确保f未被其他线程修改
if (tabAt(tab, i) == f) {
// hash值大于等于0为普通node或链表
if (fh >= 0) {
// 链表节点数从1开始累加
binCount = 1;
for (Node<K, V> e = f; ; ++binCount) {
K ek;
// table中取到的node的hash值和当前key的hash值相同
// 且(key的地址相同或key的值相同)
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
// 覆盖已存在的node
if (!onlyIfAbsent)
e.val = value;
// 跳出循环，binCount依旧是1
break;
}
Node<K, V> pred = e;
// 不覆盖的情况则加入到链表
if ((e = e.next) == null) {
pred.next = new Node<K, V>(hash, key,
value, null);
// 跳出循环，binCount依旧是1
break;
}
}
} else if (f instanceof TreeBin) { // 如果node是红黑树
// 红黑树，红黑树我不了解，不做注释
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) {
// 当链表长度超过8个，则转为红黑树
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
// 增加元素个数
addCount(1L, binCount);
return null;
}
initTable()方法
/**
* Initializes table, using the size recorded in sizeCtl.
*/
private final Node<K, V>[] initTable() {
// 局部变量性能要比直接使用成员变量高
Node<K, V>[] tab;
int sc;
// 未初始化，while循环用于CAS的自旋操作
while ((tab = table) == null || tab.length == 0) {
// sizeCtr用于标记table的初始化和扩容
// 小于0时代表有其他线程正在初始化
if ((sc = sizeCtl) < 0)
// 让出cpu时间片
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { //此时sizeCtl大于等于0，通过CAS把sizeCtl改为-1，表示当前线程正在初始化table表
// CAS操作使得只有一个线程能够进入
// 改为-1成功，初始化table
try {
// 再次检查，因为可能有多个线程同时进入while循环，有可能有其他线程已经初始化了
if ((tab = table) == null || tab.length == 0) {
// 获取table的容量
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
// 创建node节点数组
@SuppressWarnings("unchecked")
Node<K, V>[] nt = (Node<K, V>[]) new Node<?, ?>[n];
table = tab = nt;
// 等同于n * 0.75
sc = n - (n >>> 2);
}
} finally {
// 因为只有一个线程能访问到，无需再使用CAS操作
sizeCtl = sc;
}
break;
}
}
return tab;
}
addCount()方法
/**
* Adds to count, and if table is too small and not already
* resizing, initiates transfer. If already resizing, helps
* perform transfer if work is available. Rechecks occupancy
* after a transfer to see if another resize is already needed
* because resizings are lagging additions.
*
* @param x the count to add
* @param check if <0, don't check resize, if <= 1 only check if uncontended
*/
private final void addCount(long x, int check) {
CounterCell[] as;
long b, s;
// 由于并发时自旋修改baseCount值效率是很低的，故此引入了counterCells
// 随机取一个counterCell进行累加操作
// 最终累加counterCells的值再加上baseCount的值
// if判断内 第一次put值，counterCells还未初始化为null
// if判断内 通过CAS操作尝试修改baseCount值为：baseCount+1，x值由putVal方法传入，为1
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
// counterCells未初始化或者修改baseCount失败（有竞争）则进入判断体
CounterCell a;
long v;
int m;
// 必定有竞争
boolean uncontended = true;
if (as == null || (m = as.length - 1) < 0 || // counterCells未初始化或长度为0
(a = as[ThreadLocalRandom.getProbe() & m]) == null || // 随机取出的counterCell为null
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) { // 有竞争，更新当前线程对应的counterCell值
// 更新counterCell也失败了，执行fullAndCount方法，通过自旋多次尝试
fullAddCount(x, uncontended);
return;
}
// 链表长度等于1或小于等于0，不需要检查是否需要扩容
if (check <= 1)
return;
// 累加counterCell再加上baseCount
s = sumCount();
}
// 链表长度大于0，需要检查是否需要扩容
if (check >= 0) {
Node<K, V>[] tab, nt;
int n, sc;
// 自旋CAS操作更新阈值
// 元素个数大于等于阈值且小于允许的最大容量值，则进行扩容处理
while (s >= (long) (sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
// todo resizeStamp
int rs = resizeStamp(n);
// sizeCtl小于0表示已经有其他线程正在扩容
if (sc < 0) {
// rs在addCount方法中左移了16位，将低位变高位，低位用来存储有多少个线程参与扩容
// 所以这里要拿到高位的值，反向右移16位后再和sc比较
// 当扩容结束后由于sc会减去1（有一个线程在扩容就会+1），所以值不同则肯定是已经结束扩容了
// sc == rs + MAX_RESIZERS代表已经达到16位存储线程数的总大小了，新线程存不进去了
// transferIndex <= 0说明已经无法再把当前table分段了，不需要协助扩容了
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
// 协助扩容，sc + 1
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
// 协助扩容
transfer(tab, nt);
} else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
// 第一次扩容，rs左移16位后 + 2，即rs的值低位变高位，再用空出来的低位 + 2来记录扩容线程数
// 调整sizeCtl大小后进行扩容转移数据
transfer(tab, null);
// 扩容后重新计算元素数量
s = sumCount();
}
}
}
transfer()方法
/**
* Moves and/or copies the nodes in each bin to new table. See
* above for explanation.
*/
private final void transfer(Node<K, V>[] tab, Node<K, V>[] nextTab) {
// 为了讲清楚以下逻辑，我们假定tab大小是32，那么n = 32，第一个线程进入扩容，nextTab为null
int n = tab.length, stride;
// 依然是分段思想，每个线程负责一段数据的转移，这里判断后确保最小转移的步长（每段的长度）值为16，
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
if (nextTab == null) { // initiating
try {
// 创建一个大小是当前table大小的2倍的table，并赋值给nextTable，当协助扩容时将会被再次传入transfer方法
@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 = 32，而transferIndex加了volatile关键字，保证了多线程下的可见性
transferIndex = n;
}
// 32 * 2 = 64
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;
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))) {
// 第一个线程进入while循环时，按照假定值，if中nextBound = 32 - 16 = 16，并通过cas更新transferIndex = 16，那么bound = 16
// 第二个线程进入while循环时，由于nextIndex被重新赋值，变成了16，那么nextBound = 0，并通过cas更新transferIndex = 0
bound = nextBound;
// 第一个线程进入while循环时，i = 32 - 1 = 31，虽然修改了transferIndex，但是nextIndex还是之前的值32
// 第二个线程进入while循环时，i = 16 - 1 = 15
i = nextIndex - 1;
advance = false;
}
}
// 以上可以看到两个线程将tab分成了两部分，一部分 0 - 15，另一部分 16 - 31，各负责一部分的数据迁移
// 第一个线程，i = 31，n = 32，nextn = 64
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)
// 如果table下标为31的节点为null，则把用来标记的节点fwd替换到i的位置 todo，fwd
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
// 进入到else中则是开始转移节点f
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K, V> ln, hn;
if (fh >= 0) { // 普通节点，非tree
// 通过hash值与上table长度计算是低位还是高位，低位不需要迁移数据
// 高位因为f = tabAt(tab, i = (n - 1) & hash)计算的node节点和扩容前的节点不同，导致get不到值，需要数据迁移
// runBit要么等于0，要么不等于0
int runBit = fh & n;
Node<K, V> lastRun = f;
// f有下一个节点，计算下一个节点的runBit，循环下去，拿到链表最后一个节点的runBit
for (Node<K, V> p = f.next; p != null; p = p.next) {
// 计算下一个节点的runBit
int b = p.hash & n;
// 当f的runBit == 0，下一个节点的runBit不等于0时，那么被赋值为下一个节点的runBit，反之亦然，循环交替，
// 当遇到相邻两个节点的runBit都等于0或都不等于0时跳过，直到最后一个节点
// lastRun则是中文括号节点，以下几种情况
// [0] [≠0] [0] 【≠0】 [≠0]
// [0] [≠0] [0] [≠0] 【0】
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
// f链表的最后一个发生高低位变化的节点的runBit == 0，那么这个节点为低位节点，反之为高位节点
if (runBit == 0) {
// 低位节点
ln = lastRun;
hn = null;
} else {
// 高位节点
hn = lastRun;
ln = null;
}
// 从f节点开始迭代链表
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)
// Node构造方法里的ln是之前获取到的链表中最后一个发生高低位变化的低位节点（若这个节点为高位，那么ln=null）
// 例如：[0] [≠0] [0] 【≠0】 [≠0]，此时ln为null，即ln被赋值为next节点为null的新的node节点
// 当下次循环，由于当前节点仍为低位节点，ln不为null，最终会从后往前构建出一个全部用低位节点构成的链表
ln = new Node<K, V>(ph, pk, pv, ln);
else
// 与上面低位构建链表相同，从后往前构建出一个高位节点组成的链表
hn = new Node<K, V>(ph, pk, pv, hn);
}
// 低位迁移，i因为就是原本的f节点的数组下标，所以等同于没有迁移（数组下标没变，但是迁移到了新的table中）
setTabAt(nextTab, i, ln);
// 高位迁移，迁移到（i + n）的位置，即迁移到了新的table的（i + 原数组长度）的位置
setTabAt(nextTab, i + n, hn);
// 把创建出的fwd节点放到i的位置，表示正在迁移的位置（i的值在大循环里是递减的，因为线程参与扩容的先后顺序分配到的扩容段是从后往前的），
// 根据前面的计算，第一个线程拿到的是16-31段，第二个线程拿到的是0-15段
// 所以fwd的位置也是从后往前走的
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;
}
}
}
}
}
}
helpTransfer()方法
/**
* Helps transfer if a resize is in progress.
*/
final Node<K, V>[] helpTransfer(Node<K, V>[] tab, Node<K, V> f) {
Node<K, V>[] nextTab;
int sc;
// 扩容前table的最后一个元素位置被替换成ForwardingNode
// 当前节点是ForwardingNode且nextTab（在transfer方法中创建的大小是当前table两倍大小的table）不为空
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K, V>) f).nextTable) != null) {
int rs = resizeStamp(tab.length);
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
// rs在addCount方法中左移了16位，将低位变高位，低位用来存储有多少个线程参与扩容
// 所以这里要拿到高位的值，反向右移16位后再和sc比较
// 当扩容结束后由于sc会减去1（有一个线程在扩容就会+1），所以值不同则肯定是已经结束扩容了
// sc == rs + MAX_RESIZERS代表已经达到16位存储线程数的总大小了，新线程存不进去了
// transferIndex <= 0说明已经无法再把当前table分段了，不需要协助扩容了
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
// 当前线程协助扩容，增加扩容线程数
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
// nextTab有值，协助扩容
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}
fullAddCount()方法
// See LongAdder version for explanation
private final void fullAddCount(long x, boolean wasUncontended) {
int h;
// 当前线程的探针hash值未初始化，没有竞争
if ((h = ThreadLocalRandom.getProbe()) == 0) {
ThreadLocalRandom.localInit(); // force initialization
h = ThreadLocalRandom.getProbe();
wasUncontended = true;
}
boolean collide = false; // True if last slot nonempty
// 自旋设置counterCell值
for (; ; ) {
CounterCell[] as;
CounterCell a;
int n;
long v;
// counterCells有值则进入计算
if ((as = counterCells) != null && (n = as.length) > 0) {
// 通过当前线程探针hash值获取到一个counterCell且counterCell未初始化
if ((a = as[(n - 1) & h]) == null) {
// counterCells不繁忙
if (cellsBusy == 0) { // Try to attach new Cell
CounterCell r = new CounterCell(x); // Optimistic create
// 设置counterCells繁忙，防止其他线程操作此counterCell
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) {
// 赋值counterCell
rs[j] = r;
created = true;
}
} finally {
// 设置counterCells不繁忙
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: couterCells已经初始化过了，就尝试修改对应counterCell值
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)) {
// 初始化counterCells
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)) // 最后再尝试一次直接更新baseCount
break; // Fall back on using base
}
}
relaceNode()方法
/**
* Implementation for the four public remove/replace methods:
* Replaces node value with v, conditional upon match of cv if
* non-null. If resulting value is null, delete.
*/
final V replaceNode(Object key, V value, Object cv) {
int hash = spread(key.hashCode());
for (Node<K, V>[] tab = table; ; ) {
Node<K, V> f;
int n, i, fh;
// 表未初始化或元素为null
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
break;
// 节点标记为迁移，说明有其他线程在扩容，协助扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
boolean validated = false;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
validated = true;
for (Node<K, V> e = f, pred = null; ; ) {
K ek;
// key完全相同
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
V ev = e.val;
if (cv == null || cv == ev ||
(ev != null && cv.equals(ev))) {
oldVal = ev;
if (value != null)
// 替换值
e.val = value;
// 第一次循环pred为null，第二次循环被赋值为e，即f节点
// 而第二次循环的时候因为在else里已经把i节点替换为next节点，
// e也已经是e的next节点了，而pred仍然是之前的e节点
// [1] [2] [3] [4]
// 假如i = 2，那么2的节点被替换成3，[1] [3] [3] [4]
// 那么要把链表串好，则需要变成[1] [3] [4]
else if (pred != null)
pred.next = e.next;
else
// value为null则直接把i的节点替换为next
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
// 将e替换成e的next节点
// e == null说明到达链表结尾
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;
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;
else if (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
if (validated) {
if (oldVal != null) {
if (value == null)
addCount(-1L, -1);
return oldVal;
}
break;
}
}
}
return null;
}