java八股文面试[数据结构]——ConcurrentHashMap原理

HashMap不是线程安全：
在并发环境下，可能会形成环状链表（扩容时可能造成，具体原因自行百度google或查看源码分析），导致get操作时，cpu空转，所以，在并发环境中使用HashMap是非常危险的

HashTable是线程安全的：

HashTable和HashMap的实现原理几乎一样，
与HashMap的差别：
HashTable不允许key和value为null；
HashTable是线程安全的。

HashTable线程安全的策略实现代价却比较大，get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁，多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，见下图：
在这里插入图片描述

ConcurrentHashMap底层实现

JDK1.7

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

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

一个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 直接操作的是缓存中的数据。但在多处理器下，将可能导致各自的缓存数据不一致（这也是可见性问题的由来），为了保证各个处理器的缓存是一致的，就会实现缓存一致性协议，而嗅探是实现缓存一致性的常见机制。
在这里插入图片描述

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

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

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

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

volatile 的原子性问题

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

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

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

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

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

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

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

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

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

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

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

1.7结构图

在这里插入图片描述

整个ConcurrentHashMap是由一个一个的Segment组成，Segment代表一个分段，一个Segment里面包含一个HashEntry数组，每个HashEntry是一个链表结构，当对HashEntry数据的数据进行修改时，必须先获取与它对应的Segment锁。

1.8结构图

在这里插入图片描述

摒弃了Segment的概念，而是直接通过Node数组+ 链表+红黑树的数据结构来实现，并发控制使用Synchronized和CAS来操作。 树形结构查找效率 logn

总结与思考

其实可以看出JDK1.8版本的ConcurrentHashMap的数据结构已经接近HashMap，相对而言，ConcurrentHashMap只是增加了同步的操作来控制并发，

从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+红黑树,相对而言，

总结如下思考

JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segment的，包含多个HashEntry，而JDK1.8锁的粒度就是HashEntry（首节点）
JDK1.8版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用synchronized来进行同步，所以不需要分段锁的概念，也就不需要Segment这种数据结构了，由于粒度的降低，实现的复杂度也增加了
JDK1.8使用红黑树来优化链表，基于长度很长的链表的遍历是一个很漫长的过程，而红黑树的遍历效率是很快的，代替一定阈值的链表，这样形成一个最佳拍档
JDK1.8为什么使用内置锁synchronized来代替重入锁ReentrantLock，我觉得有以下几点
1. 因为粒度降低了，在相对而言的低粒度加锁方式，synchronized并不比ReentrantLock差，在粗粒度加锁中ReentrantLock可能通过Condition来控制各个低粒度的边界，更加的灵活，而在低粒度中，Condition的优势就没有了
2. JVM的开发团队从来都没有放弃synchronized，而且基于JVM的synchronized优化空间更大，使用内嵌的关键字比使用API更加自然
3. 在大量的数据操作下，对于JVM的内存压力，基于API的ReentrantLock会开销更多的内存，虽然不是瓶颈，但是也是一个选择依据