StarAndroid

Appearance

讲一下ConcurrentHashMap为什么快 ​

主要还是要对比HashMap和HashTable的设计来回答，为什么快 回答的点有

  1. 他们的数据结构设计有什么不同
  2. jdk1.7和jdk1.8后ConcurrentHashMap的设计本身有什么变化

ConcurrentHashMap与HashMap有什么区别？ ​

  1. 数据结构

HashMap的数据结构是数组+链表实现的，主体是数组，链表是为了解决Hash冲突。 在JDK1.7中ConcurrentHashMap底层采用分段数组+HashEntry数组+链表的方式实现。 在JDK1.8中ConcurrentHashMap与JDK1.8中的HashMap底层数据结构一样，都是采用数组+链表或者数组+红黑树的方式实现。这二者底层数据结构都是以数组为主体的。、

  1. 线程安全

HashMap是线程不安全的，如果在并发的情况下使用HashMap，可能**【数据覆盖的问题】**；ConcurrentHashMap是线程安全的

ConcurrentHashMap的实现原理 ​

ConcurrentHashMap的数据结构 ​

对于JDK1.7版本的实现，ConcurrentHashMap 为了提高本身的并发能力，在内部采用了Segment数组+HashEntry数组+链表 ConcurrentHashMap 定位一个元素的过程需要进行两次Hash操作，第一次 Hash 定位到 Segment，第二次 Hash 定位到元素所在的链表的头部，因此，这一种结构的带来的副作用是 Hash 的过程要比普通的 HashMap 要长，但是带来的好处是写操作的时候可以只对元素所在的 Segment 进行操作即可，不会影响到其他的 Segment。 在最理想的情况下，ConcurrentHashMap 可以最高同时支持 Segment 数量大小的写操作（刚好这些写操作都非常平均地分布在所有的 Segment上），所以，通过这一种结构，ConcurrentHashMap 的并发能力可以大大的提高。 image.png JDK 1.8中抛弃了原有的 Segment 分段锁，来保证采用Node + CAS + Synchronized来保证并发安全性。取消类 Segment，直接用table 数组存储键值对；当 Node对象组成的链表长度超过TREEIFY_THRESHOLD 时，链表转换为红黑树，提升性能。底层变更为数组 + 链表 + 红黑树。 image.png

ConcurrentHashMap的写操作 ​

  • 如果没有初始化，就调用initTable()方法对数组进行初始化；
  • 如果没有hash冲突则直接通过CAS进行无锁插入；
  • 如果需要扩容，就先进行扩容，扩容为原来的两倍；
  • 如果存在hash冲突，就通过加锁的方式进行插入，从而保证线程安全。（如果是链表就按照尾插法插入，如果是红黑树就按照红黑树的数据结构进行插入）；
  • 如果达到链表转红黑树条件，就将链表转为红黑树；
  • 如果插入成功就调用addCount()方法进行计数并且检查是否需要扩容；

image.png

ConcurrentHashMap的读操作 ​

image.png

ConcurrentHashMap和HashTable谁效率更高 ​

ConcurrentHashMap的效率要高于HashTable，因为HashTable是使用一把锁锁住整个链表结构从而实现线程安全。 而ConcurrentHashMap的锁粒度更低，在JDK1.7中采用分段锁实现线程安全，在JDK1.8中采用CAS（无锁算法）+Synchronized实现线程安全。 追问：具体说说他们的锁机制？ HashTable的锁机制是使用一把🔒锁住整个HashTable，同一时刻只能允许一个线程对它进行写操作的话，其他线程就不能对它读和写，只能阻塞等待 而ConcurrentHashMap（主要分为1.7和1.8来回答，锁的粒度是如何降低的）

ConcurrentHashMap的get()方法需要加锁吗？ ​

或者换种问法：ConcurrentHashMap是写变快还是读变快？ 不需要，get操作可以无锁是由于：

  1. Node的元素val和指针next是用volatile修饰的，保证可见性,
  2. 在多线程环境下线程A修改结点的val或者新增节点的时候是对线程B可见的。

追问：为什么volatile可以保证可见性 ​

这里可能会追问volatile的知识点，设计JVM的内存模型 使用 volatile 修饰共享变量后，每个线程要操作变量时会从主内存中将变量拷贝到本地内存作为副本，当线程操作变量副本并写回主内存后，会通过 CPU 总线嗅探机制告知其他线程该变量副本已经失效，需要重新从主内存中读取。 volatile 保证了不同线程对共享变量操作的可见性，也就是说一个线程修改了 volatile 修饰的变量，当修改后的变量写回主内存时，其他线程能立即看到最新值。

原文链接： 为什么HashMap线程不安全？以及实现HashMap线程安全的解决方案_hashmap线程安全吗 什么解决方案_gougege0514的博客-CSDN博客

扩展：HashMap HashMap夺命连环问，你觉着能答上一半吗？

扩展：关于volatile为什么能保证可见性和 Java 经典面试题：为什么 ConcurrentHashMap 的读操作不需要加锁？ - 腾讯云开发者社区-腾讯云 总结下来： 第一：使用volatile关键字会强制将修改的值立即写入主存； 第二：使用volatile关键字的话，当线程2进行修改时，会导致线程1的工作内存中缓存变量的缓存行无效（反映到硬件层的话，就是CPU的L1或者L2缓存中对应的缓存行无效）； 第三：由于线程1的工作内存中缓存变量的缓存行无效，所以线程1再次读取变量的值时会去主存读取。 值得注意的是我们的volatile关键字是加在

java
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    //可以看到这些都用了volatile修饰
    volatile V val;//保证get操作时的可见性
    volatile Node<K,V> next;//保证Node扩容时候的可见性
	···
}

在1.8中ConcurrentHashMap的get操作全程不需要加锁，这也是它比其他并发集合比如hashtable、用Collections.synchronizedMap()包装的hashmap;安全效率高的原因之一。 get操作全程不需要加锁是因为Node的成员val是用volatile修饰的和数组用volatile修饰没有关系。 数组用volatile修饰主要是保证在数组扩容的时候保证可见性。