[TOC]
1. 并发容器类介绍
2. ConcurrentHashMap
2.1 jdk1.7实现
在JDK1.7版本中，ConcurrentHashMap的数据结构是由一个Segment数组和多个HashEntry组成，如下图所示：
Segment数组的意义就是将一个大的table分割成多个小的table来进行加锁，而每一个Segment元素存储的是HashEntry数组+链表，这个和HashMap的数据存储结构一样
put操作
对于ConcurrentHashMap的数据插入，这里要进行两次Hash去定位数据的存储位置
static class Segment<K,V> extends ReentrantLock implements Serializable {
}
从上Segment的继承体系可以看出，Segment实现了ReentrantLock,也就带有锁的功能，
当执行put操作时，会进行第一次key的hash来定位Segment的位置，如果该Segment还没有初始化，即通过CAS操作进行赋值，然后进行第二次hash操作，找到相应的HashEntry的位置，这里会利用继承过来的锁的特性，在将数据插入指定的HashEntry位置时（链表的尾端），会通过继承ReentrantLock的tryLock（）方法尝试去获取锁，如果获取成功就直接插入相应的位置，如果已经有线程获取该Segment的锁，那当前线程会以自旋的方式去继续的调用tryLock（）方法去获取锁，超过指定次数就挂起，等待唤醒
简单的说, 会通过两次hash分别找到对应的Segment和hashEntry的位置, 然后再插进去, 每个Segment都是ReentrantLock锁, 所以在Segment上加锁来保证线程安全
2.2 jdk1.8 实现
JDK1.8的实现已经摒弃了Segment的概念，而是直接用Node数组+链表+红黑树的数据结构来实现，并发控制使用Synchronized和CAS来操作，整个看起来就像是优化过且线程安全的HashMap，虽然在JDK1.8中还能看到Segment的数据结构，但是已经简化了属性，只是为了兼容旧版本
这些是构成ConcurrentHashMap实现结构的基础，下面看一下基本属性：
// node数组最大容量：2^30=1073741824
private static final int MAXIMUM_CAPACITY = 1 << 30 ;
// 默认初始值，必须是2的幂数
private static final int DEFAULT_CAPACITY = 16 ;
//数组可能最大值，需要与toArray（）相关方法关联
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 ;
//并发级别，遗留下来的，为兼容以前的版本
private static final int DEFAULT_CONCURRENCY_LEVEL = 16 ;
// 负载因子
private static final float LOAD_FACTOR = 0.75f;
// 链表转红黑树阀值,> 8 链表转换为红黑树
static final int TREEIFY_THRESHOLD = 8 ;
//树转链表阀值，小于等于6（tranfer时，lc、hc=0两个计数器分别++记录原bin、新binTreeNode数量，<=UNTREEIFY_THRESHOLD 则untreeify(lo)）
static final int UNTREEIFY_THRESHOLD = 6 ;
static final int MIN_TREEIFY_CAPACITY = 64 ;
private static final int MIN_TRANSFER_STRIDE = 16 ;
private static int RESIZE_STAMP_BITS = 16 ;
// 2^15-1，help resize的最大线程数
private static final int MAX_RESIZERS = ( 1 << ( 32 - RESIZE_STAMP_BITS)) - 1 ;
// 32-16=16，sizeCtl中记录size大小的偏移量
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
// forwarding nodes的hash值
static final int MOVED = - 1 ;
// 树根节点的hash值
static final int TREEBIN = - 2 ;
// ReservationNode的hash值
static final int RESERVED = - 3 ;
// 可用处理器数量
static final int NCPU = Runtime.getRuntime().availableProcessors();
//存放node的数组
transient volatile Node<K,V>[] table;
/*控制标识符，用来控制table的初始化和扩容的操作，不同的值有不同的含义
*当为负数时：- 1 代表正在初始化，-N代表有N- 1 个线程正在 进行扩容
*当为 0 时：代表当时的table还没有被初始化
*当为正数时：表示初始化或者下一次进行扩容的大小
*/
private transient volatile int sizeCtl;
ConcurrentHashMap (int initialCapacity) 构造函数总结下：
构造函数中并不会初始化哈希表；
构造函数中仅设置哈希表大小的变量 sizeCtl；
initialCapacity 并不是哈希表大小；
哈希表大小为 initialCapacity*1.5+1 后，向上取最小的 2 的 n 次方。如果超过最大容量一半，那么就是最大容量。
put操作
final V putVal(K key, V value, boolean onlyIfAbsent){
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode()); //两次hash，减少hash冲突，可以均匀分布
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();//这里就是上面构造方法没有进行初始化，在这里进行判断，为null就调用initTable进行初始化，属于懒汉模式初始化
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //如果i位置没有数据，就直接无锁插入
if ( casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)) )
break; // no lock when adding to empty bin
}
else if ((fh = f.hash) == MOVED) //如果在进行扩容，则先辅助扩容操作 (多线程同步进行扩容)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) { //如果以上条件都不满足，那就要进行加锁操作，也就是存在hash冲突，锁住链表或者红黑树的头结点
if (tabAt(tab, i) == f) {
if (fh >= 0) {//表示该节点是链表结构
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
//这里涉及到相同的key进行put就会覆盖原先的value
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent) // hashmap 支持仅不存在时插入, 故此判断
e.val = value;
break;
}
Node<K,V> pred = e;
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;
//红黑树结构旋转插入
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {//如果链表的长度大于8时就会进行红黑树的转换
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i); // treeifyBin()方法里判断需要数组大小超过64,才会变红黑树, 和hashMap一样
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount); //统计size，并且检查是否需要扩容
return null;
}
这个put的过程很清晰，对当前的table进行无条件自循环直到put成功，可以分成以下六步流程来概述
- 如果没有初始化就先调用initTable() 方法来进行初始化过程
- 如果没有hash冲突就直接CAS插入
- 如果还在进行扩容操作就先进行扩容 helpTransfer(tab, f)
- 如果存在hash冲突，就加锁来保证线程安全，这里有两种情况，一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入，
- 最后一个如果Hash冲突时会形成Node链表，在链表长度超过8，Node数组超过64时会将链表结构转换为红黑树的结构，break再一次进入循环
- 如果添加成功就调用addCount（） 方法统计size，并且检查是否需要扩容
新增槽点值时的线程安全
此时为了保证线程安全，做了四处优化：
- 通过自旋死循环保证一定可以新增成功。
在新增之前，通过 for (Node<K,V>[] tab = table;;)这样的死循环来保证新增一定可以成功，一旦新增成功，就可以退出当前死循环，新增失败的话，会重复新增的步骤，直到新增成功为止。
- 当前槽点为空时，通过 CAS 新增。
Java 这里的写法非常严谨，没有在判断槽点为空的情况下直接赋值，因为在判断槽点为空和赋值的瞬间，很有可能槽点已经被其他线程复制了，所以我们采用 CAS 算法，能够保证槽点为空的情况下赋值成功，如果恰好槽点已经被其他线程赋值，当前 CAS 操作失败，会再次执行 for 自旋，再走槽点有值的 put 流程，这里就是自旋 + CAS 的结合。
- 当前槽点有值，锁住当前槽点。
put 时，如果当前槽点有值，就是 key 的 hash 冲突的情况，此时槽点上可能是链表或红黑树，我们通过锁住槽点，来保证同一时刻只会有一个线程能对槽点进行修改
V oldVal = null;//锁定当前槽点，其余线程不能操作，保证了安全
synchronized (f) { ... }
- 红黑树旋转时，锁住红黑树的根节点，保证同一时刻，当前红黑树只能被一个线程旋转
ConcurrentHashMap核心原理，彻底给整明白了_Java_AI乔治_InfoQ写作社区
transfer() 扩容操作
transfer 方法的主要思路是：
首先需要把老数组的值全部拷贝到扩容之后的新数组上，先从数组的队尾开始拷贝；
拷贝数组的槽点时，先把原数组槽点锁住，保证原数组槽点不能操作，成功拷贝到新数组时，把原数组槽点赋值为转移节点；
这时如果有新数据正好需要 put 到此槽点时，发现槽点为转移节点，就会一直等待，所以在扩容完成之前，该槽点对应的数据是不会发生变化的；
从数组的尾部拷贝到头部，每拷贝成功一次，就把原数组中的节点设置成转移节点；
直到所有数组数据都拷贝到新数组时，直接把新数组整个赋值给数组容器，拷贝完成。
扩容方法主要是通过在原数组上设置转移节点，put 时碰到转移节点时会等待扩容成功之后才能 put 的策略，来保证了整个扩容过程中肯定是线程安全的，因为数组的槽点一旦被设置成转移节点，在没有扩容完成之前，是无法进行操作的
会使用多线程的方式来做扩容(数据迁移), 通过 ForwardingNode (转移节点) 来表示是否被迁移过 加上 synchronized 来保证线程安全
这里的多线程不是新开一个线程池去迁移, 而是让 操作数据的线程 暂停操作来帮忙处理数据迁移(例如put时就会有这个处理) (称为辅助扩容或者多线程扩容)
get操作
ConcurrentHashMap的get操作的流程很简单，也很清晰，可以分为三个步骤来描述
- 计算hash值，定位到该table索引位置，如果是首节点符合就返回
- 如果遇到扩容的时候，会调用标志正在扩容节点ForwardingNode的find方法，查找该节点，匹配就返回
- 以上都不符合的话，就往下遍历节点，匹配就返回，否则最后就返回null
下图表示有节点成为了链表中的元素
其中"xkj11" 与"xkj9" hash冲突, 则"11"成为"9"的后驱节点, 所以直接看tab是找不到"xkj11"的, 所以get时会找到"xkj9"(的hash值) 然后比较key值是否相等, 才能确定是否为该值
ConcurrentHashMap底层实现原理(JDK1.7 & 1.8) - 简书 (jianshu.com)
2.3 面试题
ConcurrentHashMap 的 get 方法是否要加锁，为什么？
get 方法不需要加锁。因为 Node 的元素 value 和指针 next 是用 volatile 修饰的，在多线程环境下线程A修改节点的 value 或者新增节点的时候是对线程B可见的。这也是它比其他并发集合比如 Hashtable、用 Collections.synchronizedMap()包装的 HashMap 效率高的原因之一。
ConcurrentHashMap 支持 key 或者 value 为 null 吗？
不支持