ConcurrentHashMap底层详解

ConcurrentHashMap是线程安全且高效的HashMap。

一、使用原因

在并发编程中使用HashMap可能导致程序死循环。而使用线程安全的HashTable效率又非常低下，基于此产生了ConcurrentHashMap。

1.线程不安全的HashMap

在多线程环境下，使用HashMap进行put操作会引起死循环，导致CPU利用率接近100%，所以在并发情况下不建议使用HashMap.

【HashMap在并发执行put操作时，引起死循环的原因是：多线程会导致HashMap的Entry链表形成环形数据结构，一旦形成环形数据结构，Entry的next节点永远不为空，就会产生死循环，获取Entry】

2.效率低下的HashTable

HashTable用synchronized来保证线程安全，但在线程激烈的情况下HashTable的效率很低，因为当一个线程访问Hashtable的同步方法，其他线程也访问HashTable同步方法的同时，会进入阻塞或轮询状态。

【在线程激烈的情况下HashTable的效率很低的原因：所有访问HashTable的线程必须竞争同一把锁】

3.ConcurrentHashMap的锁分段技术

假如容器里有多把锁，每一把锁用于锁容器其中一部分数据，那么当多线程访问容器里不同数据段的数据时，线程间就不会存在锁竞争，从而可以有效提高并发访问效率，这就是锁分段技术。

【将数据分成一段一段地存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问】

二、ConcurrentHashMap的结构

底层数据结构：

• JDK1.7底层采用分段的数组+链表实现

• JDK1.8 采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。

（1）JDK1.7

• 提供了一个segment数组，在初始化ConcurrentHashMap的时候可以指定数组的长度，默认是16，一旦初始化后中间不可扩容。

• 在每个segment中都可以挂一个HashEntry数组，数组里面可以存储具体的元素，HashEntry数组是可以扩容的

• 在HashEntry存储的数组中存储的元素，若发生冲突，则可以挂单向链表。

• 先去计算key的hash值，然后确定segment数组下标

• 再通过hash值确定hashEntry数组中的下标存储数据

• 在进行操作数据的之前，会先判断当前segment对应下标位置是否有线程进行操作，为了线程安全使用的是ReentrantLock进行加锁，如果获取锁是被会使用cas自旋锁进行尝试

（2) JDK1.8

采用 CAS + Synchronized来保证并发安全进行实现

• CAS控制数组节点的添加

• synchronized只锁定当前链表或红黑二叉树的首节点，只要hash不冲突，就不会产生并发的问题 , 效率得到提升

总结：

• 在jdk1.7中 ConcurrentHashMap 里包含一个 Segment 数组。Segment 的结构和HashMap类似，是一 种数组和链表结构，一个 Segment 包含一个HashEntry 数组，每个 HashEntry 是一个链表结构 的元素，每个 Segment 守护着一个HashEntry数组里的元素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment的锁。

• Segment 是一种可重入的锁 ReentrantLock，每个 Segment 守护一个HashEntry 数组里得元 素，当对 HashEntry 数组的数据进行修改时，必须首先获得对应的 Segment 锁

• 在jdk1.8中的ConcurrentHashMap 做了较大的优化，性能提升了不少。首先是它的数据结构与jdk1.8的hashMap数据结构完全一致。其次是放弃了Segment臃肿的设计，取而代之的是采用Node + CAS + Synchronized来保 证并发安全进行实现，synchronized只锁定当前链表或红黑二叉树的首节点，这样只要hash不冲 突，就不会产生并发 , 效率得到提升

三、扩容机制

HashMap:

【负载因子为什么是0.75，这个在源码中有一段注释说明了，大致意思就是在时间和空间成本权衡而来，太小的值会浪费大部分空间，太大的值会增加get和put等操作的查找成本，还有根据泊松分布计算后得出的结论】

在JDK1.7的扩容机制相对简单，有以下特质：

• 空参数的构造函数：以默认容量、默认负载因子、默认阈值初始化数组。内部数组是空数组。

• 有参构造函数：根据参数确定容量、负载因子、阈值等。

• 第一次put时会初始化数组，其容量变为不小于指定容量的2的幂数。然后根据负载因子确定阈值。

• 如果不是第一次扩容，则 新容量=旧容量X2 新阈值=新容量X负载因子

JDK1.8下的**HashMap的容量变化通常存在以下几种情况**：

• 空参数的构造函数：实例化的HashMap默认内部数组是null，即没有实例化。第一次调用put方法时，则会开始第一次初始化扩容，长度为16。

• 有参构造函数：用于指定容量。会根据指定的正整数找到不小于指定容量的2的幂数，将这个数设置赋值给阈值（threshold）。第一次调用put方法时，会将阈值赋值给容量，然后让 阈值=容量X负载因子（因此并不是指定了容量就一定不会触发扩容，超过阈值后一样会扩容！！）

• 如果不是第一次扩容，则容量变为原来的2倍，阈值也变为原来的2倍。

【注：1.7 是大于阈值（threshold = factor * capacity ）且没有空位时才扩容，而 1.8 是大于阈值就扩容；1.7是先扩容再插入数据，1.8是先插入数据再扩容；HashMap的容量达到2的30次方，就不会再进行扩容了】

    ConcurrentHashMap的扩容条件和hashmap一样，集合内元素达到阈值或者链表长度达到8时扩容，不同的是CHM是线程安全的，支持多线程扩容，考虑的更多，也更为复杂。在JDK1.8中 CHM采用了CAS（CompareAndSwap，比较置换）+ synchronized 的方法来保证并发安全。CAS主要用到的主要属性sizeCtl，sizeCtl默认为0，当sizeCtl为负数时代表正在扩容或者初始化，当sizeCtl为正数时代表当前集合的扩容阈值，table为当前集合的数组。