Java 7 版本的 ConcurrentHashMap
我们首先来看一下 Java 7 版本中的 ConcurrentHashMap 的结构示意图：
从图中我们可以看出，在 ConcurrentHashMap 内部进行了 Segment 分段，Segment 继承了 ReentrantLock，可以理解为一把锁，各个 Segment 之间都是相互独立上锁的，互不影响。相比于之前的 Hashtable 每次操作都需要把整个对象锁住而言，大大提高了并发效率。因为它的锁与锁之间是独立的，而不是整个对象只有一把锁，能够显著提高在多线程环境下的并发性能。
ConcurrentHashMap采用了分段锁（Segment-based locking）的策略来实现线程安全
数据结构概述
ConcurrentHashMap在Java 7中的内部结构主要由以下几部分组成：
- Segment数组：这是ConcurrentHashMap的顶层容器，可以将其视为一个ReentrantLock数组，每个Segment对象都持有自己的锁，这样在进行读写操作时，只需锁定相关的Segment，而不是整个Map。默认有 0~15 共 16 个 Segment，所以最多可以同时支持 16 个线程并发操作（操作分别分布在不同的 Segment 上）。16 这个默认值可以在初始化的时候设置为其他值，但是一旦确认初始化以后，是不可以扩容的
- HashEntry数组：每个Segment内部维护了一个HashEntry数组，类似于HashMap中的Entry数组。HashEntry数组负责存储具体的键值对条目，每个条目包括键、值和一个指向下一个条目的指针，形成了一个链表结构。
- HashEntry链表：在HashEntry数组中，具有相同哈希码的元素会形成链表结构，这意味着如果多个键的哈希值相同，它们会被链接在一起形成链表，按照插入顺序排列。
Java 8 版本的 ConcurrentHashMap
在 Java 8 中，几乎完全重写了 ConcurrentHashMap，代码量从原来 Java 7 中的 1000 多行，变成了现在的 6000 多行，所以也大大提高了源码的阅读难度。而为了方便我们理解，我们还是先从整体的结构示意图出发，看一看总体的设计思路，然后再去深入细节。
内部结构
Java 8的ConcurrentHashMap采用了数组+链表/红黑树的结构，与Java 7相比，取消了Segment的分段锁机制，转而使用更细粒度的锁——Synchronized和CAS（Compare and Swap）操作，以及在某些情况下使用红黑树来替代链表，以提升性能。
图中的节点有三种类型。
- 第一种是最简单的，空着的位置代表当前还没有元素来填充。
- 第二种就是和 HashMap 非常类似的拉链法结构，在每一个槽中会首先填入第一个节点，但是后续如果计算出相同的 Hash 值，就用链表的形式往后进行延伸。
- 第三种结构就是红黑树结构
当第二种情况的链表长度大于某一个阈值（默认为 8），且同时满足数组长度大于等于64，ConcurrentHashMap 便会把这个链表从链表的形式转化为红黑树的形式，目的是进一步提高它的查找性能。所以，Java 8 的一个重要变化就是引入了红黑树的设计。
红黑树是每个节点都带有颜色属性的二叉查找树，颜色为红色或黑色，红黑树的本质是对二叉查找树 BST 的一种平衡策略，我们可以理解为是一种平衡二叉查找树，查找效率高，会自动平衡，防止极端不平衡从而影响查找效率的情况发生。
由于自平衡的特点，即左右子树高度几乎一致，所以其查找性能近似于二分查找，时间复杂度是 O(log(n)) 级别；反观链表，它的时间复杂度就不一样了，如果发生了最坏的情况，可能需要遍历整个链表才能找到目标元素，时间复杂度为 O(n)，远远大于红黑树的 O(log(n))，尤其是在节点越来越多的情况下，O(log(n)) 体现出的优势会更加明显。
红黑树的一些其他特点：
- 每个节点要么是红色，要么是黑色，但根节点永远是黑色的。
- 红色节点不能连续，也就是说，红色节点的子和父都不能是红色的。
- 从任一节点到其每个叶子节点的路径都包含相同数量的黑色节点。
正是由于这些规则和要求的限制，红黑树保证了较高的查找效率，所以现在就可以理解为什么 Java 8 的 ConcurrentHashMap 要引入红黑树了。好处就是避免在极端的情况下冲突链表变得很长，在查询的时候，效率会非常慢。而红黑树具有自平衡的特点，所以，即便是极端情况下，也可以保证查询效率在 O(log(n))。
ConcurrentHashMap原理概览
在ConcurrentHashMap中通过一个Node<K,V>[]数组来保存添加到map中的键值对，而在同一个数组位置是通过链表和红黑树的形式来保存的。但是这个数组只有在第一次添加元素的时候才会初始化，否则只是初始化一个ConcurrentHashMap对象的话，只是设定了一个sizeCtl变量，这个变量用来判断对象的一些状态和是否需要扩容，后面会详细解释。
- 第一次添加元素的时候，默认初期长度为16，当往map中继续添加元素的时候，通过hash值跟数组长度取与来决定放在数组的哪个位置，如果出现放在同一个位置的时候，优先以链表的形式存放，在同一个位置的个数又达到了8个以上，如果数组的长度还小于64的时候，则会扩容数组。如果数组的长度大于等于64了的话，在会将该节点的链表转换成树。
- 通过扩容数组的方式来把这些节点给分散开。然后将这些元素复制到扩容后的新的数组中，同一个链表中的元素通过hash值的数组长度位来区分，是还是放在原来的位置还是放到扩容的长度的相同位置去 。在扩容完成之后，如果某个节点的是树，同时现在该节点的个数又小于等于6个了，则会将该树转为链表。
- 取元素的时候，相对来说比较简单，通过计算hash来确定该元素在数组的哪个位置，然后在通过遍历链表或树来判断key和key的hash，取出value值。
往ConcurrentHashMap中添加元素的时候，里面的数据以数组的形式存放的样子大概是这样的：
这个时候因为数组的长度才为16，则不会转化为树，而是会进行扩容。
扩容后数组大概是这样的：
需要注意的是，扩容之后的长度不是32，扩容后的长度在后面细说。
如果数组扩张后长度达到64(不小于64)了，且继续在某个节点的后面添加元素达到8个以上的时候，则会出现转化为红黑树的情况。
转化之后大概是这样：
分析 Java 7 版本的 ConcurrentHashMap 的重要源码
ConcurrentHashMap定义
锁粗化是锁优化的一种重要措施，而锁粗化又包含"lock-splitting"（锁定拆分）和"lock-stripping"（锁条带化）。读写锁分离是一种典型的锁定拆分方式，JUC中的ReentrantReadWriteLock就是一种读写分离锁，锁定条带化是指将一把“大锁”拆分成若干个“小锁”来降低锁的竞争。ConcurrentHashMap就是通过锁条带化来做锁的优化。我们都知道ConcurrentHashMap是分段的，它的表是一个Segment数组
final Segment<K,V>[] segments;
public class ConcurrentHashMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V>, Serializable {
final Segment<K, V>[] segments;
/**
* segment分段的定义
*/
static final class Segment<K, V> extends ReentrantLock implements Serializable {
transient volatile HashEntry<K, V>[] table;
}
/**
* 存放的元素节点
*/
static final class HashEntry<K, V> {
}
}
而每个Segment都是继承了一个ReentrantLock，所以ConcurrentHashMap的每个Segment都是一把锁，不同的Segment之间的读写不构成竞争，大大降低了锁的竞争。既然每个Segment都是一把锁，那么这个segment数组的长度是多少呢？也就是说整个表我们需要多少把锁呢？
Segment内部类
ConcurrentHashMap内部有一个segments属性，是Segment类型的数组，Segment类和HashMap很相似（Java7的HashMap)，维持一个数组，数组的每个元素是HashEntry类型（可以理解为HashMap的节点），当发生hash冲突后，则使用拉链法（头插法）来解决冲突。
而Segment数组的定义如下，省略了方法：
static final class Segment<K, V> extends ReentrantLock implements Serializable {
static final int MAX_SCAN_RETRIES = Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
// segment的负载因子（segments数组中的所有segment负载因子都相同）
final float loadFactor;
// segment中保存元素的数组
transient volatile HashEntry<K, V>[] table;
// 该segment中的元素个数
transient int count;
// modify count，该segment被修改的次数
transient int modCount;
// segment的扩容阈值
transient int threshold;
}
注意每个Segment都有负载因子、以及扩容阈值，但是后面可以看到，其实segments数组中的每一个segment，负载因子和扩容阈值都相同，因为创建的时候，都是使用0号segment的负载因子和扩容阈值。
HashEntry内部类
Segment类中有一个table数组，table数组的每个元素都是HashEntry类型，和HashMap的Entry类似，源码如下：（省略了方法）
/**
* map中每个元素的类型
*/
static final class HashEntry<K, V> {
final int hash;
final K key;
volatile V value;
volatile HashEntry<K, V> next;
}
ConcurrentHashMap的一些常量
ConcurrentHashMap中有很多常量
// 默认初始容量
static final int DEFAULT_INITIAL_CAPACITY = 16;
// 默认的负载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 默认的并发级别(同时支持多少线程并发修改)
// 因为JDK7中ConcurrentHashMap中是用分段锁实现并发，不同分段的数据可以进行并发操作，同一个段的数据不能同时修改
static final int DEFAULT_CONCURRENCY_LEVEL = 16;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 每一个分段的数组容量初始值
static final int MIN_SEGMENT_TABLE_CAPACITY = 2;
// 最多能有多少个segment
static final int MAX_SEGMENTS = 1 << 16; // slightly conservative
// 尝试对整个map进行操作（比如说统计map的元素数量），可能需要锁定全部segment；
// 这个常量表示锁定所有segment前，尝试的次数
static final int RETRIES_BEFORE_LOCK = 2;
构造函数
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
// MAX_SEGMENTS是指整个表最多能分成多少个segment，也即是多少把锁
if (concurrencyLevel > MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
// Find power-of-two sizes best matching arguments
int sshift = 0;
int ssize = 1;
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
// 这部分代码是为了找到最接近concurrencyLevel的2的幂次方，
// ssize最终将等于这个值，sshift记录了左移的次数，即2的指数。
this.segmentShift = 32 - sshift;
this.segmentMask = ssize - 1;
// 根据initialCapacity和并发级别调整实际容量
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
++c;
int cap = MIN_SEGMENT_TABLE_CAPACITY;
while (cap < c)
cap <<= 1;
// 创建 Segment 数组，
// 并创建数组的第一个元素 segment[0]
Segment<K,V> s0 =
new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
(HashEntry<K,V>[])new HashEntry[cap]);
// 初始化segments数组，并将s0设置为第一个Segment
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
// 往数组写入 segment[0]
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
}
我们当使用 new ConcurrentHashMap() 无参构造函数进行初始化的，那么初始化完成后:
- Segment 数组长度为 16，不可以扩容
- Segment[i] 的默认大小为 2，负载因子是 0.75，得出初始阈值为 1.5，也就是以后插入第一个元素不会触发扩容，插入第二个会进行第一次扩容
- 这里初始化了 segment[0]，其他位置还是 null，至于为什么要初始化 segment[0]，后面的代码会介绍
- 当前 segmentShift 的值为 32 - 4 = 28，segmentMask 为 16 - 1 = 15，把它们简单翻译为移位数和掩码。
put操作
/**
* 将指定的键值对插入到此ConcurrentHashMap中。
*
* @param key 要插入的键。
* @param value 要插入的值，如果为null则抛出NullPointerException。
* @return 返回与键关联的旧值，如果不存在则返回null。
*
* 方法首先检查待插入的值是否为null，若为null则抛出异常。接着，使用哈希函数计算键的哈希值，
* 并通过位运算确定该键值对应存储在哪个Segment中。如果发现该Segment尚未初始化，则调用ensureSegment方法创建。
* 最后，在对应的Segment中执行实际的插入操作，并返回插入前与键关联的旧值。
*/
public V put(K key, V value) {
Segment<K,V> s;
// 检查value是否为null，null值不允许插入
if (value == null)
throw new NullPointerException();
// 计算键的哈希值，并定位到Segment的索引
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask; // 通过位运算得到segment的索引位置
// 使用unsafe操作获取Segments数组中的Segment，如未初始化则通过ensureSegment进行初始化
if ((s = (Segment<K,V>)UNSAFE.getObject
(segments, (j << SSHIFT) + SBASE)) == null)
s = ensureSegment(j);
// 插入新值到 segement s 中
return s.put(key, hash, value, false);
}
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 先获取锁（ReentrantLock，内部使用非公平锁）
//尝试快速获取segment的锁，失败则调用scanAndLockForPut进行更复杂的锁获取流程
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
// 获取当前Segment的哈希表
HashEntry<K,V>[] tab = table;
// 计算在哈希表中的索引位置
int index = (tab.length - 1) & hash;
// 获取该索引位置的第一个节点
HashEntry<K,V> first = entryAt(tab, index);
// 遍历链表查找匹配的键
for (HashEntry<K,V> e = first;;) {
// 节点不为空，则判断是否key是否相同
if (e != null) {
K k;
// 如果找到了匹配的键，则处理值（更新或保持不变）
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) { // 是否覆盖原来的value
e.value = value; // 覆盖原来的value
++modCount;
}
break;
}
e = e.next; // 继续遍历链表
}
else {
// 头插法，将put的k-v创建新HashEntry，放到first的前面
// 如果链表到达末尾仍未找到匹配的键，则插入新节点
if (node != null)
node.setNext(first); // 若node已初始化，则设置next指针
else
node = new HashEntry<K,V>(hash, key, value, first); // 如果node为null，则初始化
// segment中table元素数量加1
int c = count + 1;
// 检查是否需要扩容
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node); // 如果超过阈值，则扩容
else
setEntryAt(tab, index, node); // 通过UNSAFE设置table数组的index位置的元素为node
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
// 释放锁
unlock();
}
return oldValue;
}
初始化槽: ensureSegment
ConcurrentHashMap 初始化的时候会初始化第一个槽 segment[0]，对于其他槽来说，在插入第一个值的时候进行初始化。
这里需要考虑并发，因为很可能会有多个线程同时进来初始化同一个槽 segment[k]，不过只要有一个成功了就可以。
private Segment<K,V> ensureSegment(int k) {
final Segment<K,V>[] ss = this.segments;
long u = (k << SSHIFT) + SBASE; // raw offset
Segment<K,V> seg;
// 判断是否需要扩容或者创建segment，如果获取到segment不为null，则返回segment
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
// 使用当前 segment[0] 处的数组长度和负载因子来初始化 segment[k]
// 为什么要用“当前”，因为 segment[0] 可能早就扩容过了
Segment<K,V> proto = ss[0]; // “原型设计模式”，使用segments数组的0号位置segment
// 0号segment的table长度
int cap = proto.table.length;
// 0号segment的负载因子
float lf = proto.loadFactor;
// 0号segment的扩容阈值
int threshold = (int)(cap * lf);
// 创建一个HashEntry的数组，数组容量和0号segment相同
HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
// 再次检测，指定的segment是不是为null，如果为null才进行下一步操作
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))== null) {
// 创建segment
Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
//使用CAS将新创建的segment填入指定的位置
// 使用 while 循环，内部用 CAS，当前线程成功设值或其他线程成功设值后，退出
while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
break;
}
}
}
// 返回新增的segment
return seg;
}
总的来说，ensureSegment(int k) 比较简单，对于并发操作使用 CAS 进行控制。
获取写入锁: scanAndLockForPut
前面我们看到，在往某个 segment 中 put 的时候，首先会调用 node = tryLock() ? null : scanAndLockForPut(key, hash, value)，也就是说先进行一次 tryLock() 快速获取该 segment 的独占锁，如果失败，那么进入到 scanAndLockForPut 这个方法来获取锁。
/**
* 在尝试插入键值对之前，扫描对应桶的链表并尝试获取Segment的锁。
* 当直接尝试获取锁失败时，此方法会进行自旋并重新检查链表，以减少线程阻塞的几率。
*
* @param key 要插入的键。
* @param hash 键的哈希值。
* @param value 要插入的值。
* @return 为插入准备的HashEntry节点，如果在扫描过程中已创建则返回，否则返回null。
*
* 方法首先尝试获取Segment锁，如果直接获取失败，则进入循环进行以下操作：
* 1. 如果首次迭代或链表扫描未开始，检查桶中是否有匹配的键或初始化新节点。
* 2. 如果超过最大扫描重试次数（MAX_SCAN_RETRIES），则直接调用lock()阻塞等待锁。
* 3. 在每次迭代中，如果链表头发生变化（可能由于其他线程的操作），则重新扫描链表。
* 4. 自旋过程中，采用偶数次重试时检查链表头，以平衡自旋等待与及时响应链表变化的需求。
*/
private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
// 首先获取哈希值对应的桶中的第一个元素
HashEntry<K,V> first = entryForHash(this, hash);
HashEntry<K,V> e = first; // 初始化遍历指针
HashEntry<K,V> node = null; // 用于存储新建的节点，初始为null
// 初始化重试计数器为负数，表示还在寻找节点阶段
int retries = -1;
while (!tryLock()) { // 尝试获取锁，失败则进入循环
HashEntry<K,V> f; // 重新检查链表头
// 如果还在寻找节点（retries < 0），则进行如下操作
if (retries < 0) {
if (e == null) { // 如果到达链表尾部
if (node == null)
// 预先创建新节点
node = new HashEntry<K,V>(hash, key, value, null);
retries = 0; // 开始重试计数，准备获取锁
} else if (key.equals(e.key)) { // 找到匹配的键
retries = 0; // 准备获取锁
} else {
e = e.next; // 继续遍历链表
}
// 超过最大重试次数
} else if (++retries > MAX_SCAN_RETRIES) { // 超过最大重试次数
lock(); // 直接阻塞等待锁
break;
} else if ((retries & 1) == 0 && // 偶数次重试时检查链表头
(f = entryForHash(this, hash)) != first) {
e = first = f; // 重置遍历指针，因为链表头已变
retries = -1; // 重置为寻找节点状态
}
}
return node; // 返回已创建的节点，供后续操作使用
}
这个方法有两个出口，一个是 tryLock() 成功了，循环终止，另一个就是重试次数超过了 MAX_SCAN_RETRIES，进到 lock() 方法，此方法会阻塞等待，直到成功拿到独占锁。
这个方法就是看似复杂，但是其实就是做了一件事，那就是获取该 segment 的独占锁，如果需要的话顺便实例化了一下 node。
扩容: rehash
segment 数组不能扩容，扩容是 segment 数组某个位置内部的 HashEntry数组，将 HashEntry数组扩容为原来的 2 倍。
put 的时候，如果判断该值的插入会导致该 segment 的元素个数超过阈值，那么先进行扩容，再插值。该方法不需要考虑并发，因为到这里的时候，是持有该 segment 的独占锁的。
// 方法参数上的 node 是这次扩容后，需要添加到新的数组中的数据。
private void rehash(HashEntry<K,V> node) {
HashEntry<K,V>[] oldTable = table;
int oldCapacity = oldTable.length;
// 新容量为旧容量的2倍
int newCapacity = oldCapacity << 1;
// 设置新的扩容阈值
threshold = (int)(newCapacity * loadFactor);
// 创建新数组
HashEntry<K,V>[] newTable = (HashEntry<K,V>[]) new HashEntry[newCapacity];
// 新的掩码，如从 16 扩容到 32，那么 sizeMask 为 31，对应二进制 ‘000...00011111’
int sizeMask = newCapacity - 1;
// 遍历原数组，将原数组位置 i 处的链表拆分到 新数组位置 i 和 i+oldCap 两个位置
for (int i = 0; i < oldCapacity ; i++) {
// e 是链表的第一个元素
HashEntry<K,V> e = oldTable[i];
// 获取第i个位置的HashEntry节点，如果该节点为null，则该位置为空，不作处理
if (e != null) {
HashEntry<K,V> next = e.next;
// 计算应该放置在新数组中的位置，
// 假设原数组长度为 16，e 在 oldTable[3] 处，那么 idx 只可能是 3 或者是 3 + 16 = 19
int idx = e.hash & sizeMask;
if (next == null) // 该位置处只有一个元素，那比较好办
newTable[idx] = e;
else { // Reuse consecutive sequence at same slot
// e 是链表表头
HashEntry<K,V> lastRun = e;
// idx 是当前链表的头节点 e 的新位置
int lastIdx = idx;
// 下面这个 for 循环会找到一个 lastRun 节点，这个节点之后的所有元素是将要放到一起的
for (HashEntry<K,V> last = next;
last != null;
last = last.next) {
int k = last.hash & sizeMask;
if (k != lastIdx) {
lastIdx = k;
lastRun = last;
}
}
// 将 lastRun 及其之后的所有节点组成的这个链表放到 lastIdx 这个位置
newTable[lastIdx] = lastRun;
// 从头结点开始，开始将节点拷贝到新数组中
// 下面的操作是处理 lastRun 之前的节点，
// 这些节点可能分配在另一个链表中，也可能分配到上面的那个链表中
for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
V v = p.value;
int h = p.hash;
int k = h & sizeMask;
HashEntry<K,V> n = newTable[k];
newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
}
}
}
}
// 将新来的 node 放到新数组中刚刚的 两个链表之一 的 头部
int nodeIndex = node.hash & sizeMask; // add the new node
node.setNext(newTable[nodeIndex]);
newTable[nodeIndex] = node;
table = newTable;
}
get操作
get操作比较简单，不需要加锁。可见性由volatile来保证：HashEntry的value是volatile的，Segment中的HashEntry[] table数组也是volatile。这保证了其他线程对哈希表的修改能够及时地被读线程发现。
- 计算 hash 值，找到 segment 数组中的具体位置。
- segment中也是一个数组，根据 hash 找到数组中具体的位置
- 到这里是链表了，顺着链表进行查找即可
public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
int h = hash(key);
// 计算键应位于segments数组的哪个segment中
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
// 使用Unsafe获取segments数组中对应位置的Segment，且此操作是volatile读，保证了可见性
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE); // 计算key应该落在table的哪个位置
e != null; e = e.next) {
K k;
// 判断key和hash是否匹配，匹配则证明找到要查找的数据，将数据返回
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
return e.value;
}
}
return null; // key不在当前哈希表中，返回null
}
size()
ConcurrentHashMap的size()，需要统计每一个segment中的元素数量（也就是count值），因为不同的segment允许并发修改，统计过程中可能会出现修改操作，导致统计不准确。
而ConcurrentHashMap是这样解决的，先尝试不加锁进行统计两次，这两次统计，不止会统计每个segment的元素数量，还会统计每个segment的modCount(修改次数），进行汇总；如果两次统计的modCount总量相同，也就说明两次统计期间没有修改操作，证明统计的元素总量正确；如果两次modCount总量不相同，表示有修改操作，则进行重试，如果重试后，发现还是不准确（modCount不匹配），那么就尝试为所有的segment加锁，再进行统计。
/**
* 获取ConcurrentHashMap中的元素个数，如果元素个数超过Integer.MAX_VALUE，则返回Integer.MAX_VALUE
*/
public int size() {
final Segment<K, V>[] segments = this.segments;
int size; // 返回元素数量（统计结果->元素的总量）
boolean overflow; // 标志是否溢出（是否超过Integer.MAX_VALUE）
long sum; // 所有segment的modCount总量次数（整个map的修改次数）
long last = 0L; // previous sum，上一轮统计的modCount总量
int retries = -1; // 记录重试的次数
try {
// 此处for循环主要用于控制重试
for (; ; ) {
// 重试的次数如果达到RETRIES_BEFORE_LOCK，则强制获取所有segment的锁
if (retries++ == RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j) {
ensureSegment(j).lock();
// 强制获取segment的table第i个位置，并加锁
}
}
sum = 0L;
size = 0;
overflow = false;
// 开始对segments中的每一个segment中进行统计
for (int j = 0; j < segments.length; ++j) {
// 获取第j个segment
Segment<K, V> seg = segmentAt(segments, j);
// 如果segment不为空，则进行统计
if (seg != null) {
sum += seg.modCount;
int c = seg.count;
// size累加
if (c < 0 || (size += c) < 0)
overflow = true;
}
}
// 如果本次统计的modCount总量和上次一样，则表示在这两次统计之间没有进行过修改，则不再重试
if (sum == last) {
break;
}
// 记录本次统计的modCount总量
last = sum;
}
} finally {
// 判断是否加了锁（如果retries大于RETRIES_BEFORE_LOCK），则证明加了锁，于是进行释放锁
if (retries > RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
segmentAt(segments, j).unlock();
}
}
return overflow ? Integer.MAX_VALUE : size;
}
并发问题分析
添加节点的操作 put 和删除节点的操作 remove 都是要加 segment 上的独占锁的，所以它们之间自然不会有问题，我们需要考虑的问题就是 get 的时候在同一个 segment 中发生了 put 或 remove 操作。
- put 操作的线程安全性。
- 初始化槽，使用了 CAS 来初始化 Segment 中的数组。
- 添加节点到链表的操作是插入到表头的，所以，如果这个时候 get 操作在链表遍历的过程已经到了中间，是不会影响的。当然，另一个并发问题就是 get 操作在 put 之后，需要保证刚刚插入表头的节点被读取，这个依赖于 setEntryAt 方法中使用的 UNSAFE.putOrderedObject。UNSAFE.putOrderedObject方法确保了写入的有序性和可见性。这意味着，一旦一个线程完成了put操作，所有后续的get操作都能看到这个更新，即使这些get操作是在不同的线程中执行的。
- 扩容：当哈希表需要扩容时，会创建一个新的更大的数组，并将原有数组中的元素迁移到新的数组中。这个过程可能会与get操作并发发生。table属性使用了volatile关键字，这确保了对table的写操作对所有线程都是立即可见的。这意味着，如果一个线程完成了扩容操作并更新了table，那么所有其他线程都会看到这个更新后的table，无论它们是在get还是put操作中。所以，如果 get 操作此时也在进行，那么也没关系，如果 get 先行，那么就是在旧的 table 上做查询操作；而 put 先行，那么 put 操作的可见性保证就是 table 使用了 volatile 关键字。get在新的table上做查询操作。
分析 Java 8 版本的 ConcurrentHashMap 的重要源码
虽然 JDK1.7 中的 ConcurrentHashMap 解决了 HashMap 并发的安全性，但是当冲突的链表过长时，在查询遍历的时候依然很慢！
在 JDK1.8 中，HashMap 引入了红黑二叉树设计，当冲突的链表长度大于8时，会将链表转化成红黑二叉树结构，红黑二叉树又被称为平衡二叉树，在查询效率方面，又大大的提高了不少。
JDK1.8 中的ConcurrentHashMap 相比 JDK1.7 中的 ConcurrentHashMap， 它抛弃了原有的 Segment 分段锁实现，采用了 CAS + synchronized 来保证并发的安全性。
JDK1.8 中的 ConcurrentHashMap 对节点Node类中的共享变量，和 JDK1.7 一样，使用volatile关键字，保证多线程操作时，变量的可见性！
重要的属性
private static final int MAXIMUM_CAPACITY = 1 << 30;
private static final int DEFAULT_CAPACITY = 16;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;
static final int MOVED = -1; // 表示正在转移
static final int TREEBIN = -2; // 表示已经转换成树
static final int RESERVED = -3; // hash for transient reservations
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
transient volatile Node<K,V>[] table;//默认没初始化的数组，用来保存元素
private transient volatile Node<K,V>[] nextTable;//转移的时候用的数组
/**
* 用来控制表初始化和扩容的，默认值为0，当在初始化的时候指定了大小，这会将这个大小保存在sizeCtl中，大小为数组的0.75
* 当为负的时候，说明表正在初始化或扩张，
* -1表示初始化
* -(1+n) n:表示活动的扩张线程
*/
private transient volatile int sizeCtl;
Node 节点
static class Node<K,V> implements Map.Entry<K,V> {
final int 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;
}
......
}
可以看出，每个 Node 里面是 key-value 的形式，并且把 value 用 volatile 修饰，以便保证可见性，同时内部还有一个指向下一个节点的 next 指针，方便产生链表结构。
构造方法
public ConcurrentHashMap() {
}
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;
}
通过提供初始容量，计算了 sizeCtl，sizeCtl = 【 (1.5 * initialCapacity + 1)，然后向上取最近的 2 的 n 次方】。如 initialCapacity 为 10，那么得到 sizeCtl 为 16，如果 initialCapacity 为 11，得到 sizeCtl 为 32。
put 方法
可以看到，在任何一个构造方法中，都没有对存储Map元素Node的table变量进行初始化。而是在第一次put操作的时候在进行初始化。
/*
* 当添加一对键值对的时候，首先会去判断保存这些键值对的数组是不是初始化了，
* 如果没有的话就初始化数组，然后通过计算hash值来确定放在数组的哪个位置
*
* 如果这个位置为空则直接添加，如果不为空的话，则取出这个节点来
* 如果取出来的节点的hash值是MOVED(-1)的话，则表示当前正在对这个数组进行扩容，复制到新的数组，则当前线程也去帮助复制
*
* 最后一种情况就是，如果这个节点，不为空，也不在扩容，则通过synchronized来加锁，进行添加操作
* 然后判断当前取出的节点位置存放的是链表还是树
* 如果是链表的话，则遍历整个链表，直到取出来的节点的key来个要放的key进行比较，如果key相等，并且key的hash值也相等的话，
* 则说明是同一个key，则覆盖掉value，否则的话则添加到链表的末尾
* 如果是树的话，则调用putTreeVal方法把这个元素添加到树中去
*
* 最后在添加完成之后，会判断在该节点处共有多少个节点（注意是添加前的个数），如果达到8个以上了的话，
*
* 则调用treeifyBin方法来尝试将处的链表转为树，或者扩容数组
*/
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) {
throw new NullPointerException();
}
//计算 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) {
tab = initTable();
}
// 找该 hash 值对应的数组下标，得到第一个节点 f
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 如果数组该位置为空，
// 用一次 CAS 操作将这个新值放入其中即可，这个 put 操作差不多就结束了，可以拉到最后面了
// 如果 CAS 失败，那就是有并发操作，进到下一个循环就好了
if (casTabAt(tab, i, null,
new Node<K, V>(hash, key, value, null) //创建一个Node添加到数组中区，null表示的是下一个节点为空
)) {
break;
}
}
/*
* 如果检测到某个节点的hash值是MOVED，则表示正在进行数组扩张的数据复制阶段，
* 则当前线程也会参与去复制，通过允许多线程复制的功能，一次来减少数组的复制所带来的性能损失
*/
else if ((fh = f.hash) == MOVED) {
// 帮助数据迁移
tab = helpTransfer(tab, f);
}
//f 是该位置的头节点，而且不为空
else {
V oldVal = null;
/*
* 如果在这个位置有元素的话，就采用synchronized的方式加锁，
*
* 如果是链表的话(hash大于0)，就对这个链表的所有元素进行遍历，
* - 如果找到了key和key的hash值都一样的节点，则把它的值替换掉
* - 如果没找到的话，则添加在链表的最后面
*
* 如果是树的话，则调用putTreeVal方法添加到树中去
* - 在添加完之后，会对该节点上关联的的数目进行判断，
* - 如果在8个以上的话，则会调用treeifyBin方法，来尝试转化为树，或者是扩容
*/
synchronized (f) {
//再次取出要存储的位置的元素，跟前面取出来的比较
if (tabAt(tab, i) == f) {
//如果是链表的形式
//取出来的元素的hash值大于0，当转换为树之后，hash值为-2
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;
//当使用putIfAbsent的时候，只有在这个key没有设置值得时候才设置
if (!onlyIfAbsent) {
e.val = value;
}
break;
}
Node<K, V> pred = e;
//到了链表的尾部也没有发现该 key，说明之前不存在，就把新值添加到链表的最后
if ((e = e.next) == null) {
pred.next = new Node<K, V>(hash, key,
value, null);
break;
}
}
}
//如果是红黑树的形式
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) {
//检查是否满足条件并把链表转换为红黑树的形式，默认的 TREEIFY_THRESHOLD 阈值是 8
if (binCount >= TREEIFY_THRESHOLD) {
treeifyBin(tab, i);
}
//putVal 的返回是添加前的旧值，所以返回 oldVal
if (oldVal != null) {
return oldVal;
}
break;
}
}
}
addCount(1L, binCount);
return null;
}
通过以上的源码分析，我们对于 putVal 方法有了详细的认识，可以看出，方法中会逐步根据当前槽点是未初始化、空、扩容、链表、红黑树等不同情况做出不同的处理。
初始化数组: initTable
这个比较简单，主要就是初始化一个合适大小的数组，然后会设置 sizeCtl。
初始化方法中的并发问题是通过对 sizeCtl 进行一个 CAS 操作来控制的。
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
// 当table为空或长度为0时，尝试初始化table
while ((tab = table) == null || tab.length == 0) {
// 如果sizeCtl小于0，说明有其他线程正在或已经初始化table
if ((sc = sizeCtl) < 0)
// 如果当前线程失去了初始化的竞争，那么让出CPU，等待再次尝试
// 这里使用Thread.yield()而不是更重的锁，是为了提高并发性能
Thread.yield(); // lost initialization race; just spin
// 使用CAS操作将sizeCtl标记为-1，表示当前线程正在初始化table
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
//再次检查table是否已经被其他线程初始化
if ((tab = table) == null || tab.length == 0) {
// 根据sc的值初始化table的大小
// 如果sc大于0，则使用sc作为大小；否则使用默认大小DEFAULT_CAPACITY=16
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
// 创建一个新的节点数组
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
// 将新数组赋值给table，并更新tab引用
// table 是 volatile 修饰的
table = tab = nt;
// 计算新的sizeCtl值，即初始化后的容量的3/4
// 这个值用于控制何时进行哈希表的扩容
// 如果 n 为 16 的话，那么这里 sc = 12
// 其实就是 0.75 * n
sc = n - (n >>> 2);
}
} finally {
// 在finally块中，确保更新sizeCtl的值
// 这是为了防止在初始化过程中发生异常而导致sizeCtl没有被正确设置
// 设置 sizeCtl 为 sc，我们就当是 12 吧
sizeCtl = sc;
}
break;
}
}
return tab;
}
- 使用CAS锁控制只有一个线程初始化tab数组；
- sizeCtl在初始化后存储的是扩容门槛；
- 扩容门槛写死的是tab数组大小的0.75倍，tab数组大小即map的容量，也就是最多存储多少个元素。
helpTransfer 协助扩容
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
// 如果tab数组不为空，并且当前tab第一个元素为ForwardingNode类型，并且nextTab不为空
// 说明当前tab已经迁移完毕了，才去帮忙迁移其它tab的元素
// 扩容时会把旧tab的第一个元素置为ForwardingNode，并让其nextTab指向新tab数组
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
int rs = resizeStamp(tab.length);
// sizeCtl<0，说明正在扩容
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
// 扩容线程数加1
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
// 当前线程帮忙迁移元素
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}
操作步骤如下：
- 第1步，对 table、node 节点、node 节点的 nextTable，进行数据校验；
- 第2步，根据数组的length得到一个标识符号；
- 第3步，进一步校验 nextTab、tab、sizeCtl 值，如果 nextTab 没有被并发修改并且 tab 也没有被并发修改，同时 sizeCtl < 0，说明还在扩容；
- 第4步，对 sizeCtl 参数值进行分析判断，如果不满足任何一个判断，将sizeCtl + 1, 增加了一个线程帮助其扩容。
addCount 扩容判断
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
// 先尝试把数量加到baseCount上，如果失败再加到分段的CounterCell上
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
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;
}
if (check <= 1)
return;
// 计算元素个数
s = sumCount();
}
//检查是否需要扩容，默认check=1,需要检查
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
// 如果元素个数达到了扩容门槛，则进行扩容
// 注意，正常情况下sizeCtl存储的是扩容门槛，即容量的0.75倍
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
// rs是扩容时的一个标识
int rs = resizeStamp(n);
if (sc < 0) {
// sc<0说明正在扩容中
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
// 扩容已经完成了，退出循环
break;
// 扩容未完成，则当前线程加入迁移元素中
// 并把扩容线程数加1
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);
// 重新计算元素个数
s = sumCount();
}
}
}
操作步骤如下：
- 第1步，利用CAS将方法更新baseCount的值
- 第2步，检查是否需要扩容，默认check = 1，需要检查；
- 第3步，如果满足扩容条件，判断当前是否正在扩容，如果是正在扩容就一起扩容；
- 第4步，如果不在扩容，将sizeCtl更新为负数，并进行扩容处理。
扩容机制
在put方法的详解中，我们可以看到，在同一个节点的个数超过8个的时候，会调用treeifyBin方法来看看是扩容还是转化为一棵树
同时在每次添加完元素的addCount方法中，也会判断当前数组中的元素是否达到了sizeCtl的量，如果达到了的话，则会进入transfer方法去扩容
/**
* Replaces all linked nodes in bin at given index unless table is
* too small, in which case resizes instead.
* 当数组长度小于64的时候，扩张数组长度一倍，否则的话把链表转为树
*/
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) {
if ((n = tab.length) < MIN_TREEIFY_CAPACITY) //MIN_TREEIFY_CAPACITY 64
tryPresize(n << 1); // 数组扩容
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
synchronized (b) { //使用synchronized同步器，将该节点出的链表转为树
if (tabAt(tab, index) == b) {
TreeNode<K,V> hd = null, tl = null; //hd：树的头(head)
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) //把Node组成的链表，转化为TreeNode的链表，头结点任然放在相同的位置
hd = p; //设置head
else
tl.next = p;
tl = p;
}
setTabAt(tab, index, new TreeBin<K,V>(hd));//把TreeNode的链表放入容器TreeBin中
}
}
}
}
}
可以看到当需要扩容的时候，调用的时候tryPresize方法，看看trePresize的源码
/**
* 扩容表为指可以容纳指定个数的大小（总是2的N次方）
* 假设原来的数组长度为16，则在调用tryPresize的时候，size参数的值为16<<1(32)，此时sizeCtl的值为12
* 计算出来c的值为64,则要扩容到sizeCtl≥为止
* 第一次扩容之后 数组长：32 sizeCtl：24
* 第二次扩容之后 数组长：64 sizeCtl：48
* 第三次扩容之后 数组长：128 sizeCtl：94 --> 这个时候 96>64 才会退出扩容
*/
private final void tryPresize(int size) {
/*
* MAXIMUM_CAPACITY = 1 << 30
* 如果给定的大小大于等于数组容量的一半，则直接使用最大容量，
* 否则使用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;
// printTable(tab); 调试用的
/*
* 如果数组table还没有被初始化，则初始化一个大小为sizeCtrl和刚刚算出来的c中较大的一个大小的数组
* 初始化的时候，设置sizeCtrl为-1，初始化完成之后把sizeCtrl设置为数组长度的3/4
* 为什么要在扩张的地方来初始化数组呢？这是因为如果第一次put的时候不是put单个元素，
* 而是调用putAll方法直接put一个map的话，在putALl方法中没有调用initTable方法去初始化table，
* 而是直接调用了tryPresize方法，所以这里需要做一个是不是需要初始化table的判断
*/
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { //初始化tab的时候，把sizeCtl设为-1
try {
if (table == tab) {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = nt;
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
}
}
/*
* 一直扩容到的c小于等于sizeCtl或者数组长度大于最大长度的时候，则退出
* 所以在一次扩容之后，不是原来长度的两倍，而是2的n次方倍
*/
else if (c <= sc || n >= MAXIMUM_CAPACITY) {
break; //退出扩张
}
// 如果表已初始化且需要resize，但resize操作尚未开始，则尝试开始resize。
else if (tab == table) {
int rs = resizeStamp(n);
/*
* 如果正在扩容Table的话，则帮助扩容
* 否则的话，开始新的扩容
* 在transfer操作，将第一个参数的table中的元素，移动到第二个元素的table中去，
* 虽然此时第二个参数设置的是null，但是，在transfer方法中，当第二个参数为null的时候，
* 会创建一个两倍大小的table
*/
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);
}
}
}
}
在tryPresize方法中，并没有加锁，允许多个线程进入，如果数组正在扩张，则当前线程也去帮助扩容。
数组扩容的主要方法就是transfer方法
/**
* Moves and/or copies the nodes in each bin to new table. See
* above for explanation.
* 把数组中的节点复制到新的数组的相同位置，或者移动到扩张部分的相同位置
* 在这里首先会计算一个步长，表示一个线程处理的数组长度，用来控制对CPU的使用，
* 每个CPU最少处理16个长度的数组元素,也就是说，如果一个数组的长度只有16，那只有一个线程会对其进行扩容的复制移动操作
* 扩容的时候会一直遍历，知道复制完所有节点，每处理一个节点的时候会在链表的头部设置一个fwd节点，这样其他线程就会跳过他，
* 复制后在新数组中的链表不是绝对的反序的
*/
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE) //MIN_TRANSFER_STRIDE 用来控制不要占用太多CPU
stride = MIN_TRANSFER_STRIDE; // subdivide range //MIN_TRANSFER_STRIDE=16
/*
* 如果复制的目标nextTab为null的话，则初始化一个table两倍长的nextTab
* 此时nextTable被设置值了(在初始情况下是为null的)
* 因为如果有一个线程开始了表的扩张的时候，其他线程也会进来帮忙扩张，
* 而只是第一个开始扩张的线程需要初始化下目标数组
*/
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n;
}
int nextn = nextTab.length;
/*
* 创建一个fwd节点，这个是用来控制并发的，当一个节点为空或已经被转移之后，就设置为fwd节点
* 这是一个空的标志节点
*/
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
boolean advance = true; //是否继续向前查找的标志位
boolean finishing = false; // to ensure sweep(清扫) before committing nextTab,在完成之前重新在扫描一遍数组，看看有没完成的没
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing) {
advance = false;
}
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) { //已经完成转移
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1); //设置sizeCtl为扩容后的0.75
return;
}
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) {
return;
}
finishing = advance = true;
i = n; // recheck before commit
}
}
else if ((f = tabAt(tab, i)) == null) //数组中把null的元素设置为ForwardingNode节点(hash值为MOVED[-1])
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
synchronized (f) { //加锁操作
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
if (fh >= 0) { //该节点的hash值大于等于0，说明是一个Node节点
/*
* 因为n的值为数组的长度，且是power(2,x)的，所以，在&操作的结果只可能是0或者n
* 根据这个规则
* 0--> 放在新表的相同位置
* n--> 放在新表的（n+原来位置）
*/
int runBit = fh & n;
Node<K,V> lastRun = f;
/*
* lastRun 表示的是需要复制的最后一个节点
* 每当新节点的hash&n -> b 发生变化的时候，就把runBit设置为这个结果b
* 这样for循环之后，runBit的值就是最后不变的hash&n的值
* 而lastRun的值就是最后一次导致hash&n 发生变化的节点(假设为p节点)
* 为什么要这么做呢？因为p节点后面的节点的hash&n 值跟p节点是一样的，
* 所以在复制到新的table的时候，它肯定还是跟p节点在同一个位置
* 在复制完p节点之后，p节点的next节点还是指向它原来的节点，就不需要进行复制了，自己就被带过去了
* 这也就导致了一个问题就是复制后的链表的顺序并不一定是原来的倒序
*/
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n; //n的值为扩张前的数组的长度
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
/*
* 构造两个链表，顺序大部分和原来是反的
* 分别放到原来的位置和新增加的长度的相同位置(i/n+i)
*/
for (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)
/*
* 假设runBit的值为0，
* 则第一次进入这个设置的时候相当于把旧的序列的最后一次发生hash变化的节点(该节点后面可能还有hash计算后同为0的节点)设置到旧的table的第一个hash计算后为0的节点下一个节点
* 并且把自己返回，然后在下次进来的时候把它自己设置为后面节点的下一个节点
*/
ln = new Node<K,V>(ph, pk, pv, ln);
else
/*
* 假设runBit的值不为0，
* 则第一次进入这个设置的时候相当于把旧的序列的最后一次发生hash变化的节点(该节点后面可能还有hash计算后同不为0的节点)设置到旧的table的第一个hash计算后不为0的节点下一个节点
* 并且把自己返回，然后在下次进来的时候把它自己设置为后面节点的下一个节点
*/
hn = new Node<K,V>(ph, pk, pv, hn);
}
setTabAt(nextTab, i, ln);
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);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
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;
}
}
}
}
}
}
get 方法
get 方法比较简单，我们同样用源码注释的方式来分析一下：
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
//计算 hash 值
int h = spread(key.hashCode());
//如果整个数组是空的，或者当前槽点的数据是空的，说明 key 对应的 value 不存在，直接返回 null
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
//判断头结点是否就是我们需要的节点，如果是则直接返回
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
//如果头结点 hash 值小于 0，说明是红黑树或者正在扩容，就用对应的 find 方法来查找
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
//遍历链表来查找
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
总结一下 get 的过程：
- 计算 Hash 值，并由此值找到对应的槽点；
- 如果数组是空的或者该位置为 null，那么直接返回 null 就可以了；
- 如果该位置处的节点刚好就是我们需要的，直接返回该节点的值；
- 如果该位置节点是红黑树或者正在扩容，就用 find 方法继续查找；
- 否则那就是链表，就进行遍历链表查找。
JDK8中ConcurrentHashMap的同步机制
前面分析了下ConcurrentHashMap的源码，那么，对于一个映射集合来说，ConcurrentHashMap是如果来做到并发安全，又是如何做到高效的并发的呢？
首先是读操作，从源码中可以看出来，在get操作中，根本没有使用同步机制，也没有使用unsafe方法，所以读操作是支持并发操作的。
那么写操作呢？
分析这个之前，先看看什么情况下会引起数组的扩容，扩容是通过transfer方法来进行的。而调用transfer方法的只有trePresize、helpTransfer和addCount三个方法。
这三个方法又是分别在什么情况下进行调用的呢？
- tryPresize是在treeIfybin和putAll方法中调用，treeIfybin主要是在put添加元素完之后，判断该数组节点相关元素是不是已经超过8个的时候，如果超过则会调用这个方法来扩容数组或者把链表转为树。
- helpTransfer是在当一个线程要对table中元素进行操作的时候，如果检测到节点的HASH值为MOVED的时候，就会调用helpTransfer方法，在helpTransfer中再调用transfer方法来帮助完成数组的扩容
- addCount是在当对数组进行操作，使得数组中存储的元素个数发生了变化的时候会调用的方法。
所以引起数组扩容的情况如下：
- 只有在往map中添加元素的时候，在某一个节点的数目已经超过了8个，同时数组的长度又小于64的时候，才会触发数组的扩容。
- 当数组中元素达到了sizeCtl的数量的时候，则会调用transfer方法来进行扩容
那么在扩容的时候，可以不可以对数组进行读写操作呢？
事实上是可以的。当在进行数组扩容的时候，如果当前节点还没有被处理（也就是说还没有设置为fwd节点），那就可以进行设置操作。
如果该节点已经被处理了，则当前线程也会加入到扩容的操作中去。
那么，多个线程又是如何同步处理的呢？
在ConcurrentHashMap中，同步处理主要是通过Synchronized和unsafe两种方式来完成的。
- 在取得sizeCtl、某个位置的Node的时候，使用的都是unsafe的方法，来达到并发安全的目的
- 当需要在某个位置设置节点的时候，则会通过Synchronized的同步机制来锁定该位置的节点。
- 在数组扩容的时候，则通过处理的步长和fwd节点来达到并发安全的目的，通过设置hash值为MOVED
- 当把某个位置的节点复制到扩张后的table的时候，也通过Synchronized的同步机制来保证现程安全
链表转为红黑树的过程
前面在讲解tryifyBin的源码的时候讲到过，如果在当个bin上的元素超过了8个的时候，就会尝试去扩容数组或者是将链表转为红黑树。
TreeBin(TreeNode<K,V> b) {
super(TREEBIN, null, null, null); //创建的TreeBin是一个空节点，hash值为TREEBIN（-2）
this.first = b;
TreeNode<K,V> r = null;
for (TreeNode<K,V> x = b, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (r == null) {
x.parent = null;
x.red = false;
r = x;
}//
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = r;;) {//x代表的是转换为树之前的顺序遍历到链表的位置的节点，r代表的是根节点
int dir, ph;
K pk = p.key;
if ((ph = p.hash) > h) //
dir = -1;
else if (ph < h)
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk); //当key不可以比较，或者相等的时候采取的一种排序措施
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {//在这里判断要放的left/right是否为空，不为空继续用left/right节点来判断
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
r = balanceInsertion(r, x); //每次插入一个元素的时候都调用balanceInsertion来保持红黑树的平衡
break;
}
}
}
}
this.root = r;
assert checkInvariants(root);
}
转化的过程大概如下：
接下来，用链表头部的TreeNode来构造一个TreeBin，在TreeBin容器中，将链表转化为红黑树。
首先是构造一个如下的TreeBin空节点。
构造完TreeBin这个空节点之后，就开始构造红黑树，首先是第一个节点，左右子节点设置为空，作为红黑树的root节点，设置为黑色，父节点为空。
接下来遍历链表的后续节点，每添加一个元素的时候，都会通过判断hash值来决定是放在根节点的左节点还是有节点，如果左/右节点不为空，则继续以左/右节点来重复判断，直到左/右节点为空，则添加到左/右位置。
然后在每次添加完一个节点之后，都会调用balanceInsertion方法来维持这是一个红黑树的属性和平衡性。红黑树所有操作的复杂度都是O(logn)，所以当元素量比较大的时候，效率也很高。
对比Java7 和Java8 的异同和优缺点
数据结构
正如本课时最开始的两个结构示意图所示，Java 7 采用 Segment 分段锁来实现，而 Java 8 中的 ConcurrentHashMap 使用数组 + 链表 + 红黑树，在这一点上它们的差别非常大。
并发度
Java 7 中，每个 Segment 独立加锁，最大并发个数就是 Segment 的个数，默认是 16。
但是到了 Java 8 中，锁粒度更细，理想情况下 table 数组元素的个数（也就是数组长度）就是其支持并发的最大个数，并发度比之前有提高。
保证并发安全的原理
Java 7 采用 Segment 分段锁来保证安全，而 Segment 是继承自 ReentrantLock。
Java 8 中放弃了 Segment 的设计，采用 Node + CAS + synchronized 保证线程安全。
遇到 Hash 碰撞
Java 7 在 Hash 冲突时，会使用拉链法，也就是链表的形式。
Java 8 先使用拉链法，在链表长度超过一定阈值时，将链表转换为红黑树，来提高查找效率。
查询时间复杂度
Java 7 遍历链表的时间复杂度是 O(n)，n 为链表长度。
Java 8 如果变成遍历红黑树，那么时间复杂度降低为 O(log(n))，n 为树的节点个数。