在上篇文章 juc-07-ConcurrentHashMap1-java7 中介绍了同步容器 Vector 、 Hashtable 、SynchronizedList 与 SynchronizedMap 它们通过对每一个方法加 synchronized 锁来实现线程安全，但在线程竞争激烈的情况下，效率非常低下。
以HashTable举例：因为当一个线程访问 HashTable 的同步方法，其他线程也访问 HashTable 的同步方法时，会进入阻塞或轮询状态。如线程1使用 put 进行元素添加，线程2不但不能使用 put 方法添加元素，也不能使用 get 方法来获取元素，所以竞争越激烈效率越低。
接着，学习 ConcurrentHashMap的API，通过源码讲解了 ConcurrentHashMap 在Java7 中的实现，分析它的核心方法的实现原理，并且总结了核心方法的实现步骤。详细地介绍了在 Java7 中 ConcurrentHashMap 初始化时，在构造器中做了哪些工作；在进行 put() 操作时，在Segment上tryLock()加锁，实现线程安全；而在进行 get() 操作时，不需要进行加锁，只需要找到 key 对应的 Segment，找到 Segment 的table中对应的 HashEntry 链表，最后遍历链表查找key对应的 HashEntry 获取 Value。
这篇文章，我们继续扒一扒 ConcurrentHashMap 在 Java8 中的实现原理，看看在 Java8 中是各个核心方法的实现步骤，如何实现线程安全？
ConcurrentHashMap 常用方法
| 方法 | 描述 |
|---|---|
| void clear() | 清空 map |
| boolean contains(Object value) boolean containsValue(Object value) |
如果 map 中存在某个 key 存放的值 equals 入参 value，返回true， 否则返回 false |
| boolean containsKey(Object key) | 如果 map 中存在入参 key，返回true，否则返回 false |
| V get(Object key) | 返回 key 对应的 value，不存在则返回null |
| boolean isEmpty() | map为空(元素个数为0)返回 true，否则 false |
| KeySetView keySet() | 返回 map 中所有的 key Set集合 |
| Collection values() | 返回 map 中所有的 values Collection集合 |
| V put(K key, V value) | 在map中将 key 映射到的指定value。key 和 value 都不能为null。 返回 key 在map 中映射的前一个值，没有则返回 null |
| void putAll(Map<? extends K, ? extends V> m) | 遍历 m 中的所有 Entry，一个一个地调用 V put(K key, V value) 添加到 map 中 |
| V putIfAbsent(K key, V value) | 只有当 map 中不存在 key，才 put(K key, V value) , key 和 value 都不能为null。 |
| V remove(Object key) | 删除map中key对应的映射，如果key不存在，则什么都不做，返回null，否则返回key对应的value |
| int size() | map的大小 |
ConcurrentHashMap 的使用上类似 HashMap 只是 ConcurrentHashMap的所有操作是线程安全的，而 HashMap 的读操作是线程安全，写操作是非线程安全的。
还有一个区别是，ConcurrentHashMap的put操作 key 和 value 都不能为null，否则会抛出 NullPointerException，而 HashMap 的put操作允许 key 和 value 为null。
1、Java8 中 ConcurrentHashMap 的数据结构
从下图，可以看到，取消了 Java7中的Segment数组 ，直接用 table 保存数据，table 保存的是 Node 数组。
1.1、 Node的数据结构，类似 JDK1.7 HashEntry
- key
- value值
- key的hash值
- next节点的引用
看看 Node 的源码
public class ConcurrentHashMap extends AbstractMap
implements ConcurrentMap, Serializable {
...
static class Node implements Map.Entry {
// key的hash值
final int hash;
// key
final K key;
// value值
volatile V val;
// next节点的引用
volatile Node next;
Node(int hash, K key, V val, Node next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
...
}
...
}
1.2 红黑树节点的数据结构
TreeNode红黑树的节点，TreeNode extends Node，同时持有父节点、左子节点和右子节点的引用TreeBin是实际放在table数组中的，指向了红黑树的根节点，TreeBin extends Node。
1.3 与 Java7 相比的重大变化
1、取消了segment数组，直接用table(Node数组)保存数据，原本的Java7中 ConcurrentHashMap 默认并发度为16，提到到每个Node都可以并发，锁的粒度更小，减少并发冲突的概率；
2、Java7中 Segment 继承了 ReentrantLock，使用Lock接口的 tryLock() 加锁；Java8 中则使用cas+synchronized，下文会有源码分析；
3、存储数据时采用了链表+红黑树的形式， 什么时候链表转红黑树？ ，当 Node 链表的Node个数大于 TREEIFY_THRESHOLD(转为树形的阈值，值为8) 时，链表会转换为红黑树；
4、链表的数据结构遍历查询 key 对应 Node 的时间复杂度为 O(n)，而转为红黑树后查询时间复杂度则为 O(logn)，性能提升很大。
1.3.1 为什么超过8要转为红黑树
- 红黑树占用的空间更大，链表更小一些
- 冲突大于8的时候，概率很小了
- 如果大于8了，为了保证查询效率，就使用了红黑树
2、Java8中ConcurrentHashMap的构造器源码分析
sizeCtl 变量：用于标识 table 初始化或者扩容
- 负数：表示 table 正在进行初始化或者扩容，-1表示正在初始化，-N，表示有N-1个线程正在进行扩容
- 0 表示还没有被初始化，
- 正数，初始化或者是下一次进行扩容的阈值
通过下面的构造器源码，我们可以看到，所有构造器中并没有初始化 table，，在空参构造器中，什么都没做，sizeCtl依然是初始值0，而在其他有非空参构造器中只是给成员变量 sizeCtl 赋值 ，也就是计算 table 在初始化时的容量，这个容量值一定是2的n次幂 ，步骤：
1、判断入参的 initialCapacity 的合法性
2、根据 initialCapacity 计算 table 的初始化容量值 cap，并且设置变量 sizeCtl = cap;
public class ConcurrentHashMap extends AbstractMap
implements ConcurrentMap, Serializable {
...
// table 最大容量
private static final int MAXIMUM_CAPACITY = 1 << 30;
// 空参构造器时，table初始化时的默认容量，16
private static final int DEFAULT_CAPACITY = 16;
//用于标识 table 初始化或者扩容
//负数：表示 table 正在进行初始化或者扩容，-1表示正在初始化，-N，表示有N-1个线程正在进行扩容
//0 表示还没有被初始化，
//正数，table 初始化或者是下一次进行扩容的阈值
private transient volatile int sizeCtl;
// table 是 Node数组
transient volatile Node[] table;
/*
* Node节点中 hash 字段的特殊值
*/
static final int MOVED = -1; // 正在转移Node
static final int TREEBIN = -2; // 红黑树根节点的hash值
static final int RESERVED = -3; // 暂时保留
static final int HASH_BITS = 0x7fffffff; // 正常节点 hash 的可用bits
// 空参构造器
public ConcurrentHashMap() {
}
// 入参是 initialCapacity，用于计算 table 初始容量
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
// 计算 table 初始化时的容量 cap 取值是 2的n次幂
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
// tableSizeFor(c) 计算 c 的上舍入到2的n次幂，并且取值范围：[1,MAXIMUM_CAPACITY]
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
// table 初始化时的
this.sizeCtl = cap;
}
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
}
// 入参 initialCapacity 和 loadFactor 用于计算初始容量，
// concurrencyLevel只是用于约束 initialCapacity 是否合法，没有其他作用
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
// initialCapacity 的值必须要大于等于 concurrencyLevel
if (initialCapacity < concurrencyLevel) // Use at least as many bins
initialCapacity = concurrencyLevel; // as estimated threads
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
// 计算 table 初始化时的容量 cap 取值是 2的n次幂
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
// tableSizeFor(size) 计算 size 的上舍入到2的n次幂，并且取值范围：[1,MAXIMUM_CAPACITY]
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}
// 计算c的上舍入到2的n次幂，并且取值范围：[1,MAXIMUM_CAPACITY]
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;
}
...
}
3、Java8中ConcurrentHashMap put()/putIfAbsent() 方法源码分析
onlyIfAbsent模式：
1、如果 map 中存在key的映射，则返回已有的映射对应的value，不做其他事情；
2、如果 map 未存在key的映射，则将 key 映射到的指定value。
非onlyIfAbsent模式，则不管key对应的映射是否已经存在，都将 key 映射到的新的value。
put() 和 putIfAbsent() 调用的都是 putVal()，区别只是是否是 onlyIfAbsent 模式；
putVal() 方法步骤：
- 判断 key 和 value 不为null
- 使用 key.hashCode() 计算 hash 值
- 如果 table 还未初始化，使用 sizeCtl 的值初始化 table
- 找到 hash 对应table中的下标i，tabAt()获得table中下标i的元素 Node f ,这个 Node f 只是 key对应的Node所在的链表或者红黑树的根节点
4.1. 如果f==null，新建 Node，通过 cas 算法设置 Node 为table中下标i对应的元素
4.2. 如果 f 不为null，并且f的hash值为MOVED，表示正在扩容，帮助扩容
4.3. 如果 Node f 不为null，当前table的状态并不是正在扩容，用 synchronized 在Node上加锁
4.3.1. 如果 Node f 的hash值大于等于0，表示 Node f 挂的是 Node 链表，遍历链表，
4.3.1.1. 如果 key 对应的 Node 不存在，直接新建Node，并设置值为 value
4.3.1.2. 如果 key 对应的 Node 已经存在，获取key对应的旧值，如果不是onlyIfAbsent模式，则设置key的映射为新值value；
4.3.2. 如果 Node f 挂的是红黑树，在红黑树中找到或者添加 key 对应的节点 p，获取旧值，如果不是onlyIfAbsent模式，则设置key的映射为新值value；
4.4. 如果链表中的元素个数大于等于转换为红黑树的阈值 8 ，转为红黑树。如果put操作之前，就已经存在key对应的映射，返回旧值 oldValue，putVal() 方法运行结束。 - oldValue == null，则表示时新增一个Node，则map中的元素+1，并判断元素数量是否大于等于扩容阈值，如果已经大于阈值则进行扩容
5.1. 如果需要扩容，新建当前table容量2倍的 new table，并将 tab 中的所有node转移到新table中，
注意：，在扩容方法transfer(tab, nextTab)中，如果当前元素个数小于 UNTREEIFY_THRESHOLD == 6，将树转为链表
5.2. 如果不需要扩容，返回null，putVal() 方法运行结束
// 在map中将 key 映射到的指定value。key 和 value 都不能为null。返回 key 在map 中映射的前一个值，没有则返回 null
public V put(K key, V value) {
return putVal(key, value, false);
}
// onlyIfAbsent模式：如果 map 中存在key的映射，则返回已有的映射对应的value，不做其他事情；
// 如果 map 未存在key的映射，则将 key 映射到的指定value，返回 null。
public V putIfAbsent(K key, V value) {
return putVal(key, value, true);
}
/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
// 判断 key 和 value 不为null
if (key == null || value == null) throw new NullPointerException();
// 使用 key.hashCode() 计算 hash 值
int hash = spread(key.hashCode());
int binCount = 0;
// 遍历 table，这里也是自旋直到某个分支成功，最后再break出循环
for (Node[] tab = table;;) {
Node f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable();// 使用 sizeCtl 的值初始化 table
//找到 hash 对应table中的下标i，tabAt()获得table中下标i的元素 Node f，校验 Node f 是否为null
//这个 Node f 只是 key对应的Node所在的链表或者红黑树的根节点
//如果 Node f 挂的是链表，则 Node f 代表链表根节点，如果 Node f 挂的是红黑树，则f表示树的根节点。
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//如果f==null，新建 Node，通过 cas 算法设置 Node 为table中下标i对应的元素
if (casTabAt(tab, i, null, new Node(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// 找到key对应的 Node f 不为null，并且f的hash值为MOVED，表示正在扩容
else if ((fh = f.hash) == MOVED)
// 如果正在扩容，则帮助移动 Node f
tab = helpTransfer(tab, f);
else {
//table中下标i对应的元素 Node f 不为null，当前table的状态并不是正在扩容
// 这个 Node f 只是 key对应的Node所在的链表或者红黑树的根节点
V oldVal = null;
// 用 hash 定位到table的Node，用 synchronized 在Node上加锁
synchronized (f) {
if (tabAt(tab, i) == f) {
/*
hash的特殊值：
static final int MOVED = -1; // 正在转移Node
static final int TREEBIN = -2; // 红黑树根节点的hash值
static final int RESERVED = -3; // 暂时保留
static final int HASH_BITS = 0x7fffffff; // 正常节点 hash 的可用bits
*/
if (fh >= 0) {//节点hash值大于等于0，表示节点挂的是 Node 链表
//binCount表示链表中的元素个数
binCount = 1;
// 遍历链表
for (Node e = f;; ++binCount) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
// 找到链表中，key对应的 Node，获取key对应的旧值
oldVal = e.val;
if (!onlyIfAbsent)//如果不是onlyIfAbsent模式，则直接设置key的映射为新值value
e.val = value;
break;
}
Node pred = e;
if ((e = e.next) == null) {
// 找到链表末尾都还未找到key对应的 Node，表示map中还不存在该key，直接新建Node，并设置值为 value
pred.next = new Node(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {
// 如果是红黑树
Node p;
binCount = 2;
//在红黑树中找到或者添加 key 对应的节点 p，如果是添加，添加成功后返回null
if ((p = ((TreeBin)f).putTreeVal(hash, key,
value)) != null) {
// 并获取旧值
oldVal = p.val;
if (!onlyIfAbsent)//如果不是onlyIfAbsent模式，则直接设置key的映射为新值value
p.val = value;
}
}
}
}
if (binCount != 0) {
// 如果链表中的元素个数大于等于转换为红黑树的阈值 8
if (binCount >= TREEIFY_THRESHOLD)
//转为红黑树
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//map中的元素+1，并判断元素数量是否大于等于扩容阈值，进行扩容
addCount(1L, binCount);
return null;
}
// 使用 sizeCtl 的值初始化 table
private final Node[] initTable() {
Node[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
// sizeCtl<0 表示 table 正在进行初始化或者扩容，-1表示正在初始化，-N，表示有N-1个线程正在进行扩容
// Thread.yield()表示让出 cpu 资源，线程重新变成就绪状态，重新竞争cpu，也就是自旋
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {// cas算法，将 sizeCtl 设置为-1，表示当前线程正在初始化 table
try {
// 再次检查table还未被初始化
if ((tab = table) == null || tab.length == 0) {
// sc的值是 sizeCtl进行 cas 运算之前的值
// 如果是空参构造器 ConcurrentHashMap() 则 sizeCtl 还未被赋值=0；
// 如果是非空参构造器，都已对sizeCtl变量赋值，也就是计算 table 在初始化时的容量，这个容量值一定是2的n次幂
// sc > 0 表示已经在构造器中计算了 table 的初始化容量，否则是空参构造初始化 ConcurrentHashMap 则使用默认容量 DEFAULT_CAPACITY = 16；
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node[] nt = (Node[])new Node<?,?>[n];
table = tab = nt;
// 计算table下一次进行扩容的阈值，n-0.25n=0.75n
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
// map中的元素+1，并判断是否需要进行扩容，如果需要扩容，则帮助执行扩容
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
...
// 当前map中元素数量
s = sumCount();
}
if (check >= 0) {
Node[] tab, nt; int n, sc;
// 当 s表示当前map中元素数量， 大于等于扩容阈值，进行扩容
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))
// 将 tab 中的所有node，转移到 nt 中
transfer(tab, nt);
}
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
// 第二个参数为null时，新建2倍容量的table，并将 tab 中的所有node转移到新table中
transfer(tab, null);
s = sumCount();
}
}
}
// tab 中的所有node转移到 nextTab 中
private final void transfer(Node[] tab, Node[] nextTab) {
// n等于当前tab的容量
int n = tab.length, stride;
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
if (nextTab == null) { // initiating
// nextTab == null，则新建
try {
@SuppressWarnings("unchecked")
// 新table的容量时 tab的容量的两倍
Node[] nt = (Node[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n;
}
...
// 如果当前元素个数小于 UNTREEIFY_THRESHOLD == 6，将树转为链表
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
3、Java8中ConcurrentHashMap remove() 方法源码分析
remove(key) 方法会调用 replaceNode(key, null, null)，下面我们直接分析 replaceNode() 的实现。
>replaceNode(Object key, V value, Object cv)
>将节点值替换为新的value，如果入参cv不等于null，且满足 cv 等于节点的旧值才能进行替换，如果替换时，value为null，则删除节点，返回旧值
replaceNode() 方法步骤：
- 根据 key.hashCode() 计算 hash
- 如果 table 还未初始化，或者 找到 hash 对应table中的下标i，通过 tabAt() 方法获得table中下标i 的元素 Node f
这个 Node f 只是 key对应的Node所在的链表或者红黑树的根节点，如果 f==null，返回null - Node f 不为null，并且f的hash值为MOVED，表示正在扩容，帮助扩容
- 如果 Node f 不为null，当前table的状态并不是正在扩容，用 synchronized 在Node上加锁
4.1. 如果 Node f 的hash值大于等于0，表示 Node f 挂的是 Node 链表，遍历链表
4.1.1. 如果找到 key 对应的 node ，替换node的值为 value，如果 cv != null 时，需要满足 cv.equals(ev) 才能替换，ev时node的旧值。如果替换掉新值value==null，表示删除key对应的节点
4.1.2. 如果找不到key对应的node，返回 null。
4.2. 如果 Node f 挂的是红黑树，在红黑树中找到或者添加 key 对应的节点 p，获取旧值 pv，替换node的值为 value，如果 cv != null 时，需要满足 cv.equals(pv) 才能替换 - oldValue != null，则表示时删除一个Node，则map中的元素数量-1
// 删除map中key对应的映射，如果key不存在，则什么都不做，返回null，否则返回key对应的value
public V remove(Object key) {
return replaceNode(key, null, null);
}
/**
* 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.
*/
// 将节点值替换为新的value，如果入参cv不等于null，且满足 cv 等于节点的旧值才能进行替换，如果替换时，value为null，则删除节点
final V replaceNode(Object key, V value, Object cv) {
// 根据 key.hashCode() 计算 hash
int hash = spread(key.hashCode());
// 自旋遍历 table
for (Node[] tab = table;;) {
Node f; int n, i, fh;
//如果 table 还未初始化，或者 找到 hash 对应table中的下标i，通过 tabAt() 方法获得table中下标i 的元素 Node f ==null，返回null
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
break;
// 找到key对应的 Node f 不为null，并且f的hash值为MOVED，表示正在扩容，帮助扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
boolean validated = false;
// synchronized 在 Node f 上加锁
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
// Node f 的hash值大于0，链表的头节点
validated = true;
for (Node e = f, pred = null;;) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
// 找到 key 对应的 Node
V ev = e.val;
// 替换node的值为 value，如果 cv != null 时，需要满足 cv.equals(ev) 才能替换
if (cv == null || cv == ev ||
(ev != null && cv.equals(ev))) {
oldVal = ev;
if (value != null)
e.val = value;
// 下面两个else，表示新值 value==null，则直接删除node
else if (pred != null)//前节点不为null
pred.next = e.next;
else// 前节点为null，表示当前删除的node是头节点，设置node的next节点为头节点
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
if ((e = e.next) == null)// 找不到key对应的node
break;
}
}
else if (f instanceof TreeBin) {
// Node f 是红黑树的根节点
validated = true;
TreeBin t = (TreeBin)f;
TreeNode r, p;
if ((r = t.root) != null &&
(p = r.findTreeNode(hash, key, null)) != null) {
//在红黑树中找到 key 对应的节点 p，获取节点旧值 pv
V pv = p.val;
// 替换node的值为 value，如果 cv != null 时，需要满足 cv.equals(pv) 才能替换
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)
//map中的元素-1
addCount(-1L, -1);
return oldVal;
}
break;
}
}
}
return null;
}
4、Java8中ConcurrentHashMap get() 方法源码分析
>get()：查询 key 的映射值 value
get() 源码大概是如下几个步骤：
- 根据 key.hashCode() 计算 hash
- 如果table 不为null，而且用hash值，通过 tabAt() 方法找到节点 e，e是key对应的Node所在的链表或者红黑树的根节点
- 如果根节点e刚好是 key 对应的Node，返回节点e的value
- 如果节点e 的hash值小于0，表示是红黑树的根节点，遍历树找到节点p，如果p!=null，返回p的value，否则返回 null
- 如果 节点e 是链表的根节点，则遍历链表，查找是否存在key对应的node，找到则返回 node 的value，否则返回null
// 查询 key 的映射值 value
public V get(Object key) {
Node[] tab; Node e, p; int n, eh; K ek;
// 根据 key.hashCode() 计算 hash
int h = spread(key.hashCode());
// 如果table 不为null，而且用hash值，通过 tabAt() 方法找到节点 e，e是key对应的Node所在的链表或者红黑树的根节点
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 找到key对应的Node所在的链表或者红黑树的根节点 e
if ((eh = e.hash) == h) {
//根节点e刚好是 key 对应的Node，返回节点e的value
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
// 节点e 的hash值小于0，表示是红黑树的根节点，遍历树找到节点p，如果p!=null，返回p的value，否则返回 null
return (p = e.find(h, key)) != null ? p.val : null;
// 如果 节点e 是链表的根节点，则遍历链表，查找是否存在key对应的node，找到则返回 node 的value，否则返回null
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
上面，经过了好久，终于搞定了 Java8 中 ConcurrentHashMap 的 构造器、putVal()方法、remove() 和 get() 的源码分析，可以看到：
- 在构造器中，并没有初始化table，只是给 sizeCtl 变量赋值，该变量的值就是 table 初始化时的容量
- get() 方法的遍历查询 key 对应的 node 不加锁
- putVal() 方法 和 remove() 调用的 replaceNode() 中，根据 key 的 hash 值找到key对应的Node所在的链表或者红黑树的根节点，在根节点上加上 synchronized 锁，从而实现 put() 和 remove() 操作线程安全。Java8中，锁的粒度是table中的Node对象，也就是链表或者红黑树的根节点。
- 当Node链表中的元素个数大于阈值8时，由链表转为红黑树；当红黑树中的元素个数小于6时，又由红黑树转为链表。
>代码：
>github.com/wengxingxia/002juc.git