Java容器 --- ConcurrentHashMap分析

ConcurrentHashMap 引出

HashMap在多线程环境下存在线程安全问题，一般的解决方案：

使用Collections.synchronizedMap(Map)：创建线程安全的map集合；ps：在SynchronizedMap内部维护了一个普通对象Map，还有排斥锁mutex。最终结果是map的所有方法都上锁。该方法是Collections类中的静态方法，返回的是一个线程安全的HashMap
Hashtable：HashTable和HashMap一样都实现了Map接口，但是HashTable是一个线程安全的类。在HashTable中，使用的是同一个锁，所以当一个线程操作某一个功能时，其他线程想要操作另外的功能就要等待锁被让出来，比如get方法。
ConcurrentHashMap：concurrentHashMap采用了【锁分段】技术，不同的地方使用了不同的锁，功能之间的锁不一样，操作不同功能时就不再需要等待，这样就大大提高了执行效率。

ps：Hashtable与ConcurrentHashMap的区别

hashtable全表锁

jdk1.7分段锁

jdk1.8锁定Node节点（CAS + synchronized实现）

ConcurrentHashMap 的实现原理是什么？

底层数据结构和HashMap jdk1.7和jdk1.8基本一致（查询时间复杂度不同）。

多线程并发问题：

put数据丢失（被覆盖）
resize时导致循环链表问题，调用get方法死循环

ConcurrentHashMap 在 JDK1.7 和 JDK1.8 解决并发安全问题（安全机制：粒度不同）

jdk7采用分段锁+ReentrantLock。每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。
JDK1.8 的时候已经摒弃了 Segment 的概念，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6 以后对 synchronized 锁做了很多优化）

拓展：CAS是什么？自旋又是什么？

CAS 是乐观锁的一种实现方式，是一种轻量级锁，JUC 中很多工具类的实现就是基于 CAS 的。
CAS 操作：线程在读取数据时不进行加锁，在准备写回数据时，比较原值是否修改，若未被其他线程修改则写回，若已被修改，则重新执行读取流程。
存在ABA问题：版本号机制 / 时间戳解决。

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

在 JDK1.6 中，对 synchronized 锁的实现引入了大量的优化，并且 synchronized 有多种锁状态，会从无锁 -> 偏向锁 -> 轻量级锁 -> 重量级锁一步步转换。
减少内存开销。假设使用可重入锁来获得同步支持，那么每个节点都需要通过继承 AQS 来获得同步支持。但并不是每个节点都需要获得同步支持的，只有链表的头节点（红黑树的根节点）需要同步，这无疑带来了巨大内存浪费。

拓展：什么是可重入锁？有哪些？

广义上的可重入锁指的是可重复可递归调用的锁，在外层使用锁之后，在内层仍然可以使用，并且不发生死锁（前提得是同一个对象或者class），这样的锁就叫做可重入锁。ReentrantLock和synchronized都是可重入锁。但是，ReentrantLock 和 synchronized 不一样，需要手动释放锁，所以使用 ReentrantLock的时候一定要手动释放锁，并且加锁次数和释放次数要一样（不然会死锁）。ps：一般而言，可重入的函数一定是线程安全的，反之则不一定成立。

拓展：synchronized的可重入怎么实现？

每个锁关联一个线程持有者和一个计数器。当计数器为0时表示该锁没有被任何线程持有，那么任何线程都都可能获得该锁而调用相应方法。当一个线程请求成功后，JVM会记下持有锁的线程，并将计数器计为1。此时其他线程请求该锁，则必须等待。而该持有锁的线程如果再次请求这个锁，就可以再次拿到这个锁，同时计数器会递增。当线程退出一个synchronized方法/块时，计数器会递减，如果计数器为0则释放该锁。

拓展：ReentrantLock还可以实现公平锁机制。什么叫公平锁呢？也就是在锁上等待时间最长的线程将获得锁的使用权。通俗的理解就是谁排队时间最长谁先执行获取锁。

ConcurrentHashMap 的 put 方法执行逻辑是什么？

jdk1.7：

先定位到相应的 Segment ，然后再进行 put 操作。
首先会尝试获取锁，如果获取失败肯定就有其他线程存在竞争，则利用 scanAndLockForPut() 自旋获取锁。
- 尝试自旋获取锁。
- 如果重试的次数达到了 MAX_SCAN_RETRIES 则改为阻塞锁获取，保证能获取成功。

jdk1.8：

根据 key 计算出 hash 值；
判断是否需要进行初始化；
定位到 Node，拿到首节点 f，判断首节点 f：
- 如果为 null ，则通过 CAS 的方式尝试添加；
- 如果为 f.hash = MOVED = -1 ，说明其他线程在扩容，参与一起扩容；
- 如果都不满足，synchronized 锁住 f 节点，判断是链表还是红黑树，遍历插入；
当在链表长度达到 8 的时候，数组扩容或者将链表转换为红黑树。

ConcurrentHashMap 的 get 方法执行逻辑是什么？

jdk1.7：

首先，根据 key 计算出 hash 值定位到具体的 Segment ;
再根据 hash 值获取定位 HashEntry 对象
并对 HashEntry 对象进行链表遍历，找到对应元素。

由于 HashEntry 涉及到的共享变量都使用 volatile 修饰，volatile 可以保证内存可见性，所以每次获取时都是最新值。

jdk1.8：

根据 key 计算出 hash 值，判断数组是否为空；
如果是首节点，就直接返回；
如果是红黑树结构，就从红黑树里面查询；
如果是链表结构，循环遍历判断。

ConcurrentHashMap 的 get 方法是否要加锁，为什么？

get 方法不需要加锁。因为 Node 的元素 value 和指针 next 是用 volatile 修饰的，在多线程环境下线程A修改节点的 value 或者新增节点的时候是对线程B可见的。

这也是它比其他并发集合比如 Hashtable、用 Collections.synchronizedMap()包装的 HashMap 效率高的原因之一。

拓展：get 方法不需要加锁与 volatile 修饰的哈希桶数组有关吗？

没有关系。哈希桶数组table用 volatile 修饰主要是保证在数组扩容的时候保证可见性。

拓展：volatile

保证了不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其他线程来说是立即可见的。
禁止进行指令重排序。
volatile 只能保证对单次读/写的原子性。i++ 这种操作不能保证原子性。

为什么Hashtable, ConcurrentHashMap 的 key和value 不能为null（并发角度分析）

ConcurrentHashmap和Hashtable都是支持并发的，二者规定key，value均不能为null，null的话，会抛出空指针异常。

当通过get(k)获取对应的value时，如果获取到的是null时，无法判断，它是put（k,v）的时候value为null，还是这个key从来没有做过映射，出现歧义。假如线程1调用m.contains（key）返回true，然后在调用m.get(key)，这时的m可能已经不同了。因为线程2可能在线程1调用m.contains（key）时，删除了key节点，这样就会导致线程1得到的结果不明确，产生多线程安全问题，因此，Hashtable和ConcurrentHashMap的value不能为null。
key不能为空，因为采用了fail-safe机制，这种机制会使得读取的数据不一定是最新的，使用null值，就会使得其无法判断对应的key是不存在还是为空，因为你无法再调用一次contain(key）来对key是否存在进行判断，HashTable同理。故在入参时，若为 null 就报空指针异常，而且在取hashcode时，压根就没考虑空的情况

HashMap允许key和value为null，在单线程时，调用contains()和get()不会出现问题，但是多线程下，就是线程不安全的。如果要保证线程安全，应该使用ConcurrentHashMap 。

快速失败（fail—fast）

快速失败（fail—fast）是java集合中的一种机制， 在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出Concurrent Modification Exception。

迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个modCount 变量。
集合在被遍历期间如果内容发生变化，就会改变modCount的值。
每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历。

Tip：这里异常的抛出条件是检测到 modCount！= expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。

java.util包下的集合类都是快速失败的，不能在多线程下发生并发修改（迭代过程中被修改）算是一种安全机制吧。

拓展：安全失败（fail—safe）大家也可以了解下，java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。

ConcurrentHashMap 的并发度是什么？

并发度可以理解为程序运行时能够同时更新 ConccurentHashMap且不产生锁竞争的最大线程数。在JDK1.7中，实际上就是ConcurrentHashMap中的分段锁个数，即Segment[]的数组长度，默认是16，这个值可以在构造函数中设置。
如果自己设置了并发度，ConcurrentHashMap 会使用大于等于该值的最小的2的幂指数作为实际并发度，也就是比如你设置的值是17，那么实际并发度是32。
如果并发度设置的过小，会带来严重的锁竞争问题；如果并发度设置的过大，原本位于同一个Segment内的访问会扩散到不同的Segment中，CPU cache命中率会下降，从而引起程序性能下降。
在JDK1.8中，已经摒弃了Segment的概念，选择了Node数组+链表+红黑树结构，并发度大小依赖于数组的大小。

ConcurrentHashMap 迭代器是强一致性还是弱一致性？

与 HashMap 迭代器是强一致性不同，ConcurrentHashMap 迭代器是弱一致性。
ConcurrentHashMap 的迭代器创建后，就会按照哈希表结构遍历每个元素，但在遍历过程中，内部元素可能会发生变化，如果变化发生在已遍历过的部分，迭代器就不会反映出来，而如果变化发生在未遍历过的部分，迭代器就会发现并反映出来，这就是弱一致性。
这样迭代器线程可以使用原来老的数据，而写线程也可以并发的完成改变，更重要的，这保证了多个线程并发执行的连续性和扩展性，是性能提升的关键。

巨人的肩膀：

https://aobing.blog.csdn.net/article/details/103589011
https://blog.csdn.net/yunzhaji3762/article/details/113623168