Java-01-源码篇-04集合-05-ConcurrentHashMap(1)
1.1 加载因子
加载因子（Load Factor）是用来决定什么时候需要扩容的一个参数。具体来说，加载因子 = 当前元素数量 / 桶的数量，当某个桶的元素个数超过了 桶的数量 × 加载因子 时，就会触发扩容。
我们都知道 ConcurrentHashMap 的默认大小是16，默认加载因子是：0.75。解析一下什么叫做加载因子，简单的讲就是触发扩容机制的阈值。比如我的集合容量大小是 100，加载因子是：0.75，那么触发扩容的阈值就是(100 x 0.75 = 75; 当数量达到75的时候触发扩容机制。而不是在容量达到满100的时候才触发扩容机制)。通过设置加载因子的好处如下：
| 平衡性能与空间利用率 | 较低的加载因子（如 0.1）会使得哈希表在元素较少时扩容，从而减少哈希冲突，提高查找、插入和删除操作的性能。 较高的加载因子（如 0.9）会延迟扩容，节省内存空间，但可能会增加哈希冲突，降低性能。 在 |
| 控制加载频率 | 扩容是一个比较耗时的操作，因为它需要重新计算元素复制到新的桶里面。通过调整加载因子，在性能与内存之间达到一个平衡。 |
1.2 面试题：加载因子默认为什么是0.75，而不是9，或者5等等之类其他数字
所以这道题面试题问的就是加载因子的作用，从平衡性能和内存，以及控制加载频率的角度去回答即可。
比如：如果设置的加载因子过高（例如 0.1 或 0.9），意味着 ConcurrentHashMap 会在桶中存储更多的元素，减少扩容的次数，减少内存的开销。但是这样会也导致桶的元素过多，链表的长度过长。导致访问元素时的查找效率下降，发生更多的哈希冲突（hash collision）几率也逐渐增大。
较低的加载因子（0.1）意味着 ConcurrentHashMap 会在桶中存储少量的元素，但扩容的次数上升，内存的开销增多。频繁的扩容处理会导致性能开销增大。
所以取一个在性能与内存之间很好的折中植就是0.75。0.75 是一个经过大量测试验证的值，适用于大多数常见场景。它在查找效率、内存使用和扩容操作之间取得了一个很好的折中。
当然，如果具体也可以根据需求调整
对于性能要求高的应用：
尽量减少哈希冲突，提高查找、插入和删除操作的性能。降低加载因子（例如设置为 0.5 或更低）。
【原因】
较低的加载因子会使得哈希表在元素数量较少时触发扩容，从而减少哈希冲突。
每个桶中的元素数量更少，查找、插入和删除操作的时间复杂度更接近 O(1)。
【代价】
哈希表的容量会更大，占用更多的内存空间
扩容操作会更频繁，可能会带来一定的性能开销
对于内存占用比较敏感的应用：
尽量减少内存占用，提高空间利用率。
【原因】
较高的加载因子会延迟扩容，使得哈希表在元素数量接近容量时才触发扩容。
内存利用率更高，适合内存资源有限的场景。
【代价】
哈希冲突的概率会增加，尤其是在元素数量接近容量时，性能可能会下降。
查找、插入和删除操作的时间复杂度可能会增加。
1.3 初始化功能 initTable()
首先，初始化功能在第一次put时会触发。代码分析如下
我们进一步观察initTable() 方法
public V put(K key, V value) { return putVal(key, value, false); }
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; K fk; V fv;
// 当集合第一次添加元素时，触发初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
...... // 忽略其他代码
我们进一步观察initTable() 方法
/** ConcurrentHashMap 的容器*/
transient volatile Node<K,V>[] table;
/**
sizeCtl的作用
sizeCtl (< 0) 负值时：
sizeCtl = -1; 表示正在进行初始化
其他负值（如 -2，-3 等）：表示正在进行扩容，并且数字的大小指示了
当前有多少个线程正在进行扩容操作。例如，
-2 表示有一个线程在进行扩容，
-3 表示有两个线程在进行扩容。
sizeCtl = 0 时：
当 sizeCtl == 0 时，表示表格的大小使用默认值。
正值（用于表格大小的控制）：
在表格初始化完成之后，sizeCtl 变成一个正值，表示下一个阈值，
即表格的元素数量达到此值时，需要进行扩容。
例如，如果 sizeCtl 设置为 16，则表示当表格的元素数量达到 16 时，
应该触发扩容操作。
【总结】
sizeCtl 控制表格的初始化、扩容，以及扩容过程中的线程同步。
根据其值的不同，sizeCtl 在 ConcurrentHashMap 中承担着不同的角色
*/
private transient volatile int sizeCtl;
/**
Unsafe 类，里面提供CPU相关的操作指令，比如CAS。
CAS: compareAndSet 比较并交换，CAS 通过比较变量的当前值与预期值是否相同，
如果两值相同则将变量的值更新为新值，否则不做任何操作
并且还支持跳过JVM内存管理相关操作
*/
private static final Unsafe U = Unsafe.getUnsafe();
/**
通过 Unsafe 不安全类，绕过JVM的内存管理机制，直接访问硬件的内存
获取 ConcurrentHashMap.class 类里面的 sizeCtl 的字段值
*/
private static final long SIZECTL
= U.objectFieldOffset(ConcurrentHashMap.class, "sizeCtl");
private final Node<K,V>[] initTable() {
// 声明两个局部变量，而不直接使用全局的table, sizeCtl
// 避免直接多次访问全局的 table，提高代码的效率。
Node<K,V>[] tab; int sc;
// 进入 while 循环时，首先检查 table 是否为 null 或者是否为空（长度为 0）。
// 如果是，表示 table 还没有初始化
while ((tab = table) == null || tab.length == 0) {
// sizeCtl 负值集合处于初始化(-1)或者是扩容阶段(-2,-3....)
if ((sc = sizeCtl) < 0)
Thread.yield(); // 所以当前线程礼让出CPU资源（CPU时间分片）
// U.compareAndSetInt 该方法就是int类型的CAS
// 如果 sizeCtl 的当前值 不小于 0，我们尝试通过 CAS（Compare-And-Set）操作
// 来将 sizeCtl 的值从 sc 修改为 -1，表示当前线程正在进行初始化操作。
else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {
try {
// 再次检查 table 是否已经初始化，如果没有，则进行初始化。
if ((tab = table) == null || tab.length == 0) {
// 如果 sc(sizeCtl) 有正值，则表示当前容量大小，否则使用默认大小16
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
// 初始化：就是创建一个指定的大小数组赋值给table，并记录sizeCtl的值。
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
// 计算并更新 sc 的值。sc 记录下一个阈值，即元素数量达到多少时需要扩容。
// 此计算方法是基于表格大小的 75%（即 n - (n >>> 2)，
// 实际上就是 n * 0.75）。当元素数量超过该阈值时，将会触发扩容。
sc = n - (n >>> 2); // 可以理解成这样的 0.75 加载因子是写固定的0.75。
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}public class Test {
public static void main(String[] args) {
ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
map.put("key1", "value1");
System.out.println(map);
}
}
1.4 总结
ConcurrentHashMap 的初始化，如果是第一次进行初始化，则容量大小为 16，加载因子(0.75)计算的阈值为12。ConcurrentHashMap 由于是线程安全的，在初始化的体现通过 Unsafe不安全类提供CAS操作来实现。通过CAS 判断 sizeCtl 值。
sizeCtl 用于控制集合的扩容，初始化。比如 -1 表示正在初始化，其他的负数表示正在扩容 -2 一个线程扩容，-3 两个线程，以此类推，
sizeCtl = 0 表示 初始化完成了。
sizeCtl > 0 表示触发扩容的阈值。第一次为12 。
1.5 构造方法
/** 最大值 */
private static final int MAXIMUM_CAPACITY = 1 << 30;
/** 默认容量大小 */
private static final int DEFAULT_CAPACITY = 16;
/** 默认加载因子大小 */
private static final float LOAD_FACTOR = 0.75f;
public ConcurrentHashMap() {}
/**
* @param initialCapacity 初始容量
*/
public ConcurrentHashMap(int initialCapacity) {
this(initialCapacity, LOAD_FACTOR, 1);
}
/**
* @param initialCapacity 初始容量
* @param loadFactor 加载因子
*/
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
}
/**
* @param initialCapacity 初始容量
* @param loadFactor 加载因子
* @param concurrencyLevel 内部更新线程个数，估计将同时更新映射的线程数。
* 此值用于帮助调整内部数据结构的大小，以减少线程间的竞争。
*/
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;
}
/** 该方法支持传入一个map */
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
this.sizeCtl = DEFAULT_CAPACITY; // 阈值大小为 16
putAll(m);
}1.6 总结
ConcurrentHashMap 的构造方法，提供手动设置初始容量和加载因子以及内部线程个数。限制容量的范围大小 0 到 MAXIMUM_CAPACITY（1 << 30 ）。
并且从里面也可以得知，在设置阈值大小的时候都是通过 sizeCtl (size Control ) 来接收。所以从这样也可以知道初始化的时候，用它来进行一个参看和判断。正数的就表示扩容阈值大小，等触发扩容，或者是初始化时，将其sizeCtl 改为 负值。 -1 表示 初始值，-2 表示一个线程扩容，-3 表示两个线程扩容，以此类推，毕竟ConcurrentHashMap支持线程安全。扩容完之后又将计算新的阈值大小赋值给 sizeCtl.
所以才说 sizeCtl 是掌管控制ConcurrentHashMap的初始化，扩容的一个重要变量。
1.7 新增功能
public V put(K key, V value) { return putVal(key, value, false); }
1.8 面试题：直接从上到下，添加一次就可以吗？为什么要通过一个for 进行无限循环添加？
其实这并非是集合章节的知识点，这个是多线程章节的知识点。因为ConcurrentHashMap支持多线程并发，所以需要考虑到多线程的情况下。
作用：持续重试和处理并发操作
在并发数据结构中，许多操作（如插入、删除、扩容等）都可能需要在多个线程同时访问的环境下执行。使用无限循环可以确保：
重试操作：如果某个操作（如插入、更新或删除）由于并发冲突（例如，另一个线程正在修改同一个桶或节点）而无法立即成功执行，程序可以在内部重新尝试执行该操作。
保证条件满足后继续执行：在并发环境下，操作的执行结果通常依赖于其他线程的状态，因此可能需要在条件不满足时继续尝试直到成功。
处理扩容等需要重新计算大小的操作：
例如，在 ConcurrentHashMap 中，当插入元素导致负载过高时，可能需要扩容哈希表。扩容通常涉及以下步骤：
1 重新计算哈希表的大小
2 重新分配内存
3 重新散列所有现有元素
这些操作往往需要多次尝试，直到哈希表的大小适合当前元素的数量。在此过程中，循环结构可以帮助处理这一过程，直到操作完成。
确保原子性操作
在高并发环境下，有时需要使用 CAS（比较并交换） 或类似的机制(JDK7 的线程安全是通过 分段锁 Segment )来确保线程安全。例如，可能需要反复检查某个条件（如节点是否已被更新），直到确认操作成功。
避免死锁或竞争条件
使用无限循环可以防止由于竞争条件引起的操作失败。通过在循环中不断尝试，确保操作的成功执行，同时避免因并发冲突或竞争条件导致程序永久卡住。
操作的延迟执行
有些操作可能会依赖某些状态或条件，并且需要在特定的时机才执行。例如，在表格扩容时，可能需要等到某些条件满足才继续执行下一个步骤。无限循环允许在这些条件准备好时才继续操作。
1.9下面看新增逻辑分析
final V putVal(K key, V value, boolean onlyIfAbsent) {
// 这里可以说明 ConcurrentHashMap 不支持key,value为null
// 这样设计是为了避免二义性：何为二义性。
/**
在并发环境下，null 值可能会导致语义上的歧义，无法区分以下两种情况：
key 不存在：调用 get(key) 返回 null，可能表示该 key 不存在。
key 存在，但 value 为 null：调用 get(key) 返回 null，也可能表示该 key 存在，但其对应的 value 是 null。
这种二义性会导致程序逻辑难以处理，尤其是在并发场景下，可能会引发难以调试的问题。
*/
if (key == null || value == null) throw new NullPointerException();
// 获取键 key 的哈希值，用于确定元素的位置，spread()进一步优化并降低哈希冲突的概率
int hash = spread(key.hashCode());
/** 记录当前桶中的元素个数 */
int binCount = 0;
// 忽略添加逻辑
addCount(1L, binCount); // 记录当前桶的元素数量+1
return null;
}补充一下ConcurrentHashMap 当中桶 (bin) 指的是什么，指定的就是 Node<K, V>[] table 。table[] 有多大，就有多少个桶，而我们知道 table 。是在初始化或者扩容的时候进行更新。所以这里的 binCount 就是指定当前桶的元素个数。而元素放在哪个桶的位置，是由计算的hash值来决定的。
新增逻辑大概考虑到五种情况
【情况一】：第一次新增触发初始化
【情况二】： 矫正hash计算得出的索引没有桶
【情况三】：新增遇到正在扩容处理，通过helpTransfer 来处理
【情况四】：处理key值相同，value不覆盖(ConcurrentHashMap默认都是key相同，value覆盖，有参数 onlyIfAbsent来决定，onlyIfAbsent 意思就是：是否只有值缺席的时候才添加。)
【情况五】：正常插入元素。（链表树化成红黑树也在这里处理）
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; K fk; V fv;
// 【情况一】：第一次新增触发初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
/**
* 【情况二】：如果计算得到索引所对应的桶为null: (f = null) == null
* 当索引对应的桶为null,就通过CAS重新将元素添加到桶里面。并break;表示新增结束
* 额外讲解：避免了哈希值超过桶的范围
* i 表示 索引，(n - 1) & hash 作用
* 假如当桶大小只有32时，但是计算出的索引超过了32，比如 55。
* n = 32，n - 1 = 31（二进制 11111）。
* 如果 hash = 55，二进制表示为 110111。
* (55 & 31) 的结果是 55 & 11111 = 111，即索引为 7。
*/
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
break; // no lock when adding to empty bin
}
/**
* 【情况三】：如果桶的哈希值为 MOVED，表示该位置正在进行哈希表扩容操作。
* 此时调用 helpTransfer() 来帮助完成扩容
*/
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
/**
* 【情况四】：
* 如果 onlyIfAbsent 为 true
* key 相同，value就不更新了。
* 而put方法，put(K key, V value) { return putVal(key, value, false); }
* 很显然是key相同，value覆盖更新
*/
else if (onlyIfAbsent // check first node without acquiring lock
&& fh == hash
&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
&& (fv = f.val) != null)
return fv;
// 【情况五】：正常的插入与更新
else {
V oldVal = null;
synchronized (f) { //加锁 synchronized (f)，确保线程安全。
if (tabAt(tab, i) == f) {
/**
* 链表（fh >= 0）：遍历当前桶中的链表，查找键是否存在。
* 如果存在，更新值；如果不存在，将新节点添加到链表末尾。
* 俗称：key 相同时，key不变，value覆盖
*/
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
// key 冲突，value覆盖逻辑
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
// key 不冲突，直接添加key, value
// (ConcurrentHashMap里面的元素都是以Node为基础。)
// 所以通过新增的put(key, value); 都会封装成一个Node 元素。
// 这个Node里面存储的真正key和value
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key, value);
break;
}
}
}
// 如果当前桶已经是红黑树，则通过 putTreeVal() 方法处理。
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;
}
}
// 保留节点处理（f instanceof ReservationNode）：
// 如果桶中是保留节点，则抛出异常
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
// 链表树化：桶中的元素数量大于等于 TREEIFY_THRESHOLD（默认 8），转红黑树
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}2.0 扩容机制 tryPresize
tryPresize 旨在根据给定的 size 计算新的容量，并尝试扩容哈希表。它会根据表的当前状态，所需容量和线程安全的操作来决定是否进行扩容。
在代码内部我们可以看出，两处需要进行扩容处理。一处是putAll()方法。一个是在新增时有一处是 链表树化的扩容。
public void putAll(Map<? extends K, ? extends V> m) {
tryPresize(m.size());
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
putVal(e.getKey(), e.getValue(), false);
} private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n;
if (tab != null) {
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
// ...... 忽略其他代码看扩容逻辑代码
private final void tryPresize(int size) {
/**
* 扩容的大小 = c
* 根据传入的size大小来决定，如果size大于最大值MAXIMUM_CAPACITY，
* 那么c就是最大值，调用 tableSizeFor 方法计算一个合适的容量。
* tableSizeFor 的作用是返回大于等于给定值的最小 2 的幂次方
*/
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
tableSizeFor(size + (size >>> 1) + 1);
int sc;
/** 这里我们都知道，1.3 初始化功能的时候提到过
sizeCtl 有多重身份，
sizeCtl < 0 时，表示正在处于初始化或者是扩容当中,
-1 表示初始化， -2，-3表示扩容，-2是一条线程，-3是两条线程扩容，依次类推
sizeCtl = 0 时，初始化完成了，
sizeCtl > 0 时，sizeCtl表示加载的阈值（有容量大小 X 加载因子得来的）
*/
while ((sc = sizeCtl) >= 0) {
Node<K,V>[] tab = table; int n;
// 处理初始化
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c; // n = 本次最终扩容的大小
if (U.compareAndSetInt(this, SIZECTL, sc, -1)) { // 通过CAS进行更新
try {
if (table == tab) {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = nt;
// 重新计算 sizeCtl 新的阈值（n - (n >>> 2)，即 0.75 * n）
// 这里是通过位运算来的。写死了 0.75 加载因子
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
}
}
// 目标容量不在范围内，不处理扩容了
// 如果目标容量 c 小于等于当前阈值 sc，或者当前容量 n 已经达到最大容量 MAXIMUM_CAPACITY
else if (c <= sc || n >= MAXIMUM_CAPACITY)
break;
// 触发扩容机制
else if (tab == table) {
int rs = resizeStamp(n);
if (U.compareAndSetInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
}
}
}