Java后端面试高频问题：ConcurrentHashMap

1.ConcurrentHashMap底层实现

JDK1.7

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

一个ConcurrentHashMap中有一个Segments数组，一个Segments中存储一个HashEntry数组，每个HashEntry是一个链表结构的元素。

segment继承自ReentrantLock锁。

首先将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一段数据时，其他段的数据也能被其他线程访问，实现了真正的并发访问。

get()操作：

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

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

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

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

put()操作：

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

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

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

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

JDK1.8

底层数据结构：Node数组+链表+红黑树 采用Synchronized和CAS来保证线程安全。

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时，会将链表的转化为红黑树。

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

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

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

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

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

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

3.ConcurrentHashMap和Hashtable的区别？

1.底层数据结构：

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

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

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

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

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

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

4.HashMap与ConcurrentHashMap的区别？

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

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

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

5.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() 方法去获取锁，超过指定次数就挂起，等待唤醒。