一、注释解读
/**
* A hash table supporting full concurrency of retrievals and
* high expected concurrency for updates. This class obeys the
* same functional specification as {@link java.util.Hashtable}, and
* includes versions of methods corresponding to each method of
* {@code Hashtable}. However, even though all operations are
* thread-safe, retrieval operations do <em>not</em> entail locking,
* and there is <em>not</em> any support for locking the entire table
* in a way that prevents all access. This class is fully
* interoperable with {@code Hashtable} in programs that rely on its
* thread safety but not on its synchronization details.
*
- 是一个支持完全并发的查找检索，和高并发更新的 hashtable
- 遵循 hashtable 相同的功能规范，并且有相对应的版本
- 虽然所有的操作都是线程安全的，而且查找不需要加锁，但是并不支持对整个表锁定来阻止所有的访问
- 他可以和 hashtable 互操作，因为他依赖线程安全，但是不依赖同步细节
/* <p>Retrieval operations (including {@code get}) generally do not
* block, so may overlap with update operations (including {@code put}
* and {@code remove}). Retrievals reflect the results of the most
* recently <em>completed</em> update operations holding upon their
* onset. (More formally, an update operation for a given key bears a
* <em>happens-before</em> relation with any (non-null) retrieval for
* that key reporting the updated value.) For aggregate operations
* such as {@code putAll} and {@code clear}, concurrent retrievals may
* reflect insertion or removal of only some entries. Similarly,
* Iterators, Spliterators and Enumerations return elements reflecting the
* state of the hash table at some point at or since the creation of the
* iterator/enumeration. They do <em>not</em> throw {@link
* java.util.ConcurrentModificationException ConcurrentModificationException}.
* However, iterators are designed to be used by only one thread at a time.
* Bear in mind that the results of aggregate status methods including
* {@code size}, {@code isEmpty}, and {@code containsValue} are typically
* useful only when a map is not undergoing concurrent updates in other threads.
* Otherwise the results of these methods reflect transient states
* that may be adequate for monitoring or estimation purposes, but not
* for program control.
- 检索操作一般来说不会阻塞，所以可以和更新操作并发进行
- 检索反映了最近已完成更新操作的结果。对于 putall 和 clear 这样的集合操作，并发检索可能反映仅插入或删除某些条目
- 类似地，Iterators，Spliterators和Enumerations在迭代器/枚举的创建时或之后的某个时刻返回反映哈希表状态的元素。他们不会抛出 ConcurrentModificationException
- 但是，迭代器被设计成每次只能被一条线程使用
- size、isEmpty、containsValue 这类聚合状态的方法结果，只有在 map 不是处于并发更新状态时才有用
- 否则这些结果，只能用于监控或者估计，而不能用于程序控制
/* <p>The table is dynamically expanded when there are too many
* collisions (i.e., keys that have distinct hash codes but fall into
* the same slot modulo the table size), with the expected average
* effect of maintaining roughly two bins per mapping (corresponding
* to a 0.75 load factor threshold for resizing). There may be much
* variance around this average as mappings are added and removed, but
* overall, this maintains a commonly accepted time/space tradeoff for
* hash tables. However, resizing this or any other kind of hash
* table may be a relatively slow operation. When possible, it is a
* good idea to provide a size estimate as an optional {@code
* initialCapacity} constructor argument. An additional optional
* {@code loadFactor} constructor argument provides a further means of
* customizing initial table capacity by specifying the table density
* to be used in calculating the amount of space to allocate for the
* given number of elements. Also, for compatibility with previous
* versions of this class, constructors may optionally specify an
* expected {@code concurrencyLevel} as an additional hint for
* internal sizing. Note that using many keys with exactly the same
* {@code hashCode()} is a sure way to slow down performance of any
* hash table. To ameliorate impact, when keys are {@link Comparable},
* this class may use comparison order among keys to help break ties.
*
- 当hashcode冲突太多时，table 会动态扩展，并保持每个映射两个桶位的预期平均效果
- 因为映射被增加或删除，所以这个平均值会有比较大的方差，但是总体来看，他维持了一个可接受的时间空间的平衡
- 但是，对他进行 resize 会是一个相对缓慢的操作。最好是提供一个估计的大小值作为构造参数
- 另一个构造参数 loadFactor 提供了另一种自定义初始 table 的方法：通过指定计算用于分配给给定元素的空间的值——表的密度
- 同时为了兼容该类之前的版本，构造函数可以选择指定预期的{@code concurrencyLevel}作为内部大小调整的附加提示
- 太多的hashcode 相同时会降低性能，所以当 key 可排序时就用排序
/* <p>ConcurrentHashMaps support a set of sequential and parallel bulk
* operations that, unlike most {@link Stream} methods, are designed
* to be safely, and often sensibly, applied even with maps that are
* being concurrently updated by other threads; for example, when
* computing a snapshot summary of the values in a shared registry.
* There are three kinds of operation, each with four forms, accepting
* functions with Keys, Values, Entries, and (Key, Value) arguments
* and/or return values. Because the elements of a ConcurrentHashMap
* are not ordered in any particular way, and may be processed in
* different orders in different parallel executions, the correctness
* of supplied functions should not depend on any ordering, or on any
* other objects or values that may transiently change while
* computation is in progress; and except for forEach actions, should
* ideally be side-effect-free. Bulk operations on {@link java.util.Map.Entry}
* objects do not support method {@code setValue}.
- 可扩展频率映射ConcurrentHashMaps支持一组顺序和并行批量操作，与大多数{@link Stream}方法不同，它们被设计为安全且通常合理地应用，即使是由其他线程同时更新的映射;
-
因为ConcurrentHashMap的元素没有以任何特定的方式排序，并且可以在不同的并行执行中以不同的顺序处理，因此所提供的函数的正确性不应该依赖于任何排序，或者当计算进行的时候，其他可能瞬间改变的对象或值。除了 forearch外，就没有什么副作用
/* * Overview: * * The primary design goal of this hash table is to maintain * concurrent readability (typically method get(), but also * iterators and related methods) while minimizing update * contention. Secondary goals are to keep space consumption about * the same or better than java.util.HashMap, and to support high * initial insertion rates on an empty table by many threads. * * This map usually acts as a binned (bucketed) hash table. Each * key-value mapping is held in a Node. Most nodes are instances * of the basic Node class with hash, key, value, and next * fields. However, various subclasses exist: TreeNodes are * arranged in balanced trees, not lists. TreeBins hold the roots * of sets of TreeNodes. ForwardingNodes are placed at the heads * of bins during resizing. ReservationNodes are used as * placeholders while establishing values in computeIfAbsent and * related methods. The types TreeBin, ForwardingNode, and * ReservationNode do not hold normal user keys, values, or * hashes, and are readily distinguishable during search etc * because they have negative hash fields and null key and value * fields. (These special nodes are either uncommon or transient, * so the impact of carrying around some unused fields is * insignificant.) * - 这个 hashtable 是为了在最小化更新竞争的同时，保持并发的可读性。也是为了使空间消耗不高于 hashmap，并支持多线程在空表上的高插入速率
- 此 map 还有一些特殊的子类：TreeNode 换成了平衡树，TreeBins 保存 TreeNode 的根节点，ForwardingNodes 在 resize 的时候，被放在 bin 的头节点，ReservationNodes 被用作占位符。这几个子类都不持有正常的 key，value 或者 hash，在搜索中很容易区分，因为他们保存负的 hash，null key
/*The table is lazily initialized to a power-of-two size upon the
* first insertion. Each bin in the table normally contains a
* list of Nodes (most often, the list has only zero or one Node).
* Table accesses require volatile/atomic reads, writes, and
* CASes. Because there is no other way to arrange this without
* adding further indirections, we use intrinsics
* (sun.misc.Unsafe) operations.
*
* We use the top (sign) bit of Node hash fields for control
* purposes -- it is available anyway because of addressing
* constraints. Nodes with negative hash fields are specially
* handled or ignored in map methods.
table 在第一次插入数据的时候，会被懒加载成 2 次幂大小。每个桶位都会包含一个 node 列表。
对 table 的访问必须是 volatile 或者原子性的读，或者 CAS。
带有负变量的 node 通常被特殊处理或者忽略。
/* Insertion (via put or its variants) of the first node in an
* empty bin is performed by just CASing it to the bin. This is
* by far the most common case for put operations under most
* key/hash distributions. Other update operations (insert,
* delete, and replace) require locks. We do not want to waste
* the space required to associate a distinct lock object with
* each bin, so instead use the first node of a bin list itself as
* a lock. Locking support for these locks relies on builtin
* "synchronized" monitors.
*
* Using the first node of a list as a lock does not by itself
* suffice though: When a node is locked, any update must first
* validate that it is still the first node after locking it, and
* retry if not. Because new nodes are always appended to lists,
* once a node is first in a bin, it remains first until deleted
* or the bin becomes invalidated (upon resizing).
*
第一次在空的桶位插入一个 node，是通过 CAS 来操作的。这是目前大部分键值对 put最常用的方法。
其他的插入、删除和替换操作都需要锁。我们不想为每个桶位都加一个锁，这样太浪费空间。所以我们使用每个桶位的第一个 node 作为锁。这些锁的实现依赖于内部的同步监视器。
当一个 node 被锁定的时候，任何修改操作必须在 lock 之后验证他是否仍然是第一个 node。因为新 node 不停的再往 list 中添加。当一个 node 处于桶位的第一个时，除非被删除或者 resize，否则他一直是第一位。
* Lock contention probability for two threads accessing distinct
* elements is roughly 1 / (8 * #elements) under random hashes.
*
* Actual hash code distributions encountered in practice
* sometimes deviate significantly from uniform randomness. This
* includes the case when N > (1<<30), so some keys MUST collide.
* Similarly for dumb or hostile usages in which multiple keys are
* designed to have identical hash codes or ones that differs only
* in masked-out high bits. So we use a secondary strategy that
* applies when the number of nodes in a bin exceeds a
* threshold. These TreeBins use a balanced tree to hold nodes (a
* specialized form of red-black trees), bounding search time to
* O(log N). Each search step in a TreeBin is at least twice as
* slow as in a regular list, but given that N cannot exceed
* (1<<64) (before running out of addresses) this bounds search
* steps, lock hold times, etc, to reasonable constants (roughly
* 100 nodes inspected per operation worst case) so long as keys
* are Comparable (which is very common -- String, Long, etc).
* TreeBin nodes (TreeNodes) also maintain the same "next"
* traversal pointers as regular nodes, so can be traversed in
* iterators in the same way.
在随机哈希下，访问不同元素的两个线程的锁争用概率大约是1 /（8 * #elements）。
- 但是在实践中遇到的实际哈希码分布有时会明显偏离均匀随机性。当 N>2^30时，一些 key 必定会冲突。所以我们在 node 数量超过临界值时，使用了第二种策略——平衡树，一种特殊形式的红黑树，搜索复杂度为 O(logN)。
- TreeBins 中的搜索每次搜索都是普通 list 的两倍时间。但是当 N小于 1<<64，且只要 key 是可比较时，treeBins 会限制搜索和锁定时间在一个合理的范围内，最坏的情况是每次操作检查 100 个节点。
TreeBin节点（TreeNodes）也保持与常规节点相同的“下一个”遍历指针，因此可以以相同的方式遍历迭代器。
*
* The table is resized when occupancy exceeds a percentage
* threshold (nominally, 0.75, but see below). Any thread
* noticing an overfull bin may assist in resizing after the
* initiating thread allocates and sets up the replacement array.
* However, rather than stalling, these other threads may proceed
* with insertions etc. The use of TreeBins shields us from the
* worst case effects of overfilling while resizes are in
* progress. Resizing proceeds by transferring bins, one by one,
* from the table to the next table. However, threads claim small
* blocks of indices to transfer (via field transferIndex) before
* doing so, reducing contention. A generation stamp in field
* sizeCtl ensures that resizings do not overlap. Because we are
* using power-of-two expansion, the elements from each bin must
* either stay at same index, or move with a power of two
* offset. We eliminate unnecessary node creation by catching
* cases where old nodes can be reused because their next fields
* won't change. On average, only about one-sixth of them need
* cloning when a table doubles. The nodes they replace will be
* garbage collectable as soon as they are no longer referenced by
* any reader thread that may be in the midst of concurrently
* traversing table. Upon transfer, the old table bin contains
* only a special forwarding node (with hash field "MOVED") that
* contains the next table as its key. On encountering a
* forwarding node, access and update operations restart, using
* the new table.
当占用超过临界值时，就会触发 resize。在启动线程分配和设置替换数组之后，任何注意到过满bin的线程都可以帮助resize。但是，其他线程可能会继续处理插入等操作，而不是阻塞。当 resize 进行的时候，treebins 的应用使我们免受多度填充的最坏影响。
Resize 是通过 transferring bin 来处理的。因为是 2 次幂的扩张，所以元素要么不动，要么移动 2 次幂的位置。我们通过旧节点的 next filed 不会变的情况来实现旧节点的重用，这样可以减少新节点的创建。一般来说，只有六分之一的情况需要克隆。一旦它们不再被可能同时遍历表中的任何读取器线程引用，它们替换的节点将是可垃圾收集的。在传输时，旧表bin仅包含特殊转发节点（具有散列字段“MOVED”），其包含下一个表作为其密钥。 在遇到转发节点时，使用新表重新启动访问和更新操作。
二、重要常量和变量
/**
* The array of bins. Lazily initialized upon first insertion.
* Size is always a power of two. Accessed directly by iterators.
在第一次插入操作时初始化，存储 node 节点，大小是2的幂次方
*/
transient volatile Node<K,V>[] table;
/**
* The next table to use; non-null only while resizing.
扩容时生成的新数组，默认为 null，大小为原数组的两倍
*/
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.
* 基本计数器，主要在没有竞争的时候使用，通过 CAS 操作更新
* 保存所有节点的个数和，类似于hashmap 的 size
*/
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：哈希表在初始化
0：默认值
大于0：相当于 HashMap 中的 threshold，表示阈值
小于-1：代表有多个线程正在进行扩容
多线程之间，以volatile的方式读取sizeCtl属性，来判断ConcurrentHashMap当前所处的状态。通过cas设置sizeCtl 属性，告知其他线程ConcurrentHashMap的状态变更。
不同状态，sizeCtl所代表的含义也有所不同。
未初始化：
sizeCtl=0：表示没有指定初始容量。
sizeCtl>0：表示初始容量,相当于 HashMap 中的 threshold，表示阈值
正常状态：
sizeCtl=0.75n ,扩容阈值
初始化中：
sizeCtl=-1,标记作用，告知其他线程，正在初始化
扩容中:
sizeCtl < 0 : 表示有其他线程正在执行扩容
sizeCtl = (resizeStamp(n) << RESIZE_STAMP_SHIFT) + 2 :表示此时只有一个线程在执行扩容
小于-1：代表有多个线程正在进行扩容
*/
private transient volatile int sizeCtl;
/**
* The next table index (plus one) to split while resizing.
*/
// 扩容索引，表示已经分配给扩容线程的table 数组索引位置，主要用来协调多个线程，并且安全的获取多个桶位
private transient volatile int transferIndex;
/**
* Minimum number of rebinnings per transfer step. Ranges are
* subdivided to allow multiple resizer threads. This value
* serves as a lower bound to avoid resizers encountering
* excessive memory contention. The value should be at least
* DEFAULT_CAPACITY.
* 每次进行tranfer的最小值。
用于数据表扩容之后每次搬移数据的步长
每个cpu强制处理的最小Map容量数
这个参数是作为一个避免 reseize 线程遇到过多内存争用的下限。至少为DEFAULT_CAPACITY的值。
*/
private static final int MIN_TRANSFER_STRIDE = 16;
// 表的最大容量
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;
// 默认并发数
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
// 装载因子
private static final float LOAD_FACTOR = 0.75f;
// 转化为红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
// 由红黑树转化为链表的阈值
static final int UNTREEIFY_THRESHOLD = 6;
// 转化为红黑树的表的最小容量
static final int MIN_TREEIFY_CAPACITY = 64;
//一个用于连接两个table的节点类。它包含一个nextTable指针，用于指向下一张表。而且这个节点的key value next指针全部为null，它的hash值为-1. 这里面定义的find的方法是从nextTable里进行查询节点，而不是以自身为头节点进行查找。
ForwardingNode
三、重要方法
1、初始化 initTable 方法
/**
* Initializes table, using the size recorded in sizeCtl.
* 初始化数组table，
* 如果sizeCtl小于0，说明别的数组正在进行初始化，则让出执行权
* 如果sizeCtl大于0的话，则初始化一个大小为sizeCtl的数组
* 否则的话初始化一个默认大小(16)的数组
* 然后设置sizeCtl的值为数组长度的3/4
*/
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
// 如果sizeCtl小于0，说明别的数组正在进行初始化，则让出执行权
if ((sc = sizeCtl) < 0)
Thread.yield();
//SIZECTL：表示当前对象的内存偏移量，sc表示期望值，-1表示要替换的值，设定为-1表示要初始化表了
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
//cas 返回 true，进入真正的初始化逻辑
if ((tab = table) == null || tab.length == 0) {
//指定了大小的时候就创建指定大小的Node数组，否则创建指定大小(16)的Node数组
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长度为数组长度的3/4
sizeCtl = sc;
}
break;
}
}
return tab;
}
主要的几个方法调用链：
2、putVal 方法
putVal()方法逻辑：
- 首先判断存储节点的 table 数组是否为null，null的话进行初始化，然后再次循环
- 当 table 不为空时，通过计算hash值来确定放在数组的哪个位置，若插入节点为空，则通过 CAS 操作直接插入
- 若插入节点hash 值为 MOVED(-1)的话，则表示当前正在对这个数组进行扩容，则当前线程也去帮助扩容，调用
helpTransfer() - 当插入节点不为空，也不在扩容时，通过加锁
synchronized来进行添加操作- 判断当前要插入的节点类型，是链表还是红黑树
- 如果是链表的话，则遍历整个链表，直到取出来的节点的key来个要放的key进行比较，如果key相等，并且key的hash值也相等的话，则说明是同一个key，则覆盖掉value，返回 oldValue。否则的话则添加到链表的末尾。同时用 binCount记录该链表中节点的个数。
- 如果是红黑树，则调用putTreeVal方法把这个元素添加到树中去，返回 oldVal
- 跳出
synchronized操作，对 binCount 进行判断，当 binCount 大于TREEIFY_THRESHOLD，调用treeifyBin()将链表转换成红黑树，或者扩容数组 - 调用
addCount()方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
//获取key 的 hash 值
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)
//第一次 put 的时候，进行初始化
tab = initTable();
///通过哈希计算出应该插入的位置，获取该位置的 node f
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
}
//如果f哈希值是 moved，表示正在进行数组扩张的数据复制阶段
//当前线程也会去参与复制，通过允许多线程复制的功能，一次来减少数组的复制所来带的性能损失
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
//如果这个节点不为空，也不在扩容，那么采用 synchronized 方式加锁，进行添加操作
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
//取出来的元素的hash值大于0，即是链表。当转换为树之后，hash值为-2
if (fh >= 0) {
binCount = 1;
//这里通过 for 循环遍历整个链表，通过e = e.next来不断往后遍历
for (Node<K,V> e = f;; ++binCount) {
K ek;
//如果要存的元素的hash，key 和该节点的相同时，直接替换 value
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;
//如果 hash 和 key 不相同，则判断下一个节点是否为空，
//为空的话，将数据插入下一个节点
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
//如果 hash 值小于 0 ，f 是红黑树类型
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
//调用 putTreeVal 插入红黑树
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
//当一个bin的 node数量达到 8 的时候，扩张数组或者将节点转换为 tree
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//计数
addCount(1L, binCount);
return null;
}
3、 treeifyBin 链表转换成红黑树
当一个 bin 的 node 数量在添加完之后大于 8 时，将会调用 treeifyBin 方法尝试进行扩容
该方法的逻辑是：当 table 数组的长度小于 64 的时候，调用 tryPresize将数组扩容成两倍，否则的话，将链表转换成红黑树
/**
* Replaces all linked nodes in bin at given index unless table is
* too small, in which case resizes instead.
当数组长度小于 64 的时候，double 数组长度，否则将链表转换成红黑树
*/
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) {
//如果数组长度小于MIN_TREEIFY_CAPACITY，进行扩容
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
//否则将该 bin 的链表转换为树
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
synchronized (b) {
if (tabAt(tab, index) == b) {
TreeNode<K,V> hd = null, tl = null;
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;
}
//把 TreeNode 放入容器
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
4、tryPresize 扩容方法
在 tryPresize 方法中，并没有加锁，允许多个线程进入，如果数组正在扩荣，那么当前线程也要去帮忙。
在判断完一系列异常情况之后，最后直接调用 transfer 方法进行扩容
private final void tryPresize(int size) {
//如果当前 table 的大小，超过最大容量的一半，那么直接使用最大容量，否则用 tableSizeFor 计算
//后面table一直要扩容到这个值小于等于sizeCtrl(数组长度的3/4)才退出扩容
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
int sc;
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table; int n;
//如果数组table还没有被初始化，则初始化一个大小为sizeCtrl和刚刚算出来的c中较大的一个大小的数组
/* 为什么要在扩张的地方来初始化数组呢？这是因为如果第一次put的时候不是put单个元素，
而是调用putAll方法直接put一个map的话，在putALl方法中没有调用initTable方法去初始化table，
而是直接调用了tryPresize方法，所以这里需要做一个是不是需要初始化table的判断*/
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
//初始化的时候，设置sizeCtrl为-1
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if (table == tab) {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = nt;
sc = n - (n >>> 2);
}
} finally {
//初始化完成之后把sizeCtrl设置为数组长度的3/4
sizeCtl = sc;
}
}
/*
* 一直扩容到的c小于等于sizeCtl或者数组长度大于最大长度的时候，则退出
* 所以在一次扩容之后，不是原来长度的两倍，而是2的n次方倍
*/
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
else if (tab == table) {
int rs = resizeStamp(n);
if (sc < 0) {
Node<K,V>[] nt;
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
/*
* transfer的线程数加一,该线程将进行transfer的帮忙
* 在transfer的时候，sc表示在transfer工作的线程数
*/
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);
}
}
}
5、addCount 方法
- 对 table 的长度加一。无论是通过修改 baseCount，还是通过使用 CounterCell。当 CounterCell 被初始化了，就优先使用他，不再使用 baseCount。
- 检查是否需要扩容，或者是否正在扩容。如果需要扩容，就调用扩容方法，如果正在扩容，就帮助其扩容。
/**
* Adds to count, and if table is too small and not already
* resizing, initiates transfer. If already resizing, helps
* perform transfer if work is available. Rechecks occupancy
* after a transfer to see if another resize is already needed
* because resizings are lagging additions.
* 增加 count 计数，当table 太小且没有扩容时，启动扩容
* 如果正在扩容，那么就让当前工作线程去帮助扩容。
* @param x the count to add
* @param check if <0, don't check resize, if <= 1 only check if uncontended
*/
//这里 x=1，check=binCount，意思就是插入一个节点之后，将 table 长度加 1
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
//如果 counterCells 不为空，或者修改 BaseCount 失败，进入 if
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
//如果 counterCell 为空（尚未出现并发），或者
//随机取余一个数组位置为空 或者
//修改这个槽位的 value 失败(出现并发)，那么执行 fullAddAcount
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
//这里将插入的节点数增加到 table 长度
fullAddCount(x, uncontended);
return;
}
//binCount<=1 说明没有哈希冲突
if (check <= 1)
return;
//遍历 counterCell 数组，累加到 baseCount 上
s = sumCount();
}
//当 binCount>=0 进入这个分支
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
//当baseCount(也就是 map.size)>sizeCtl(超过扩容的阈值），
//且 table 不为空，且 table 长度小于最大值
//则进入while 循环进行扩容
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
//当其他线程正在扩容
if (sc < 0) {
//这里是对扩容结束的判断
// 如果 sc 的低 16 位不等于 标识符（校验异常 sizeCtl 变化了）
// 如果 sc == 标识符 + 1 （扩容结束了，不再有线程进行扩容）（默认第一个线程设置 sc ==rs 左移 16 位 + 2，当第一个线程结束扩容了，就会将 sc 减一。这个时候，sc 就等于 rs + 1）
// 如果 sc == 标识符 + 65535（帮助线程数已经达到最大）
// 如果 nextTable == null（结束扩容了）
// 如果 transferIndex <= 0 (转移状态变化了)
// 结束循环
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
// 如果可以帮助扩容，那么将 sc 加 1. 表示多了一个线程在帮助扩容
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
// 如果不在扩容，将 sc 更新：标识符左移 16 位 然后 + 2. 也就是变成一个负数。高 16 位是标识符，低 16 位初始是 2.
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
// 更新 sizeCtl 为负数后，告诉其他线程已经开始扩容，
transfer(tab, null);
s = sumCount();
}
}
}
6、helpTransfer 方法
此函数用于在扩容时将table表中的结点转移到nextTable中
/**
* Helps transfer if a resize is in progress.
*/
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
int rs = resizeStamp(tab.length);
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}
7、扩容的关键方法是 transfer
Transfer 方法逻辑：
- 线程执行Put，发现容量要扩容了，这个时候的transferIndex = table.length = 32。
通过计算 CPU 核心数和 Map 数组的长度得到每个线程（CPU）要帮助处理多少个桶，并且这里每个线程处理都是平均的。默认每个线程处理 16 个桶。因此，如果长度是 16 的时候，扩容的时候只会有一个线程扩容。
-
初始化临时变量 nextTable。将其在原有基础上扩容两倍。
-
死循环开始转移。多线程并发转移就是在这个死循环中，根据一个 finishing 变量来判断，该变量为 true 表示扩容结束，否则继续扩容。
- 扩容线程A 以cas的方式修改transferindex=31-16=16 ,然后按照降序迁移table[31]--table[16]这个区间的hash桶。
- 迁移hash桶时，会将桶内的链表或者红黑树，按照一定算法，拆分成2份，将其插入nextTable[i]和nextTable[i+n]（n是table数组的长度）。 迁移完毕的hash桶,会被设置成ForwardingNode节点，以此告知访问此桶的其他线程，此节点已经迁移完毕。
- 此时，线程2访问到了ForwardingNode节点，如果线程2执行的put或remove等写操作，那么就会先帮其扩容。如果线程2执行的是get等读方法，则会调用ForwardingNode的find方法，去nextTable里面查找相关元素。
多线程无锁扩容的关键就是通过CAS设置sizeCtl与transferIndex变量，协调多个线程对table数组中的node进行迁移。
TransferIndex 用 volatile 修饰了，获取 sizeCtl 和node 的售后，都是通过 CAS，因此支持并发的情况
/**
* Moves and/or copies the nodes in each bin to new table. See
* above for explanation.
*
* transferIndex 表示转移时的下标，初始为扩容前的 length。
*
* 我们假设长度是 32
*/
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// 将 length / 8 然后除以 CPU 核心数。如果得到的结果小于 16，那么就使用 16。
// 这里的目的是让每个 CPU 处理的桶一样多，避免出现转移任务不均匀的现象，如果桶较少的话，默认一个 CPU（一个线程）处理 16 个桶
//如果CPU数量过多导致每个线程分到的待处理的Hash桶的数量小于预设值，就将其置为预设值
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range 细分范围 stridea：TODO
// 新的 table 尚未初始化
if (nextTab == null) { // initiating
try {
// 扩容 2 倍
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
// 更新
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
// 扩容失败， sizeCtl 使用 int 最大值。
sizeCtl = Integer.MAX_VALUE;
return;// 结束
}
// 更新成员变量
nextTable = nextTab;
// 初始化时 transferindex =数组长度，意思就是转移指针处于数组末尾
transferIndex = n;
}
// 新 tab 的 length
int nextn = nextTab.length;
// 创建一个 fwd 节点，用于占位。当别的线程发现这个槽位中是 fwd 类型的节点，则跳过这个节点。
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
// 首次推进为 true，如果等于 true，说明需要再次推进一个下标（i--），反之，如果是 false，那么就不能推进下标，需要将当前的下标处理完毕才能继续推进
//advance作为Hash桶操作完成的标志变量
boolean advance = true;
// 完成状态，如果是 true，就结束此方法。
//finishing作为扩容完成的标志变量
boolean finishing = false; // to ensure sweep before committing nextTab
// 死循环,i 表示下标，bound 表示当前线程可以处理的当前桶区间最小下标
for (int i = 0, bound = 0;;) {
//=============================while循环开始=========================================
Node<K,V> f; int fh;
// 如果当前线程可以向后推进；这个循环就是控制 i 递减。同时，每个线程都会进入这里取得自己需要转移的桶的区间
while (advance) {
int nextIndex, nextBound;
// 对 i 减一，判断是否大于等于 bound （正常情况下，如果大于 bound 不成立，说明该线程上次领取的任务已经完成了。那么，需要在下面继续领取任务）
// 如果对 i 减一大于等于 bound（还需要继续做任务），或者完成了，修改推进状态为 false，不能推进了。任务成功后修改推进状态为 true。
// 通常，第一次进入循环，i-- 这个判断会无法通过，从而走下面的 nextIndex 赋值操作（获取最新的转移下标）。其余情况都是：如果可以推进，将 i 减一，然后修改成不可推进。如果 i 对应的桶处理成功了，改成可以推进。
if (--i >= bound || finishing)
// 这里设置 false，是为了防止在没有成功处理一个桶的情况下却进行了推进
advance = false;
// 这里的目的是：1. 当一个线程进入时，会选取最新的转移下标。
//2. 当一个线程处理完自己的区间时，如果还有剩余区间的没有别的线程处理。再次获取区间。
else if ((nextIndex = transferIndex) <= 0) {
// 如果小于等于0，说明没有区间了 ，i 改成 -1，推进状态变成 false，不再推进，
//表示，扩容结束了，当前线程可以退出了
// 这个 -1 会在下面的 if 块里判断，从而进入完成状态判断
i = -1;
// 这里设置 false，是为了防止在没有成功处理一个桶的情况下却进行了推进
advance = false;
}
扩容线程，在迁移数据之前，首先要将transferIndex右移（以cas的方式修改 transferIndex=transferIndex-stride(要迁移hash桶的个数)），获取迁移任务。每个扩容线程都会通过for循环+CAS的方式设置transferIndex，因此可以确保多线程扩容的并发安全。
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;// 这个值就是当前线程可以处理的最小当前区间最小下标
i = nextIndex - 1; // 初次对i 赋值，这个就是当前线程可以处理的当前区间的最大下标
// 这里设置 false，是为了防止在没有成功处理一个桶的情况下却进行了推进，这样对导致漏掉某个
//桶。下面的 if (tabAt(tab, i) == f) 判断会出现这样的情况。
advance = false;
}
}
//=============================while循环结束=========================================
// 如果 i 小于0 （不在 tab 下标内，按照上面的判断，领取最后一段区间的线程扩容结束）
// 如果 i >= tab.length(不知道为什么这么判断)
// 如果 i + tab.length >= nextTable.length （不知道为什么这么判断）
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) { // 如果完成了扩容
nextTable = null;// 删除成员变量
table = nextTab;// 更新 table
sizeCtl = (n << 1) - (n >>> 1); // 更新阈值
return;// 结束方法。
}// 如果没完成
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {// 尝试将 sc -1. 表示这个线程结束帮助扩容了，将 sc 的低 16 位减一。
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)// 如果 sc - 2 不等于标识符左移 16 位。如果他们相等了，说明没有线程在帮助他们扩容了。也就是说，扩容结束了。
return;// 不相等，说明没结束，当前线程结束方法。
finishing = advance = true;// 如果相等，扩容结束了，更新 finising 变量
i = n; // 再次循环检查一下整张表
}
}
else if ((f = tabAt(tab, i)) == null) // 获取老 tab i 下标位置的变量，如果是 null，就使用 fwd 占位。
advance = casTabAt(tab, i, null, fwd);// 如果成功写入 fwd 占位，再次推进一个下标
else if ((fh = f.hash) == MOVED)// 如果不是 null 且 hash 值是 MOVED。
advance = true; // already processed // 说明别的线程已经处理过了，再次推进一个下标
else {
// 到这里，说明这个位置有实际值了，且不是占位符。对这个节点上锁。为什么上锁，防止 putVal 的时候向链表插入数据
synchronized (f) {
// 判断 i 下标处的桶节点是否和 f 相同
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;// low, height 高位桶，低位桶
// 如果 f 的 hash 值大于 0 。TreeBin 的 hash 是 -2
if (fh >= 0) {
// 对老长度进行与运算（第一个操作数的的第n位于第二个操作数的第n位如果都是1，那么结果的第n为也为1，否则为0）
// 由于 Map 的长度都是 2 的次方（000001000 这类的数字），那么取于 length 只有 2 种结果，一种是 0，一种是1
// 如果是结果是0 ，Doug Lea 将其放在低位，反之放在高位，目的是将链表重新 hash，放到对应的位置上，让新的取于算法能够击中他。
int runBit = fh & n;
Node<K,V> lastRun = f; // 尾节点，且和头节点的 hash 值取于不相等
// 遍历这个桶
for (Node<K,V> p = f.next; p != null; p = p.next) {
// 取于桶中每个节点的 hash 值
int b = p.hash & n;
// 如果节点的 hash 值和首节点的 hash 值取于结果不同
if (b != runBit) {
runBit = b; // 更新 runBit，用于下面判断 lastRun 该赋值给 ln 还是 hn。
lastRun = p; // 这个 lastRun 保证后面的节点与自己的取于值相同，避免后面没有必要的循环
}
}
if (runBit == 0) {// 如果最后更新的 runBit 是 0 ，设置低位节点
ln = lastRun;
hn = null;
}
else {
hn = lastRun; // 如果最后更新的 runBit 是 1， 设置高位节点
ln = null;
}// 再次循环，生成两个链表，lastRun 作为停止条件，这样就是避免无谓的循环（lastRun 后面都是相同的取于结果）
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
// 如果与运算结果是 0，那么就还在低位
if ((ph & n) == 0) // 如果是0 ，那么创建低位节点
ln = new Node<K,V>(ph, pk, pv, ln);
else // 1 则创建高位
hn = new Node<K,V>(ph, pk, pv, hn);
}
// 其实这里类似 hashMap
// 设置低位链表放在新链表的 i
setTabAt(nextTab, i, ln);
// 设置高位链表，在原有长度上加 n
setTabAt(nextTab, i + n, hn);
// 将旧的链表设置成占位符
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);
// 和链表相同的判断，与运算 == 0 的放在低位
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
} // 不是 0 的放在高位
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
// 如果树的节点数小于等于 6，那么转成链表，反之，创建一个新的树
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;
}
}
}
}
}
}
四、ConcurrentHashMap 的并发控制
1、get 方法是没有加锁的，如果读的时候有线程在 put 怎么办？
估计是通过 tabAt方法，调用 unsafe.getObjectVolatile方法来保证写操作对读的可见性的
2、涉及写的方面
1) 初始化 table 的时候，通过sizeCtl 的 CAS 操作和 table 的 Volatile 来控制并发
2）put 操作的时候，
- 通过 tabAt 和 casTabAt 来对空节点进行插入
- 通过加锁来对非空节点进行插入
- 调用 helpTransfer 来帮助扩容 table
3）扩容的时候，通过 volatile transferIndex，sizeCtl 的 CAS 操作，以及对每个节点的加锁循环处理来控制并发
- putVal 通过
binCount>=TREEIFY_THRESHOLD =8来判断是否需要调用 treeifyBintreeifyBin 通过
table.length<MIN_TREEIFY_CAPACITY =64来判断是否需要tryPresize -
addCount 通过
map.size>sizeCtl=0.75n来判断是否需要扩容第一条扩容之后，addCount 还会继续扩容吗
不会同时满足