ConcurrentHashMap源码剖析-JDK18
前语
ConcurrentHashMap是一个线程安全的HashMap，首要用于处理HashMap中并发问题。
在ConcurrentHashMap之前，也有线程安全的HashMap，比方HashTable和Collections.synchronizedMap，但遍及功率低下。
Hashtable功率不高是由于它对数据操作的时分都会经过synchronized上锁，也便是咱们在讲synchronized说的同步办法。而Collections.synchronizedMap的功率不高是由于在SynchronizedMap内部保护了一个一般目标Map，还有 排挤锁mutex，咱们在调用这个办法的时分就需求传入一个Map，mutex参数能够传也能够不传。创立出synchronizedMap之后，再操作map的时分，就会对这些办法上锁(如下)，也便是咱们说的同步代码块，所以功能不高。
因而，才有了JDK1.5引进的ConcurrentHashMap！
ConcurrentHashMap在JDK1.7之前改变不大，在1.8中修正了较多，下面剖析一下1.7和1.8中的改变：
- 锁方面： 由分段锁（
Segment承继自ReentrantLock）晋级为 CAS+synchronized完成； - 数据结构层面： 将
Segment变为了Node，减小了锁粒度，使每个Node独立，由本来默许的并发度16变成了每个Node都独立，提高了并发度； - hash抵触： 1.7中产生hash抵触选用链表存储，1.8中先运用链表存储，后边满意条件后会转化为红黑树来优化查询。由于运用了红黑树，jdk1.7中链表查询杂乱度为O(N)，jdk1.8中红黑树优化为O(logN))。
承继与完成
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
implements ConcurrentMap<K,V>, Serializable
能够看到ConcurrentHashMap承继了AbstractMap，完成了ConcurrentMap和Serializable。
AbstractMap，这是一个java.util包下的抽象类，供给Map接口的主干完成，以最大极限地削减完成Map这类数据结构时所需的作业量，一般来讲，假如需求重复造轮子——自己来完成一个Map，那一般便是承继AbstractMap。
ConcurrentHashMap完成了ConcurrentMap这个接口，ConcurrentMap是在JDK1.5时跟着J.U.C包引进的，这个接口其实便是供给了一些针对Map的原子操作：
package java.util.concurrent;
import java.util.Map;
import java.util.Objects;
import java.util.function.BiConsumer;
import java.util.function.BiFunction;
import java.util.function.Function;
public interface ConcurrentMap<K,V> extends Map<K,V> {
//回来指定key对应的值；假如Map不存在该key，则回来defaultValue
default V getOrDefault(Object key, V defaultValue) { ...}
//遍历Map的一切Entry，并对其进行指定的aciton操作
default void forEach(BiConsumer<? super K, ? super V> action) {...}
//假如Map不存在指定的key，则刺进<K,V>；不然，直接回来该key对应的值
V putIfAbsent(K key, V value);
//删去与<key,value>彻底匹配的Entry，并回来true；不然，回来false
boolean remove(Object key, Object value);
//假如存在key，且值和oldValue共同，则更新为newValue，并回来true；不然，回来false
boolean replace(K key, V oldValue, V newValue);
//假如存在key，则更新为value，回来旧value；不然，回来null
V replace(K key, V value);
//遍历Map的一切Entry，并对其进行指定的funtion操作
default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) {...}
//假如Map不存在指定的key，则经过mappingFunction核算出value并刺进
default V computeIfAbsent(K key , Function<? super K, ? extends V> mappingFunction{...}
//假如Map存在指定的key，则经过mappingFunction核算出value并替换旧值
default V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {...}
//依据指定的key，查找value；然后依据得到的value和remappingFunction从头核算出新值，并替换旧值
default V compute(K key , BiFunction<? super K, ? super V, ? extends V> remappingFunction) {...}
//假如key不存在，则刺进value；不然，依据key对应的值和remappingFunction核算出新值，并替换旧值
default V merge(K key, V value , BiFunction<? super V, ? super V, ? extends V> remappingFunction) {...}
而Serializable则标志这个类能够进行序列化。
数据结构
ConcurrentHashMap的数据结构比照HashMap要杂乱许多，所以在看结构器之前先剖析一下它的数据结构。
从上图能够看出，table总共包括 4 种不同类型的桶，不同的桶用不同色彩表明，分别是Node、TreeBin、ForwardingNode和ReservationNode这四种结点。
别的，TreeBin结点所衔接的是一颗红黑树，红黑树结点运用TreeNode表明，加上前面四种总共是5种结点。
而这儿没有直接运用TreeNode的原因是由于红黑树的操作比较杂乱，包括构建、左旋、右旋、删去，平衡等操作，用一个署理结TreeBin来包括这些杂乱操作，其实是一种 “责任别离”的思维，别的TreeBin中也包括了一些加/解锁操作。
Node结点
- Node是其它四种类型结点的父类；
- 默许链接到table[i]，即桶上的结点便是Node结点；
- 当呈现hash抵触时，Node结点会首先以链表的办法链接到table上，当超越阈值的时分才会转化为红黑树。
/**
* 一般的Entry结点, 以链表办法保存时才会运用, 存储实践的数据.
*/
static class Node<K, V> implements Map.Entry<K, V> {
final int hash; //经过key核算hash值，经过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)));
}
/**
* 链表查找.
*/
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;
}
}
TreeNode结点
TreeNode是红黑树的结点，TreeNode不会直接链接到桶上面，而是由TreeBin链接，TreeBin会指向红黑树的根结点。
/**
* 红黑树结点, 存储实践的数据.
*/
static final class TreeNode<K, V> extends Node<K, V> {
boolean red;
TreeNode<K, V> parent;
TreeNode<K, V> left;
TreeNode<K, V> right;
/**
* prev指针是为了便利删去.
* 删去链表的非头结点时，需求知道它的前驱结点才干删去，所以直接供给一个prev指针
*/
TreeNode<K, V> prev;
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);
}
/**
* 以当时结点（this）为根结点，开端遍历查找指定key.
*/
final TreeNode<K, V> findTreeNode(int h, Object k, Class<?> kc) {
if (k != null) {
TreeNode<K, V> p = this;
do {
int ph, dir;
K pk;
TreeNode<K, V> q;
TreeNode<K, V> pl = p.left, pr = p.right;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.findTreeNode(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
}
return null;
}
}
TreeBin结点
TreeBin相当于TreeNode的署理结点；TreeBin会直接链接到 table[i] 上，该结点供给了一系列红黑树相关的操作，以及加锁、解锁操作。
/*
TreeNode的署理结点（相当于封装了TreeNode的容器，供给针对红黑树的转化操作和锁操控）
hash值固定为-2
*/
static final class TreeBin<K,V> extends Node<K,V> {
TreeNode<K,V> root; // 红黑树结构的根结点
volatile TreeNode<K,V> first; // 链表结构的头结点
volatile Thread waiter; // 最近的一个设置WAITER标识位的线程
volatile int lockState; // 全体的锁状况标识位，0为初始态
// values for lockState
static final int WRITER = 1; // 二进制001，红黑树的写锁状况
static final int WAITER = 2; // 二进制010，红黑树的等候获取写锁状况（优先锁，当有锁等候，读就不能增加了）
// 二进制100，红黑树的读锁状况，读能够并发，每多一个读线程，lockState都加上一个READER值，
static final int READER = 4;
/*
在hashCode持平而且不是Comparable类型时，用此办法判别巨细.
*/
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;
}
// 将以b为头结点的链表转化为红黑树
TreeBin(TreeNode<K,V> b) {...}
// 经过lockState,对红黑树的根结点➕写锁.
private final void lockRoot() {
if (!U.compareAndSetInt(this, LOCKSTATE, 0, WRITER))
contendedLock(); // offload to separate method ，Possibly blocks awaiting root lock.
}
//开释写锁
private final void unlockRoot() { lockState = 0; }
// 从根结点开端遍历查找，找到“持平”的结点就回来它，没找到就回来null，当存在写锁时，以链表办法进行查找，后会面会介绍
final Node<K,V> find(int h, Object k) {... }
/**
* 查找指定key对应的结点,假如未找到，则直接刺进.
* @return 直接刺进成功回来null, 替换回来找到的结点的oldVal
*/
final TreeNode<K,V> putTreeVal(int h, K k, V v) {...}
/*
删去红黑树的结点：
1. 红黑树规划太小时，回来true，然后进行 树 -> 链表 的转化，最终删去;
2. 红黑树规划满足时，不必变换成链表，但删去结点时需求加写锁;
*/
final boolean removeTreeNode(TreeNode<K,V> p) {...}
// 以下是红黑树的经典操作办法，改编自《算法导论》
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root , TreeNode<K,V> p) { ...}
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root , TreeNode<K,V> p) {...}
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root , TreeNode<K,V> x) {...}
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root, TreeNode<K,V> x) { ... }
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {...} //递归查看红黑树的正确性
private static final long LOCKSTATE= U.objectFieldOffset(TreeBin.class, "lockState");
}
ForwardingNode结点
ForwardingNode结点仅仅在 扩容 时才会运用
/**
* ForwardingNode是一种暂时结点，在扩容进行中才会呈现，hash值固定为-1，且不存储实践数据。
* 假如旧table数组的一个hash桶中悉数的结点都搬迁到了新table中，则在这个桶中放置一个ForwardingNode，即table[i]=ForwardingNode。
* 读操作碰到ForwardingNode时，将操作转发到扩容后的新table数组上去履行；写操作碰见它时，则测验帮忙扩容。
*/
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;
}
// 在新的数组nextTable上进行查找
Node<K, V> find(int h, Object k) {
// loop to avoid arbitrarily deep recursion on forwarding nodes
outer:
for (Node<K, V>[] tab = nextTable; ; ) {
Node<K, V> e;
int n;
if (k == null || tab == null || (n = tab.length) == 0 ||
(e = tabAt(tab, (n - 1) & h)) == null)
return null;
for (; ; ) {
int eh;
K ek;
if ((eh = e.hash) == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
if (eh < 0) {
if (e instanceof ForwardingNode) {
tab = ((ForwardingNode<K, V>) e).nextTable;
continue outer;
} else
return e.find(h, k);
}
if ((e = e.next) == null)
return null;
}
}
}
}
ReservationNode结点
保存结点，ConcurrentHashMap中的一些特别办法会专门用到该类结点。
/**
* 保存结点.
* hash值固定为-3， 不保存实践数据
* 只在computeIfAbsent和compute这两个函数式API中充任占位符加锁运用
*/
static final class ReservationNode<K, V> extends Node<K, V> {
ReservationNode() {
super(RESERVED, null, null, null);
}
Node<K, V> find(int h, Object k) {
return null;
}
}
结构器办法
ConcurrentHashMap供给了五个结构器，这五个结构器内部最多也仅仅核算了下table的初始容量巨细，并没有进行实践的创立table数组的作业。
由于ConcurrentHashMap用了一种懒加载的方法，只要到初次刺进键值对的时分，才会真实的去初始化table数组。
空结构器
public ConcurrentHashMap() {
}
指定table初始容量的结构器
/**
* 指定table初始容量的结构器.
* tableSizeFor会回来大于入参（initialCapacity + (initialCapacity >>> 1) + 1）的最小2次幂值
*/
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;
}
依据已有的Map结构
/**
* 依据已有的Map结构ConcurrentHashMap.
*/
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
this.sizeCtl = DEFAULT_CAPACITY;
putAll(m);
}
指定table初始容量和负载因子的结构器
/**
* 指定table初始容量和负载因子的结构器.
*/
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
}
指定table初始容量、负载因子、并发等级的结构器
/**
* 指定table初始容量、负载因子、并发等级的结构器.
* <p>
* 留意：concurrencyLevel仅仅为了兼容JDK1.8曾经的版别，并不是实践的并发等级，loadFactor也不是实践的负载因子
* 这两个都失去了原有的含义，仅仅对初始容量有必定的操控效果
*/
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (initialCapacity < concurrencyLevel)
initialCapacity = concurrencyLevel;
long size = (long) (1.0 + (long) initialCapacity / loadFactor);
int cap = (size >= (long) MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int) size);
this.sizeCtl = cap;
}
常量/字段
源码中常量如下：
/**
* 最大容量.
*/
private static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默许初始容量
*/
private static final int DEFAULT_CAPACITY = 16;
/**
* 最大数组长度
*/
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 负载因子，为了兼容JDK1.8曾经的版别而保存。
* JDK1.8中的ConcurrentHashMap的负载因子恒定为0.75
*/
private static final float LOAD_FACTOR = 0.75f;
/**
* 链表转树的阈值，即链接结点数大于8时， 链表转化为树.
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 树转链表的阈值，即树结点树小于6时，树转化为链表.
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 在链表转变成树之前，还会有一次判别：
* 即只要键值对数量大于MIN_TREEIFY_CAPACITY，才会产生转化。
* 这是为了避免在Table树立初期，多个键值对刚好被放入了同一个链表中而导致不必要的转化。
*/
static final int MIN_TREEIFY_CAPACITY = 64;
/**
* 在树转变成链表之前，还会有一次判别：
* 即只要键值对数量小于MIN_TRANSFER_STRIDE，才会产生转化.
*/
private static final int MIN_TRANSFER_STRIDE = 16;
/**
* 用于在扩容时生成仅有的随机数.
*/
private static int RESIZE_STAMP_BITS = 16;
/**
* 可一起进行扩容操作的最大线程数.
*/
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
/**
* The bit shift for recording size stamp in sizeCtl.
*/
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
static final int MOVED = -1; // 标识ForwardingNode结点（在扩容时才会呈现，不存储实践数据）
static final int TREEBIN = -2; // 标识红黑树的根结点
static final int RESERVED = -3; // 标识ReservationNode结点（）
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
/**
* CPU中心数，扩容时运用
*/
static final int NCPU = Runtime.getRuntime().availableProcessors();
源码中字段如下：
/**
* Node数组，标识整个Map，初次刺进元素时创立，巨细总是2的幂次.
*/
transient volatile Node<K, V>[] table;
/**
* 扩容后的新Node数组，只要在扩容时才非空.
*/
private transient volatile Node<K, V>[] nextTable;
/**
* 操控table的初始化和扩容（重要⭐⭐⭐）
* 0 : 初始默许值
* -1 : 有线程正在进行table的初始化
* >0 : table初始化时运用的容量，或初始化/扩容完成后的threshold
* -(1 + nThreads) : 记载正在履行扩容使命的线程数
*/
private transient volatile int sizeCtl;
/**
* 扩容时需求用到的一个下标变量.
*/
private transient volatile int transferIndex;
/**
* 计数基值,当没有线程竞赛时，计数将加到该变量上。类似于LongAdder的base变量
*/
private transient volatile long baseCount;
/**
* 计数数组，呈现并发抵触时运用。类似于LongAdder的cells数组
*/
private transient volatile CounterCell[] counterCells;
/**
* 自旋标识位，用于CounterCell[]扩容时运用。类似于LongAdder的cellsBusy变量
*/
private transient volatile int cellsBusy;
// 视图相关字段
private transient KeySetView<K, V> keySet;
private transient ValuesView<K, V> values;
private transient EntrySetView<K, V> entrySet;
put()办法
put办法是ConcurrentHashMap类的中心办法
/**
* 刺进键值对，<K,V>均不能为null.
*/
public V put(K key, V value) {
return putVal(key, value, false);
}
这儿提一嘴，为什么ConcurrentHashMap和Hashtable的key和value都不答应为null，而HashMap能够呢？
这是由于ConcurrentHashMap和Hashtable都是支撑并发的，这样会有一个问题，当你经过get(k)获取对应的value时，假如获取到的是null时，你无法判别，它是put（k,v）的时分value就为null，仍是这个key从来没有做过映射。
而HashMap对错并发的，能够经过contains(key)来进行校验。而支撑并发的Map在调用m.contains（key）和m.get(key)时m或许现已不同了。
put办法内部调用了putVal这个私有办法：
/**
* 实践的刺进操作
* @param onlyIfAbsent true:仅当key不存在时,才刺进
*/
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode()); // 再次核算hash值
/**
* 运用链表保存时，binCount记载table[i]这个桶中所保存的结点数；
* 运用红黑树保存时，binCount==2，确保put后更改计数值时能够进行扩容查看，一起不触发红黑树化操作
*/
int binCount = 0;
for (Node<K, V>[] tab = table; ; ) { // 自旋刺进结点，直到成功
Node<K, V> f;
int n, i, fh;
if (tab == null || (n = tab.length) == 0) // CASE1: 初次初始化table —— 懒加载
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // CASE2: table[i]对应的桶为null
// 留意下上面table[i]的索引i的核算办法：[ key的hash值 & (table.length-1) ]
// 这也是table容量有必要为2的幂次的原因，读者能够自己看下当table.length为2的幂次时，(table.length-1)的二进制办法的特色 —— 满是1
// 合作这种索引核算办法能够完成key的均匀分布，削减hash抵触
if (casTabAt(tab, i, null, new Node<K, V>(hash, key, value, null))) // 刺进一个链表结点
break;
} else if ((fh = f.hash) == MOVED) // CASE3: 发现ForwardingNode结点，阐明此刻table正在扩容，则测验帮忙数据搬迁
tab = helpTransfer(tab, f);
else { // CASE4: 呈现hash抵触,也便是table[i]桶中现已有了结点
V oldVal = null;
synchronized (f) { // 锁住table[i]结点
if (tabAt(tab, i) == f) { // 再判别一下table[i]是不是第一个结点, 避免其它线程的写修正
if (fh >= 0) { // CASE4.1: table[i]是链表结点
binCount = 1;
for (Node<K, V> e = f; ; ++binCount) {
