ConcurrentHashMap的实现机制是一直在变化的， 其中8的变化较大， 下面分别说明一下在Java7和Java8中他们的实现机制。

Java 7 实现原理

主要是基于分离锁来实现的。这样做的目的是， 在进行并发操作的时候， 只需要锁住相应的Segment, 而不需要去锁住整个数据， 提高并发性能。

存储数据的是一个个的Segment，Segment是继承自ReentrantLock，所以它本质上就是一个锁。

每个Segment内部都有一个HashEntry的数组， 这个HashEntry数组存储方式和HashMap内部的table数组类似， 哈希相同的元素也是以链表形式存储。

get

在并发的时候，get操作只要能保证可见性即可， 所以没有同步操作。

  1. 定位元素所属的segment
  2. 利用jdk提供的Unsafe方法保证以可见性的方式获取元素，UNSAFE.getObjectVolatile()

put

  1. 利用UNSAFE.getObject() 方法获取元素所属的segment
  2. 利用所属的segment获取可重入锁，从而将该segment锁住， 防止其他的线程进行并发写
  3. 会有一个无线循环， 在该循环内部， 会确定该元素的key是否在HashEntry数组中， 从而决定是进行插入还是更新。

size

由于需要考虑并发， 计算总容量的时候， 如果锁住整个数据，会导致性能很差。所以ConcurrentHashMap在此处使用了重试机制。

在进行size操作的时候， 通过重试机制（默认2次）获取值，如果重试的时候没有发生变化， 则直接返回旧值， 如果发生了变化，则还是要通过获取锁来进行计算。

Java 8 实现原理

和HashMap类似，其内部存储数据的结构是也是一个大的桶数组Node[]， 数组节点是链表或者是红黑树。其数组定义如下：

1
transient volatile Node<K,V>[] table;

总结几点：

  1. 内部虽仍然有Segment的定义, 但是只是为了保证序列化的兼容性， 并没有任何用处
  2. Node中的value和next都是用volatile来修饰， 保证变量的可见性
  3. 大量使用CAS操作， 可以有效减少锁的使用

put

对上面源码几处关键处进行一下说明：

  1. 当数组为空的时候进行初始化， 说明初始化的调用时机是第一次put的时候， 和HashMap类似
  2. 定位当前数组下标处是否存在节点， 若不存在，则利用CAS尝试写入， 如果失败则自旋保证成功，因为此处是使用CAS进行写入， 所以是不需要加锁的。
    定位索引的方法（与HashMap一样）： i = (n - 1) & hash
  3. 如果检测到当前正在扩容， 则帮助其进行扩容
  4. 当以上条件都不满足时， 说明此处已经存在节点， 则对该节点上锁， 此处直接使用synchronized进行加锁， 且加锁的对象只是该节点而不是整个数据
  5. 获取该节点的锁之后， 判断该节点类型， 若是链表，则遍历链表插入
  6. 若是红黑树，则遍历红黑树插入
  7. 判断是否要将链表转换为红黑树，临界值和HashMap一样也是8

其整体流程与HashMap较为相似， 就其中几个关键不同之处进行说明：

  1. 当插入一个新节点的时候， HashMap是直接插入，而ConcurrentHashMap使用CAS进行无锁插入
  2. ConcurrentHashMap多了一个状态判断， 当发现Map正在扩容，则调用helpTransfer()帮助其进行扩容， 以加快扩容速度。
  3. 当索引处已经存在节点， 此时往该索引处添加元素时， ConcurrentHashMap 首先对该节点加锁， 在获取到该节点的锁之后再进行后续操作， 这样既能保证插入操作的线程安全性，同时因为只对该节点加锁，没有对整个数据加锁， 从而减少锁竞争， 提高效率。

get

get方法没有加锁， 而是利用CAS来进行处理， 可以提高查询效率。

下面是源码对应的关键几步进行分析：

  1. 利用CAS获取数组列表下标处的节点
  2. 如果当前节点（链表头结点）刚好是要找的节点， 则直接返回当前节点值
  3. 如果eh<0, 表示当前正在扩容或者该位置是红黑树， 调用find查找
  4. 以上条件都不满足， 表明该位置是链表， 遍历链表进行查找

size

其调用的是sumCount()方法，采用分而冶之进行计数

1
2
3
4
5
6
7
8
9
10
11
final long sumCount() {
        CounterCell[] as = counterCells; CounterCell a;
        long sum = baseCount;
        if (as != null) {
            for (int i = 0; i < as.length; ++i) {
                if ((a = as[i]) != null)
                    sum += a.value;
            }
        }
        return sum;
    }

CAS简单介绍

上面章节中多次提到cas，下面简单介绍一下。

Compare and Swap， 比较并交换， 包含了两个动作。在现代CPU中，提供了一个CAH指令，保证这两个动作的原子性。

CAS的核心有三个参数：

  • V 内存位置
  • A 旧的预期值
  • B 要修改的值，也就是新值

首先要明白， 每个线程都会有一个自己的内存空间，在进行操作时， 首先会将主内存的值copy一份到自己的线程内存空间， 然后再刷新到主内存。

举一个简单例子， 比如a+1 这个操作，此时a的值时0， 当有thread1、thread2两个线程都执行的时候， 其情况是怎么样的？

  1. thread1、thread2将主内存中的a的值copy到自己的线程内存空间，此时对于这两个线程而言，他们的 预期值 A 都是0， 要修改的值 B 都是1
  2. 然后就会执行 比较并交换的动作， thread1将a的旧预期值与主内存中a的值进行比较， 此时发现两者相等，就会直接将要修改的值a=1刷新到主内存， 此时主内存中a的值就变成了1
  3. 此时thread2在提交的时候，发现a的预期值0与主内存中a的值1不相等， 就会放弃本次提交。提交失败之后，会继续重复执行步骤1的操作， 直到成功。

使用UnSafe操作cas是不推荐的， 在Java9之后， 提供了VarHandle来进行CAS操作， 一般流程都是首先获取变量句柄，然后调用其cas方法。

CAS中常见的一个A-B-A问题，由于CAS是在更新时比较新值与旧值，如果刚好新值从A变为B再改为A， 此时这个比较实际上就无效了， Java提供了一个AtomicStampedReference类， 为引用建立版本号， 每次变更值的时候， 版本号都会发生变化， 从而确定该值是否真的改变。