1. ConcurrentHashMap结构
Java8 以前ConcurrentHashMap是数组+链表
Java8及以后ConcurrentHashMap是数组+链表+红黑树
结构这方面和HashMap比较类似，具体参考：https://www.cnblogs.com/enhance/p/11168399.html
2. ConcurrentHashMap线程安全
HashMap是线程不安全
HashTable线程安全，实现线程安全原理是对整个整个Hash表加锁。如下图所示这样效率会比较低
ConcurrentHashMap线程安全，实现线程安全原理：
2.1 分段锁：
Java8之前，采用分段锁。采用分段锁这样将锁范围变小，提高并发度。
ConcurrentHashMap首先hash(key)%segment.len找到对应segment段；然后再次hash找到对应segment下hashEntry（HashEntry可以理解为一个hashMap）
put()操作流程：hash(key)%segment.len找到对应segment——>线程申请该segment锁（如果没获取到锁线程进入阻塞状态）——>获取到锁的线程对segment[i]hashEntry进行put操作，由于segment锁继承自ReentrantLock独占的可重入锁，所以拿到segment后操作不需要考虑并发。
2.2 CAS+synchronzied
java8之前分段锁并发度等于segment长度（16个），并且segment是不会扩容，只有segment[i]下的hashEntry才会扩容，当并发量越来越大也只有16个并发度，其他线程会进入阻塞状态
ConcurrentHashMap put操作流程：
a)首先判断put的key value不能为空，若为空则抛出空指针异常。因为如果为空则无法hash计算，造成线程不安全
b)初始化：第一次put操作时需要初始化。初始化核心思想时只允许一个线程对ConcurrentHashMap进行初始化，有其他线程正在初始化数组，此时使用 Thread.yield() 将当前线程由运行态进入到就绪态，让出CPU资源；即当前线程在外面自旋，直到table初始化完毕才能跳出while循环。这样保证ConcurrentHashMap同时只会被一个线程初始化
c)没有hash冲突：初始化之后，数组已经被创建出来，并且数组位置未被占用，采用基于主内存地址，创建node节点，并通过CAS将其插入到当前位置
d) resize: 寻址到位置正在进行扩容/迁移操作即数组位置的hash值=moved=-1，将当前线程键入到扩容/迁移大军，通过执行transfer()方法来协助其他线程进行扩容/迁移操作
f)hash冲突：首先只有在hash冲突时加synchronized锁。这个锁的粒度是针对单个数组元素（而不是整个数组），确保线程安全的将需要插入的节点写入到链表或者红黑树中。
其次这种情况大致分为三个部分：
遍历链表，将节点插入到链表中；如果链表中存在相同key的节点，则根据onlyIfAbsent判断是否替换value值；否者将新Node放入到链表尾部。
如果节点类型是红黑树节点，将节点插入到红黑树中；如果找到相同key的节点，则根据onlyIfAbsent判断是否替换value值。
如果链表长度大于8，则转换元素存储类型，即链表转红黑树。
g)KV键值对总数+1
ConcurrenthashMap put源码
public V put(K key, V value) {
return putVal(key, value, false);
}
/**
* Implementation for put and putIfAbsent
*/
final V putVal(K key, V value, boolean onlyIfAbsent) {
// key和value都不允许为空，因为如果为空的话，线程不安全，会出现数据错乱。
if (key == null || value == null) throw new NullPointerException();
// 使用扰动函数计算key的hash值
int hash = spread(key.hashCode());
int binCount = 0;
// phase1：对数组做无限循环，其中包含四种情况的判断
for (Node<K, V>[] tab = table; ; ) {
Node<K, V> f;
int n, i, fh;
/**
* part1, table数组需要被创建，即table数组为null 或 长度为0，则懒汉式初始化数组
*/
if (tab == null || (n = tab.length) == 0)
tab = initTable();
/**
* part2，table数组已经被创建，并且寻址后的数组位置没有被占用。
* 因为table数组是线程间可见的，但数组元素不是。所以采用volatile读的方式来读取数组中的元素，保证每次拿到的数据都是最新的。
* tabAt(tab, i = (n - 1) & hash)) 相当于 table[i]
*/
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 直接基于主内存地址，创建Node节点 并 通过CAS将其插入到当前位置；CAS失败则进入下一次table数组循环
if (casTabAt(tab, i, null,
new Node<K, V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// part3: 寻址到的位置正在进行扩容/迁移操作，即：数组位置的hash值 = MOVED = -1，
else if ((fh = f.hash) == MOVED)
// 当前线程加入到扩容/迁移大军，帮助数组进行扩容/迁移。
tab = helpTransfer(tab, f);
// part4：其他情况，即：hash冲突的场景
else {
V oldVal = null;
// 只针对单个数组元素采用synchronized锁（而不是对整个数组加锁），确保线程安全的将节点插入到链表 或 红黑树中
synchronized (f) {
if (tabAt(tab, i) == f) {
// 当前节点的hash值大于0，表明该节点是正常节点，不是被扩容/迁移中的节点。
if (fh >= 0) {
binCount = 1;
// phase1: 遍历链表，将节点插入到链表中
for (Node<K, V> e = f; ; ++binCount) {
K ek;
// 待插入的key与已有链表节点f的key相同
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
// 如果onlyIfAbsent为false对value值进行替换
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K, V> pred = e;
// 如果链表中没有key和待插入的key相同，封装新节点插入到链表的尾部。
if ((e = e.next) == null) {
pred.next = new Node<K, V>(hash, key,
value, null);
break;
}
}
}
/**
* 红黑树的操作
*
* phase2: 如果节点类型是红黑树节点，将节点插入到红黑树中，如果找到相同key的节点，则根据onlyIfAbsent判断是否替换value值
*/
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;
}
}
}
}
/**
* phase3: 转换元素存储类型，即：链表转红黑树的操作
*/
if (binCount != 0) {
// 如果链表的个数大于等于8，则将链表转为红黑树
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
// 如果存在旧的value值，则将旧的value值返回
if (oldVal != null)
return oldVal;
break;
}
}
}
// phase2：将ConcurrentHashMap中存储的KV键值对总数+1
addCount(1L, binCount);
return null;
}
View Code
初始化源码：
初始化线程核心思想是只有一个线程对ConcurrentHashmap进行初始化。初始化数组线程安全时通过volatile修饰变量sizeCtl结合CAS实现
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
//如果表为空才进行初始化操作
while ((tab = table) == null || tab.length == 0) {
//sizeCtl 小于零说明已经有线程正在进行初始化操作
//当前线程应该放弃 CPU 的使用
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
//否则说明还未有线程对表进行初始化，那么本线程就来做这个工作
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
//保险起见，再次判断下表是否为空
try {
if ((tab = table) == null || tab.length == 0) {
//sc 大于零说明容量已经初始化了，否则使用默认容量
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
//根据容量构建数组
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
//计算阈值，等效于 n*0.75
sc = n - (n >>> 2);
}
} finally {
//设置阈值
sizeCtl = sc;
}
break;
}
}
return tab;
}
View Code
3. 触发扩容条件
扩容触发都是在新增插入key-value节点后触发的，其中包括两种情况
3.1 新增节点后，链表长度达到8，会调用treeifyBin（tab, i)方法将链表转为红黑树，不过在treeifyBin(tab,i)中会先对数组长度进行判断，如果数组长度小于64，则会对数组两倍扩容（此时不会进行红黑树操作），进而通过transfer()方法重新调整节点位置；如果数组长度大于等于64才会进行红黑树填充操作
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) {
//如果数组长度小于64，则i女性数组扩充
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
//如果数组长度大于64，则进行红黑树填充操作
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
...
}
}
View Code
3.2 新增节点后会调用addCount()方法将元素个数+1，并检查是否需要扩容，当数组元素个数达到扩容阈值sizeCtl时会触发transfer方法对数组进行两倍扩容
参考文献： https://blog.csdn.net/Saintmm/article/details/122911586
标签：key,ConcurrentHashMap,hash,tab,链表,线程,数组 From： https://www.cnblogs.com/enhance/p/17154478.html