ConcurrentHashMap(CHM)是java.util.concurrent包下的一个类，本质上是一个HashMap，因此功能和HashMap一样，但是在HashMap的基础上，提供了对指定的Node节点加锁来保证数据并发更新的安全性。在JDK1.8中的存储结构是由数组、单向链表、红黑树组成。

当我们初始化一个CHM实例时，默认会初始化一个长度为16的数组。由于CHM它的核心仍然是hash表，所以必然会存在hash冲突问题。CHM采用链式寻址法来解决hash冲突。

当hash冲突比较多的时候，会造成链表长度较长，这种情况会使得CHM中数据元素的查询时间复杂度变成O(n)。因此在JDK1.8中，引入了红黑树的机制。当数组长度大于64并且链表长度大于等于8的时候，单向链表就会转换为红黑树。

另外，随着CHM的动态扩容，一旦链表长度小于8，红黑树会退化成单向链表。

ConcurrentHashMap在JDK1.8中的数据结构

ConcurrentHashMap在JDK1.8中的数据结构

ConcurrentHashMap的put()方法逻辑

1.判断key或者value是否为null，是则抛出空指针异常。

2.根据传入key的hash值计算索引位置。

3.遍历table数组，如果table为null或者table的长度为0，则调用initTable()初始化table。

4.否则判断索引位置在table表中当前节点是否为null，如果为空利用CAS尝试将元素插入。

5.如果当前位置的hashcode==MOVED==-1，说明这是一个ForwaringNodes节点，即正在进行扩容，那么当前线程加入扩容。

6.如果判断索引位置在table表中当前节点不为null，则利用synchronized锁写入数据(分为链表写入和红黑树写入)

7.如果节点长度大于8则要转换为红黑树。

ConcurrentHashMap的put()流程图

ConcurrentHashMap的get()方法逻辑

1.首先计算hash值，定位到该table索引位置，如果满足条件，直接返回对应的值。

2.如果遇到扩容(hash值为负值)，会调用标志正在扩容节点ForwardingNode的find()方法，查找该节点，匹配就返回。

3.以上都不符合的话，就往下遍历节点，匹配就返回，否则最后就返回null。

ConcurrentHashMap的get操作为什么不需要加锁

get操作可以无锁是由于Node的元素val和指针next使用volatile修饰的，在多线程环境下线程A修改节点的val或者新增节点的时候对线程B可见的。

数组上的volatile的目的是：为了使得Node数组在扩容的时候对其他线程具有可见性而加的volatile。

ConcurrentHashMap的initTable()初始化数组的流程

首先，CHM是使用懒加载的方式，就是在添加元素时判断数组是否为null或者数组长度是否为0才进行数组初始化，其次，initTable()中使用一个sizCtl的变量控制着数组在初始化和扩容操作。

-1代表当前数组正在初始化。

小于-1低16位代表当前数组正在扩容的线程个数。

0代表数据还没初始化。

大于0代表当前数组的扩容阈值或当前数组的初始化大小。

首先循环判断数组是否为null或者数组长度是否为0，是则判断sizeCtl是否小于0，小于0则代表当前数组正在初始化，当前线程则进入等待。

如果sizeCtl的值小于0位否，则通过CAS方式将sizCtl的值修改为-1，代表当前线程可以进行初始化。

进入初始化后，会再次判断数组是否为null或者数组长度是否为0，然后开始初始化。如果sizeCtl大于0，就初始化sizCtl长度的数组。

如果sizeCtl等于0，就初始化默认的长度。接着就是创建一个Node节点数组，之后还会计算下次扩容的阈值，且赋值给sizeCtl。

ConcurrentHashMap的扩容流程

首先，CHM触发扩容的点有几个，一个是链表转红黑树前对数组长度的判断。其次是putAll()时传入的Map过大，最后是put()达到阈值时。

首先是在基于当前数组的长度先计算出一个扩容标识戳，目的是为了保证协助扩容的线程的初始数组长度是一致的。

并且扩容标识戳的二进制中的第16个位置一定是1，这是为了保证扩容标志戳在左移16位后它的最高位一定是1代表是一个负数，在后面的sizCtl会用到。

当开始扩容之后，会将扩容标志戳左移16位并且加2赋值给sizCtl。从而代表当前正在扩容。

而低16位的标识就代表当前正在参与扩容的线程数+1也就是值为2，其实是代表有一个线程正在扩容。

并且+2的目的是为了保证最后一个结束迁移数据的线程要再从头到尾检查一次整个数组的数据是否迁移到了新数组上。

每当有一个线程来协助扩容时，就会对sizeCtl+1，表示有一个线程加入到当前扩容的操作里。

ConcurrentHashMap的resize()流程图

ConcurrentHashMap的size()

是非线程安全的。也就是说，当有线程调用put方法在添加元素的时候，其他线程在调用size()方法获取的元素个数和实际存储元素个数是不一致的。原因是size()方法是一个非同步的方法，put()和size()并没有实现同步锁。

put()的实现逻辑是在hash表上添加或者修改某个元素，然后再对总的元素个数进行累加。

其中，线程的安全性仅仅局限在hash表数组粒度的锁同步，避免同一个节点出现数据竞争带来线程安全问题。数组元素个数的累加方式用到了两个方案：

当线程竞争不激烈的时候，直接用CAS的方式对一个long类型的变量(baseCount)做原子递增。

当线程竞争比较激烈的时候，使用一个CounterCell数组，用分而治之的思想减少线程竞争，从而实现元素个数的原子累加。

size()的逻辑就是遍历CounterCell数组中的每个value值进行累加，再加上baseCount，汇总得到一个结果。所以很明显，size()得到的数据和真实数据必然是不一致的。

因此从size()本身来看，它的整个计算过程是线程安全的，因为这里用到了CAS的方式解决了并发更新问题。但是站在CHM全局角度来看，put()和size()之间的数据是不一致的，因此也就不是线程安全的。

直接在size()加锁，就会造成数据写入的并发冲突，对性能造成影响。CHM并发集合中，对于size()数量的一致性需求并不大，并发集合更多的是去保证数据存储的安全性。

ConcurrentHashMap的size()流程图

ConcurrentHashMap的size()

ConcurrentHashMap中的key不允许为null

首先，在CHM的源码中的put()方法，如果key或者value为空，则抛出空指针异常。

其次，CHM这么设计的原因是为了避免在多线程并发环境场景下的歧义问题。也就是说当一个线程从CHM获取某个key，如果返回的结果是null的时候，这个线程无法确认，这个null表示的是确实不存在这个key，还是说存在key，但是value为null。

这种不确定性会造成线程安全性问题，而CHM本身又是一个线程安全的集合。所以才这么设计。

ConcurrentHashMap中的key不允许为null

ConcurrentHashMap在JDK1.8中的优化

1.在1.8中在保证线程安全时是基于CAS和Synchronized的同步代码块做的，而相比于1.7的Segment实现的分段锁它的效率要更高。

2.在1.8中引入红黑树，很明显如果出现了hash冲突那么数据会挂在数组下面成为一个链表，而链表的查询时间复杂度是O(n)，如果链表过长会导致查询的效率比较低。所以引入了红黑树，当链表达到一定长度后会转换为红黑树，从而查询的时间复杂度变成了O(logn)，提升查询性能。

3.计数器这块，在1.7中使用Segment加锁做++操作，而在1.8中借助baseCount和counterCells两个原子属性，并配合多次使用CAS操作。

4.1.7中的扩容通过加锁再去扩容来保证安全，而1.8允许多线程并发扩容，通过一个sizeCtr核心变量来保证多线程并发扩容的安全，并且还能做到协助扩容的功能。