ConcurrentHashMap底层结构和原理详解

分手后的思念是犯贱 2023-10-01 10:59 19阅读 0赞

## ConcurrentHashMap ##

*  **ConcurrentHashMap是线程安全的数组,是HashTable的替代品,同为线程安全,其性能要比HashTable更好**
 *  **HashMap不是线程安全：**  
    在并发环境下，可能会形成环状链表（扩容时可能造成，具体原因自行百度google或查看源码分析），导致get操作时，cpu空转，所以，在并发环境中使用HashMap是非常危险的
 *  **HashTable是线程安全的**：  
    HashTable和HashMap的实现原理几乎一样，  
    **与HashMap的差别：**  
    HashTable不允许key和value为null；  
    HashTable是线程安全的。
    
    HashTable线程安全的策略实现代价却比较大，get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，见下图：
    
    ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_20_color_FFFFFF_t_70_g_se_x_16]

### ① ConcurrentHashMap底层实现 ###

> JDK1.7

底层数据结构：Segments数组+HashEntry数组+链表，采用**分段锁**保证安全性

**容器中有多把锁，每一把锁锁一段数据，这样在多线程访问时不同段的数据时，就不会存在锁竞争了，这 样便可以有效地提高并发效率。这就是ConcurrentHashMap所采用的”分段锁”思想，见下图：**

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_20_color_FFFFFF_t_70_g_se_x_16 1]

*  一个ConcurrentHashMap中有一个Segments数组，一个Segments中存储一个HashEntry数组，每个HashEntry是一个链表结构的元素。
 *  segment继承自ReentrantLock锁。 首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一段数据时，其他段的数据也能被其他线程访问，实现了真正的并发访问。
 *  可以通过构造函数指定,数组扩容不会影响其他的segment,get无需加锁,volatile保证内存可见性

**get()操作**：

HashEntry中的value属性和next指针是用volatile修饰的，保证了可见性，所以每次获取的都是最新值，get过程不需要加锁。

1.将key传入get方法中，先根据key的hashcode的值找到对应的segment段。

2.再根据segment中的get方法再次hash，找到HashEntry数组中的位置。

3.最后在链表中根据hash值和equals方法进行查找。

ConcurrentHashMap的get操作跟HashMap类似，只是ConcurrentHashMap第一次需要经过一次hash定位到Segment的位置，然后再hash定位到指定的HashEntry，遍历该HashEntry下的链表进行对比，成功就返回，不成功就返回null。

**put()操作**：

1.将key传入put方法中，先根据key的hashcode的值找到对应的segment段

2.再根据segment中的put方法，加锁lock()。

3.再次hash确定存放的hashEntry数组中的位置

4.在链表中根据hash值和equals方法进行比较，如果相同就直接覆盖，如果不同就插入在链表中。

> JDK1.8

底层数据结构：Synchronized + CAS +Node +红黑树.Node的val和next都用volatile保证,保证可见性,查找,替换,赋值操作都使用CAS

> **为什么在有Synchronized 的情况下还要使用CAS**
> 
> 因为CAS是乐观锁,在一些场景中(并发不激烈的情况下)它比Synchronized和ReentrentLock的效率要高,当CAS保障不了线程安全的情况下(扩容或者hash冲突的情况下)转成Synchronized 来保证线程安全,大大提高了低并发下的性能.

锁 : 锁是锁的链表的head的节点,不影响其他元素的读写,锁粒度更细,效率更高,扩容时,阻塞所有的读写操作(因为扩容的时候使用的是Synchronized锁,锁全表),并发扩容.

读操作无锁 :

*  Node的val和next使用volatile修饰,读写线程对该变量互相可见
 *  数组用volatile修饰,保证扩容时被读线程感知

**get()操作**：

get操作全程无锁。get操作可以无锁是由于Node元素的val和指针next是用volatile修饰的。

在多线程环境下线程A修改节点的val或者新增节点的时候是对线程B可见的。

1.计算hash值，定位到Node数组中的位置

2.如果该位置为null，则直接返回null

3.如果该位置不为null，再判断该节点是红黑树节点还是链表节点

如果是红黑树节点，使用红黑树的查找方式来进行查找

如果是链表节点，遍历链表进行查找

**put()操作**：

1.先判断Node数组有没有初始化，如果没有初始化先初始化initTable();

2.根据key的进行hash操作，找到Node数组中的位置，如果不存在hash冲突，即该位置是null，直接用CAS插入

3.如果存在hash冲突，就先对链表的头节点或者红黑树的头节点加synchronized锁

4.如果是链表，就遍历链表，如果key相同就执行覆盖操作，如果不同就将元素插入到链表的尾部， 并且在链表长度大于8， Node数组的长度超过64时，会将链表的转化为红黑树。

5.如果是红黑树，就按照红黑树的结构进行插入。

### ② 总线嗅探机制 ###

使用 volatile 修饰共享变量后，每个线程要操作变量时会从主内存中将变量拷贝到本地内存作为副本，当线程操作变量副本并写回主内存后，会通过 **CPU 总线嗅探机制**告知其他线程该变量副本已经失效，需要重新从主内存中读取。

volatile 保证了不同线程对共享变量操作的可见性，也就是说一个线程修改了 volatile 修饰的变量，当修改后的变量写回主内存时，其他线程能立即看到最新值。

--------------------

在现代计算机中，CPU 的速度是极高的，如果 CPU 需要存取数据时都直接与内存打交道，在存取过程中，CPU 将一直空闲，这是一种极大的浪费，所以，为了提高处理速度，CPU 不直接和内存进行通信，而是在 CPU 与内存之间加入很多寄存器，多级缓存，它们比内存的存取速度高得多，这样就解决了 CPU 运算速度和内存读取速度不一致问题。

由于 CPU 与内存之间加入了缓存，在进行数据操作时，先将数据从内存拷贝到缓存中，CPU 直接操作的是缓存中的数据。但在多处理器下，将可能导致各自的缓存数据不一致（这也是可见性问题的由来），为了保证各个处理器的缓存是一致的，就会实现缓存一致性协议，而**嗅探是实现缓存一致性的常见机制**。

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_20_color_FFFFFF_t_70_g_se_x_16 2]

> 注意，缓存的一致性问题，不是多处理器导致，而是多缓存导致的。

**嗅探机制工作原理**：每个处理器通过监听在总线上传播的数据来检查自己的缓存值是不是过期了，如果处理器发现自己缓存行对应的内存地址修改，就会将当前处理器的缓存行设置无效状态，当处理器对这个数据进行修改操作的时候，会重新从主内存中把数据读到处理器缓存中。

> 注意：基于 CPU 缓存一致性协议，JVM 实现了 volatile 的可见性，但由于总线嗅探机制，会不断的监听总线，如果大量使用 volatile 会引起总线风暴。所以，volatile 的使用要适合具体场景。

使用 volatile 和 synchronized 锁都可以保证共享变量的可见性。相比 synchronized 而言，volatile 可以看作是一个轻量级锁，所以使用 volatile 的成本更低，因为它不会引起线程上下文的切换和调度。但 volatile 无法像 synchronized 一样保证操作的原子性。

**volatile 的原子性问题**

所谓的原子性是指在一次操作或者多次操作中，要么所有的操作全部都得到了执行并且不会受到任何因素的干扰而中断，要么所有的操作都不执行。

在多线程环境下，volatile 关键字可以保证共享数据的可见性，但是并不能保证对数据操作的原子性。也就是说，多线程环境下，使用 volatile 修饰的变量是**线程不安全的**。

要解决这个问题，我们可以使用锁机制，或者使用原子类（如 AtomicInteger）。

这里特别说一下，对任意单个使用 volatile 修饰的变量的读 / 写是具有原子性，但类似于 `flag = !flag` 这种复合操作不具有原子性。简单地说就是，**单纯的赋值操作是原子性的**。

### ③ 有关ConcurrentHashMap的一些问题 ###

#### 1、JDK1.8中为什么使用synchronized替换可重入锁ReentrantLock？ ####

Segment继承了ReentrantLock，所以Segment是一种可重入锁。

1.**Segment可重入锁锁住的是一个HashEntry数组，synchronized锁住的只是发生hash冲突的链表\]的头节点或红黑树的节点，提高了并发性能**。

2.从JDK1.6开始，对 synchronized 锁的实现引入了大量的优化，并且 synchronized 有多种锁状态，会从偏向锁 -> 轻量级锁 -> 重量级锁一步步转换。

只要并发的线程可以在一定次数的自旋内拿到锁（偏向锁不用自旋），那么synchronized就不会升级为重量级锁，等待的线程也不会被挂起，减少了线程挂起和唤醒的切换的过程开销。

而ReentrantLock不会自旋，会直接挂起，这样一来就很容易会多出线程上下文开销的代价。

3.减少内存开销 。假设使用可重入锁来获得同步支持，那么每个节点都需要通过继承 AQS 来获得同步支持。但并不是每个节点都需要获得同步支持的，只有链表\]的头节点（红黑树的根节点）需要同步，这无疑带来了巨大内存浪费。

#### 2、ConcurrentHashMap和Hashtable的区别？ ####

1.**底层数据结构**：

JDK1.7的ConcurrentHashMap底层采用：Segments数组+HashEntry数组+链表

JDK1.8的ConcurrentHashMap底层采用：Node数据+链表+红黑树

Hashtable底层数据结构采用：数组+链表

2.**实现线程安全的方式**：

在JDK1.7中ConcurrentHashMap采用分段锁实现线程安全。

在JDK1.8中ConcurrentHashMap采用synchronized和CAS来实现线程安全。

Hashtable采用synchronized来实现线程安全。在方法上加synchronized同步锁。

#### 3、HashMap与ConcurrentHashMap的区别？ ####

HashMap是非线程安全的，这意味着不应该在多线程中对这些Map进行修改操作，否则会产生数据不 一致的问题，甚至还会因为并发插入元素而导致链表成环，这样在查找时就会发生死循环，影响到整个应用程序。

Collections工具类可以将一个Map转换成线程安全的实现，其实也就是通过一个包装类，然后把所有功能都委托给传入的Map，而包装类是基于synchronized关键字来保证线程安全的（Hashtable也是基于synchronized关键字），底层使用的是互斥锁，性能与吞吐量比较低。

ConcurrentHashMap的实现细节远没有这么简单，因此性能也要高上许多。

它没有使用一个全局锁来锁住自己，而是采用了减少锁粒度的方法，尽量减少因为竞争锁而导致的阻塞与冲突，而且ConcurrentHashMap的检索操作是不需要锁的。

#### 4、ConcurrentHashMap是怎么分段分组的？ ####

**get操作：**

Segment的get操作实现非常简单和高效，先经过一次再散列，然后使用这个散列值通过散列运算定位到 Segment，再通过散列算法定位到元素。get操作的高效之处在于整个**get过程都不需要加锁**，除非读到空的值才会加锁重读。原因就是将使用的共享变量定义成 volatile 类型。

**put操作：**

当执行put操作时，会经历两个步骤：

1.  判断是否需要扩容；
2.  定位到添加元素的位置，将其放入 HashEntry 数组中。

插入过程会进行第一次 key 的 hash 来定位 Segment 的位置，如果该 Segment 还没有初始化，即通过CAS 操作进行赋值，然后进行第二次 hash 操作，找到相应的 HashEntry 的位置，这里会利用继承过来的锁的特性，在将数据插入指定的 HashEntry 位置时（尾插通过继承 ReentrantLock 的 tryLock() 方法尝试去获锁，如果获取成功就直接插入相应的位置，如果已经有线程获取该 Segment的锁，那当前线程会以自旋的方式去继续的调用 tryLock() 方法去获取锁，超过指定次数就挂起，等待唤醒。

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/41ba8193ef704506875b4efa4d29f79f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3blsZXnpLo=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/1fbe63ca461c4af591036dd9ce364a14.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3blsZXnpLo=,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBAY3blsZXnpLo_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/2f19b5673c55495395727b68761bdee5.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAY3blsZXnpLo=,size_20,color_FFFFFF,t_70,g_se,x_16