Java并发包源码分析:ConcurrentHashMap(JDK1.8版本)

一、概述

• 在JDK1.7主要通过定义Segment分段锁来实现多个线程对ConcurrentHashMap的数据的并发读写操作。整个ConcurrentHashMap由多个Segment组成，每个Segment保存整个ConcurrentHashMap的一部分数据，Segment结合ReentrantLock，即Segment继承于ReentrantLock，来实现写互斥，读共享，具体为有多少个Segment，则任何时候可以最多支持这么多个线程同时进行写操作，任意多个线程进行读操作。在ConcurrentHashMap的Segment实现中，对写操作使用ReentrantLock来进行加锁，读操作不加锁，通过volatile来实现线程之间的可见性。具体可以参考我的另外一篇文章：Java并发包源码分析：ConcurrentHashMap（JDK1.7版本）
• 在JDK1.8中为了进一步优化ConcurrentHashMap的性能，去掉了Segment分段锁的设计，在数据结构方面，则是跟HashMap一样，使用一个哈希表table数组，即数组 + 链表或者数组 + 红黑树。而线程安全方面是结合CAS机制来实现的，CAS底层依赖JDK的UNSAFE所提供的硬件级别的原子操作。同时在HashMap的基础上，对哈希表table数组和链表节点的value，next指针等使用volatile来修饰，从而实现线程可见性。

二、核心字段

• 哈希表table数组，如下与HashMap一样也是使用一个Node类型的数组table来定义的，不同之处是使用volatile修饰该数组。
• baseCount和counterCells：用来记录当前ConcurrentHashMap存在多少个元素使用的，在进行增删链表节点时，默认是更新baseCount的值即可，如果同时存在多个线程并发进行对链表节点的增删操作，则放弃更新baseCount，而是counterCells数组中添加一个CounterCell，之后在计算size的时候，累加baseCount和遍历并累加counterCells。

// 链式哈希表数组
transient volatile Node<K,V>[] table;
// 用于size方法统计元素个数使用
private transient volatile long baseCount;
private transient volatile CounterCell[] counterCells;

• 链表节点Node的定义：value，next使用volatile修饰保证线程可见性。

三、核心方法

1. UNSAFE：硬件级别的原子操作

• 主要定义了获取，更新，添加链表节点Node的方法，具体为基于UNSAFE类提供的硬件级别的原子操作来保证线程安全，而不是通过加锁机制，如synchronized关键字，ReentrantLock重入锁来实现，即无锁化。

2.put写操作

• 写操作主要在putVal方法定义，实现逻辑与HashMap的putVal基本一致，只是相关操作，如获取链表节点，更新链表节点的值value和新增链表节点，都会使用到UNSAFE提供的硬件级别的原子操作，而如果是更新链表节点的值或者在一个已经存在的链表中新增节点，则是通过synchronized同步锁来实现线程安全性。

1. 如果当前需要put的key对应的链表在哈希表table中还不存在，即还没添加过该key的hash值对应的链表，则调用UNSAFE的casTabAt方法，基于CAS机制来实现添加该链表头结点到哈希表table中，避免该线程在添加该链表头结的时候，其他线程也在添加的并发问题；如果CAS失败，则进行自旋，通过继续第2步的操作；
2. 如果需要添加的链表已经存在哈希表table中，则通过UNSAFE的tabAt方法，基于volatile机制，获取当前最新的链表头结点f，由于f指向的是ConcurrentHashMap的哈希表table的某条链表的头结点，故虽然f是临时变量，由于是引用共享的该链表头结点，所以可以使用synchronized关键字来同步多个线程对该链表的访问。在synchronized(f)同步块里面，则是与HashMap一样遍历该链表，如果该key对应的链表节点已经存在，则更新，否则在链表的末尾新增该key对应的链表节点。

• 使用synchronized同步锁的原因：因为如果该key对应的节点所在的链表已经存在的情况下，可以通过UNSAFE的tabAt方法基于volatile获取到该链表最新的头节点，但是需要通过遍历该链表来判断该节点是否存在，如果不使用synchronized对链表头结点进行加锁，则在遍历过程中，其他线程可能会添加这个节点，导致重复添加的并发问题。故通过synchronized锁住链表头结点的方式，保证任何时候只存在一个线程对该链表进行更新操作。
• 锁的范围缩小：相对于JDK1.7的Segment分段锁，即分段锁的写操作，在操作之前需要先获取lock锁，即不管是（1）链表不存在，添加链表头结点，（2）还是更新链表节点，（3）还是在已经存在的链表中添加节点，都需要先获取lock锁，而在JDK1.8的写操作中，（1）如果该链表不存在，添加链表头的时候是不需要加锁的，因为是往哈希表table数组的某个位置填充值，不需要遍历链表之类的，所以可以基于UNSAFE的casTabAt方法，即CAS机制检查table数组的该位置是否存在元素（链表头结点）来实现线程安全，这是写操作最先检查的；如果该链表已经存在，即（2）（3）则需要通过synchronized来锁住该链表头结点，而在JDK1.7的实现中是锁住该Segment内部的整个哈希表table数组，所以这里也是一个性能提升的地方，缩小了锁的范围。

3.get读操作

• get读操作由于是从哈希表中查找并读取链表节点数据，不会对链表进行写更新操作，故基于volatile的happend-before原则保证的线程可见性（即一个线程的操作对其他线程可见），即可保证get读取到该key对应的最新链表节点，整个过程不需要进行加锁。
• 具体为table和Node的value和next均是volatile修饰。

4.size容量计算

• size方法为计算当前ConcurrentHashMap一共存在多少链表节点，与JDK1.7中每次需要遍历segments数组来计算不同的是，在JDK1.8中，使用baseCount和counterCells数组，在增删链表节点时，实时更新来统计，在size方法中直接返回即可。整个过程不需要加锁。
• 并发修改异常处理：CounterCell的value值为1，作用是某个线程在更新baseCount时，如果存在其他线程同时在更新，则放弃更新baseCount的值，即保持baseCount不变，而是各自往counterCells数组添加一个counterCell元素，在size方法中，累加counterCells数组的value，然后与baseCount相加，从而获取准确的大小。