简单谈谈ConcurrentHashMap

Briefly talk about ConcurrentHashMap

Posted by if on 2021-11-05
Estimated Reading Time 5 Minutes
Words 1.5k In Total

简单谈谈ConcurrentHashMap

前言

本文学习与B站ConcurrentHashMap底层原理剖析

本文只简单讲解ConcurrentHashMap的一些面试题,用于理解ConcurrentHashMap,并不会特别深入

如果对于HashMap不熟悉的读者,在阅读本文前可以先阅读我的另一篇博客《简单谈谈HashMap》

ConcurrentHashMap的实现原理是什么?

jdk7原理

JDK7中的ConcurrentHashMap由Segment和HashEntry组成,即ConcurrentHashMap把哈希桶数组切分成小数组(Segment) ,每个小数组有n个HashEntry组成。

分为了多个小数组Segment,并为每个Segment都上了锁,我们称之为分段锁

将数据分为一段一段的存储,然后给每一 段数据配一把锁,当一个线程占用锁访问其中一段数据时,其他段的数

据也能被其他线程访问,实现并发访问。

jdk8原理

ConcurrentHashMap采用了和1.8的hashmap相同的结构:数组+链表+红黑树

在锁的实现上,抛弃了原有的Segment分段锁,采用CAS + synchronized实现更加细粒度的锁。将锁的级别控制在了更细粒度的哈希桶数组元素级别,只需要锁住这个链表头节点(红黑树的根节点), 就不会影响其他的哈希桶数组元素的读写,大大提高了并发度。

get方法需要加锁吗?为什么?

get方法不需要加锁

使用了volatile关键字,保证了内存的可见性

多线程的环境下修改了节点的value和新增了节点对于其他线程是可见的

(在1.7中的HashEntry也是用的volatile修饰value和next,道理一样的)

1
2
3
4
5
6
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
}

ConcurrentHashMap不支持key或value为空的原因是什么?

在很多java资料中,都有提到 ConcurrentHashmap HashMap和Hashtable都是key-value存储结构,但他们有一个不同点是 ConcurrentHashmap、Hashtable不支持key或者value为null,而HashMap是支持的

ConcurrentHashmap和Hashtable都是支持并发的,这样会有一个问题,当你通过get(k)获取对应的value时,如果获取到的是null时,你无法判断,它是put(k,v)的时候value为null,还是这个key从来没有做过映射。

HashMap是非并发的,可以通过contains(key)来做这个判断来进一步分析

而支持并发的ConcurrentHashmap和Hashtable在调用m.contains(key)和m.get(key)时,m可能已经不同了

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

HashMap迭代器是强一致性不同, ConcurrentHashMap 迭代器是弱一致性

ConcurrentHashMap的迭代器创建后,就会按照哈希表结构遍历每个元素

但在遍历过程中,内部元素可能发生变化,如果变化发生在已遍历过的部分,迭代器就不会反映出来

而如果变化发生在未遍历过的部分,迭代器就会发现并反映出来,这就是弱一致性。

这样迭代器线程可以使用原来老的数据,而写线程也可以并发的完成改变,保证了多个线程并发执行的连续性和扩展性,是性能提升的关键。

JDK 7和JDK 8中ConcurrentHashMap的区别是什么?

底层数据结构

  • JDK7底层数据结构是使用Segment组织的数组+链表
  • JDK8中取而代之的是数组+链表+红黑树的结构,在链表节点数量大于8 (且数据总量大于等于64)时,会将链表转化为红黑树进行存储

查询时间复杂度

  • JDK7的遍历链表O(n)
  • JDK8 变成遍历红黑树O(logN)

保证线程安全机制

  • JDK7采用Segment的分段锁机制实现线程安全,其中Segment继承自ReentrantLock
  • JDK8采用CAS+synchronized保证线程安全

锁的粒度

  • JDK7是对需要进行数据操作的Segment加锁
  • JDK8调整为对每个数组元素的头节点加锁

JDK 8中为什么使用同步锁synchronized替换ReentrantLock?

synchronized性能提升

在JDK6中对synchronized锁的实现引入了大量的优化,会从无锁->偏向锁->轻量级锁->重量级锁一步步转换就是锁膨胀的优化,以及有锁的粗化锁消除自适应自旋等优化

提升并发度减少内存开销

CAS + synchronized方式时加锁的对象是每个链条的头结点,相对Segment再次提高了并发度

如果使用可重入锁达到同样的效果,则需要大量继承自ReentrantLock的对象,造成巨大内存浪费。

ConcurrentHashMap的并发度是怎么设计的?

并发度可以理解为程序运行时能够同时更新ConcurrentHashMap且不产生锁竞争的最大线程数

在JDK7中,实际上就是ConcurrentHashMap中的分段锁个数,即Segment[的数组长度,默认是16,这个值可以在构造函数中设置。

如果自己设置了并发度,ConcurrentHashMap会使用大于等于该值的最小的2的幂指数作为实际并发度

如果并发度设置的过小,会带来严重的锁竞争问题

如果并发度设置的过大,原本位于同一个Segment内的访问会扩散到不同的Segment中,引起程序性能下降

因为有着种种限制和问题,在jdk8中进行了优化,抛弃了segment和分段锁,转而锁头结点,结构为数组+链表+红黑树

ConcurrentHashMap和Hashtable的效率哪个更高?为什么?

ConcurrentHashMap比Hashtable效率更高

因为Hashtable给整个哈希表加锁从而实现线程安全

ConcurrentHashMap的锁粒度更低

  • 1.7的分段锁
  • 1.8的CAS+Synchronized锁头结点

多线程下安全的操作Map还有其它方法吗?

使用Hashtable代替

new一个Hashtable用作map,对全表上锁,效率不高,参考上一条问题

1
Map<String, String> hashtable = new Hashtable<>();

使用Collections.synchronizedMap转为SynchronizedMap

Collections的synchronizedMap将HashMap转为线程安全的SynchronizedMap

本质上也是对全表上锁,效率不如ConcurrentHashMap

1
2
HashMap<String, String> map = new HashMap<>();
Map<String, String> synchronizedMap = Collections.synchronizedMap(map);

本个人博客提供的内容仅用于个人学习,不保证内容的正确性。通过使用本站内容随之而来的风险与本站无关!