面试系列之-ConcurrentHashMap实现原理（JAVA基础）

concurrentHashMap与hashMap

concurrentHashMap用 transient volatile Node<K,V>[] table修饰，使用volatile来保证某个变量内存的改变对其他线程即时可见，在配合CAS可以实现不加锁对并发操作的支持。get操作可以无锁是由于Node的元素val和指针next是用volatile修饰的，在多线程环境下线程A修改结点的val或者新增节点的时候是对线程B可见的；

• HashMap是线程不安全的，当出现多线程操作时，会出现安全隐患；而ConcurrentHashMap是线程安全的；
• HashMap不支持并发操作，没有同步方法，ConcurrentHashMap支持并发操作，通过继承 ReentrantLock（JDK1.7重入锁）/CAS和synchronized(JDK1.8内置锁，用在如链表树化或者扩容等过程中)来进行加锁（分段锁），每次需要加锁的操作锁住的是一个 segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全；
• HashMap中key和vaule都是可以为null的，而ConcurrentHashMap中key和value是不可以为null的；

ConcurrentHashMap采用锁分段技术，将整个Hash桶进行了分段node，也就是将这个大的数组分成了几个小的片段node，而且每个小的片段node上面都有锁存在，那么在插入元素的时候就需要先找到应该插入到哪一个片段node，然后再在这个片段上面进行插入，而且这里还需要获取node锁；ConcurrentHashMap让锁的粒度更精细一些，并发性能更好；

在jdk1.8里面ConcurrentHashMap锁的粒度，是数组中的某一个节点，而在jdk1.7里面。它锁定的是Segment，锁的范围要更大，所以性能上它会更低。

concurrentHashMap 1.7的实现

JDK1.7中ConcurrentHashMap采用的就是分段锁，就是把整个table分割为n个部分，每个部分就是一个Segment；每个Segment中由HashEntry数组组成，这里的HashEnrty数组结构和HashMap中的相同，由数组+链表组成； 当对某个Segment加锁时，其他的Segment并不会受影响，理想状态下，所有线程操作的都是不同的segment，就可以降低锁的竞争，而且还是线程安全的；

Segment继承于ReentrantLock，tryLock和lock是ReentrantLock中的方法，tryLock不会阻塞，抢锁成功就返回true，失败就返回false，lock方法抢锁成功则返回，失败则会进入同步队列，阻塞等待获取锁；Segment类似于HashMap的结构，内部拥有一个Entry数组，数组中的每个元素又是一个链表，同时又是一个ReentrantLock（Segment继承了ReentrantLock）；

通过key的hash定位到具体的segment，再通过一次hash定位到具体元素，由于 HashEntry 中的 value 属性是用 volatile 关键词修饰的，保证了内存可见性，所以每次获取时都是最新值；

concurrentHashMap 1.8的实现

JDK1.8中的ConcurrentHashMap实现，完全重构了JDK1.7，不再使用分段锁，而是给数组中的每个头节点都加锁，并且用的是synchronized。整体采用CAS+synchronized来保证并发的安全性；JDK1.8的实现降低锁的粒度，JDK1.7版本锁的粒度是基于Segment的，包含多个HashEntry，而JDK1.8锁的粒度就是HashEntry（首节点）；

JDK1.8版本的数据结构变得更加简单，使得操作也更加清晰流畅，因为已经使用synchronized来进行同步，所以不需要分段锁的概念，也就不需要Segment这种数据结构了，由于粒度的降低，实现的复杂度也增加了；

synchronized锁升级

有四种状态：无锁，偏向锁，轻量级锁和重量级锁。

• 当一个对象被创建后，还没有线程进入，这个时候对象处于无锁状态。
• 这时有个线程A访问同步块获取锁时，锁对象会变成偏向锁，这个是通过CAS修改对象头中的锁标识位，偏向锁顾名思义就是偏向第一次获取到他的线程，第二次执行到代码块时，会先判断持有线程是否改变，没有就不用加锁了，避免了额外开销。
• 如果发生了锁竞争，这个时候偏向锁就会升级为轻量级锁，也就是自旋锁，通过不断CAS判断锁对是否被成功获取，长时间的自旋比较消耗性能，所以会控制自旋次数，默认是10次，如果超过次数就会升级为重量级锁，升级后，发生锁竞争，没有获取到锁的就会自动挂起，等待被唤醒；这个升级过程是不可逆的；

put操作

• 判断表是否为空，如果为空就初始化表initTable()，只有一个线程可以初始化成功；
• 如果已经初始化，则找到当前key所在桶是判断是否为空，若为空则通过CAS把新节点插入此位置casTabAt()，只有一个线程可以CAS成功；
• 如果key所在桶不为空，则判断节点的hash值是否为-1，若为-1则说明当前数组正在扩容；
• 如果如果key所在桶不为空，且没在扩容，则给桶中的第一个节点对象加锁synchronized，然后判断是否是链表或者树，然后插入数据；
• 判断链表长度是否大于8，如果是链表转为红黑树；

get操作

get方法不用加锁，是非阻塞的，重写Node类，通过volatile修饰next来实现每次获取都是最新值；

JDK1.8为什么使用内置锁synchronized来代替重入锁ReentrantLock

1. 因为粒度降低了，在相对而言的低粒度加锁方式，synchronized并不比ReentrantLock差，在粗粒度加锁中ReentrantLock可能通过Condition来控制各个低粒度的边界，更加的灵活，而在低粒度中，Condition的优势就没有了；
2. 在大量的数据操作下，对于JVM的内存压力，基于API的ReentrantLock会开销更多的内存，虽然不是瓶颈，但是也是一个选择依据；
3. synchronized则是JVM直接支持的，JVM能够在运行时作出相应的优化措施：锁粗化、锁消除、锁自旋等等。这就使得synchronized能够随着JDK版本的升级而不改动代码的前提下获得性能上的提升；

ConcurrentHashMap的键值对为什么不能为null，而HashMap却可以

当通过get(k)获取对应的value时，如果获取到的是null时，无法判断，它是put（k,v）的时候value为null，还是这个key从来没有做过映射；HashMap是非并发的，可以通过contains(key)来做这个判断；而支持并发的Map在调用m.contains(key)和m.get(key)的时候，m可能已经不同了；

concurrentHashMap的扩容

1、如果新增节点之后，所在链表的元素个数达到了阈值 8，则会调用treeifyBin方法把链表转换成红黑树，不过在结构转换之前，会对数组长度进行判断，实现如下：如果数组长度n小于阈值MIN_TREEIFY_CAPACITY，默认是64，则会调用tryPresize方法把数组长度扩大到原来的两倍，并触发transfer方法，重新调整节点的位置；

2、调用put方法新增节点时，在结尾会调用addCount方法记录元素个数，并检查是否需要进行扩容，当数组元素个数达到阈值时，会触发transfer方法，重新调整节点的位置；

扩容状态下其他线程对集合进行插入、修改、删除、合并、compute 等操作时遇到 ForwardingNode 节点会触发扩容 ；

putAll 批量插入或插入节点后发现存在链表长度达到 8 个或以上，但数组长度为 64 以下时会触发扩容 ；

注意：桶链表长度达到 8 个或以上，并且数组长度为 64 以下时只会触发扩容而不会将链表转为红黑树 ；

当数组长度不够的时候，ConcurrentHashMap它需要对数组进行扩容,而在扩容时间上，ConcurrentHashMap引入了多线程并发扩容的一个实现，简单来说多个线程对原始数组进行分片，分片之后，每个线程去负责一个分片的数据迁移，从而去整体的提升了扩容过程中的数据迁移的一个效率；

扩容期间在未迁移到的hash桶插入数据会发生什么

只要插入的位置扩容线程还未迁移到，就可以插入，当迁移到该插入的位置时，就会阻塞等待插入操作完成再继续迁移 ；

并发情况下，各线程中的数据可能不是最新的，那为什么get方法不需要加锁

get操作全程不需要加锁是因为Node的成员val是用volatile修饰的，在多线程环境下线程A修改结点的val或者新增节点的时候是对线程B可见的；

CAS算法在ConcurrentHashMap中的应用

• CAS是一种乐观锁，在执行操作时会判断内存中的值是否和准备修改前获取的值相同，如果相同，把新值赋值给对象，否则赋值失败，整个过程都是原子性操作，无线程安全问题；
• ConcurrentHashMap的put操作是结合自旋用到了CAS，如果hash计算出的位置的槽点值为空，就采用CAS+自旋进行赋值，如果赋值是检查值为空，就赋值，如果不为空说明有其他线程先赋值了，放弃本次操作，进入下一轮循环；