List

LinkedHashMap

TreeMap

HashMap

ConcurrentHashMap

Hashtable(弃用)

Map 接口

Queue

Set

• ArrayList
• LinkedList
• Vector(弃用)

• LinkedList
• PriorityQueue
• ArrayDeque

• HashSet
• LinkedHashSet
• TreeSet

Java 集合

Color：

• 蓝色为我引用的笔记
• 黄色为当前提出的问题(应该是未解决的问题，还需要我去解决)
• 绿色为提出的问题被解决，在后面给出答案
• 红色为TODO

集合的分类

迭代器的实现原理

CopyOnWriteArrayList 的实现原理

Collection 接口

杂项(即考的不多的部分)

为什么一定要是 2 的幂

若 key 为 null，存储在 table[0] 的位置

Put 操作

当链表总容量(MIN_TREEIFY_CAPACITY) $\ge$ 64 且一个桶中的链表长度达到 8 (TREEIFY_THRESHOLD)则转换为红黑树，若桶中元素减少到 6(UNTREEIFY_THRESHOLD )，则转换回链表

• 位运算效率更高：位运算(&)比取余运算(%)更高效。当长度(length)为 2 的幂次方时，hash % length 等价于 hash & (length - 1)。
• 可以更好地保证哈希值的均匀分布：扩容之后，在旧数组元素 hash 值比较均匀的情况下，新数组元素也会被分配的比较均匀，最好的情况是会有一半在新数组的前半部分，一半在新数组后半部分。
• 扩容机制变得简单和高效：扩容后只需检查哈希值高位的变化来决定元素的新位置，要么位置不变（高位为 0），要么就是移动到新位置（高位为 1，原索引位置 i+原容量 length）。即让 rehash 变得更加高效

数组+链表+红黑树

当哈希表容量（即桶数组长度）小于 64 时，即使链表长度超过 8，也不会立即树化。而是在先触发扩容，扩大桶数组容量，避免树化带来的复杂性。扩容后，如果链表仍然过长，则真正开始树化。
即当容量小于 64 且某个桶链表长度大于等于 8 时会进行扩容(但不一定会树化)

扩容(resize())

没有

怎样的情况触发扩容

JDK 1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。

get 操作

数组+链表

HashMap 多线程操作导致死循环问题

ArrayList 的底层原理

JDK8 及其以后

底层数据结构

JDK7 及其以前

保证 HashMap 大小一定为 2 的幂

loadFactor 为什么是 0.75？

/**
 * 找到大于或等于 cap 的最小2的幂
 */
static final int tableSizeFor(int cap) {
    int n = cap - 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;
}

当 HashMap 中存储的键值对数量超过了一个阈值（threshold）时，就会触发扩容。

• 阈值是当前容量乘以加载因子(capacity * loadFactor)。
• loadFactor 的默认值是 0.75f

对于各个操作的源码分析

询问大模型即可： 分析一下ArrayList的各个操作的源码，并给出操作流程

modCount 用于记录列表结构性修改的次数。结构性修改是指那些可能会改变列表大小（size）的操作，或者以其他方式扰乱正在进行的迭代的操作。

使用 synchronized 关键字或其他并发控制手段来保护其内部状态，所以线程不安全。

• 高并发会导致数据不一致问题，丢 ConcurrentModificationException 异常

与其他Map的区别

自动扩容机制

HashMap 的底层原理

checkForComodification() 方法用于检测在迭代过程中，列表是否被并发修改（或者说，是否在迭代器之外被结构性修改）。若 modCount != expectedModCount 即自己和自己不同了，则抛出异常

• Vector (old，严格的线程安全，性能差)
• Collections.synchronizedList(List<T> list) (同上，对所有方法同步)
• java.util.concurrent.CopyOnWriteArrayList

为什么有快速查找的能力

杂项（即自己对于原理的问题）

modcount 是什么？有什么用

底层实现依赖于数组：

• 随机访问
• 内存连续性

线程安全吗？不安全用什么

动态数组的关键，当内部数组不足以容纳新元素时触发。
在关于添加元素的方法中都会涉及扩容。

• JDK7 及以后，默认是空数组(以前默认为 10)
• 需要扩容时，底层触发 grow() 方法
  • 新容量为原来的 1.5 倍，若仍不够，则以传入的为准
  • 确定新容量后，使用 Arrays.copyOf 方法(旧的被回收，分配新的，更大的新数组)
  • 频繁的扩容会影响性能(由上一点看出，扩容时间复杂度为 $O(n)$)

扩容机制

1. 底层数据结构
2. 各个操作的复杂度不同
3. 内存开销不同
4. ArrayList 具有随机访问能力

与 LinkedList 的区别

推荐：

• JDK7的HashMap头插法循环的问题
• 为什么 HashMap 会死循环？

无锁尝试(CAS)

put 方法

加锁操作(CAS 失败)

如果目标哈希桶为空，会尝试使用 CAS 操作原子性地将新节点设置为该桶的头节点。

如果后续是链表

如果是 TreeBin(红黑树)

ForwardingNode 的作用： 当一个线程完成了某个旧桶中所有节点的迁移后，它会在旧表的该桶位置放置一个 ForwardingNode。这个 ForwardingNode 包含指向新表（nextTable）的引用。后续如果其他线程访问这个已被迁移的旧桶，ForwardingNode 会将请求转发到新表中继续处理，这样就不会丢失更新或读到旧数据。

遍历链表，如果找到相同的 key 则更新 value；否则，将新节点追加到链表末尾。

调用 TreeBin 的 putTreeVal 方法将键值对插入到红黑树中。TreeBin 内部会处理红黑树的平衡和并发。

通常是完全无锁的。直接通过哈希定位，然后遍历链表或在红黑树中查找。volatile 保证了读取到的是最新的值。

JDK7

get 方法

定位桶

由于 Node 的 val 和 next（对于链表）以及 TreeBin 内部结构的恰当同步（例如 volatile 读或 TreeBin 自身的同步机制），get 操作可以并发执行且能获取到最新的数据。

int hash = spread(key.hashCode());

说明有其他线程同时修改了 table[i] 或 table[i] 已有节点，
则需要对该桶的头节点进行加锁。

如果 table[i] 不为 null 且不是 ForwardingNode： 这意味着该桶已经有节点了。

get 操作在大部分情况下是不需要加锁的。HashEntry 中的 value 和 next 指针通常用 volatile 修饰，保证了内存可见性。只有在需要读取可能会被并发修改的结构（如读取过程中发现链表头被替换）时，才可能需要一些轻量级的同步或重试。

先尝试不加锁地累加所有 Segment 的大小，如果在此过程中某个 Segment 被修改了（通过 modCount 判断），则重试。如果重试多次失败，最终可能需要锁住所有 Segment 来确保准确性。

get 方法

size 方法

详细的说明到 JUC 中去

创建新数组，容量翻倍，新的扩容阈值也会相应地重新计算

是的，由 concurrencyLevel 决定，并向上调整为最接近的 2 的幂

为什么需要判断 ForwardingNode？
实现安全的并发迁移：扩容时，旧的哈希表节点要迁移到新表。如果操作中没有转发节点，旧表的访问者可能会访问到已经迁移不完整或者移除的节点，会导致错误或数据不一致。

协同迁移和访问：多个线程同时操作结构，其中部分线程可能正在完成旧表到新表的迁移，另外一些线程正尝试访问数据。通过判断是否为 ForwardingNode，线程能够：

• 识别该槽位已经转发，立即跳转到新表。
• 避免在旧表上重复查找无效数据。
• 协助完成迁移操作（比如迁移过程中的协作推进）。

table[i] = ForwardingNode 表示：

• 在旧的数组的第 i 个槽位，存放的是转发节点。
• 访问者如果遇到这个节点，应该跳转（forward）到新的数组中去查找该键、插入或删除。-

数据迁移

创建一个新的、容量为原容量两倍的数组，然后将旧数组中的所有键值对重新计算哈希值和新的索引（这个过程称为 rehash），并迁移到新的数组中。(相对耗时)

如何进行数据迁移的？整个扩容的过程是怎样的？

更新引用

HashMap 和 Hashtable 的区别

HashMap 和 TreeMap 区别

HashMap 和 HashSet 区别

数组+链表/红黑树

分段的数组+链表

与 HashMap 的 JDK8 版本实现相似

JDK7 的实现的问题：

• 对于 segment 创建时指定后续无法更改。导致固定的并发级别。
• 内存开销大
• size()操作的复杂性

Hashtable 采用数组+链表的形式

底层数据结构

JDK7

JDK8

若拆分后，某个新桶中的节点数量仍然很多(即超过 UNTREEIFY_THRESHOLD =6)，则保持红黑树结构/重新构建红黑树

(e.hash & oldCap) == 0，则该节点在新表中的索引仍然是 i

若拆分后，桶的节点数量少于这个值，则会被反树化(untreeify)，变回链表结构以减少开销

先获取 key 的 hashCode 值，然后进行 rehash/spread

定位 segment 索引

(e.hash & oldCap) != 0，则该节点在新表中的索引是 i+oldcap

可参考 synchronized*

升级路径：(需要注意各个锁的使用场景和作用)

• 无锁
• 偏向锁
• 轻量级锁
• 重量级锁

具体内容在此不赘述，对于这块的内容，放入 JUC，这个内容很重要

有的，tableSizeFor 方法来实现，实现方式和 HashMap(JDK8)一模一样，HashMap 部分也给出了代码

tableSizeFor 方法的参数是预期的容量，返回的是 2 的幂的结果。

如果直接在参数填写 size<<1 的话就会导致返回的值可能偏高

JDK7

红黑树

也会根据 (e.hash & oldCap) 的结果被分配到新表的两个不同索引位置。

HashMap 的 table 引用指向这个 newTable，并更新 threshold。

链表

单个节点

允许同一个线程多次获取它已经持有的同一个锁，而不会导致该线程自身被阻塞（即不会发生死锁）
关键依赖于当前持有锁的线程以及一个持有计数器

• 当该锁没有被占有或被请求锁占有都可以成功获取锁，计数器加一即可
• 否则，请求锁的线程被阻塞直到锁被完全释放

对于每个节点，新节点要么在原索引(i)，要么在原索引+旧容量(i+oldcap)位置

根据其哈希值重新计算在新 newTable 中的索引，并将其放入 newTable 的相应位置。

HashTable 使用 synchronized 来保证线程安全，但效率很低(几乎所有方法都加了 synchronized )

HashTable 为数组+链表的结构ConcurrentHashMap 底层数据结构则如上总结内容

对于 ConcurrentHashMap 实现线程安全分支如下面的总结

• 内部主要是一个 Entry[] table 数组，其中每个 Entry 是一个单向链表节点，用于解决哈希冲突。Entry 包含 hash, key, value, 和 next 指针。
• 当哈希冲突发生时，新的 Entry 会被添加到对应桶（bucket）的链表头部。

将数据分为一段一段(Segment，默认大小为 16)进行存储，对于每个段配备一把锁。

每个 Segment 包含一个 HashEntry 数组，每个 HashEntry 为链表的结构，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 的锁。也就是说，对同一 Segment 的并发写入会被阻塞，不同 Segment 的写入是可以并发执行的。

• 感觉每个 Segment 都像是一个小型的 HashMap(JDK7)
• Segment 继承了 ReentrantLock，为可重入锁

取消了 Segment 分段锁，从而转向使用 Node + CAS + synchronized 来保证并发安全(又有点像 HashMap 的 JDK8 实现了)

同样是当多个线程尝试修改同一个哈希桶（bucket）中的数据时，只有在发生哈希冲突，即多个键映射到同一个桶的头节点时，才会对该桶的头节点加 synchronized 锁

JDK8

迭代器行为

与 HashMap 的区别

null key/value 的支持

性能

value 和 next 指针通常是 volatile 的。

当一个桶被树化后，该桶在 table 数组中实际存放的是一个 TreeBin 对象。TreeBin 封装了红黑树的根节点以及相关的锁（ReentrantLock 或者直接使用 synchronized (this)）。它负责红黑树的查找、插入、删除等操作，并处理并发控制。

TreeBin

Node 数组

ForwardingNode

在扩容（resize）过程中使用的一种特殊节点。当一个桶的迁移完成并发到新表后，旧表中的该桶会放置一个 ForwardingNode，其 find 方法会将后续的访问（如 get, put）导向到新表中。

高并发访问的缓存场景

适合缓存频繁读写数据，减少锁竞争。

是否并发

多线程共享状态维护

如统计次数、实时数据聚合等场景，比如统计某些业务访问量、访问频率等。

底层数据结构

扩容机制

复杂操作中的线程安全容器

在分布式系统或异步框架中，常作为线程间共享数据结构。

HashMap：快速失败机制

ConcurrentHashMap：弱一致性

在并发环境中，get(key) 返回 null 时，如果允许值为 null，则无法明确区分是“键不存在”还是“键存在但其对应的值就是 null”。禁止 null 可以消除这种歧义，简化并发逻辑。

使用场景不同，HashMap 不用于并发场景

ConcurrentHashMap 不允许的原因

扩容期间的操作

get 操作

put() / remove() 等修改操作

• 如果操作的 bin 尚未被迁移，且没有其他线程正在迁移它，则正常操作（可能需要锁住该 bin 的头节点）。
• 如果操作的 bin 正在被某个线程迁移（即该 bin 的头节点被锁住了），则当前线程会阻塞在该 bin 的锁上，等待迁移完成。
• 如果操作的 bin 已经是 ForwardingNode，则操作会被重定向到 nextTable 中进行。
• 如前所述，执行修改操作的线程在发现扩容正在进行时，可能会先 helpTransfer()。

是否线程安全

与 HashTable 的区别

底层数据结构不同

实现线程安全的方式

区别

HashMap 通过 key 的 hashcode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。(在 JDK8 中解决 Hash 冲突方式变化)

扰动函数

1. 可以保证扩容之后 1/2 概率不变，1/2 概率变为 i+oldcap 位置
2. 为了极致的效率，就是需要牺牲空间的

private int hash(Object k) {
    int h = k.hashCode();
    // Spread bits to regularize both segment and index locations,
    // using variant of single-word Wang/Jenkins hash.
    h += (h <<  15) ^ 0xffffcd7d;
    h ^= (h >>> 10);
    h += (h <<   3);
    h ^= (h >>>  6);
    h += (h <<   2) + (h << 14);
    return h ^ (h >>> 16);
}

例如：
(n-1)=...000111...
hash=10110101...

则对于 hash 高位一定变为 0，hash 的低位一定保持原状

默认情况下拆分后，若重新构建节点个数仍然是大于 6 的，则重新构建一个新的红黑树

在 JDK 8 中对此进行了优化，它会将原链表拆分成两条新的子链表：

• 一条是所有在新表中索引不变的节点（低位链表 loHead, loTail）
• 另一条是所有在新表中索引变为 i + oldCap 的节点（高位链表 hiHead, hiTail）。
• 然后将这两条子链表分别挂到 newTable[i] 和 newTable[i + oldCap] 上。

这样做可以保持元素在链表中的相对顺序，并且避免了对每个元素都重新完整计算哈希和索引。

• 首先检查 table[i] 的第一个节点，看其键是否与要查找的 key 相同。
• 如果不同，并且 table[i] 的 next 节点不为 null：
  • 红黑树: 如果 table[i] 是一个红黑树的节点 (TreeNode)，则调用红黑树的查找方法（通常是 getTreeNode(hash, key)）在树中查找。
  • 链表: 否则，遍历该桶中的链表，逐个比较节点的键是否与要查找的 key 相同。

//JDK1.8
	static final int hash(Object key) {
		int h;
	  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }
//JDK.7
	static int hash(int h) {
		h ^= (h >>> 20) ^ (h >>> 12);
		return h ^ (h >>> 7) ^ (h >>> 4);
	}

因为 n 为 2 的幂，则 n - 1 为全 1 的二进制串，则 hash 和 n-1 的与操作转换为 hash%n 了。

• 默认 0.75f 是时间和空间成本之间的一个权衡。
• 较高的负载因子（如 0.9）会减少空间开销（数组更满才扩容），但会增加查找成本（因为哈希冲突的可能性更大，链表/树更长）。
• 较低的负载因子（如 0.5）会增加空间开销（数组很空就扩容），但会减少查找成本（哈希冲突更少）。

感觉主要是 equals 效率十分低下，使用 hashCode 方式会以很快的速度排除掉不可能的选择

简单来说：即无解，必须保证他们的一致性

冲突的情况以及后果

这其实是一个比较蠢的问题了，因为两个 hash 的定义是不一样的

• 对于 HashMap 中的索引是对于底层的 Node 数组的，得到的索引是数组的索引
• 而红黑树比较的索引是 hashCode() 这个"hash"值

对于两个 hash 值的关系则根据扰动函数

链表：

• 先比较其 hashCode() 方法
  • 若不同，则一定不是目标节点
  • 若相同，则调用 equals() 方法
    • 若返回 true，则找到了匹配的 key，返回 value
    • 若返回 false，则说明不是目标节点，继续遍历

若遍历完都没有找到，返回null

发生冲突的情况即为：两个方法的返回值不相对应

• HashMap (以及其他依赖这些约定的集合类，如 TreeSet, TreeMap) 的行为可能会变得不可预测和混乱。

即可能导致：

• 在 get 操作时提前终止在不该终止的节点
• 可能找不到存在的元素
• 可能错误地替换元素或无法替换
• 违反集合的语义(在 TreeSet 中根据 compareTo 判定唯一性)
• 数据结构损坏/性能下降

红黑树：其实和链表差不多，都是先比较 hashCode() 然后比较 equals 方法来判定，但不同的点是：

• 每到达一个 TreeNode，将目标 key 的 hash 值与当前节点的 hash 值进行比较
  • 若目标 key 的 hash 值小于 TreeNode 的，(若存在)则必定在当前节点的左子树，向左子节点移动
  • 若目标 key 的 hash 值大于 TreeNode 的，(若存在)则必定在当前节点的右子树，向右子节点移动
  • 若目标 key 的 hash 值等于 TreeNode 的，则需要进一步比较键本身
    • 若 equals 方法返回 true，查找结束
    • 返回 false，则需要根据 key 的可比较性来决定是去哪边
      • 如果实现了 Comparable 接口，则调用 compareTo 返回值确定去哪个子节点(<0:左;>0:右)，若返回 0，则表示实现不一致(equals 和 compareTo)，即出现冲突
      • 若没有实现 compareTo 接口，则使用 HashMap 的 TreeNode 内部的备用比较机制：即比较类名/ identityHashCode() 来决定向左/右子树走

若遍历完这颗红黑树都没有找到，返回 null

其实就是比较远古的原理：当 n=2^ k，有：hash%n=(n-1)&hash

只是这里的 n=ssize(ssize 是 2 的幂)，hash=这里的 hash 的高 N 位

因为 hashCode 返回的是一个 int，不一定是正数，&INT_MAX 主要就是为了返回的值一定是正数(因为 i = (n - 1) & hash(hash % n) 是索引，必须为正)

即取 hash 的高位前 N 位&Mask(二进制位一个 0，N-1 个 1)

对于不同的 java 包装类/容器，有着不一样的规则？这个问题可以去问大模型

do {
	next = e.next;
	if ((e.hash & oldCap) == 0) {
		if (loTail == null)
			loHead = e;
		else
			loTail.next = e;
		loTail = e;
	}
	else {
		if (hiTail == null)
			hiHead = e;
		else
			hiTail.next = e;
		hiTail = e;
	}
} while ((e = next) != null);

JDK7 的插入方式：

//元素连接到桶中，这里相当于单链表的插入，总是插入在最前面，指针指向他下面的一个元素
e.next=newTable[i];
//newTable[i]的值总是最新插入的值
newTable[1] = e;
//继续下一个元素
e=next;

final Segment<K,V> segmentFor(int hash) {
    // segmentShift 和 segmentMask 是在构造 ConcurrentHashMap 时根据 concurrencyLevel 计算出来的
    // segmentMask = ssize - 1 (ssize 是 segment 数组的长度, 即 2^N)
    // segmentShift = 32 - N // 即 32 - log2(ssize)
    // (hash >>> segmentShift) & segmentMask
    return segments[(hash >>> segmentShift) & segmentMask];
}

    static final int spread(int h) {
        return (h ^ (h >>> 16)) & HASH_BITS;
        //HASH_BITS = 0x7fffffff，即INT_MAX=2^31-1
    }

和 HashMap 原因相同

同样会对 hashCode 进行扰动

定位即 int index = (n - 1) & h

n 为 table 数组的大小，是 2 的幂

首先计算键的哈希值并经过扰动函数处理，然后计算出数组索引。接着访问对应索引的桶。如果桶为空，则返回 null。如果桶不为空，则需要遍历桶中的数据结构（链表或红黑树）。在遍历过程中，会先比较哈希值，如果哈希值相同，再调用键的 equals() 方法进行精确比较。如果找到匹配的键，则返回对应的值；如果遍历完整个结构都没有找到，则返回 null。

若 hash 值相同，如何遍历桶中的链表/红黑树的？

JDK8 尾插法没有问题的实现方式

条件：

1. HashMap 使用头插法进行数据插入（JDK 1.8 之前）；
2. 多线程同时添加；
3. 触发了 HashMap 扩容。

参与扩容的线程（包括发起者和其他后来“帮助”的线程）会通过 CAS 操作递减 transferIndex 来领取一段（一个 stride，通常有最小大小限制，如 16 个 bin）旧 table 中的 bin 进行迁移。线程从旧表的尾部开始向前领取任务块。

• 一个线程完成其领取的 stride 后，会尝试领取下一个 stride。
• 在 putVal、compute 等修改操作中，如果线程(其他线程)发现 table 正在扩容（通过检查 nextTable != null），它可能会先调用 helpTransfer() 方法加入到扩容的队伍中，帮助迁移一部分数据，然后再在新表中执行其原始操作。这确保了扩容过程不会因为单个线程缓慢而被严重拖延，并能更快完成。

• 判断完成：当 transferIndex 减到 0 或负数（表示所有 bin 区间都已被分配处理），并且所有参与迁移的线程都完成了它们的工作（通过 sizeCtl 中编码的活跃迁移线程数减为特定值判断）。
• 切换 table：将 ConcurrentHashMap 的 table 引用指向 nextTable。
• 重置状态：nextTable 设置为 null。sizeCtl 被更新为新容量计算出的下一次扩容阈值（一个正数）。

加锁当前 bin：线程会 synchronized(f) 锁住旧表 table[i] 的头节点 f（如果非空）。这是非常细粒度的锁，只锁住当前正在迁移的这一个 bin，不影响其他 bin 的并发访问或迁移。

检查是否已被迁移：如果 table[i] 已经是 ForwardingNode，说明这个 bin 已经被其他线程处理过了，直接跳过。

节点重哈希与分配

在新表中安放节点：将构建好的 "low list/tree" 放到 nextTable[i]，将 "high list/tree" 放到 nextTable[i + oldCap]。

遍历并迁移领取的 bin：对于领取的每一个 bin i

推进与协助

• 将该 bin 中的所有节点（链表或红黑树）遍历一遍。
• 对于每个节点，根据其哈希值和旧的容量 oldCap，决定它在新表 nextTable 中的位置：
  • 如果 (node.hash & oldCap) == 0，则该节点在新表中的索引仍然是 i。这些节点构成 "low list/tree"。
  • 如果 (node.hash & oldCap) != 0，则该节点在新表中的索引是 i + oldCap。这些节点构成 "high list/tree"。
• 这样，原来一个旧 bin 中的节点会被拆分到新表中的最多两个 bin 中。
• 红黑树处理：如果原 bin 是 TreeBin (红黑树)，TreeBin 自己有 split() 方法来高效地将树节点拆分到 low 和 high 两组，并根据拆分后各组的节点数量决定在新表中是保持 TreeBin 还是退化为链表（如果节点数 <= UNTREEIFY_THRESHOLD）。

若容量小于 MAXIMUM_CAPACITY=1<<30，则 newCapacity 为 n<<1

设置 sizeCtl 标记：设置为一个负值(-1)

sizeCtl：

• 0：表示哈希表尚未初始化，将使用默认初始容量。
• 正数：如果哈希表已初始化，它表示下一次触发扩容的阈值（即容量 * 负载因子）。
• -1：表示哈希表正在进行初始化。
• 负数且小于 -1：表示哈希表正在进行扩容。其具体值的计算方式为 -(1 + n)，其中 n 是正在参与扩容的线程数量的 16 位编码（高 16 位是一个扩容戳，低 16 位是 1 + 参与线程数）。

任务分配（领取 stride）

放置 ForwardingNode：在该旧 bin table[i] 的所有节点迁移完毕后，将 table[i] 设置为一个指向 nextTable 的 ForwardingNode。

更新 sizeCtl 为负值

扩容初始化(由一个线程发起)

检测到需要扩容：某个桶节点数过多或者总元素达到某个阈值(当前容量乘以负载因子)时

分配 nextTable(大小为 n<<1)

线程会根据自身的 ThreadLocalRandom.getProbe() 值（一个与线程相关的探针值，用于减少不同线程选择同一个 cell 的概率）来映射到 counterCells 数组中的一个特定索引。

扩容过程主要由 tryPresize()（尝试预先调整大小，可能是初始化或扩大）和 transfer()（实际的数据迁移）方法驱动。

核心步骤

核心步骤

并发数据迁移(Transfer)

迁移完成

addCount(long x, int check) 方法

• 如果查找的 bin 是正常的 Node 或 TreeBin，则直接查找。
• 如果查找到的 bin 是一个 ForwardingNode，则会透明地跳转到 nextTable 中对应的位置继续查找。

这个过程对调用者是无感的，并且通常是无锁的。

内部有 volatile long value ，当 CAS 竞争激烈时，线程会被导向一个随机选择的（或基于线程探针的）CounterCell 上，并通过 CAS 更新该 CounterCell 的 value

若 CAS 失败则使用 CounterCell[] counterCells

当进行 put 或 remove 操作时，会尝试通过 CAS (Compare-And-Swap) 操作直接原子地更新 baseCount

支持并发扩容

提供线程安全的、高并发的哈希表实现

ConcurrentHashMap的底层实现

ConcurrentHashMap 的底层原理

JDK8

如何实现线程安全的

因为原本集中在 baseCount 上的写竞争被分散到了多个 CounterCell 上。不同的线程很可能在更新不同的 CounterCell，从而大大降低了单个计数点上的冲突概率。

因为当竞争非常激烈的时候，仅仅靠 baseCount 进行 CAS 操作是不行的(会造成严重的性能问题)，为了避免死磕这个变量，采用分散计数，初始化一个 CounterCell 对象数组(内部含有 value 的字段)，也通过 CAS 来进行更新 value 的操作

size 方法

counterCells 数组是懒初始化的，并且其大小会根据需要动态调整。

树化检查

size()返回的是 int，当存储元素很大时无法返回精确值(返回保留的低 32 位值)。其目的是为了兼容旧的 Map 接口中 size() 返回 int 的约定。

volatile long baseCount

向链表添加新节点后，如果链表长度达到 TREEIFY_THRESHOLD(8)，并且哈希表容量足够大，则会调用 treeifyBin 方法将该链表转换为红黑树。

会