1、基本变量
//链表转树的阈值
static final int TREEIFY_THRESHOLD = 8;
//树转链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
//每次转移的桶的数量，多线程操作时相当于每个线程一次可以操作的数量
private static final int MIN_TRANSFER_STRIDE = 16;
//扩容转移数据是下一次转移开始的位置（这个是反过来的从大到小）
private transient volatile int transferIndex;1.1 CAS操作
Unsafe类是用来做cas操作的，都是native方法，代码由C++实现，下面的变量表示对应变量的偏移
例如：compareAndSwapInt(Object o, long offset, int expected, int x);
表示对象o偏移位置offset的变量如果和期望值expected相等，把变量值设置为x
private static final sun.misc.Unsafe U;
//下面的long变量表示对应的this同名变量的偏移量
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;1、table初始化
1、table会延迟到第一次put时初始化，同过使用循环+CAS的套路，可以保证一次只有一个线程会初始化table。
2、在table为空的时候如果sizeCtl小于0，则说明已经有线程开始初始化了，其它线程通过Thread.yield()让出CPU时间片，等待table非空即可。
3、否则使用CAS将sizeCtl的值换为-1，置换成功则初始化table。
4、注意table的大小为sizeCtl，初始化后将sizeCtl的值设为n - (n >>> 2)即0.75n，这个值用来确定是否需要为table扩容。
//Initializes table, using the size recorded in sizeCtl.
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
//判断是否已经有线程在初始化，如果有则让出CPU，之后继续自旋判断
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
//cas操作设置sizeCtl的值
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")
//初始化table
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
sc = n - (n >>> 2);//设置sizeCtl=0.75n
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}2、put操作（putVal方法）
1、首先计算key的hash值
2、判断table是否为空，如果是就初始化
3、根据hash值取余确定桶的位置，并判断桶是否为空，如果是空，通过cas操作设置进去
4、如果桶的第一个节点非空，并且hash=MOVED，说明有线程正在进行扩容，调用helpTransfer帮助扩容
5、对桶加锁并判断节点是链表还是树，根据不同情况插入节点
6、判断是否达到链表转树的阈值
7、统计节点数
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
//1、首先计算key的hash值
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//2、判断table是否为空，如果是就初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//3、根据hash值取余确定桶的位置，并判断桶是否为空，如果是空
//通过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
}
//4、如果桶的第一个节点非空，并且hash=MOVED，说明有线程正在进行扩容，
//调用helpTransfer帮助扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
//5、对桶加锁并判断节点是链表还是树，根据不同情况插入节点
synchronized (f) {
if (tabAt(tab, i) == f) {//保证多线程环境下的安全性，再一次检查
if (fh >= 0) {//hash值大于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;
}
//否则说明是一个新Key，插入表尾
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) {
//6、判断是否达到链表转树的阈值
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//7、统计节点数
addCount(1L, binCount);
return null;
}3、链表转树
1、判断链表节点是否小于64，如果是优先使用扩容
2、对桶加锁
3、依次把链表节点集合转成树结点集合
4、把树结点集合转成红黑树，这颗红黑树是链表和树结构的结合，它同样通过next引用串成了一个链表
private final void treeifyBin(Node<K,V>[] tab, int index) {//将tab[index]链表转树
Node<K,V> b; int n, sc;
if (tab != null) {
//1、判断链表节点是否小于64，如果是优先使用扩容
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
//为了多线程环境下的安全性，再次判断该桶是否为空，hash>0表示是链表
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
synchronized (b) {//2、对桶加锁
if (tabAt(tab, index) == b) {//加锁后再次判断
TreeNode<K,V> hd = null, tl = null;
//3、依次把链表节点集合转成树结点
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;
}
//4、把树结点集合转成红黑树
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}4、扩容
1、由于扩容允许并发操作，首先通过CPU数量，计算允许每个线程能处理的桶的数量stride，最少每个线程处理16个
2、申请nextTable数组
3、把nextTab设置为ForwardingNode,表示正在进行扩容操作
4、每个线程进来的线程去获取自己能处理区域，每个线程通过cas操作设置transferIndex变量，设置成功则线程获得table中（transferIndex, transferIndex-stride)这一段的处理权限
- 类似下图这样的，stride=16，反向分配的，先来的线程从后面获取桶段
5、循环依次处理每一个桶：
5.1 如果当前桶首节点是链表，把链表节点重新分配到两个桶，一部分在原位置i，一分部在i+n位置
5.2 如果是红黑树，这里有点意思，同样是通过一个for像链表一样遍历，分成两部分，一个将放在i位置，一个将放在i+n位置。
那么问题来了，这里既然是树，为什么可以像链表一样操作呢？
这里被分成两个部分后，再根据这两个部分是否达到了树转列表的阈UNTREEIFY_THRESHOLD=6确定是转成链表还是组织成红黑树。
6、处理完成一个桶后，会把该桶对应位置设置为执行新链表的ForwardingNode（
当put操作遇到fwd节点时会帮助转移，然后进入新table操作）
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
//取CPU的数量，确定每个线程迁移的Node的数量，确保不会少于MIN_TRANSFER_STRIDE=16个
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
//申请数组nextTable
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;
//把nextTab设置为ForwardingNode,表示正在进行扩容操作
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;
}
/**
nextIndex从n开始
这里每个线程进来的时候通过cas操作设置transferIndex变量，
如果成功表示该线程处理nextIndex-stride这一段桶的迁移
即 i=[nextIndex-1, nextIndex-stride] 这一段桶
*/
//不相等，说明不到最后一个线程，直接退出transfer方法
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);
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)
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
//hash>0表示链表,链表节点重新分配到两个桶，一部分在原位置i，一分部在i+n位置
if (fh >= 0) {
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);
}
//将拆分后的列表通过cas操作设置为对应的桶中
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
//把当前桶设置为指向新table的ForwardingNode
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;
//这里的代码比较有意思
//由于这里的红黑树是一个树和链表的结合体，TreeNode同时也是一个Node
//所以这里可以像链表一样遍历，使用这种结构是为了方便遍历
//依次取出树的节点，根据节点hash的结果分到地位和高位链表
//后面把链表转成树，同时会保持链表的结构
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;
}
}
//把树拆分成了低位（放在位置i）和高位(位置i+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;
//拆分后的结构设置到相应的桶中
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}5、统计元素数量
1、简单通过CouterCell数组的和，由于可能有其他线程在进行增删操作，这个数据并不是精确的。
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;
}