抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

并发下 Map 常见面试题及参考答案。

作者:IT王小二
博客:https://itwxe.com

面试必问的那些东西,看源码看大概流程,记录下常问的题目及个人理解的参考答案。

一、HashMap 和 HashTable 有什么区别?

1、HashMap 是线程不安全的,HashTable 是线程安全的。
2、由于线程安全,所以 HashTable 的效率比不上 HashMap 。
3、HashMap 最多只允许一条记录的键为 null,允许多条记录的值为 null,而 HashTable 不允许。
4、HashMap 默认初始化数组的大小为 16,HashTable为11,前者扩容时,扩大两倍,后者扩大两倍 + 1 。
5、HashMap 需要重新计算 hash 值,而 HashTable 直接使用对象的hashCode 。

二、Java 中的另一个线程安全的与 HashMap 极其类似的类是什么?同样是线程安全,它与 HashTable 在线程同步上有什么不同?

1、问题1

ConcurrentHashMap 类(是 Java 并发包 java.util.concurrent 中提供的一个线程安全且高效的 HashMap 实现)。

2、问题2

HashTable 是使用 synchronize 关键字加锁的原理(就是对对象加锁)。

而针对 ConcurrentHashMap,在 JDK 1.7 中采用分段锁的方式;JDK 1.8 中直接采用了 CAS(无锁算法)+ synchronized,也采用分段锁的方式并大大缩小了锁的粒度。

三、HashMap & ConcurrentHashMap 的区别?

1、HashMap线程并发下不安全,ConcurrentHashMap线程并发下安全,即HashMap不加锁,而ConcurrentHashMap加锁。

2、HashMap 的键值对允许有 null,但是 ConCurrentHashMap 都不允许。

3、HashMap在数据结构上,实现红黑树的节点类不同。

四、为什么 ConcurrentHashMap 比 HashTable 效率要高?

1、HashTable 使用一把锁(锁住整个链表结构)处理并发问题,多个线程竞争一把锁,容易阻塞,且效率低

2、ConcurrentHashMap

JDK 1.7 中使用分段锁(ReentrantLock + Segment + HashEntry),相当于把一个 HashMap 分成多个段,每段分配一把锁,这样支持多线程访问。锁粒度:基于 Segment,包含多个 HashEntry 。

JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度:Node(首结点)(实现 Map.Entry<K,V>)。锁粒度降低了。

五、针对 ConcurrentHashMap 锁机制具体分析(JDK 1.7 VS JDK 1.8)?

1、JDK 1.7 中,采用分段锁的机制,实现并发的更新操作,底层采用数组+链表的存储结构,包括两个核心静态内部类 Segment 和 HashEntry。

  • Segment 继承 ReentrantLock(重入锁) 用来充当锁的角色,每个Segment 对象守护每个散列映射表的若干个桶
  • HashEntry 用来封装映射表的键-值对
  • 每个桶是由若干个 HashEntry 对象链接起来的链表

2、JDK 1.8 中,采用 CAS + Synchronized + Node 来保证并发安全。取消类Segment,直接用 table 数组存储键值对;当 HashEntry 对象组成的链表长度超过 TREEIFY_THRESHOLD 时,链表转换为红黑树,提升性能。底层变更为数组 + 链表 + 红黑树。

六、ConcurrentHashMap 在 JDK 1.8 中,为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock?

1、JVM 开发团队在 1.8 中对 synchronized 做了大量性能上的优化,而且基于 JVM 的 synchronized 优化空间更大,更加自然。
2、在大量的数据操作下,对于 JVM 的内存压力,基于 API 的ReentrantLock 会开销更多的内存。

七、ConcurrentHashMap 简单介绍?

1、重要的常量:private transient volatile int sizeCtl;

  • 当为负数时,-1 表示正在初始化,-N 表示 N - 1 个线程正在进行扩容。
  • 当为 0 时,表示 table 还没有初始化。
  • 当为其他正数时,表示初始化或者下一次进行扩容的大小。

2、数据结构:

  • Node 是存储结构的基本单元,继承 HashMap 中的 Entry,用于存储数据。
  • TreeNode 继承 Node,但是数据结构换成了二叉树结构,是红黑树的存储结构,用于红黑树中存储数据。
  • TreeBin 是封装 TreeNode 的容器,提供转换红黑树的一些条件和锁的控制。

3、存储对象时(put() 方法):

  • 如果没有初始化,就调用 initTable() 方法来进行初始化。
  • 如果需要扩容,就先进行扩容。
  • 如果没有 hash 冲突就直接 CAS 无锁插入。
  • 如果存在 hash 冲突,就加锁来保证线程安全,两种情况:一种是链表形式就直接遍历到尾端插入,一种是红黑树就按照红黑树结构插入。
  • 如果该链表的数量大于阀值 8,就要先转换成红黑树的结构,break 再一次进入循环。
  • 如果添加成功就调用 addCount() 方法统计 size,并且检查是否需要扩容。

4、扩容方法

  • transfer():默认容量为 16,扩容时,容量变为原来的两倍。
  • helpTransfer():调用多个工作线程一起帮助进行扩容,这样的效率就会更高。

5、获取对象时:get()方法

  • 计算 hash 值,定位到该 table 索引位置,如果是首结点符合就返回。
  • 如果遇到扩容时,会调用标记正在扩容结点 ForwardingNode.find() 方法,查找该结点,匹配就返回。
  • 以上都不符合的话,就往下遍历结点,匹配就返回,否则最后就返回 null 。

八、ConcurrentHashMap 的并发度是什么?

  • 1.7 中程序运行时能够同时更新 ConccurentHashMap 且不产生锁竞争的最大线程数。默认为 16,且可以在构造函数中设置。当用户设置并发度时,ConcurrentHashMap 会使用大于等于该值的最小 的 2 的乘方数作为实际并发度(假如用户设置并发度为 17,实际并发度则为 32)。
  • 1.8 中并发度则无太大的实际意义了,主要用处就是当设置的初始容量小于并发度,将初始容量提升至并发度大小。

都读到这里了,来个 点赞、评论、关注、收藏 吧!

评论



Copyright Author Powered Theme

ICP