C/C++教程

高薪程序员&面试题精讲系列45之你熟悉ConcurrentHashMap吗?

本文主要是介绍高薪程序员&面试题精讲系列45之你熟悉ConcurrentHashMap吗?,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一. 面试题及剖析

1. 今日面试题

你了解过java.util.concurrent并发包中的哪些API?

你了解ConcurrentHashMap吗?

ConcurrentHashMap的特点是什么?

ConcurrentHashMap的底层原理是什么?

ConcurrentHashMap中涉及到了哪些数据结构?

ConcurrentHashMap为什么是线程安全的?

HashMap与ConcurrentHashMap的区别有哪些?

为什么ConcurrentHashMap的读操作不需要加锁?

2. 题目剖析

今天的题目依然很多,而且也都是关于集合的。从名字上来看,今天的集合与之前的HashMap集合也具有一定的关系,他俩可以算是“亲兄弟”,在用法上几乎相同,性能上也差不太多,但是在线程安全性方面比HashMap要优秀一些。所以涉及到多线程并发操作时,经常需要用到这个ConcurrentHashMap,我们面试时也会经常被问到ConcurrentHashMap与HashMap的区别。

ConcurrentHashMap是我们工作和面试时常用常考的一个集合,所以也要请各位重点掌握,接下来 壹哥 就带各位详细的梳理一下ConcurrentHashMap的知识脉络。

二. 背景概述

在开始复习ConcurrentHashMap之前,壹哥 先给各位简单陈述一些“故事背景”,以此来弄明白我们为什么要学习一个全新的ConcurrentHashMap,就用之前的HashMap不行吗?为什么还要学习一个新的集合呢?这里我们先来回顾一下HashMap中存在的问题。

1. JDK 8之前HashMap存在的问题

HashMap是我们日常开发中最常见的一种集合容器,它以键值对的形式来完成对数据的存储,但众所周知,它在高并发的情境下是不安全的!

比如当我们进行put(k,v)操作时,如果触发了扩容操作,就需要将原数组中的内容重新拷贝到新的扩容数组中,并需要进行rehash操作。但是在进行扩容的这个过程中,如果其他线程也在进行put()操作,而且恰好有两个元素的 hash 值相同,就会出现hash冲突,此时就需要在同一数组下用链表来进行表示。

我们知道,在JDK 8之前的HashMap中,是采用 头插法 来解决链表中的冲突节点的,而多线程高并发操作同一条链表时有可能直接导致 闭链,引起get(k)操作时出现 死循环

2. JDK 8之后HashMap的改进

当然,JDK 8以后,对 HashMap 的内部作了很大的改进,底层采用 数组+链表+红黑树 的数据结构来存储数据。并且rehash 的过程也进行了改动,不再直接操作原链,而是基于 复制 算法的思想,定义了两条链表分别完成对原链中结点的分离操作。另外还把 头插法 改为了 尾插法,所以即使在多线程环境下也是较为安全的。

但HashMap毕竟不是并发容器,除非源码中进行大改,否则还是不能应对高并发的场景。即使没有因多线程访问而造成什么问题,但效率也会受到影响。例如在多线程场景下,同时添加元素的时候可能会造成数据的丢失,遍历Map时可能会触发并发修改异常等。

总之,传统的HashMap在单线程非并发环境下使用起来是比较好的,但是在多线程并发环境下就存在着不少问题,既然如此,我们就要想办法解决或者规避这些存在的问题。

3. 并发安全的集合容器

那如何解决多线程并发操作集合时存在的这些问题呢?有没有较为安全的 Map集合呢?当然是有的,目前Java给咱们提供了3种相对安全的 Map集合操作方式,分别如下:

  • HashTable
  • Collections.synchronizedMap(map)
  • ConcurrentHashMap

对于上面提到的这3种并发集合操作方式,我们先来看看前两种。这两种其实都是利用 粗粒度的同步方式,在高并发情况下,执行性能比较低,接下来 壹哥 简单分析一下它们存在的问题。

HashtableHashTable是在put()、get()、size()等各种方法上添加 “synchronized” 锁,来保证线程安全,这会导致所有的并发操作都要竞争同一把锁,一个线程在进行同步操作时,其他线程只能等待,大大降低了并发操作的效率。

Collections.synchronizedMap()Collections提供了一个同步包装器方法synchronizedMap(),它虽然在方法中没有添加synchronized锁,但是 利用了 “this” 作为互斥的 mutex,所以严格地说,synchronizedMap跟 HashTable 一样,对性能并没有实际的提升改进。

所以后来Java就提供了另一个专门适合多线程高并发环境中的集合--ConcurrentHashMap!

因为ConcurrentHashMap就成了本文的主角,相对前两种Map集合的操作方式来说,其在设计思想上有了较大的变化,极大的提高了 Map 的并发操作性能。

ConcurrentHashMap是 HashMap 的并发版本,它是线程安全的,并且在高并发环境下,性能比 HashMap 高很多。

但就 ConcurrentHashMap本身的实现来说,不同JDK版本之间又有着较大的差异,典型的就是 JDK 7 和 JDK 8 这两个版本,可以说是发生了翻天覆地的变化。那么本文会基于这两个版本,来讲解ConcurrentHashMap的实现及区别,但我的重点肯定是放在 JDK 8 这个版本上,因为JDK 7 已经成为了过去式,我们没必要深入研究,仅做了解即可。

所以本文主要基于JDK 8,从ConcurrentHashMap的主要属性、特征、构造方法、put过程、扩容过程、size过程、get过程等方面,结合源码深入讲解ConcurrentHashMap的工作原理。

三. ConcurrentHashMap简介

本节相关面试题:

ConcurrentHashMap的特点是什么?

你了解过java.util.concurrent并发包中的哪些API?

1. ConcurrentHashMap概念特征

由于在多线程环境下,常规的HashMap可能会在数组扩容及重哈希时出现 死循环、脏读 等线程安全问题,虽然有HashTable、Collections.synchronizedMap()可以取代HashMap进行并发操作,但因它们都是利用一个 全局的synchronized锁 来同步不同线程之间的并发访问,因此性能较差。

所以Java就从JDK 1.5版本开始,在J.U.C(java.util.concurrent并发包)引入了一个高性能的并发操作集合---ConcurrentHashMap(可以简称为CHM)。该集合在读数据时不需要加锁,写数据时会加锁,但锁的粒度较小,不会对整个集合加锁。而其内部又大量的利用了 volatile,final,CAS等lock-free(无锁并发)技术,减少了锁竞争对于性能的影响,具有更好的写并发能力,但降低了对读一致性的要求。因此既保证了并发操作的安全性,又确保了读、写操作的高性能,可以说它的并发设计与实现都非常的精巧。

另外ConurrentHashMap中的key与value都不能为null,否则会产生空指针异常!

2. ConcurrentHashMap类关系

ConcurrentHashMap与HashMap具有相同的父类AbstractMap,他俩可以说是“亲兄弟”,所以ConcurrentHashMap在一般的特性和使用上与HashMap基本是一致的,甚至很多底层原理也是相似的。

但两者所在的包是不同的,ConcurrentHashMap是在java.util.concurrent包中,HashMap是在java.util包中,我们可以参考下图:

以上所述的ConcurrentHashMap概念及特征,是不区分版本的,但实际上不同版本的ConcurrentHashMap内部实现差异很大,所以面试时经常会被问到不同版本之间的差异、各自特征,接下来 壹哥 会针对JDK 7 与 JDK 8 这两个经典版本分别进行阐述。

四. 不同JDK版本中的ConcurrentHashMap对比

1. JDK 7的ConcurrentHashMap小结

JDK 7中的ConcurrentHashMap,当长度过长时,碰撞会很频繁的发生,链表的增改删查操作都会消耗很长的时间,影响性能。

JDK 7中的ConcurrentHashMap主要使用Segment分段锁来实现并发控制,把Map分割成若干个Segment。在put()时需要锁住Segment,get()时候不需要加锁,使用volatile来保证可见性。

当统计全局数量时(比如size),首先会尝试多次计算modCount来确定。这几次尝试时,会判断是否有其他线程进行了修改操作,如果没有,则直接返回size;如果有,则需要依次锁住所有的Segment来计算。

2. JDK 8的ConcurrentHashMap小结

  • 不采用Segment而是采用Node,减小了锁的粒度;
  • 设计了MOVED状态,在resize过程中,线程2还在put数据时,线程1会帮助resize;
  • 使用3个CAS操作来确保Node中的一些原子性操作,这种方式代替了锁;
  • sizeCtl的不同值代表了不同含义,起到了控制的作用;
  • 使用synchronized而不是ReentrantLock。

五. 结语

本篇文章,壹哥 暂时先对ConcurrentHashMap做个简单介绍。关于ConcurrentHashMap的底层原理、数据结构、扩容机制、冲突解决等内容,受限于篇幅,壹哥 会分成若干篇文章进行讲解,欢迎大家持续关注。今天的内容你都记住了吗?

这篇关于高薪程序员&面试题精讲系列45之你熟悉ConcurrentHashMap吗?的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!