最近总是在分析源码，感觉源码也不是想象上的那么难，今天我来记录一下我对ConcurrentHashMap的理解。这里只敢说记录，不敢说分析，因为ConcurrentHashMap的代码确实有点难以理解，本文不对代码进行死磕，也就是说，可能不会对某一行代码进行死磕，而是对整个ConcurrentHashMap类进行整体的理解。
本文参考资料：
1.ConcurrentHashMap源码分析（JDK8版本）
2. 死磕 Java 并发：J.U.C 之 Java 并发容器：ConcurrentHashMap
3.深入浅出ConcurrentHashMap1.8
4.深入分析ConcurrentHashMap1.8的扩容实现
5.方腾飞、魏鹏、程晓明的《Java 并发编程的艺术》
1.为什么要使用ConcurrentHashMap？
其实，楼主都觉得这个问题问的非常傻逼，为什么使用ConcurrentHashMap呢？当然是为了线程安全呗。其实这个回答是比较笼统的，这里面还有很多的问题没有涉及到，比如说，使用最多的HashMap在多线程模型下的缺点，传统线程安全的HashTable的问题等等。
(1).线程不安全的HashMap
我们才学习HashMap的时候，就知道HashMap是线程不安全的，但是不知道HashMap由于多线程会导致什么问题。下面，我们来看一段代码：
public class Demo {
public static void main(String[] args) {
final Map<String, String> map = new HashMap<>(2);
Thread t = new Thread(new Runnable() {
@Override
public void run() {
for(int i = 0; i < 100000; i++){
new Thread(new Runnable() {
@Override
public void run() {
map.put(UUID.randomUUID().toString(), "");
}
}).start();
}
}
});
t.start();
try {
t.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
HashMap在并发执行put操作是会引起死循环，是因为多线程会导致HashMap的Entry链表形成数据结构，一旦形成环形数据结构，Entry的next节点永远不为空，就会产生死循环获取Entry。
(2).效率低下的HashTable
HashTable使用synchronized关键字来保证线程安全，但在线程竞争激烈的情况下HashTable的效率非常低下。因为当一个线程访问HashTable的同步方法，其他线程也访问HashTable的同步方法，会进入阻塞或者轮询状态。如果线程1在使用put进行元素添加，线程2不但不能使用put方法添加元素也不能使用get方法来获取元素，所以竞争越激烈效率越低。
(3).ConcurrentHashMap
相较于笨重的HashTable，ConcurrentHashMap就显得非常高效。ConcurrentHashMap降低了锁的粒度，其中在1.7中，设置了Segment数组，来表示不同数据段，在1.8中，取消了Segment数组，进一步降低了锁的粒度。由于本文是分析1.8的ConcurrentHashMap，所以不对1.7的版本过多的解释。
2.ConcurrentHashMap的模型图
1.8在1.7的基础上进一步的优化，使得ConcurrentHashMap的锁的粒度进一步降低。我们还是先来看看ConcurrentHashMap的结构图：
我们看到的是，在1.8的内部，维持了一个Node数组，用来存储数据。实际上，ConcurrentHashMap结构与HashMap的结构类似，基本结构都是数组+链表+红黑树。但是在ConcurrentHashMap里面，红黑树在Node数组内部存储的不是一个TreeNode对象，而是一个TreeBin对象，TreeBin内部维持着一个红黑树。
3.ConcurrentHashMap的内部类
简单的看过ConcurrentHashMap的结构图之后，现在来了解一下ConcurrentHashMap的内部类，这个在后面我们理解源码有一定的帮助。
(1).Node类
Node类在ConcurrentHashMap的内部类是最基本的类，其中桶里面装的就是Node元素，还有就是TreeBin、TreeNode等都继承于Node类。我们先来看看Node的代码：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
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;
}
}
我们来看一下Node成员变量：
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
hash用来存储该key的hash值，但是这里面有三个状态需要注意：
| 名称 | 值 | 描述 |
|---|---|---|
| MOVED | -1 | hash值为-1的Node，表示当前节点已经被处理过了，这中情况将出现多线程扩容的情况下，后面会详细的解释 |
| TREEBIN | -2 | hash值为-2的Node，表示当前的节点是TreeBin |
| RESERVED | -3 | 保留的hash值，用在ReservationNode上面 |
key用来存储的key值，val用来存储value值，这个就不用多说。next字段表示下一个Node，这个在出现哈希冲突时，将定位在相同位置上的Node使用链表连接起来。
我们还需要注意一点是,我们不能够通过调用setValue方法来改变Node的值。
public final V setValue(V value) {
throw new UnsupportedOperationException();
}
(2).TreeNode类和TreeBin类
TreeNode类表示的是红黑树上的每个节点。当一个链表上的节点数量超过了指定的值，会将这个链表变为红黑树，当然每个节点就转换为TreeNode。不像HashMap，ConcurrentHashMap在桶里面直接存储的不是TreeNode，而是一个TreeBin，在TreeBin内部维护一个红黑树，也就是说TreeNode在TreeBin内部使用的。
(3).ForwardingNode类
这个是辅助类，通常在扩容时用到。此时如果一个线程在进行扩容操作，另一个线程put一个元素进来，如果看到对应的位置上面是ForwardingNode对象的话，那么就参与扩容的操作队列来。其中ForwardingNode对象来源有两个：1.原来的位置为null，但是此时复制操作已经到当前位置的后面了，会将这个原来的桶的这个位置置为ForwardingNode对象；2.原来位置不为null，但是已经操作过这个位置了。
我们来来ForwardingNode的源码：
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;
}
//省略了find方法代码
}
在ForwardingNode里面，我们发现了一个nextTable对象，这个对象表示扩容之后的数组，当一个线程访问到了一个ForwardingNode对象，就知道当前正在进行扩容操作，当前这个线程会帮助扩容（扩容分为两步：1.数组容量增大2倍；2.将原数组的元素拷贝到新数组里面去），将原数组的元素复制到这个nextTable里面去。
4.基本成员变量
我们在分析ConcurrentHashMap的源码时，还是先来看看它基本的成员变量。
| 变量名 | 描述 |
|---|---|
| table | 桶数组，用来存储Node元素的。默认为null，只在第一次put操作的进行初始化，该数组的长度永远为2的n次方。 |
| nextTable | 默认为null，当不为null，表示当前正在进行扩容操作，这个数组就是扩容之后的数组，长度为原数组的两倍。 |
| baseCount | 记录map中元素个数，由于是多线程操作，baseCount记录的不准确，所以要结合counterCells 来使用保证记录的正确性。 |
| sizeCtl | 表初始化和扩容的控制位。其中，当为-1时，表示当前table数组正在被初始化；当为-N时，表示有N-1个线程在进行扩容操作；当为0（默认值）时，表示当前table还未使用，此时table为null；当为其余正整数时，表示table的容量，默认是table大小的0.75倍，在代码中使用的是(n - (n>>>2))的方式来计算0.75 |
5.构造方法
在ConcurrentHashMap里面，我觉得有两个构造方法需要我们关注，一个是无参数的构造方法，这个构造方法非常的简单，是一个空的构造方法，还有一个就是带初始容量的构造方法：
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}
在这个构造方法里面最主要的是，初始化sizeCtl。在这里保证sizeCtl必须是2的n次方,所以这里调用tableSizeFor方法的目的就是调整sizeCtl大小为2的n次方。
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;
}
假设给出大小为100，调用这个方法之后，会将大小调整为256。
6.table数组的初始化
在前面，对table数组的初始化也有所提及。table不会在构造方法里面进行初始化，而是在第一次put操作时，进行初始化。我们来看看：
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;
//发现table数组尚未初始化，调用initTable方法来对table数组进行初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//省略了其余代码
}
在调用put方法时，如果发现table尚未被初始化，会调用initTable方法来初始化。我们来看看initTable方法的代码：
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
//sizeCtl小于0，表示已经有线程在对table数组进行初始化，现在这个线程要做的就是让出cpu时间，
//全力支持table初始化
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
//此时有一个线程在对table数组进行是初始化，如果使用CAS算法对sizeCtl字段更新成功，
//表示当前线程可以对table数组进行初始化。
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;
}
在initTable方法中，我们发现table数组只能被一个线程初始化。如果一个线程在初始化table数组，会将sizeCtl字段更新为-1，其他线程看到sizeCtl为-1时，就知道当前已经有线程在初始化table数组，他们需要做的是，全力支持那个线程初始化table数组--让出cpu占用时间。
同时，我们看到当table数组更新成功之后，sizeCtl更新为table数组大小的0.75倍：
sc = n - (n >>> 2);
7.put操作
我们使用HashMap最多的操作就是put操作和get操作。这里先对put进行分析。我们先总体看一下put的代码：
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;
}
这里，我先将整个put方法的代码贴出，让大家有一个总体上概念，然后再来一一解释，整个put操作的流程。
整个put操作分为4种情况：
1.如果当前table没有被初始化，会先初始化，重新进行put操作(循环操作，保证put成功)。
2.通过hash计算，定位位置，如果位置上为null，表示可以直接放进去。
3.如果对应位置的元素已经被标记为MOVED，即Node的hash为MOVED，那么表示当前table数组在进行扩容操作，此时，当前的线程会帮助扩容。
4.如果通过hash计算之后的位置不为null，表示出现了哈希冲突，此时会锁住当前这个位置上的Node对象，然后将新添加的Node添加这个位置链表或者红黑树上。
(1).hash计算
put操作的第一步就是hash计算，这里的hash计算，我认为分为两步：
1.调用spread方法将key的hashcode再次hash。
2.通过(n - 1) & hash方法来计算该元素定位的位置。
我们先来看看spread方法：
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
我先来解释一下>>>运算符的含义：
>>>的基本操作就是左移，然后高位补0，这里的左移表示连符号位都要跟着左移；而>>只是左移数值位，不移动符号位。
h ^ (h >>> 16)与运算过程如下图：
异或操作完成之后，然后跟HASH_BITS取与操作，我认为是为了消除符号位的影响。
至于(n - 1) & hash计算，其实就是hash % n的计算，具体的解释，大家可以参考我的Java 源码分析-ThreadLocal,这篇文章里面有相关的解释。
(2).元素放入数组
由于初始化table数组在前面已经说了，所以这里直接说赋值的情况。在这种情况下，还有分为两种情况：1.对应位置为null；2.对应位置不为null。这里将将两种情况分别讨论一下。
A.对应位置为null
这种情况比较简单，直接调用了casTabAt方法进行赋值：
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
}
这里使用Unsafe类来对变量进行CAS更新，具体的实现原理，楼主也不是很清楚，实在抱歉！
A.对应位置不为null
这种情况下，就比较复杂了，我们先来看看代码：
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;
}
这种情况下，新添加的Node肯定会添加到这个位置后面，当然为了保证线程安全，肯定锁住当前的Node，这样将锁的粒度降到了每个Node上，一个Node的put操作不会影响其他Node的操作。
锁住了之后，当然就要添加Node。这里分为两种情况，一种原来的Node不是TreeBin，也就是说原来就是一个链表，这样直接添加到链表的内部就行了；还有就是原来的Node本身就是一个TreeBin，那么我们通过调用TreeBin内部的方法来添加一个Node，至于红黑树的平衡性，让TreeBin自己来维持，我们外部不需要关注。
添加完成之后，还需要一个操作，那就是如果当前链表达到了阈值，需要将链表变为红黑树。这一步的解释在后面在详细的说。
8.更新baseCount
在putVal方法的循环执行完毕之后，一个Node肯定放入进去了，此时就需要调用addCount方法来更新baseCount变量：
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
//更新baseCount
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
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();
}
//检测是否需要扩容
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
if (sc < 0) {
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);
s = sumCount();
}
}
}
addCount方法里面分为主要两个操作：1.更新baseCount；2.检测是否扩容。这里由于在讨论更新baseCount，所以不对扩容操作进行详细的解释，之后会做详细的解释。
更新baseCount的操作分成了两步：1.尝试更新baseCount变量；2.如果更新失败，或者counterCells为null会调用fullAddCount方法进行循环更新。
我们来看看fullAddCount的代码：
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) {
// 如果counterCells数组对应位置上为null，创建一个cell，
//放在这个位置上。
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
//如果对应位置上不为null，尝试更新value值
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;
//如果对应不为null，并且更新失败，表示此时counterCells数组的容量过小，
//此时需要扩容。
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);
}
//初始化counterCells数组
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
}
}
这个方法的代码比较长，理解起来可能麻烦，我来说明整个方法的作用和执行的过程。
在解释这个方法之前，先解释一下baseCount和counterCells含义。两个都是用记录元素个数，只是记录的时机不同的。当要更新元素个数时，优先更新baseCount，如果baseCount更新成功的话，表示更新元素个数的操作已经完成了；如果更新失败的话，此时会考虑更新counterCells数组中某一个（随机的）cell的value值。因此，map的元素个数 = baseCount + 所有的cell的value值。
在调用fullAddCount方法之前，在addCount方法里面进行了两次尝试：1.尝试更新baseCount；2.尝试更新counterCells数组随机位置上的一个cell的value。如果这两次尝试都失败的话，则需要调用fullAddCount来保证元素个数正确的更新。
而这个fullAddCount方法的作用就是更新cell的value值。
整个fullAddCount方法的执行步骤：
1.如果counterCells为null，先初始化counterCells数组，默认大小为0。
2.如果counterCells不为null，根据产生的随机，通过(n - 1) & h找到一个位置，如果这个位置为null的话，创建一个cell对象放在这个位置上面。
3.如果这个位置上面不为null，首先会尝试更新这个cell的value值，如果更新成功的话，表示更新操作完成，否则执行第4步。
4.如果第3步的更新操作失败，表示此时counterCells数组的容量可能不足以应付这么多的线程了。所以此时counterCells数组需要扩容。
9.扩容操作
当我们put一个元素之后，如果此时元素已经达到了扩容的阈值了，就需要扩容。我们先来看看addCount方里面的扩容部分：
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
//表示已经有线程在进行扩容操作
if (sc < 0) {
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);
}
//当前线程是唯一的或是第一个发起扩容的线程 此时nextTable=null
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
s = sumCount();
}
}
addcount方法扩容部分有两种情况：1. sc<0情况下，表示当前已经有线程在进行扩容操作了，此时当前这个线程需要参与帮助扩容的任务中来；2. 另一个情况，当前线程只有一个线程准备扩容操作。第一种情况为什么不调用helperTransfer方法来表示帮助扩容的含义，这个原因，我也不是很懂，但是比较了第一种情况的代码与helperTransfer方法的代码，两者其实比较类似。
现在我们来看看transfer方法究竟为我们做了什么。由于transfer方法代码过长，所以这里不完全展出来，这里使用分段形式来解释。
首先，如果是第一个线程调用transfer方法进行扩容操作，那么nextTable肯定为null。所以transfer方法的第一步就是创建新数组，新数组的容量是旧数组的两倍：
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;
}
扩容之后，此时需要将原来的数组进行复制操作了。这个过程支持多线程操作。在看这个过程之前，我们先来看看几个变量的含义。
| 变量名 | 类型 | 描述 |
|---|---|---|
| fwd | ForwardingNode | 用来作为占位符，表示当前位置已经被处理过 |
| advance | boolean | advance为true，表示当前这个节点已经被处理，这个与fwd区别在于，advance为false表示当前节点(i位置)可以被处理 |
| finishing | boolean | finishing为true，表示当前扩容操作已经操作完毕 |
接下来，我们来分析一下transfer方法的执行过程。大体的流程是，遍历这个原来的桶数组，然后复制到新数组里面去。
首先，必须找到一个可以被处理的Node节点，这个节点可以为null，也可以不为null，但是不能为fwd对象，因为如果是fwd对象，表示当前已经被处理过，没必要再去处理。
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))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
上面的代码中，只要advance为false，就退出while循环，表示当前尝试着处理这个位置上的Node。这里说的是尝试着处理，意思就是，可能不会被处理，比如说，已经有现在在处理了；或者这个位置已经被处理，已经为fwd了。
首先，如果这个位置上为null的话，那么直接将这个位置设置成fwd。
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
如果当前这个节点已经被处理了，直接将advance设置为true，进行下一次位置的选择。
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
其他情况下，表示可以处理这个节点，这里处理的意思，是可以将这个位置上的所有节点拷贝到新数组里面去。这里分为两种情况，我们来一一的分析。
首先，第一种情况就是节点本身为一个链表结构。
Node<K,V> ln, hn;
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);
}
//将原来链表上的一部分就放在原位置
setTabAt(nextTab, i, ln);
//将原来链表上的另一部分放在 i + n的位置上
setTabAt(nextTab, i + n, hn);
//处理完毕，将这个位置上设置为fwd，后面的线程看到之后，知道这个节点已经被处理了
setTabAt(tab, i, fwd);
advance = true;
}
整个过程是非常简单，就是将原来的链表分为了两部分，一部分在原来的 i 位置上，一部分在 i+ n的位置上。这里涉及到了喜闻乐见的反转链表，这里不对反转链表做解释，后面会详细的解释反转链表的原因，到时候会回来详细的解释这段代码。
现在来看看复制操作的第二种类型。如果当前位置上的Node为TreeBin类型，表示为红黑树，此时要做的操作跟链表的操作也是非常类似，将树分为两个部分，一个部分在原来的i位置上，另一个部分在i + n的位置上。
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;
最后，如果所有的节点被赋值完毕之后，表示扩容操作已经完成了,此时finishing为true。
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
//将nextTable置为null，以便下次扩容
nextTable = null;
table = nextTab;
//将sizeCtl的值调整为长度的0.75
sizeCtl = (n << 1) - (n >>> 1);
return;
}
//sizeCtl减一，表示当前有个线程参与扩容
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
}
}
10.反转链表的原因
楼主的思路来自于深入分析ConcurrentHashMap1.8的扩容实现，如果大家可以参考一下。刚刚，我们对transfer方法的复制操作有了一个大概的理解，这里将对其详细分析。
在解释这段代码之前，我们先对这段代码里面几个变量有一个初步的理解。
| 变量名 | 类型 | 描述 |
|---|---|---|
| runBit | int | 位置为每个节点的hash值与n进行与操作，经过第一次循环，runBit记录的是最后一个hash值变化的Node的hash值。可能这里拗口，待会举一个详细例子。 |
| lastRun | Node | 默认值为当前位置第一个Node，经过第一次循环，lastRun记录的是最后一个hash值变化的Node。 |
| ln | Node | 默认值为null，是放在新数组 i 位置上的链表头结点。 |
| hn | Node | 默认值为null，是放在新数组 i + n 位置上的链表头结点 |
在上面的表格中，提到最后一个hash值变化的Node，这句话可能比较拗口，这里举一个简单的例子来表达意思。
上图中是一个链表的模型，其中，我将这个链表中的节点分为两类：1.一类是节点的hash值相同的；2.第二类是跟第一类的hash值不同的。所以，从这个链表中我们可以得到，lastRun为节点6，runBit也是节点6与n进行与操作得到的值。为什么是节点6呢？因为在6之后，节点类型没有再变了。
Node<K,V> ln, hn;
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);
}
//将原来链表上的一部分就放在原位置
setTabAt(nextTab, i, ln);
//将原来链表上的另一部分放在 i + n的位置上
setTabAt(nextTab, i + n, hn);
//处理完毕，将这个位置上设置为fwd，后面的线程看到之后，知道这个节点已经被处理了
setTabAt(tab, i, fwd);
advance = true;
}
结合源码来分析，runBit默认为节点1的hash和n与操作的值。后面依次记录与上一次runBit的不同值，最后通过runBit == 0将所有的节点分为了两类。
现在我们结合上面的图做一个假设。我们假设紫色节点的hash值&n为0，那么蓝色节点的hash值&n就不为0。经过第一次循环，得出 ln = lastRun = 节点6，hn = null。
此时我们来分析第二次循环，先来看看紫色节点构成ln链表的过程。
我看到ln链表只是部分反转了，默认部分是没有反转了。其中得到的ln链表放在新数组的i位置上。
然后我们再来看看hn链表的构成过程。
我们发现hn链表是完全反转的。从而，我们得出一个结论，哪个链表默认为null，那个链表就是完全反转的。
最终，我们终于知道了，一个反转链表得出的原因，其实不是故意为之，而是加快复制操作速度，因为lastRun之后的节点进行复制操作不需要创建新节点。
11.get操作
前面详细的说了put操作和扩容操作，这里简单的分析一下get操作，get操作相比于前面的操作就非常的简单。先来看看源码：
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
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;
}
//当节点为TreeBin或者ForwardingNode
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;
}
整个get操作分为三种情况：1.table数组指定位置的第一个节点就匹配成功，直接返回；2.table数组指定位置上的hash值小于0，此时当前位置可能已经被其他在扩容时处理过，或者当前位置的Node为一个TreeBin，不管是那种类型的Node，调用的都是find方法来获取Node节点；3.其余情况下，直接遍历链表查找。
12.size操作
size操作里面，主要有两个方法提供，一个是传统的size方法，一个是ConcurrentHashMap比较提倡的mappingCount方法。我们先来看看size方法：
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
size方法里面调用sumCount方法，sumCount方法才是真正计算元素个数的方法。我们来看看sumCount方法：
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;
}
可能大家对这个方法计算方式不太好理解，其实这种计算方式取决于前面的设计方式。在前面我说到过，map的元素个数 = baseCount + 所有的cell的value值。这个结论是因为多线程更新个数时，如果只在baseCount里面记录，一个原因是多线程更新可能会出错，另一个原因是竞争性太大了。所以，设计理念就变成了，当baseCount更新失败时，表示baseCount变量当前忙碌，可以将这个增量添加到一个不忙的cell里面去，这样竞争性就降低了。
我们再来看看mappingCount方法：
public long mappingCount() {
long n = sumCount();
return (n < 0L) ? 0L : n; // ignore transient negative values
}
达到的效果感觉跟size都差不多，只不过是一个返回int，一个返回long而已。
