[toc] ## ConcurrentHashMap的实现原理是什么? ### JDK7  1. 结构上，JDK7中的ConcurrentHashMap由`Segment`和`HashEntry`组成，即ConcurrentHashMap把哈希桶数组切分成小数组(Segment) ，每个小数组有n个HashEntry组成。 2. 锁实现上，将数据分为一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一段数据时，其他段的数据也能被其他线程访问，实现并发访问。 #### Segment源码解读  Segment是ConcurrentHashMap的一个内部类主要的组成，继承自`ReentrantLock`。volatile修饰`HashEntry<K, V>[] table`可以保证在数组扩容时的可见性。 #### HashEntry<K,V>源码  volatile修饰HashEntry的数据value和下一个节点next, 保证了多线程环境下数据获取时的可见性! ### JDK8  1. 结构上，JDK8中的ConcurrentHashMap选择了与HashMap相同的Node数组+链表+红黑树结构； 2. 在锁的实现上，抛弃了原有的Segment分段锁，采用`CAS` + `synchronized`实现更加细粒度的锁。将锁的级别控制在了更细粒度的哈希桶数组元素级别，只需要锁住这个链表头节点(红黑树的根节点)，就不会影响其他的哈希桶数组元素的读写，大大提高了并发度。 #### Node<K,V>  ### JDK7和JDK8中ConcurrentHashMap的区别是什么? - 底层**数据结构**: JDK7底层数据结构是使用Segment组织的数组+链表，JDK8中取而代之的是数组+链表+红黑树的结构,在链表节点数量大于8 (且数据总量大于等于64)时，会将链表转化为红黑树进行存储。 - 查询**时间复杂度**:从JDK7的遍历链表0(n)，JDK8 变成遍历红黑树0(logN)。 - 保证**线程安全机制**: JDK7 采用Segment的分段锁机制实现线程安全，其中Segment继承自ReentrantLock。 JDK8采用CAS+synchronized保证线程安全。 - **锁的粒度**: JDK7 是对需要进行数据操作的Segment加锁，JDK8 调整为对每个数组元素的头节点加锁。 ## 基本特点 ### ConcurrentHashMap的get方法需要加锁吗?为什么? get过程不需要加锁，除非读到值是空值的时候才需要加锁重读。JDK8中，因为Node和HashEntry的**元素value**和**指针next**是用`volatile`修饰的，在多线程环境下线程A修改节点的value或者新增节点的时候是对线程B可见的。 > jdk7，get方法将要使用的共享变量都定义成volatile类型，如用于统计当前Segement大小的count字段和用于存储值的HashEntry的value。 #### 复习一下volatile的内存语义： 定义成volatile的变量，能够在线程之间保持可见性，能够被多线程同时读，并且保证不会读到过期的值，但是只能被单线程写（有一种情况可以被多线程写，就是写入的值不依赖于原值），在get操作里只需要读不需要写共享变量count和value，所以可以不用加锁。之所以不会读到过期的值，是因为根据Java内存模型的`happen before原则`，对volatile字段的**写入操作先于读操作**，即使两个线程同时修改和获取volatile变量，get操作也能拿到最新的值，这是用**volatile替换锁的经典应用场景**。 ### ConcurrentHashMap不支持key或value为null的原因是什么? 因为ConcorrentHashMap工作于多线程环境，如果ConcurrentHashMap.get(key)返回null, 就无法判断值是null，还是没有该key；而单线程的HashMap却可以用containsKey(key)判断是否包含了这个key。 ``` /** * Created by Mr.zihan on 2021/12/23. * connect to cowboy2014@qq.com */ public class ConcurrentHashMapTest { public static void main(String[] args) { ConcurrentHashMap<String, Object> map = new ConcurrentHashMap<>(); // map.put(null, "hello"); //java.lang.NullPointerException map.put("hello", "world"); map.put("world", null); //java.lang.NullPointerException // System.out.println(map.contains(null));//java.lang.NullPointerException System.out.println(map.containsKey("hello")); System.out.println(map.contains("world")); } } ``` 特点：key和value均不能为空； ### ConcurrentHashMap迭代器是强一致性还是弱一 致性? 与HashMap迭代器是强一致性不同， ConcurrentHashMap 迭代器是弱一致性。 ConcurrentHashMap的**迭代器**创建后，就会按照哈希表结构遍历每个元素，但在遍历过程中，内部元素可能会发生变化，如果变化发生在已遍历过的部分，迭代器就不会反映出来，而如果变化发生在未遍历过的部分，迭代器就会发现并反映出来，这就是**弱一致性**。 这样迭代器线程可以使用原来老的数据，而写线程也可以并发的完成改变，保证了多个线程并发执行的连续性和扩展性，是性能提升的关键。 ### JDK8中为什么使用synchronized替换Reentrantlock? 1. synchronized性能提升，在JDK6中对synchronized锁的实现引入了大量的优化，会从无锁->偏向锁-> 轻量级锁 ->重量级锁一步步转换就是锁膨胀的优化。以及有锁的粗化锁消除自适应自旋等优化。 2. 提升并发度和减少内存开销，CAS + synchronized方式时加锁的对象是每个链条的头结点，相对Segment再次提 高了并发度。如果使用可重入锁达到同样的效果，则需要大量继承自ReentrantLock的对象，造成巨大内存浪费。 ### ConcurrentHashMap的并发度是怎么设计的? **并发度概念**：可以理解为程序运行时能够同时更新ConccurentHashMap且不产生锁竞争的最大线程数。 1. 在JDK7中，实际上就是ConcurrentHashMap中的分段锁个数，即Segment[]的数组长度， 默认是16, 这个值可以 在构造函数中设置。 2. 如果自己设置了并发度，ConcurrentHashMap 会使用大于等于该值的最小的2的幂指数作为实际并发度。如果并 发度设置的过小，会带来严重的锁竞争问题;如果并发度设置的过大，原本位于同一个Segment内的访问会扩散 到不同的Segment中，从而引起程序性能下降。 3. 在JDK8中，已经摒弃了Segment的概念，选择了Node数组+链表+红黑树结构，并发度大小依赖于数组的大小。 ### ConcurrentHashMap和Hashtable的效率哪个更高?为什么? ConcurrentHashMap的效率要高于Hashtable。 1. 因为Hashtable给整个哈希表加锁从而实现线程安全。 2. 而ConcurrentHashMap的锁粒度更低: 在JDK7中采用Segment锁(分段锁)实现线程安全 在JDK8中采用CAS+synchronized实现线程安全。 ### 多线程下安全的操作Map还有其它方法吗? 可以使用Collections.synchronizedMap(Map类型的对象)方法进行加同步锁。把对象转换成SynchronizedMap<K, V>类型。 如果传入的是HashMap对象，其实也是对HashMap做的方法做了一层包装，里面使用**对象锁**（mutex）来保证多线程场景下，线程安全，本质也是对HashMap进行全表锁。在竞争激烈的多线程环境下性能依然也非常差，不推荐使用！ `java.util.Collections.SynchronizedMap`： ``` private static class SynchronizedMap<K,V> implements Map<K,V>, Serializable { private static final long serialVersionUID = 1978198479659022715L; private final Map<K,V> m; // Backing Map final Object mutex; // Object on which to synchronize SynchronizedMap(Map<K,V> m) { this.m = Objects.requireNonNull(m); mutex = this; } SynchronizedMap(Map<K,V> m, Object mutex) { this.m = m; this.mutex = mutex; } public int size() { synchronized (mutex) {return m.size();} } } ```