详解ConcurrentHashMap及JDK8的优化

JDK8的ConcurrentHashMap

1. 数据结构：取消了Segment分段锁的数据结构，取而代之的是Node数组+链表+红黑树的结构，从而实现了对每一行数据进行加锁，进一步减少并发冲突的概率。

Node类成员变量Node的元素val和指针next都标注volatile，目的是在多线程环境下线程A修改结点的val或者新增节点的时候是对线程B可见的。

ConcurrentHashMap有成员变量transient volatile Node<K,V>[] table，目的是为了使Node数组在扩容的时候对其他线程具有可见性而加的volatile。（例如：volatile int array[10]是指array的地址是volatile的而不是数组元素的值是volatile的.）

1. 保证线程安全机制：JDK7采用segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK8采用CAS(读)+Synchronized(写)保证线程安全。
2. 锁的粒度：原来是对需要进行数据操作的Segment加锁，JDK8调整为对每个数组元素加锁（Node）。
3. 链表转化为红黑树：定位结点的hash算法简化会带来弊端，Hash冲突加剧，因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。
4. 查询时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)。
5. JDK8推荐使用mappingCount方法而不是size方法获取当前map表的大小，因为这个方法的返回值是long类型，size方法是返回值类型是int。

JDK8的get过程

1. 计算hash值，定位到该table索引位置，如果是首节点符合就返回
2. 如果遇到扩容的时候，会调用标志正在扩容节点ForwardingNode的find方法，查找该节点，匹配就返回
3. 以上都不符合的话，就往下遍历节点，匹配就返回，否则最后就返回null

写到这的时候，笔者建议大家去了解下Redis的渐进式扩容，是另一种思想，都值得学习。一句话帮助理解Redis的渐进式扩容：由于Redis是单线程，而且数据量较大时，无法一次性快速扩容，所以Redis首先申请一个新的容量加倍的哈希表，然后在插入，删除，更新操作的时候，调用rehash函数（dictRehash函数），将原有操作单元的链表移植到新的哈希表中，当原有哈希表全部移植过去，扩容结束。

JDK8的size过程

两个重要变量：

1. baseCount用于记录节点的个数，是个volatile变量
2. counterCells是一个辅助baseCount计数的数组，每个counterCell存着部分的节点数量，这样做的目的就是尽可能地减少冲突。

counterCell类使用了 @sun.misc.Contended 标记的类，内部一个 volatile变量。这个注解标识着这个类需要避免 "伪共享".

避免伪共享(false sharing)。缓存系统中是以缓存行（cache line）为单位存储的。缓存行是2的整数幂个连续字节，
一般为32-256个字节。最常见的缓存行大小是64个字节。当多线程修改互相独立的变量时，如果这些变量共享同一个缓存行，就会无意中影响彼此的性能，这就是伪共享。所以伪共享对性能危害很大。
没有这个注解之前，是通过使用拼接把缓存行加满来解决这个问题，让缓存之间的修改互不影响。

ConcurrentHashMap节点的数量 = baseCount+counterCells每个cell记录下来的节点数量

由于JDK8在统计这个数量的时候并没有进行加锁，所以这个结果并不是绝对准确的。原理都是相通的，可以顺道看看LongAdder的longValue方法。想学习更多J.U.C的原子操作类，可以查看这篇博客

更新size的过程：

总体的原则就是：先尝试更新baseCount，失败再利用CounterCell。

1. 通过CAS尝试更新baseCount ，如果更新成功则完成，如果CAS更新失败会进入下一步
2. 线程通过随机数ThreadLocalRandom.getProbe() & (n-1) 计算出在counterCells数组的位置，如果不为null，则CAS尝试在couterCell上直接增加数量，如果失败，counterCells数组会进行扩容为原来的两倍，继续随机，继续添加

JDK8的put过程

对当前的table进行无条件自循环直到put成功

1. 如果没有初始化就先调用initTable（）方法来进行初始化过程
2. 如果没有hash冲突就直接CAS插入
3. 如果还在进行扩容操作就先进行扩容
4. 如果存在hash冲突，就加synchronized锁来保证线程安全，这里有两种情况，一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入，
5. 最后一个如果该链表的数量大于阈值8，就要先转换成黑红树的结构，break再一次进入循环
6. 如果添加成功就调用addCount方法统计size，并且检查是否需要扩容

FAQ

ConcurrentHashMap迭代器是强一致性还是弱一致性？

ConcurrentHashMap迭代器是弱一致性，hashmap迭代器是强一直性。

ConcurrentHashMap可以支持在迭代过程中，向map添加新元素，而HashMap则抛出了ConcurrentModificationException，因为HashMap包含一个修改计数器，当你调用他的next()方法来获取下一个元素时，迭代器将会用到这个计数器。

ConcurrentHashMap一定线程安全么？

ConcurrentHashMap使用不当，也会造成死循环的。以后会有博客来介绍~

哎呀，如果我的名片丢了。微信搜索“全菜工程师小辉”，依然可以找到我