* ---------------- Fields -------------- */
/**
* The array of bins. Lazily initialized upon first insertion.
* Size is always a power of two. Accessed directly by iterators.
*/
*这里要注意一下，volatile修饰了table，这样的好处是当某一个线程扩容时，另一个线程可见，
*虽然volatile对于不能保证引用类型的变量内部可见，但是这里时扩容，换了一个数组地址发生了改变，所以是可见的
transient volatile Node<K,V>[] table;
/**
* The next table to use; non-null only while resizing.
*/
*当扩容的时候使用nextTable
private transient volatile Node<K,V>[] nextTable;
/**
* Base counter value, used mainly when there is no contention,
* but also as a fallback during table initialization
* races. Updated via CAS.
*/
* 用于统计容量
private transient volatile long baseCount;
/**
* Table initialization and resizing control. When negative, the
* table is being initialized or resized: -1 for initialization,
* else -(1 + the number of active resizing threads). Otherwise,
* when table is null, holds the initial table size to use upon
* creation, or 0 for default. After initialization, holds the
* next element count value upon which to resize the table.
*/
*控制标识符，用来控制table的初始化和扩容的操作，不同的值有不同的含义
*当为负数时：-1代表正在初始化，-N代表有N-1个线程正在 进行扩容
*当为0时：代表当时的table还没有被初始化
*当为正数时：当初始化或扩容完成后，为 下一次的扩容的阈值大小
private transient volatile int sizeCtl;
/**
* The next table index (plus one) to split while resizing.
*/
private transient volatile int transferIndex;
/**
* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
*/
private transient volatile int cellsBusy;
/**
* Table of counter cells. When non-null, size is a power of 2.
*/
private transient volatile CounterCell[] counterCells;
// views
private transient KeySetView<K,V> keySet;
private transient ValuesView<K,V> values;
private transient EntrySetView<K,V> entrySet;
static class Node<K,V> implements Map.Entry<K,V> {
//key的hash值
final int hash;
final K key;
//val和next都会在扩容时发生变化，所以加上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;
}
public final K getKey() { return key; }
public final V getValue() { return val; }
public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
public final String toString(){ return key + "=" + val; }
public final V setValue(V value) {
throw new UnsupportedOperationException();
}
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)));
}
/**
* Virtualized support for map.get(); overridden in subclasses.
*/
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;
}
}
比较重要的点就是在它的成员属性加了volatile关键字，保证了可见性和有序性。
树化节点
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);
}
......
static final class TreeBin<K,V> extends Node<K,V> {
//指向TreeNode列表和根节点
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 增加数据时读锁的状态
/**
* Tie-breaking utility for ordering insertions when equal
* hashCodes and non-comparable. We don't require a total
* order, just a consistent insertion rule to maintain
* equivalence across rebalancings. Tie-breaking further than
* necessary simplifies testing a bit.
*/
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;
………………………………
}
TreeBin从字面含义中可以理解为存储树形结构的容器，而树形结构就是指TreeNode，所以TreeBin就是封装TreeNode的容器，它提供转换黑红树的一些条件和锁的控制。
entry数组的初始化并不是在构造函数里面，而是在第一次调用put方法的时候检测是否初始化了，如果没有那么进行初始化。（这里和hashmap是一样的）
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
//【每次循环都获取最新的Node数组引用】
while ((tab = table) == null || tab.length == 0) {
//sizeCtl是一个标记位，若为-1也就是小于0，代表有线程在进行初始化工作了
if ((sc = sizeCtl) < 0)
//【让出CPU时间片】
Thread.yield(); // lost initialization race; just spin
//【CAS操作，将本实例的sizeCtl变量设置为-1】
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
//如果CAS操作成功了，代表本线程将负责初始化工作
try {
//再检查一遍数组是否为空
if ((tab = table) == null || tab.length == 0) {
//在初始化Map时，sizeCtl代表数组大小，默认16
//所以此时n默认为16
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
//Node数组
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
//将其赋值给table变量
table = tab = nt;
//通过位运算，n减去n二进制右移2位，相当于乘以0.75
//例如16经过运算为12，与乘0.75一样，只不过位运算更快
sc = n - (n >>> 2);
}
} finally {
//将计算后的sc（12）直接赋值给sizeCtl，表示达到12长度就扩容
//由于这里只会有一个线程在执行，直接赋值即可，没有线程安全问题
//只需要保证可见性
sizeCtl = sc;
}
break;
}
}
return tab;
}
使用cas自旋+标记位（标记位必然是volatile的） 来确保只有一个线程能够初始化。
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
//对key的hashCode进行散列
int hash = spread(key.hashCode());
int binCount = 0;
//【一个无限循环，直到put操作完成后退出循环】
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//当Node数组为空时进行初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//Unsafe类volatile的方式取出hashCode散列后通过与运算得出的Node数组下标值对应的Node对象
//【此时的Node对象若为空，则代表还未有线程对此Node进行插入操作】
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//直接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)
//【帮助扩容】
tab = helpTransfer(tab, f);
else {
V oldVal = null;
//对Node对象进行加锁，插入到当前结点的拉链后面
synchronized (f) {
//二次确认此Node对象还是原来的那一个
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
//【无限循环，直到完成put】
for (Node<K,V> e = f;; ++binCount) {
K ek;
//和HashMap一样，先比较hash，再比较equals
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) {
//和链表头Node节点不冲突，就将其初始化为新Node作为上一个Node节点的next
//形成链表结构
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
...
}
如果当前数组中Node结点为空，那么cas尝试加入，成功则结束，如果不成功，再一次循环。如果正在扩容，那么帮助扩容，整个map扩容完成后才能够put。在进行put的时候会把当前的Node结点锁住，也就是把这个桶给锁了，然后再put保证安全插入。
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
//根据机器CPU核心数来计算，一条线程负责Node数组中多长的迁移量
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
//本线程分到的迁移量
//假设为16（默认也为16）
stride = MIN_TRANSFER_STRIDE; // subdivide range
//nextTab若为空代表线程是第一个进行迁移的
//初始化迁移后的新Node数组
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
//这里n为旧数组长度，左移一位相当于乘以2
//例如原数组长度16，新数组长度则为32
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变量为新数组
nextTable = nextTab;
//假设为16
transferIndex = n;
}
//假设为32
int nextn = nextTab.length;
//【标示Node对象，此对象的hash变量为-1】
//【在get或者put时若遇到此Node，则可以知道当前Map正在迁移】
//【传入nextTab对象】
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;
//i为当前正在处理的Node数组下标，每次处理一个Node节点就会自减1
if (--i >= bound || finishing)
advance = false;
//假设nextIndex=16
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
//由以上假设，nextBound就为0
//且将nextIndex设置为0
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
//bound=0
bound = nextBound;
//i=16-1=15
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
}
}
//此时i=15，取出Node数组下标为15的那个Node，若为空则不需要迁移
//直接设置占位标示，代表此Node已处理完成
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
//【检测此Node的hash是否为MOVED，MOVED是一个常量-1，也就是上面说的占位Node的hash】
//【如果是占位Node，证明此节点已经处理过了，跳过i=15的处理，继续循环】
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
//【锁住这个Node，开始迁移这个桶】
synchronized (f) {
//确认Node是原先的Node
if (tabAt(tab, i) == f) {
//ln为lowNode，低位Node，hn为highNode，高位Node
//这两个概念下面以图来说明
Node<K,V> ln, hn;
if (fh >= 0) {
//此时fh与原来Node数组长度进行与运算
//如果高X位为0，此时runBit=0
//如果高X位为1，此时runBit=1
int runBit = fh & n;
Node<K,V> lastRun = f;
for (Node<K,V> p = f.next; p != null; p = p.next) {
//这里的Node，都是同一Node链表中的Node对象
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
//正如上面所说，runBit=0，表示此Node为低位Node
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
//Node为高位Node
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;
//若hash和n与运算为0，证明为低位Node，原理同上
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);
//这里将高位Node与地位Node都各自组成了两个链表
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
//【将低位Node设置到新Node数组中，下标为原来的位置】
setTabAt(nextTab, i, ln);
//【将高位Node设置到新Node数组中，下标为原来的位置加上原Node数组长度】
setTabAt(nextTab, i + n, hn);
//【将此Node设置为占位Node，代表处理完成，这里最后才会把原table的Node结点置为fwd，也就是说，如果get的时候发现时fwd，那么说明此node已经迁移完了，那么也就可以通过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;
}
}
//【链表放入TreeBin会转为红黑树】
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;
}
}
}
}
}
}
第一点说明：区分ln（低位Node）、hn（高位Node）
举个例：如果一开始容量是16，那么8和24在一个桶里面，那么如果要是扩容成32，那么8和24就在不同的桶里面了，因为每次只会扩容为原来的两倍，所以原来桶里面的元素只会在扩容后的固定两个桶里面。所以可以分成两个桶直接插入到新的map里面。
第二点说明：红黑树桶仍然会更具高低位转为两个拉链，如果两个拉链超过了最小树化的长度，那么会放入到TreeBin中，TreeBin负责把拉链转为红黑树。
整体使用的是高并发累加器的思想（如果不了解，可以在我之前的博客里找到）。
//计数，并检查长度是否达到阈值
private final void addCount(long x, int check) {
//【计数桶】
CounterCell[] as; long b, s;
//【如果counterCells不为null，则代表已经初始化了，直接进入if语句块】
//【若竞争不严重，counterCells有可能还未初始化，为null，先尝试CAS操作递增baseCount值】
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
//进入此语句块有两种可能
//1.counterCells被初始化完成了，不为null
//2.CAS操作递增baseCount值失败了，说明有竞争
CounterCell a; long v; int m;
//标志是否存在竞争
boolean uncontended = true;
//1.先判断计数桶是否还没初始化，则as=null，进入语句块
//2.判断计数桶长度是否为空或，若是进入语句块
//3.这里做了一个线程变量随机数，与上桶大小-1，若桶的这个位置为空，进入语句块
//4.到这里说明桶已经初始化了，且随机的这个位置不为空，尝试CAS操作使桶加1，失败进入语句块
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
//统计容器大小
s = sumCount();
}
...
}
//出现竞争，导致CAS失败
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语句块
if ((as = counterCells) != null && (n = as.length) > 0) {
//从计数桶数组随机选一个计数桶，若为null表示该桶位还没线程递增过
if ((a = as[(n - 1) & h]) == null) {
//查看计数桶busy状态是否被标识
if (cellsBusy == 0) { // Try to attach new Cell
//若不busy，直接new一个计数桶
CounterCell r = new CounterCell(x); // Optimistic create
//CAS操作，标示计数桶busy中
if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean created = false;
try { // Recheck under lock
CounterCell[] rs; int m, j;
//在锁下再检查一次计数桶为null
if ((rs = counterCells) != null &&
(m = rs.length) > 0 &&
rs[j = (m - 1) & h] == null) {
//将刚刚创建的计数桶赋值给对应位置
rs[j] = r;
created = true;
}
} finally {
//标示不busy了
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
//走到这里代表计数桶不为null，尝试递增计数桶
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
//若CAS操作失败了，到了这里，会先进入一次，然后再走一次刚刚的for循环
//若是第二次for循环，collide=true，则不会走进去
else if (!collide)
collide = true;
//计数桶扩容，一个线程若走了两次for循环，也就是进行了多次CAS操作递增计数桶失败了
//则进行计数桶扩容，CAS标示计数桶busy中
else if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
try {
//确认计数桶还是同一个
if (counterCells == as) {// Expand table unless stale
//将长度扩大到2倍
CounterCell[] rs = new CounterCell[n << 1];
//遍历旧计数桶，将引用直接搬过来
for (int i = 0; i < n; ++i)
rs[i] = as[i];
//赋值
counterCells = rs;
}
} finally {
//取消busy状态
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)) {
//初始化计数桶…
//若有线程同时初始化计数桶，由于CAS操作只有一个线程进入这里
boolean init = false;
try { // Initialize table
//再次确认计数桶为空
if (counterCells == as) {
//【初始化一个长度为2的计数桶】
CounterCell[] rs = new CounterCell[2];
//h为一个随机数，与上1则代表结果为0、1中随机的一个
//也就是在0、1下标中随便选一个计数桶，x=1，放入1的值代表增加1个容量
rs[h & 1] = new CounterCell(x);
//将初始化好的计数桶赋值给ConcurrentHashMap
counterCells = rs;
init = true;
}
} finally {
//最后将busy标识设置为0，表示不busy了
cellsBusy = 0;
}
if (init)
break;
}
else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
break; // Fall back on using base
}
}
计数桶
计数桶初始长度为2，在竞争大的时候不够用，就会对计数桶进行扩容，两个问题：
所有的get操作都是无锁的，所以说这些数据需要是volatile的。
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
//此过程与HashMap的get操作无异，不多赘述
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//【当hash<0,有可能是在迁移,使用fwd占位Node去查找新table中的数据】
else if (eh < 0)
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;
}
eh<0的情况详细分析，同时也分析在写的时候读的情况。
这里eh只会等于-1，map在进行扩容，最终到新的table上面去寻找。如果到新table上发现时链表，那么直接可以线性查找，如果是一个TreeBin的话，也就是说这个桶还在转换，由链表转为红黑树，由于红黑树结点有一个next属性，也就是说，在没有构造完成红黑树之前，还是会进行线性查找（TreeBin的find方法），如果构造完成了的话，那么就不是TreeBin，而是TreeNode。