汅api免费版大全免费_杭州本地推广平台_泰安seo培训_微软优化大师

一、HashMap

关键属性

int threshold;
final float loadFactor; //负载因子，默认是0.75

put() 方法实现

关键步骤说明：

初始化或扩容检查
如果哈希表 table 为空或长度为0，调用 resize() 初始化数组。resize() 方法在首次插入时创建默认容量（16）的数组。
计算桶位置并插入新节点
通过 (n - 1) & hash 计算键的桶索引（等价于取模运算，但更高效）。若该位置为空，直接插入新节点。
处理哈希冲突
- 首节点匹配：检查桶的第一个节点是否与待插入的 key 相同（哈希值和 equals 均匹配）。
- 红黑树插入：若节点是 TreeNode 类型，调用红黑树的插入方法 putTreeVal。
- 链表遍历：遍历链表查找是否存在相同 key。若未找到，在链表尾部插入新节点，并检查是否需要树化。
树化条件
当链表长度达到 TREEIFY_THRESHOLD（默认8）且数组长度 ≥ MIN_TREEIFY_CAPACITY（64）时，链表转换为红黑树。否则优先扩容。
更新已存在的键值对
若找到相同 key 的节点，根据 onlyIfAbsent 参数决定是否更新值，并返回旧值。
扩容与回调
新增节点后，检查总节点数是否超过扩容阈值 threshold，若超过则调用 resize() 扩容。afterNodeInsertion 和 afterNodeAccess 是 LinkedHashMap 用于维护顺序的回调方法，在 HashMap 中为空实现。

public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}/*** 实现Map接口的put操作及相关方法。** @param hash         通过key计算的哈希值* @param key          要插入的键* @param value        要插入的值* @param onlyIfAbsent 如果为true，不覆盖已存在的值* @param evict        如果为false，表示哈希表处于创建模式（例如初始化）* @return 返回旧值（如果存在），否则返回null*/
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; // 哈希表的数组引用Node<K,V> p; // 目标桶中的第一个节点（当前节点）int n, i;  // n: 哈希表长度；i: 计算出的桶索引// 1. 检查哈希表是否未初始化或为空，若是则通过resize()初始化if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length; // 初始化并获取新长度，resize是扩容方法，我们后面再讲// 2. 计算桶索引：(n - 1) & hash 等价于 hash % n（n为2的幂时）// 检查该桶是否为空，若空则直接插入新节点if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k; // 用于记录已存在的键值对节点（若找到）// 3. 检查桶的第一个节点是否与待插入的key匹配if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;  // 记录匹配的节点// 4. 若当前节点是红黑树节点，调用红黑树的插入方法else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);// 5. 否则处理链表冲突else {// 遍历链表查找是否存在相同的keyfor (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) { // 到达链表尾部p.next = newNode(hash, key, value, null); // 在尾部插入新节点// 如果链表长度超过树化阈值（默认8），转换为红黑树if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}// 检查链表中的节点是否与key匹配if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break; // 找到相同key，退出循环p = e; // 继续遍历下一个节点}}// 6. 如果找到已存在的key（e不为null）if (e != null) { // existing mapping for keyV oldValue = e.value;// 根据onlyIfAbsent决定是否更新值（若旧值为null则强制更新）if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);  // 回调方法（LinkedHashMap维护访问顺序）HashMap为空实现return oldValue; // 返回旧值}}// 7. 新增节点后的操作++modCount; // 修改次数递增（用于fail-fast机制）if (++size > threshold) // 检查是否超过扩容阈值resize(); // 扩容afterNodeInsertion(evict); // 回调方法（LinkedHashMap维护插入顺序）HashMap为空实现return null; // 无旧值，返回null
}

说明：

modCount的作用

modCount 是 记录哈希表结构被修改的次数 的关键变量，它的自增操作（++modCount）是为了实现 fail-fast（快速失败）机制，确保在多线程环境下（或单线程迭代时）如果检测到并发修改，立即抛出 ConcurrentModificationException，避免数据不一致的风险。

跟踪结构性修改
每次对 HashMap 的结构进行修改时（如添加新节点、删除节点、扩容等），modCount 会自增。
结构性修改 指的是改变哈希表中键值对数量或内部结构（如链表转红黑树）的操作。
与迭代器配合实现 fail-fast
当通过迭代器（如 entrySet().iterator()）遍历 HashMap 时，迭代器会记录初始的 modCount 值（称为 expectedModCount）。
在每次迭代过程中（如调用 next() 或 remove()），会检查当前的 modCount 是否等于 expectedModCount：
- 如果不相等，说明有其他线程（或当前线程的其他操作）修改了哈希表结构，立即抛出**** **ConcurrentModificationException**。
- 这种机制能快速暴露并发问题，而不是继续执行导致不可预测的结果。

threadhold

threshold 是 HashMap 触发扩容的阈值，当 HashMap 中键值对的数量（size）超过 threshold 时，就会触发扩容（resize()）。它的赋值过程是 延迟初始化（Lazy Initialization） 的，并非在构造方法中直接赋值，而是在第一次插入数据时（调用 put() 方法）通过 resize() 方法初始化。

扩容阈值
threshold = capacity * loadFactor
当 size > threshold 时，HashMap 会触发扩容（resize()），将容量翻倍（newCapacity = oldCapacity * 2），并重新哈希所有键值对。
初始容量的动态计算
如果未显式指定初始容量（如使用默认构造方法 new HashMap<>()），HashMap 会采用默认容量 16，并根据负载因子（loadFactor，默认 0.75）计算初始阈值：
threshold = 16 * 0.75 = 12。

哈希扰动：(h = key.hashCode()) ^ (h >>> 16)

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

- <font style="color:rgb(36, 41, 46);">目的：让hashcode的高16位右移与低16位异或运算，使得低16位更有散列性，降低哈希碰撞概率（Java 8 改进）</font>
- <font style="color:rgb(36, 41, 46);">对比：Java 7 用了 4 次位运算+5次异或运算，计算更复杂但效果类似</font>

计算桶位置：(n-1) & hash
- 原理：用数组长度取模（当n是2的幂时等效）
处理哈希冲突：
- 链表插入：Java 8 使用尾插法（新节点追加到链表尾部）

if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);break;
}

- **<font style="color:rgb(36, 41, 46);">树化阈值</font>**<font style="color:rgb(36, 41, 46);">：链表长度 ≥8 且数组长度 ≥64 时转换为红黑树（Java 8 新增）</font>
- <font style="color:rgb(36, 41, 46);">对比：Java 7 使用头插法，多线程下可能导致死循环</font>

扩容检查：
- 触发条件：size > threshold（threshold = capacity * loadFactor）
- 对比：Java 7 在插入前检查，Java 8 在插入后检查

get() 方法实现

关键步骤详解

1. 计算桶索引：(n - 1) & hash

作用：将哈希值映射到哈希表数组的某个桶（索引位置）。

2. 优先检查第一个节点

目的：优化查找速度，大多数情况下键值对分散良好，桶中只有一个节点。
条件：
- first.hash == hash：哈希值必须相等（避免哈希冲突时的错误匹配）。
- key == first.key 或 key.equals(first.key)：引用相等或逻辑相等。

3. 处理链表或红黑树

链表：
- 若第一个节点不匹配且后续节点存在（e = first.next），则遍历链表。
- 使用 do-while 循环依次检查每个节点的哈希值和键。
红黑树：
- 若第一个节点是 TreeNode，调用 getTreeNode(hash, key) 在红黑树中查找（时间复杂度 O(log n)）。

4. 红黑树查找：getTreeNode

实现逻辑：
- 从根节点出发，根据哈希值和键的比较结果，递归进入左子树或右子树。
- 哈希值相同时，再通过 key.equals(k) 判断是否匹配。

5. 终止条件

成功：找到哈希值和键均匹配的节点，立即返回。
失败：遍历完链表或树仍未找到，返回 null。

public V get(Object key) {Node<K,V> e;// 调用 getNode 方法查找键对应的节点，若存在则返回其值，否则返回 nullreturn (e = getNode(hash(key), key)) == null ? null : e.value;
}/*** 实现 Map.get 及相关方法的核心逻辑* @param hash  键的哈希值（通过 hash(key) 计算）* @param key   要查找的键* @return      找到的节点，若不存在则返回 null*/
final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab;  // 当前哈希表数组Node<K,V> first;  // 目标桶（bucket）的第一个节点Node<K,V> e;      // 用于遍历链表或树的临时节点int n;            // 哈希表数组的长度（容量）K k;              // 临时变量，用于存储节点的键// 1. 检查哈希表是否已初始化且长度大于0，同时目标桶的第一个节点是否存在if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) { // 计算桶索引：(n-1) & hash// 2. 总是先检查第一个节点是否匹配（快速路径）if (first.hash == hash && // 哈希值相等((k = first.key) == key || (key != null && key.equals(k)))) {return first; // 直接返回第一个节点}// 3. 如果第一个节点不匹配，且存在后续节点（链表或树）if ((e = first.next) != null) {// 4. 如果第一个节点是树节点，调用红黑树的查找方法if (first instanceof TreeNode) {return ((TreeNode<K,V>)first).getTreeNode(hash, key);}// 5. 如果是链表，遍历所有节点查找匹配项do {if (e.hash == hash && // 检查哈希值((k = e.key) == key || (key != null && key.equals(k)))) {return e; // 找到匹配节点}} while ((e = e.next) != null); // 继续遍历下一个节点}}// 6. 哈希表未初始化、目标桶为空或未找到匹配节点，返回 nullreturn null;
}

扩容机制（resize）

关键步骤解析：

容量与阈值计算
- 根据旧容量和阈值，确定新容量和阈值。若已初始化，容量翻倍；若未初始化，根据构造参数或默认值初始化。
数据迁移策略
- 单个节点：直接重新哈希到新位置。
- 红黑树：调用 split 方法拆分树，可能退化为链表。
- 链表：拆分为低位链表（索引不变）和高位链表（索引+旧容量），保持原有顺序，避免死循环。
哈希优化
- 通过 (e.hash & oldCap) == 0 快速判断节点应归属的链表，避免重新计算哈希值。

final Node<K,V>[] resize() {// 保存当前哈希表的引用Node<K,V>[] oldTab = table;// 获取旧表的容量（若未初始化则为0）int oldCap = (oldTab == null) ? 0 : oldTab.length;// 获取旧表的扩容阈值int oldThr = threshold;// 定义新容量和新阈值int newCap, newThr = 0;// 情况1：当前哈希表已初始化（oldCap > 0）if (oldCap > 0) {// 若旧容量已达最大容量（1<<30），不再扩容，阈值设为Integer.MAX_VALUEif (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab; // 直接返回旧表}// 否则，新容量 = 旧容量 * 2（左移1位）else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY) // 旧容量 >= 默认容量（16）时newThr = oldThr << 1; // 新阈值 = 旧阈值 * 2}// 情况2：哈希表未初始化，但阈值已设置（通过构造函数指定初始容量）else if (oldThr > 0)newCap = oldThr; // 新容量 = 旧阈值（此时阈值是构造函数计算出的容量）// 情况3：哈希表未初始化且无指定容量（使用默认参数）else {               newCap = DEFAULT_INITIAL_CAPACITY; // 默认容量16newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 默认阈值12}// 若新阈值为0（由情况1的未满足条件分支或情况2触发）if (newThr == 0) {float ft = (float)newCap * loadFactor; // 计算新阈值 = 新容量 * 负载因子newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE); // 确保不超过最大值}threshold = newThr; // 更新全局阈值// 创建新容量的Node数组@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab; // 更新哈希表引用// 若旧表不为空，开始数据迁移if (oldTab != null) {for (int j = 0; j < oldCap; ++j) { // 遍历旧表的每个桶Node<K,V> e;if ((e = oldTab[j]) != null) { // 当前桶有数据oldTab[j] = null; // 清空旧表引用，帮助GC// 情况A：单个节点（无链表或树）if (e.next == null)newTab[e.hash & (newCap - 1)] = e; // 直接计算新位置// 情况B：红黑树节点else if (e instanceof TreeNode)((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 拆分树结构// 情况C：链表节点（保持顺序迁移）else { // 低位链表（扩容后索引不变）Node<K,V> loHead = null, loTail = null;// 高位链表（扩容后索引 = 原索引 + oldCap）Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {next = e.next;// 判断节点属于低位还是高位链表if ((e.hash & oldCap) == 0) { // 哈希值对应旧容量的高位为0if (loTail == null)loHead = e; // 低位链表头elseloTail.next = e; // 链接到低位链表尾部loTail = e; // 更新低位链表尾} else { // 哈希值对应旧容量的高位为1if (hiTail == null)hiHead = e; // 高位链表头elsehiTail.next = e; // 链接到高位链表尾部hiTail = e; // 更新高位链表尾}} while ((e = next) != null);// 将低位链表放入新表的原索引位置if (loTail != null) {loTail.next = null;newTab[j] = loHead;}// 将高位链表放入新表的原索引 + oldCap位置if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab; // 返回扩容后的新表
}

为什么(e.hash & oldCap) == 0？

避免重新计算哈希值：直接利用原有哈希值的特定位，无需重新计算整个哈希。
链表拆分高效：通过一次遍历即可将链表拆分为两部分，时间复杂度为O(n)，避免多次计算索引。
避免死循环：保持链表顺序（Java 8优化），解决了Java 7中并发扩容可能导致的链表死循环问题。

为什么需要扩容？

避免哈希碰撞过多导致性能下降
保持负载因子（默认0.75）在合理范围

二、ConcurrentHashMap 并发实现

关键属性

//协调多线程环境下的表初始化和扩容操作。
// sizeCtl = -1	表正在初始化（仅一个线程能成功进入）
// sizeClt < -1	表正在扩容。此时高 16 位表示扩容标识戳（resize stamp），低 16 位表示扩容线程数+1
// sizeCtl = 0	默认初始状态，表示未指定初始容量（使用默认值 16）
// sizeCtl > 0	下一次触发扩容的阈值（容量 × 负载因子，默认 0.75）
private transient volatile int sizeCtl;static final int MOVED     = -1; // hash for forwarding nodes
static final int TREEBIN   = -2; // hash for roots of trees
static final int RESERVED  = -3; // hash for transient reservations
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash//元素计数
// 基础计数（baseCount）：
// 优先尝试直接通过 CAS 更新 baseCount。若成功且无竞争，直接返回。
// 分段计数（CounterCell[]）：
// 若检测到竞争（counterCells != null 或 CAS 失败），则使用 CounterCell 数组分散竞争，减少线程冲突。每个线程通过哈希（ThreadLocalRandom.getProbe() & m）选择一个计数单元进行 CAS 更新。
private transient volatile long baseCount;
private transient volatile CounterCell[] counterCells;

put() 方法实现

public V put(K key, V value) {return putVal(key, value, false); // 调用实际插入方法，默认覆盖旧值
}//onlyIfAbsent 如果为true，不覆盖已存在的值
final V putVal(K key, V value, boolean onlyIfAbsent) {// 检查空指针（ConcurrentHashMap不允许null键值）if (key == null || value == null) throw new NullPointerException();// 计算哈希：通过扰动函数使哈希分布更均匀，且确保最高位为0int hash = spread(key.hashCode());int binCount = 0; // 记录链表/TreeBin的节点数（用于树化判断）// 自旋循环直到插入成功（处理并发竞争）for (Node<K,V>[] tab = table;;) {Node<K,V> f; int n, i, fh;// CASE 1: 表未初始化则初始化（延迟初始化）if (tab == null || (n = tab.length) == 0)tab = initTable(); // 使用sizeCtl控制并发初始化// CASE 2: 目标桶位为空（通过CAS无锁插入）else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {// 原子操作插入新节点（无需加锁）if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))break; // 插入成功则退出循环}// CASE 3: 检测到MOVED节点（哈希桶正在扩容）else if ((fh = f.hash) == MOVED)tab = helpTransfer(tab, f); // 协助数据迁移，后面再讲// CASE 4: 哈希冲突，锁住链表头节点else {V oldVal = null;synchronized (f) { // 同步代码块（锁粒度细化到单个桶）(锁的是头节点)// 再次确认节点未被修改（防止并发操作）if (tabAt(tab, i) == f) {// 处理链表节点（fh >= 0）if (fh >= 0) {binCount = 1;// 遍历链表查找或插入for (Node<K,V> e = f;; ++binCount) {K ek;// 找到相同key的节点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<>(hash, key, value, null);break;}}}// 处理红黑树节点（TreeBin的hash固定为-2）else if (f instanceof TreeBin) {Node<K,V> p;binCount = 2; // TreeBin计数为2// 调用红黑树插入方法if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {oldVal = p.val;if (!onlyIfAbsent)p.val = value; // 覆盖旧值}}}}// 后处理：树化检查和返回旧值if (binCount != 0) {// 链表长度 >=8 时尝试树化（若表长度>=64）if (binCount >= TREEIFY_THRESHOLD)treeifyBin(tab, i);if (oldVal != null)return oldVal; // 返回被覆盖的值break;}}}// 更新元素计数，并检查是否需要扩容addCount(1L, binCount); return null; // 新插入节点返回null
}

哈希冲突处理：

同步锁：对桶头节点加 synchronized 锁

synchronized (f) {// 处理链表或红黑树插入
}

对比：Java 7 使用分段锁（Segment），锁粒度较大

为么ConcurrentHashMap不允许null键值？

1. 消除并发环境下的歧义性

歧义问题：在并发场景中，当调用 get(key) 返回 null 时，无法确定是键不存在，还是键对应的值本身为 null。例如：
- 线程 A 调用 get(key) 得到 null，但此时无法区分是键不存在，还是其他线程刚刚将值设为 null。
- 如果线程 B 在此时插入或删除了该键，线程 A 后续调用 containsKey(key) 的结果可能与之前的 get 不一致，导致逻辑混乱。
明确语义：禁止 null 后，get(key) 返回 null 唯一表示键不存在，简化了并发逻辑的判断。

2. 简化实现与提升性能

内部优化：ConcurrentHashMap 通过分段锁、CAS 操作等机制实现高效并发。若允许 null，需在哈希计算、节点操作等环节增加额外的空值检查，增加代码复杂性和性能开销。
状态一致性：非 null 约束可避免因 null 值干扰内部状态管理（如锁竞争、哈希冲突解决），确保数据结构的稳定性。

3. 鼓励更健壮的编程实践

显式处理缺失值：强制开发者使用明确的占位符（如 Optional）或特殊对象表示“空值”，避免隐式的 null 滥用，减少潜在的 NullPointerException。
与并发设计哲学一致：其他并发容器（如 ConcurrentLinkedQueue）也普遍禁用 null，以保持行为一致性和可预测性。

HashMap 和 ConcurrentHashMap 的哈希扰动的区别？

HashMap：追求简单高效的哈希分散，直接异或扰动后用于索引计算。
ConcurrentHashMap：在扰动基础上增加位运算HASH_BITS 的值为 0x7fffffff（二进制 0111...1111），确保结果始终为非负数。确保与内部状态标志兼容，同时适配并发控制机制。

获取某个桶tabAt()

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}

线程安全地获取哈希桶数组（Node<K,V>[]）中指定索引位置的节点的核心方法。

作用：以 volatile 语义读取指定内存位置的对象。确保读取的是主内存中的最新值，而非线程本地缓存（解决可见性问题）。
通过位运算高效计算索引 i 处元素的内存地址偏移量。

某个桶插入元素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);
}

增加元素数量addCount()方法

原子性地更新元素数量并触发扩容检查的核心方法。

1、线程安全地维护全局元素计数

2、在元素数量达到阈值时触发扩容（保证哈希表性能）

private final void addCount(long x, int check) {CounterCell[] as; long b, s; // 定义计数单元数组、基础计数值和总计数// 条件1：counterCells 已初始化（说明存在高并发竞争）// 条件2：尝试直接更新 baseCount 失败（CAS 失败，存在竞争）if ((as = counterCells) != null ||!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {CounterCell a; long v; int m;boolean uncontended = true; // 标记 CAS 操作是否成功// 条件1：counterCells 未初始化// 条件2：counterCells 已初始化但长度为0（异常情况）// 条件3：当前线程对应的 CounterCell 未初始化// 条件4：尝试更新 CounterCell 的值失败（CAS 失败）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; // 更新完成直接返回}// check <=1 时不触发扩容检查（优化性能）if (check <= 1)return;// 计算当前总元素数（baseCount + 所有 CounterCell 的值）s = sumCount();}// 若 check >=0 则检查是否需要扩容if (check >= 0) {Node<K,V>[] tab, nt; int n, sc;// 循环检查扩容条件：// 1. 当前元素数 s >= 扩容阈值 sizeCtl// 2. 哈希表已初始化且未达到最大容量while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&(n = tab.length) < MAXIMUM_CAPACITY) {int rs = resizeStamp(n); // 生成扩容戳（标识当前扩容批次）// 情况1：当前已有线程在扩容（sc < 0）if (sc < 0) {// 校验扩容是否已完成或无效扩容状态：// 1. 扩容戳不匹配（说明扩容已结束或属于其他批次）// 2. 无剩余迁移任务（transferIndex <= 0）// 3. 扩容线程数超过最大值if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||transferIndex <= 0)break;// 尝试增加扩容线程数（CAS 更新 sizeCtl）if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))transfer(tab, nt); // 协助数据迁移}// 情况2：当前无扩容进行，尝试发起扩容（CAS 设置 sizeCtl）else if (U.compareAndSwapInt(this, SIZECTL, sc,(rs << RESIZE_STAMP_SHIFT) + 2))transfer(tab, null); // 启动迁移（nextTable 由 transfer 创建）s = sumCount(); // 重新计算当前元素数量}}
}

1. 更新元素计数

基础计数（**baseCount**）：
优先尝试直接通过 CAS 更新 baseCount。若成功且无竞争，直接返回。
分段计数（**CounterCell[]**）：
若检测到竞争（counterCells != null 或 CAS 失败），则使用 CounterCell 数组分散竞争，减少线程冲突。每个线程通过哈希（ThreadLocalRandom.getProbe() & m）选择一个计数单元进行 CAS 更新。
后备机制（**fullAddCount**）：
若 CounterCell 未初始化或 CAS 失败，进入 fullAddCount 方法处理初始化、扩容或重试逻辑。

2. 扩容触发条件

扩容阈值（**sizeCtl**）：
当总元素数 s >= sizeCtl 时触发扩容。
扩容协调：
- 扩容戳（**resizeStamp**）：基于当前哈希表长度生成唯一标识，确保多批次扩容不冲突。
- 扩容线程数控制：通过 CAS 操作原子性地增加 sizeCtl 中的线程数标记。

3. 扩容执行

协助迁移（**transfer**）：
已有扩容进行时，当前线程协助迁移数据（transfer(tab, nt)）。
新扩容启动：
无扩容时，通过 CAS 设置 sizeCtl 并启动迁移（transfer(tab, null)）。

initTable()初始化方法

/*** 初始化哈希表。此方法采用CAS+自旋保证多线程环境下的安全初始化。*/
private final Node<K,V>[] initTable() {Node<K,V>[] tab; int sc; // sizeCtl 的临时变量// 自旋操作：当 table 未初始化或长度为0时持续尝试while ((tab = table) == null || tab.length == 0) {// CASE 1：sizeCtl < 0 表示其他线程正在初始化，让出CPU资源if ((sc = sizeCtl) < 0) {Thread.yield(); // 通过yield()让出CPU，避免不必要的竞争// CASE 2：尝试通过CAS获取初始化权（将 sizeCtl 设置为-1）} else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {try {// 双重检查：再次确认 table 未被其他线程初始化if ((tab = table) == null || tab.length == 0) {// 确定初始容量：若 sizeCtl > 0 则使用其值，否则使用默认16int n = (sc > 0) ? sc : DEFAULT_CAPACITY;// 创建 Node 数组（底层哈希表）@SuppressWarnings("unchecked")Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];table = tab = nt; // 赋值给成员变量 table 和局部变量 tab// 计算扩容阈值：n - n/4 = 0.75n（负载因子为0.75）sc = n - (n >>> 2); // 等价于 sc = n * 0.75}} finally {// 无论是否成功初始化，都将 sizeCtl 设置为扩容阈值sizeCtl = sc; // 此时 sc 可能是阈值或原值（如果其他线程已初始化）}break; // 初始化完成，退出自旋}}return tab; // 返回初始化后的哈希表
}

get() 方法实现

public V get(Object key) {Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;// 1. 计算键的哈希值（通过 spread 保证高位参与哈希分布，减少冲突）int h = spread(key.hashCode());// 2. 检查哈希表已初始化，且目标桶位置存在节点（通过原子读 tabAt 保证可见性）if ((tab = table) != null && (n = tab.length) > 0 &&(e = tabAt(tab, (n - 1) & h)) != null) {// 3. 检查头节点的哈希值与键是否匹配if ((eh = e.hash) == h) {// 3.1 头节点直接命中（地址或 equals 匹配）if ((ek = e.key) == key || (ek != null && key.equals(ek)))return e.val;}// 4. 头节点哈希值为负，说明当前桶处于特殊状态（如扩容或树化）else if (eh < 0)// 4.1 调用节点的 find 方法（可能为树节点或 ForwardingNode）// 树的话Node为TreeBinNode  调用其中的find方法的话// 扩容的话为ForwardingNodereturn (p = e.find(h, key)) != null ? p.val : null;// 5. 遍历链表查找目标节点（头节点哈希匹配但键未命中）while ((e = e.next) != null) {if (e.hash == h &&((ek = e.key) == key || (ek != null && key.equals(ek))))return e.val;}}// 6. 未找到匹配节点return null;
}

扩容机制（transfer）

功能说明

transfer 方法是 ConcurrentHashMap 扩容操作的核心实现，负责将旧哈希表（table）中的节点迁移到新哈希表（nextTab）。其核心目标如下：

渐进式扩容：通过多线程协作分段迁移数据，避免单线程阻塞。
并发安全：通过 CAS、synchronized 和状态标记保证线程安全。
数据完整性：迁移过程中确保读操作能正常访问旧表或新表。
树化与退化：处理红黑树节点，并在必要时将树退化为链表。

// 参数说明// tab：当前哈希表（旧表），待迁移的数组。// nextTab：新哈希表，扩容后的数组；若为 null，则初始化为旧表的两倍大小。
// 关键变量说明// stride：每个线程负责迁移的桶区间（步长），最小为 MIN_TRANSFER_STRIDE（默认 16）。// ForwardingNode：占位节点，标记某个桶已迁移完成，读操作遇到此节点会转发到新表。// advance：控制线程是否继续处理下一个桶。// finishing：标记迁移是否完成，最后一个线程负责收尾工作。// transferIndex：全局迁移进度指针，记录下一个待分配迁移任务的桶索引。
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {int n = tab.length, stride;// 计算每个线程处理的桶区间大小（stride）// 默认每个线程处理 n/8/NCPU 个桶，最小为 MIN_TRANSFER_STRIDE=16if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)stride = MIN_TRANSFER_STRIDE; // 确保不低于最小值// 初始化新数组（仅在第一个发起扩容的线程中执行）if (nextTab == null) {try {@SuppressWarnings("unchecked")// 创建两倍大小的新数组Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];nextTab = nt;} catch (Throwable ex) { // 处理内存不足异常（OOME）sizeCtl = Integer.MAX_VALUE; // 扩容失败，sizeCtl设为最大值return;}nextTable = nextTab; // 更新全局新数组引用transferIndex = n;   // 迁移起始索引，从旧数组末尾开始}int nextn = nextTab.length; // 新数组长度// 创建ForwardingNode节点，用于标记迁移完成的桶ForwardingNode<K,V> fwd = new ForwardingNode<>(nextTab);boolean advance = true;  // 控制是否推进到下一个桶boolean finishing = false; // 是否完成所有迁移// 主循环：i为当前处理的桶索引，bound为当前线程负责的区间下界for (int i = 0, bound = 0;;) {Node<K,V> f; int fh;// 步骤1：确定当前线程需要处理的桶区间while (advance) {int nextIndex, nextBound;// 情况1：当前区间未处理完，i减1继续处理if (--i >= bound || finishing)advance = false;// 情况2：所有桶已分配完毕，设置i=-1表示结束else if ((nextIndex = transferIndex) <= 0) {i = -1;advance = false;}// 情况3：CAS更新transferIndex，分配下一个区间else if (U.compareAndSwapInt(this, TRANSFERINDEX, nextIndex,nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {bound = nextBound;       // 当前线程负责的区间下界i = nextIndex - 1;       // 从nextIndex-1开始倒序处理advance = false;}}// 步骤2：检查迁移是否全部完成if (i < 0 || i >= n || i + n >= nextn) {int sc;if (finishing) { // 所有迁移完成nextTable = null;        // 清除临时引用table = nextTab;         // 更新全局数组为新表sizeCtl = (n << 1) - (n >>> 1); // 更新阈值（新容量的0.75倍）return;}// 当前线程完成自己的任务，通过CAS减少sizeCtl的线程计数if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {// 检查是否是最后一个退出的线程（sc-2等于扩容标识）if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)return;finishing = advance = true; // 最后一个线程需重新检查所有桶i = n; // 从n开始倒序检查}}// 步骤3：处理空桶（标记为ForwardingNode）else if ((f = tabAt(tab, i)) == null)advance = casTabAt(tab, i, null, fwd); // CAS设置ForwardingNode// 步骤4：跳过已处理的桶（hash=MOVED表示已迁移）else if ((fh = f.hash) == MOVED)advance = true;// 步骤5：处理非空桶（链表或树）else {synchronized (f) { // 加锁保证线程安全if (tabAt(tab, i) == f) { // 再次验证未被修改Node<K,V> ln, hn; // 低位链和高位链// 情况1：处理链表节点（fh >=0）if (fh >= 0) {int runBit = fh & n; // 计算散列位Node<K,V> lastRun = f;// 找到最后一个变化runBit的节点for (Node<K,V> p = f.next; p != null; p = p.next) {int b = p.hash & n;if (b != runBit) {runBit = b;lastRun = p;}}// 根据runBit初始化ln和hn头节点if (runBit == 0) {ln = lastRun;hn = null;} else {hn = lastRun;ln = null;}// 遍历链表，将节点分配到ln或hnfor (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<>(ph, pk, pv, ln); // 插入ln头部elsehn = new Node<>(ph, pk, pv, hn); // 插入hn头部}// 将ln和hn放入新数组的i和i+n位置setTabAt(nextTab, i, ln);setTabAt(nextTab, i + n, hn);setTabAt(tab, i, fwd); // 标记旧桶为已处理advance = true;}// 情况2：处理树节点（TreeBin）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;// 遍历树节点，分割到lo和hifor (Node<K,V> e = t.first; e != null; e = e.next) {int h = e.hash;TreeNode<K,V> p = new TreeNode<>(h, e.key, e.val, null, null);if ((h & n) == 0) { // 低位树if ((p.prev = loTail) == null)lo = p;elseloTail.next = p;loTail = p;++lc;} else { // 高位树if ((p.prev = hiTail) == null)hi = p;elsehiTail.next = p;hiTail = p;++hc;}}// 根据节点数量决定是否转为链表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;}}}}}
}

关键设计说明：

分片迁移（Stride）
每个线程处理一个桶区间（stride），默认大小是n/(8*NCPU)，最小16。通过transferIndex全局变量分配任务区间，多线程协作完成迁移。
ForwardingNode的作用
迁移完成的桶会被标记为ForwardingNode（hash=MOVED），其他线程遇到时会协助迁移或直接访问新表。
链表分割逻辑
根据hash & oldCap是否为0，将链表拆分为低位链（ln）和高位链（hn），分别放入新数组的i和i + oldCap位置。
树节点处理
红黑树迁移后，若节点数小于等于UNTREEIFY_THRESHOLD（默认6），则转为链表；否则新建TreeBin。
线程安全
使用synchronized锁定桶头节点，结合CAS更新transferIndex和sizeCtl，保证多线程扩容的正确性。

helpTransfer()协助迁移方法

/*** 协助从旧的哈希表（tab）迁移数据到新表。* 当某个桶遇到 ForwardingNode 节点时，调用此方法让当前线程协助迁移。* * @param tab 当前线程看到的哈希表（可能正在扩容）* @param f   当前桶的头节点（必须是 ForwardingNode）* @return 返回新表（nextTable）若正在迁移，否则返回原表*/
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {Node<K,V>[] nextTab; int sc;// 检查表不为空、节点是 ForwardingNode，且新表 nextTable 已初始化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) {  // sizeCtl < 0 表示正在扩容// 校验扩容状态是否失效，若失效则退出协助if ((sc >>> RESIZE_STAMP_SHIFT) != rs ||  // 扩容标记不匹配（非同一轮扩容）sc == rs + 1 ||                       // 无更多线程需要协助（旧版逻辑）sc == rs + MAX_RESIZERS ||            // 协助线程数已达最大值transferIndex <= 0)                   // 所有桶已分配完毕，无需迁移break;  // 退出循环，不再协助// 尝试通过 CAS 增加 sizeCtl 的低 16 位（增加一个协助线程）if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {transfer(tab, nextTab);  // 调用实际迁移方法break;  // 迁移完成后退出循环}}return nextTab;  // 返回新表，供后续操作使用}return table;  // 未协助迁移或迁移已完成，返回当前表（可能是原表或新表）
}

关键逻辑说明：

条件检查：
- **tab** 非空且 **f** 是 **ForwardingNode**：确保当前桶已迁移，需转发到新表。
- **nextTable** ****存在：确认扩容已开始且新表已初始化。
扩容标记**** **resizeStamp()**：
- 生成一个与旧表长度相关的唯一标记（高16位为特征码，低16位包含容量信息），用于校验多轮扩容。
循环校验与协助：
- 一致性检查：确保新表 nextTab 和全局表引用未变化，避免协助过期的扩容。
- **sizeCtl** ****状态：负数表示扩容中，其高16位存储扩容标记，低16位记录协助线程数+1。
- 终止条件：
 - 扩容标记不匹配（非同一轮扩容）。
 - 协助线程数已满或迁移完成（transferIndex <= 0）。
- CAS 增加协助线程：成功则调用 transfer() 执行数据迁移。
返回值：
- 若协助成功，返回新表 nextTab，后续操作直接操作新表。
- 若条件不满足或迁移完成，返回当前表（可能是原表或已完成迁移的新表）。

注意事项：

线程协作机制：通过 sizeCtl 的原子操作协调多线程，避免重复迁移和资源竞争。
ForwardingNode 作用：作为占位节点提示当前桶已迁移，引导操作到新表。
扩容标记校验：确保所有协助线程处理同一轮扩容，防止多轮扩容并发导致数据错乱。

此方法通过精细的状态判断和原子操作，实现了高效、安全的多线程协同扩容，显著提升 ConcurrentHashMap 在大数据量下的性能表现。

三、与JAVA 7的实现差异

哈希冲突处理：

同步锁：对桶头节点加 synchronized 锁

synchronized (f) {// 处理链表或红黑树插入
}

对比：Java 7 使用分段锁（Segment），锁粒度较大

扩容机制：

Java 7 的扩容只能在锁住 Segment 的情况下进行
Java 8 的并发扩容效率提升 30% 以上

特性	Java 7	Java 8
数据结构	数组+链表	数组+链表+红黑树
哈希冲突处理	头插法	尾插法
锁机制	分段锁（Segment）	CAS + synchronized
并发扩容	单线程扩容	多线程协同扩容
哈希计算	4次位运算+5次异或	1次位运算+1次异或
时间复杂度	链表查询 O(n)	最差 O(logn)

四、关键设计思想

空间换时间：通过负载因子控制空间利用率
降低竞争：
- HashMap 通过树化防止链表过长
- ConcurrentHashMap 通过分段锁/CAS 减少锁竞争
渐进式优化：Java 8 的并发扩容不会阻塞所有操作
失败重试机制：CAS 失败后通过循环重试保证原子性

五、典型问题示例

为什么HashMap线程不安全？
- 多线程同时扩容可能导致死循环（Java 7）
- 数据覆盖问题（Java 8）
ConcurrentHashMap为什么放弃分段锁？
- 细粒度锁（synchronized）在 Java 8 中性能大幅提升
- 分段锁内存消耗较大（每个 Segment 继承 ReentrantLock）
树化阈值为8的科学依据？
- 根据泊松分布，哈希冲突达到8的概率小于千万分之一